An Efficient and Scalable Approach for Path Queries on Public Transportation Networks

Public transportation is crucial for mitigating environmental pollution and alleviating traffic congestion. As a fundamental problem in public transportation networks, path query aims to find the optimal path from a source vertex to a destination vertex. Several methods have been proposed to speed up the path queries by utilizing indexes. However, these methods suffer from significant performance issues in both query processing and index construction, limiting their scalability on large networks. To this end, we analyze the performance bottlenecks of existing methods and design a new efficient index-based method leveraging the properties of graph tree decomposition, the tree decomposition based index ensures that only a small set of labels is examined during query processing. Additionally, we develop linear-time, cache-friendly algorithms to efficiently handle multi-edges in public transportation networks, which avoids the expensive Dijkstra search and check operations in index construction, thereby addressing the performance bottlenecks of existing methods. Building on these techniques, we present new algorithms for both query processing and index construction. Furthermore, we theoretically analyze the time complexity of our method and existing methods regarding index construction and prove that our method scales better for large number of parallel edges. We also showcase the effectiveness of our method in handling numerous parallel edges by integrating them in other tree decomposition based index frameworks. Extensive experiments on 13 real-world public transportation networks demonstrate that our method outperforms existing approaches by one to three orders of magnitude in both query processing and index construction.