SCG-tree: shortcut enhanced graph hierarchy tree for efficient spatial queries on massive road networks

Abstract

Nowadays, location-based services are widely used, requiring instant responses to a large volume of multiple spatial queries over massive road networks, i.e., single-pair shortest path (SPSP) query, k-nearest neighbor (kNN) query, and range query. Creating index-based structure for each kind of query is costly, hence it is important to handle multiple spatial queries within one efficient structure. Partition-based hierarchical approaches show promising potential to meet the requirement. However, existing approaches require large search space on massive road networks especially for long-distance queries, which is inefficient and hard to scale. To overcome the drawbacks, we propose the shortcut-enhanced graph hierarchy tree (SCG-tree), which leverages shortcuts to effectively prune the search space over a hierarchical structure. With the SCG-tree, a pruned shortcut-based method is designed to answer SPSP query, and a two-phase expansion strategy is proposed to leverage shortcuts for kNN and range queries. Theoretical analyses show the superiority of proposed shortcut-based query algorithms. Extensive experiments demonstrate that our approach can achieve three times speedup for kNN query and an order of magnitude speedup for SPSP and range queries over existing methods on real road networks that scale up to 24 million nodes and 58 million edges.

Graphical abstract

Keywords

spatial query / road network / index

References

[1] Huang H, Gartner G, Krisp J M, Raubal M, Van de Weghe N . Location based services: ongoing evolution and research agenda. Journal of Location Based Services, 2018, 12( 2): 63–93

[2] Jiang H, Li J, Zhao P, Zeng F, Xiao Z, Iyengar A . Location privacy-preserving mechanisms in location-based services: a comprehensive survey. ACM Computing Surveys (CSUR), 2022, 54( 1): 4

[3] Sánchez P, Bellogín A . Point-of-interest recommender systems based on location-based social networks: a survey from an experimental perspective. ACM Computing Surveys (CSUR), 2022, 54( 11s): 223

[4] Alam M, Torgo L, Bifet A . A survey on spatio-temporal data analytics systems. ACM Computing Surveys, 2022, 54( 10s): 219

[5] Pan X,Wu L, Long F, Ang M. Exploiting user behavior learning for personalized trajectory recommendations. Frontiers of Computer Science, 2022, 16(3): 163610

[6] Chen F, Zhang Y, Chen L, Meng X, Qi Y, Wang J . Dynamic traveling time forecasting based on spatial-temporal graph convolutional networks. Frontiers of Computer Science, 2023, 17( 6): 176615

[7] Delling D, Goldberg A V, Pajor T, Werneck R F . Customizable route planning in road networks. Transportation Science, 2015, 51( 2): 566–591

[8] Huang J, Wang H, Fan M, Zhuo A, Li Y. Personalized prefix embedding for POI auto-completion in the search engine of Baidu maps. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020, 2677–2685

[9] Delling D, Werneck R F . Customizable point-of-interest queries in road networks. IEEE Transactions on Knowledge and Data Engineering, 2015, 27( 3): 686–698

[10] Ning B, Li X, Yang F, Sun Y, Li G, Yuan G Y . Group relational privacy protection on time-constrained point of interests. Frontiers of Computer Science, 2023, 17( 3): 173607

[11] Shen B, Zhao Y, Li G, Zheng W, Qin Y, Yuan B, Rao Y. V-tree: efficient kNN search on moving objects with road-network constraints. In: Proceedings of the 33rd IEEE International Conference on Data Engineering. 2017, 609–620

[12] Zhong R, Li G, Tan K L, Zhou L, Gong Z . G-tree: an efficient and scalable index for spatial search on road networks. IEEE Transactions on Knowledge and Data Engineering, 2015, 27( 8): 2175–2189

[13] Li Z, Chen L, Wang Y. G*-tree: an efficient spatial index on road networks. In: Proceedings of the IEEE 35th International Conference on Data Engineering. 2019, 268–279

[14] Dijkstra E W . A note on two problems in connexion with graphs. Numerische Mathematik, 1959, 1( 1): 269–271

[15] Hart P E, Nilsson N J, Raphael B . A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 1968, 4( 2): 100–107

[16] Bast H, Delling D, Goldberg A, Müller-Hannemann M, Pajor T, Sanders P, Wagner D, Werneck R F. Route planning in transportation networks. In: Kliemann L, Sanders P, eds. Algorithm Engineering. Cham: Springer, 2016, 19–80

