Tree Decomposition based Top-k Shortest Distance Query on Large-scale Road Networks

Top-k shortest distance query is important for a large variety of location applications. However, with increasing data scale and dynamic updates on large-scale road networks, it is hard to deploy naive network traversal method for query efficiency. In this research, we propose a practical indexing solution based on tree decompostion, which can efficient answer top-k shortest distance query approximately with high precision in a few tens of microseconds. Meanwhile, the indexing cost is acceptable which is suitable for dynamic graphs with traffic updates in a few tens of minutes.