ArcadeDB находит маршрут через Флориду, прочитав 346 перекрёстков вместо миллиона

Dijkstra vs. A* vs. Contraction Hierarchies

ArcadeDB добавил в свою мультимодельную базу Customizable Contraction Hierarchies — алгоритм маршрутизации, который переносит основную работу с момента запроса на этап подготовки. На дорожной сети Флориды из 1,07 млн перекрёстков Dijkstra для маршрута Таллахасси — Корал-Гейблс перебирает 1 029 617 перекрёстков, A* — 840 138, а CCH — всего 346, отвечая за 0,039 мс вместо 99 мс. Иерархия живёт в графовом аналитическом представлении и синхронизируется с каждым коммитом: изменение веса дороги подхватывается за доли миллисекунды, а запрос всегда возвращает точный маршрут.