{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T11:04:11Z","timestamp":1761649451339,"version":"3.33.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T00:00:00Z","timestamp":1737504000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T00:00:00Z","timestamp":1737504000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Front. Comput. Sci."],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s11704-024-40459-x","type":"journal-article","created":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T15:46:33Z","timestamp":1737560793000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["SCG-tree: shortcut enhanced graph hierarchy tree for efficient spatial queries on massive road networks"],"prefix":"10.1007","volume":"19","author":[{"given":"Zhuo","family":"Cao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chun","family":"Cao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianqiu","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingwei","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhefei","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zi","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoxing","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,22]]},"reference":[{"issue":"2","key":"40459_CR1","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1080\/17489725.2018.1508763","volume":"12","author":"H Huang","year":"2018","unstructured":"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\u201393","journal-title":"Journal of Location Based Services"},{"issue":"1","key":"40459_CR2","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/3423165","volume":"54","author":"H Jiang","year":"2022","unstructured":"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","journal-title":"ACM Computing Surveys (CSUR)"},{"issue":"11s","key":"40459_CR3","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1145\/3510409","volume":"54","author":"P S\u00e1nchez","year":"2022","unstructured":"S\u00e1nchez P, Bellog\u00edn 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","journal-title":"ACM Computing Surveys (CSUR)"},{"issue":"10s","key":"40459_CR4","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1145\/3507904","volume":"54","author":"M Alam","year":"2022","unstructured":"Alam M, Torgo L, Bifet A. A survey on spatio-temporal data analytics systems. ACM Computing Surveys, 2022, 54(10s): 219","journal-title":"ACM Computing Surveys"},{"issue":"3","key":"40459_CR5","doi-asserted-by":"publisher","first-page":"163610","DOI":"10.1007\/s11704-020-0243-2","volume":"16","author":"X Pan","year":"2022","unstructured":"Pan X, Wu L, Long F, Ang M. Exploiting user behavior learning for personalized trajectory recommendations. Frontiers of Computer Science, 2022, 16(3): 163610","journal-title":"Frontiers of Computer Science"},{"issue":"6","key":"40459_CR6","doi-asserted-by":"publisher","first-page":"176615","DOI":"10.1007\/s11704-023-2704-x","volume":"17","author":"F Chen","year":"2023","unstructured":"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","journal-title":"Frontiers of Computer Science"},{"issue":"2","key":"40459_CR7","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1287\/trsc.2014.0579","volume":"51","author":"D Delling","year":"2015","unstructured":"Delling D, Goldberg A V, Pajor T, Werneck R F. Customizable route planning in road networks. Transportation Science, 2015, 51(2): 566\u2013591","journal-title":"Transportation Science"},{"key":"40459_CR8","doi-asserted-by":"publisher","first-page":"2677","DOI":"10.1145\/3394486.3403318","volume-title":"Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining","author":"J Huang","year":"2020","unstructured":"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\u20132685"},{"issue":"3","key":"40459_CR9","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1109\/TKDE.2014.2345386","volume":"27","author":"D Delling","year":"2015","unstructured":"Delling D, Werneck R F. Customizable point-of-interest queries in road networks. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(3): 686\u2013698","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"3","key":"40459_CR10","doi-asserted-by":"publisher","first-page":"173607","DOI":"10.1007\/s11704-022-2090-9","volume":"17","author":"B Ning","year":"2023","unstructured":"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","journal-title":"Frontiers of Computer Science"},{"key":"40459_CR11","first-page":"609","volume-title":"Proceedings of the 33rd IEEE International Conference on Data Engineering","author":"B Shen","year":"2017","unstructured":"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\u2013620"},{"issue":"8","key":"40459_CR12","doi-asserted-by":"publisher","first-page":"2175","DOI":"10.1109\/TKDE.2015.2399306","volume":"27","author":"R Zhong","year":"2015","unstructured":"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\u20132189","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"40459_CR13","first-page":"268","volume-title":"Proceedings of the IEEE 35th International Conference on Data Engineering","author":"Z Li","year":"2019","unstructured":"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\u2013279"},{"issue":"1","key":"40459_CR14","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E W Dijkstra","year":"1959","unstructured":"Dijkstra E W. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, 1(1): 269\u2013271","journal-title":"Numerische Mathematik"},{"issue":"2","key":"40459_CR15","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"P E Hart","year":"1968","unstructured":"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\u2013107","journal-title":"IEEE Transactions on Systems Science and Cybernetics"},{"key":"40459_CR16","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-319-49487-6_2","volume-title":"Algorithm Engineering","author":"H Bast","year":"2016","unstructured":"Bast H, Delling D, Goldberg A, M\u00fcller-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\u201380"},{"issue":"4","key":"40459_CR17","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/2530531","volume":"46","author":"C Sommer","year":"2014","unstructured":"Sommer C. Shortest-path queries in static networks. ACM Computing Surveys (CSUR), 2014, 46(4): 45","journal-title":"ACM Computing Surveys (CSUR)"},{"issue":"5","key":"40459_CR18","doi-asserted-by":"publisher","first-page":"406","DOI":"10.14778\/2140436.2140438","volume":"5","author":"L Wu","year":"2012","unstructured":"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\u2013417","journal-title":"Proceedings of the VLDB Endowment"},{"key":"40459_CR19","first-page":"624","volume-title":"Proceedings of the 39th IEEE International Conference on Data Engineering","author":"S Anirban","year":"2023","unstructured":"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\u2013636"},{"key":"40459_CR20","first-page":"802","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases","author":"D Papadias","year":"2003","unstructured":"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\u2013813"},{"issue":"3","key":"40459_CR21","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1109\/TKDE.2010.243","volume":"24","author":"K C K Lee","year":"2012","unstructured":"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\u2013560","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"5","key":"40459_CR22","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1145\/3187009.3177736","volume":"11","author":"S Luo","year":"2018","unstructured":"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\u2013606","journal-title":"Proceedings of the VLDB Endowment"},{"key":"40459_CR23","first-page":"319","volume-title":"Proceedings of the 7th International Workshop on Experimental and Efficient Algorithms","author":"R Geisberger","year":"2008","unstructured":"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\u2013333"},{"key":"40459_CR24","first-page":"147","volume-title":"Proceedings of the Meeting on Algorithm Engineering & Expermiments","author":"T Akiba","year":"2014","unstructured":"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\u2013154"},{"key":"40459_CR25","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1145\/3448016.3459245","volume-title":"Proceedings of 2021 International Conference on Management of Data","author":"Z Chen","year":"2021","unstructured":"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\u2013325"},{"key":"40459_CR26","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1145\/3318464.3389746","volume-title":"Proceedings of 2020 ACM SIGMOD International Conference on Management of Data","author":"D Ouyang","year":"2020","unstructured":"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\u20131795"},{"issue":"6","key":"40459_CR27","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1007\/s00778-023-00789-x","volume":"32","author":"D Ouyang","year":"2023","unstructured":"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\u20131287","journal-title":"The VLDB Journal"},{"issue":"6","key":"40459_CR28","doi-asserted-by":"publisher","first-page":"492","DOI":"10.14778\/2904121.2904125","volume":"9","author":"T Abeywickrama","year":"2016","unstructured":"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\u2013503","journal-title":"Proceedings of the VLDB Endowment"},{"key":"40459_CR29","doi-asserted-by":"publisher","DOI":"10.1515\/9781400884179","volume-title":"Linear Programming and Extensions","author":"G B Dantzig","year":"1963","unstructured":"Dantzig G B. Linear Programming and Extensions. Princeton: Princeton University Press, 1963"},{"key":"40459_CR30","first-page":"156","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A V Goldberg","year":"2005","unstructured":"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\u2013165"},{"key":"40459_CR31","first-page":"568","volume-title":"Proceedings of the 13th Annual European Symposium","author":"P Sanders","year":"2005","unstructured":"Sanders P, Schultes D. Highway hierarchies hasten exact shortest path queries. In: Proceedings of the 13th Annual European Symposium. 2005, 568\u2013579"},{"issue":"5","key":"40459_CR32","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1109\/TKDE.2002.1033772","volume":"14","author":"S Jung","year":"2002","unstructured":"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\u20131046","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"40459_CR33","first-page":"230","volume-title":"Proceedings of the 10th International Symposium on Experimental Algorithms","author":"I Abraham","year":"2011","unstructured":"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\u2013241"},{"key":"40459_CR34","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/1007912.1007931","volume-title":"Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures","author":"K Andreev","year":"2004","unstructured":"Andreev K, R\u00e4cke H. Balanced graph partitioning. In: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures. 2004, 120\u2013124"},{"issue":"1","key":"40459_CR35","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1006\/jpdc.1997.1404","volume":"48","author":"G Karypis","year":"1998","unstructured":"Karypis G, Kumar V. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 1998, 48(1): 96\u2013129","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"11","key":"40459_CR36","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.14778\/3342263.3342265","volume":"12","author":"Y Wang","year":"2019","unstructured":"Wang Y, Li G, Tang N. Querying shortest paths on time dependent road networks. Proceedings of the VLDB Endowment, 2019, 12(11): 1249\u20131261","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"6","key":"40459_CR37","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R W Floyd","year":"1962","unstructured":"Floyd R W. Algorithm 97: shortest path. Communications of the ACM, 1962, 5(6): 345","journal-title":"Communications of the ACM"},{"issue":"5","key":"40459_CR38","doi-asserted-by":"publisher","first-page":"602","DOI":"10.14778\/3377369.3377371","volume":"13","author":"D Ouyang","year":"2020","unstructured":"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\u2013615","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"3","key":"40459_CR39","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s41019-023-00227-6","volume":"8","author":"Z Chen","year":"2023","unstructured":"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\u2013278","journal-title":"Data Science and Engineering"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-024-40459-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11704-024-40459-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-024-40459-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T15:46:38Z","timestamp":1737560798000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11704-024-40459-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,22]]},"references-count":39,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["40459"],"URL":"https:\/\/doi.org\/10.1007\/s11704-024-40459-x","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"value":"2095-2228","type":"print"},{"value":"2095-2236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,22]]},"assertion":[{"value":"8 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Competing interests The authors declare that they have no competing interests or financial conflicts to disclose.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics"}}],"article-number":"199610"}}