search

Project-OSRM / osrm-backend

Open Source Routing Machine - C++ backend
http://map.project-osrm.org
BSD 2-Clause "Simplified" License
6.29k stars 3.32k forks source link

Compress routing graph #5219

Open danpat opened 5 years ago

danpat commented 5 years ago

Currently, OSRM stores/loads the routing graph in a fairly naive adjacency list structure consisting of simple lists of edge and node data.

https://github.com/Project-OSRM/osrm-backend/blob/master/include/util/static_graph.hpp#L315-L320

There are a couple of papers that describe techniques for more efficiently compressing graph data structures, such as:

Compact Representations of Separable Graphs - https://www.cs.cmu.edu/~guyb/papers/BBK03.pdf

Log(Graph): A Near-Optimal High-Performance Graph Representation - https://spcl.inf.ethz.ch/Research/Performance/LogGraph/loggraph_full.pdf

There are several techniques described in these papers that we could implement in OSRM to reduce some data structure sizes significantly (in particlar, the .hsgr file).

github-actions[bot] commented 2 months ago

This issue seems to be stale. It will be closed in 30 days if no further activity occurs.

jcoupey commented 2 weeks ago

This idea still seems relevant for potential improvements, so I'm flagging it as a feature request in order to keep track.