Assessing the complexity of a path search optimization method based on clustering for a transport graph
Published in EPJ Data Science, 2025
Dmitrii Fedorov, Georgii Kontsevik, Roman Bashirov, Sergey Mityagin, Liubov Tupikina, Nikita Zakharenko, Semen Budennyy (2025). Assessing the complexity of a path search optimization method based on clustering for a transport graph. EPJ Data Science, 14, 32.
Overview
RIDE is a Python library for hierarchical pathfinding on transport and other graph structures. The research examines how graph clustering can accelerate repeated route queries, and how graph size and density affect the balance between computation time and route accuracy.
Method
The graph is partitioned into communities using Louvain clustering. A smaller centroid graph represents connections between these communities and can be reused across queries.
Graph preprocessing, from the RIDE repository. Click to view full size.
For a route query, a path through the centroid graph selects relevant communities. The search then runs on the corresponding subgraph of the original network, reducing the search area. This approximate approach trades some route accuracy for speed. The library also provides an exact A* configuration with higher memory requirements.
Hierarchical route search, from the RIDE repository.
Evaluation
The paper evaluates the method on more than 750 real-world city graphs and synthetic networks. It analyses query acceleration, preprocessing complexity and deviations from optimal routes, alongside theoretical estimates of performance.
Paper and code
Read the open-access publication · RIDE on GitHub · Documentation
Poster presentation
Presented at Sber AI R&D Day 2025 — Poster Session.