[17] Sommer C . Shortest-path queries in static networks. ACM Computing Surveys (CSUR), 2014, 46( 4): 45

[18] Wu L, Xiao X, Deng D, Cong G, Zhu A D, Zhou S . Shortest path and distance queries on road networks: an experimental evaluation. Proceedings of the VLDB Endowment, 2012, 5( 5): 406–417

[19] Anirban S, Wang J, Islam S. Experimental evaluation of indexing techniques for shortest distance queries on road networks. In: Proceedings of the 39th IEEE International Conference on Data Engineering. 2023, 624–636

[20] Papadias D, Zhang J, Mamoulis N, Tao Y. Query processing in spatial network databases. In: Proceedings of the 29th International Conference on Very Large Data Bases. 2003, 802–813

[21] Lee K C K, Lee W C, Zheng B, Tian Y . Road: a new spatial object search framework for road networks. IEEE Transactions on Knowledge and Data Engineering, 2012, 24( 3): 547–560

[22] Luo S, Kao B, Li G, Hu J, Cheng R, Zheng Y . TOAIN: a throughput optimizing adaptive index for answering dynamic kNN queries on road networks. Proceedings of the VLDB Endowment, 2018, 11( 5): 594–606

[23] Geisberger R, Sanders P, Schultes D, Delling D. Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: Proceedings of the 7th International Workshop on Experimental and Efficient Algorithms. 2008, 319–333

[24] Akiba T, Iwata Y, Kawarabayashi K I, Kawata Y. Fast shortest-path distance queries on road networks by pruned highway labeling. In: Proceedings of the Meeting on Algorithm Engineering & Expermiments. 2014, 147–154

[25] Chen Z, Fu A W C, Jiang M, Lo E, Zhang P. P2H: efficient distance querying on road networks by projected vertex separators. In: Proceedings of 2021 International Conference on Management of Data. 2021, 313–325

[26] Ouyang D, Wen D, Qin L, Chang L, Zhang Y, Lin X. Progressive top-k nearest neighbors search in large road networks. In: Proceedings of 2020 ACM SIGMOD International Conference on Management of Data. 2020, 1781–1795

[27] Ouyang D, Wen D, Qin L, Chang L, Lin X, Zhang Y . When hierarchy meets 2-hop-labeling: efficient shortest distance and path queries on road networks. The VLDB Journal, 2023, 32( 6): 1263–1287

[28] Abeywickrama T, Cheema M A, Taniar D . k-nearest neighbors on road networks: a journey in experimentation and in-memory implementation. Proceedings of the VLDB Endowment, 2016, 9( 6): 492–503

[29] Dantzig G B. Linear Programming and Extensions. Princeton: Princeton University Press, 1963

[30] Goldberg A V, Harrelson C. Computing the shortest path: A search meets graph theory. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 2005, 156–165

[31] Sanders P, Schultes D. Highway hierarchies hasten exact shortest path queries. In: Proceedings of the 13th Annual European Symposium. 2005, 568–579

[32] Jung S, Pramanik S . An efficient path computation model for hierarchically structured topographical road maps. IEEE Transactions on Knowledge and Data Engineering, 2002, 14( 5): 1029–1046

[33] Abraham I, Delling D, Goldberg A V, Werneck R F. A hub-based labeling algorithm for shortest paths in road networks. In: Proceedings of the 10th International Symposium on Experimental Algorithms. 2011, 230–241

[34] Andreev K, Räcke H. Balanced graph partitioning. In: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures. 2004, 120–124

[35] Karypis G, Kumar V . Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 1998, 48( 1): 96–129

[36] Wang Y, Li G, Tang N . Querying shortest paths on time dependent road networks. Proceedings of the VLDB Endowment, 2019, 12( 11): 1249–1261

[37] Floyd R W . Algorithm 97: shortest path. Communications of the ACM, 1962, 5( 6): 345

[38] Ouyang D, Yuan L, Qin L, Chang L, Zhang Y, Lin X . Efficient shortest path index maintenance on dynamic road networks with theoretical guarantees. Proceedings of the VLDB Endowment, 2020, 13( 5): 602–615

[39] Chen Z, Feng B, Yuan L, Lin X, Wang L . Fully dynamic contraction hierarchies with label restrictions on road networks. Data Science and Engineering, 2023, 8( 3): 263–278

RIGHTS & PERMISSIONS

Higher Education Press