{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:59:01Z","timestamp":1750309141406,"version":"3.41.0"},"reference-count":78,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T00:00:00Z","timestamp":1729641600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["1914635 and 2151254"],"award-info":[{"award-number":["1914635 and 2151254"]}]},{"name":"United States Department of Agriculture - National Institute of Food and Agriculture","award":["20196901229853"],"award-info":[{"award-number":["20196901229853"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>\n            Skyline path queries (SPQs) extend skyline queries to multi-dimensional networks, such as multi-cost road networks (MCRNs). Such queries return a set of non-dominated paths between two given network nodes. Despite the existence of extensive works on evaluating different SPQ variants, SPQ evaluation is still very inefficient due to the nonexistence of efficient index structures to support such queries. Existing index building approaches for supporting shortest-path query execution, when directly extended to support SPQs, use an unreasonable amount of space and time to build, making them impractical for processing large graphs. In this article, we propose a novel index structure,\n            <jats:italic>backbone index<\/jats:italic>\n            , and a corresponding index construction method that condenses an initial MCRN to multiple smaller summarized graphs with different granularity. We present efficient approaches to find approximate solutions to SPQs by utilizing the backbone index structure. Furthermore, considering making good use of historical query and query results, we propose two models,\n            <jats:bold>S<\/jats:bold>\n            kyline\n            <jats:bold>P<\/jats:bold>\n            ath\n            <jats:bold>G<\/jats:bold>\n            raph\n            <jats:bold>N<\/jats:bold>\n            eural\n            <jats:bold>N<\/jats:bold>\n            etwork (SP-GNN) and\n            <jats:bold>T<\/jats:bold>\n            ransfer SP-GNN (TSP-GNN), to support effective SPQ processing. Our extensive experiments on real-world large road networks show that the backbone index can support finding meaningful approximate SPQ solutions efficiently. The backbone index can be constructed in a reasonable time, which dramatically outperforms the construction of other types of indexes for road networks. As far as we know, this is the first compact index structure that can support efficient approximate SPQ evaluation on large MCRNs. The results on the SP-GNN and TSP-GNN models also show that both models can help get approximate SPQ answers efficiently.\n          <\/jats:p>","DOI":"10.1145\/3660632","type":"journal-article","created":{"date-parts":[[2024,4,23]],"date-time":"2024-04-23T12:37:02Z","timestamp":1713875822000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Backbone Index and GNN Models for Skyline Path Query Evaluation over Multi-cost Road Networks"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-1984-0411","authenticated-orcid":false,"given":"Qixu","family":"Gong","sequence":"first","affiliation":[{"name":"Computer Science, New Mexico State University, Las Cruces, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5367-4059","authenticated-orcid":false,"given":"Huiying","family":"Chen","sequence":"additional","affiliation":[{"name":"Computer Science, New Mexico State University, Las Cruces, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1350-1846","authenticated-orcid":false,"given":"Huiping","family":"Cao","sequence":"additional","affiliation":[{"name":"Computer Science, New Mexico State University, Las Cruces, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-6159-094X","authenticated-orcid":false,"given":"Jiefei","family":"Liu","sequence":"additional","affiliation":[{"name":"Computer Science, New Mexico State University, Las Cruces, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,10,23]]},"reference":[{"key":"e_1_3_3_2_2","volume-title":"Proceedings of the Learning on Graphs Conference","author":"Abboud Ralph","year":"2022","unstructured":"Ralph Abboud, Radoslav Dimitrov, and Ismail Ilkan Ceylan. 2022. Shortest path networks for graph property prediction. In Proceedings of the Learning on Graphs Conference. PMLR, 5\u20131."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_3_3_4_2","article-title":"Finding non-dominated paths in uncertain road networks","author":"Aljubayrin Saad","year":"2016","unstructured":"Saad Aljubayrin, Bin Yang, Christian S. Jensen, and Rui Zhang. 2016. Finding non-dominated paths in uncertain road networks. Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.","journal-title":"Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems."},{"key":"e_1_3_3_5_2","first-page":"97","volume-title":"2009 Proceedings of the 11th Workshop on Algorithm Engineering and Experiments.","author":"Batz G. Veit","year":"2009","unstructured":"G. Veit Batz, Daniel Delling, Peter Sanders, and Christian Vetter. 2009. Time-dependent contraction hierarchies. In 2009 Proceedings of the 11th Workshop on Algorithm Engineering and Experiments.SIAM, 97\u2013105."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2014.06.065"},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1111\/j.1467-9671.2008.01107.x","article-title":"Network density estimation: A GIS approach for analysing point patterns in a network space","volume":"12","author":"Borruso G.","year":"2008","unstructured":"G. Borruso. 2008. Network density estimation: A GIS approach for analysing point patterns in a network space. Transactions in GIS 12, 3 (2008), 377\u2013402.","journal-title":"Transactions in GIS"},{"key":"e_1_3_3_8_2","first-page":"85","article-title":"A backbone extraction method with local search for complex weighted networks","author":"Bu Zhan","year":"2014","unstructured":"Zhan Bu, Zhiang Wu, Liqiang Qian, Jie Cao, and Guandong Xu. 2014. A backbone extraction method with local search for complex weighted networks. In Proceedings of the 2014 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining.85\u201388.","journal-title":"Proceedings of the 2014 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining."},{"key":"e_1_3_3_9_2","first-page":"144","volume-title":"Proceedings of the EDBT","author":"Chang Yanchuan","year":"2023","unstructured":"Yanchuan Chang, Egemen Tanin, Xin Cao, and Jianzhong Qi. 2023. Spatial structure-aware road network embedding via graph contrastive learning. In Proceedings of the EDBT. OpenProceedings.org, 144\u2013156."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s41060-016-0017-y"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2016.2602702"},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","DOI":"10.1145\/3448016.3459245","article-title":"P2H: Efficient distance querying on road networks by projected vertex separators","author":"Chen Zitong","year":"2021","unstructured":"Zitong Chen, A. Fu, Minhao Jiang, Eric Lo, and Pengfei Zhang. 2021. P2H: Efficient distance querying on road networks by projected vertex separators. In Proceedings of the 2021 International Conference on Management of Data.","journal-title":"Proceedings of the 2021 International Conference on Management of Data."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330925"},{"key":"e_1_3_3_14_2","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/j.jtrangeo.2018.05.012","article-title":"Transport network backbone extraction: A comparison of techniques","volume":"69","author":"Dai Liang","year":"2018","unstructured":"Liang Dai, Ben Derudder, and Xingjian Liu. 2018. Transport network backbone extraction: A comparison of techniques. Journal of Transport Geography 69 (2018), 271\u2013281. https:\/\/www.sciencedirect.com\/science\/article\/abs\/pii\/S0966692317307391","journal-title":"Journal of Transport Geography"},{"issue":"1","key":"e_1_3_3_15_2","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra Edsger W.","year":"1959","unstructured":"Edsger W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 1 (1959), 269\u2013271.","journal-title":"Numerische Mathematik"},{"key":"e_1_3_3_16_2","first-page":"1241","volume-title":"Proceedings of the SIGMOD Conference","author":"Ding Bailu","year":"2019","unstructured":"Bailu Ding, Sudipto Das, Ryan Marcus, Wentao Wu, Surajit Chaudhuri, and Vivek R. Narasayya. 2019. AI meets AI: Leveraging query executions to improve index recommendations. In Proceedings of the SIGMOD Conference. ACM, 1241\u20131258."},{"key":"e_1_3_3_17_2","first-page":"226","volume-title":"Proceedings of the Kdd","author":"Ester Martin","year":"1996","unstructured":"Martin Ester, Hans-Peter Kriegel, J\u00f6rg Sander, and Xiaowei Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Kdd. 226\u2013231."},{"issue":"6","key":"e_1_3_3_18_2","doi-asserted-by":"crossref","first-page":"1443","DOI":"10.1007\/s11280-017-0444-2","article-title":"Continuous range-based skyline queries in road networks","volume":"20","author":"Fu Xiaoyi","year":"2017","unstructured":"Xiaoyi Fu, Xiaoye Miao, Jianliang Xu, and Yunjun Gao. 2017. Continuous range-based skyline queries in road networks. World Wide Web 20, 6 (2017), 1443\u20131467.","journal-title":"World Wide Web"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"e_1_3_3_20_2","article-title":"Technical report, TR-CS-NMSU-2022-0223, Supplementary Materials","author":"Gong Qixu","unstructured":"Qixu Gong and Huiping Cao. Technical report, TR-CS-NMSU-2022-0223, Supplementary Materials. Retrieved February 23, 2022 from https:\/\/computerscience.nmsu.edu\/_files\/documents\/TR-CS-NMSU-2022-02-23.pdf","journal-title":"R"},{"key":"e_1_3_3_21_2","first-page":"926","article-title":"Skyline queries constrained by multi-cost transportation networks","author":"Gong Qixu","year":"2019","unstructured":"Qixu Gong, Huiping Cao, and Parth Nagarkar. 2019. Skyline queries constrained by multi-cost transportation networks. In Proceedings of the 2019 IEEE 35th International Conference on Data Engineering.926\u2013937.","journal-title":"Proceedings of the 2019 IEEE 35th International Conference on Data Engineering."},{"key":"e_1_3_3_22_2","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1145\/3292500.3330934","volume-title":"Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Guan Sheng","year":"2019","unstructured":"Sheng Guan, Hanchao Ma, and Yinghui Wu. 2019. Attribute-driven backbone discovery. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 187\u2013195."},{"key":"e_1_3_3_23_2","volume-title":"Proceedings of the CIKM","author":"Gubichev Andrey","year":"2010","unstructured":"Andrey Gubichev, Srikanta J. Bedathur, Stephan Seufert, and Gerhard Weikum. 2010. Fast and accurate estimation of shortest paths in large graphs. In Proceedings of the CIKM."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_3_3_25_2","first-page":"1035","volume-title":"Proceedings of the SIGMOD Conference","author":"Hasan Shohedul","year":"2020","unstructured":"Shohedul Hasan, Saravanan Thirumuruganathan, Jees Augustine, Nick Koudas, and Gautam Das. 2020. Deep learning models for selectivity estimation of multi-attribute queries. In Proceedings of the SIGMOD Conference. ACM, 1035\u20131050."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3397271.3401063"},{"key":"e_1_3_3_27_2","volume-title":"Proceedings of the CIKM","author":"Huang Y.","year":"1996","unstructured":"Y. Huang, N. Jing, and Elke A. Rundensteiner. 1996. Effective graph clustering for path queries in digital map databases. In Proceedings of the CIKM."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.016127"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/69.687976"},{"key":"e_1_3_3_30_2","first-page":"1489","volume-title":"Proceedings of the ICDE","author":"Kaoudi Zoi","year":"2020","unstructured":"Zoi Kaoudi, Jorge-Arnulfo Quian\u00e9-Ruiz, Bertty Contreras-Rojas, Rodrigo Pardo-Meza, Anis Troudi, and Sanjay Chawla. 2020. ML-based cross-platform query optimization. In Proceedings of the ICDE. IEEE, 1489\u20131500."},{"key":"e_1_3_3_31_2","doi-asserted-by":"crossref","unstructured":"George Karypis and Vipin Kumar. 1998. Multilevel k-way partitioning scheme for irregular graphs. J. Parallel Distributed Comput. 48 1 (1998) 96\u2013129.","DOI":"10.1006\/jpdc.1997.1404"},{"key":"e_1_3_3_32_2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/978-3-642-13193-6_8","volume-title":"Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010. Proceedings 9","author":"Kieritz Tim","year":"2010","unstructured":"Tim Kieritz, Dennis Luxen, Peter Sanders, and Christian Vetter. 2010. Distributed time-dependent contraction hierarchies. In Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010. Proceedings 9. Springer, 83\u201393."},{"key":"e_1_3_3_33_2","volume-title":"Proceedings of the GIS","author":"Kriegel Hans-Peter","year":"2007","unstructured":"Hans-Peter Kriegel, Peer Kr\u00f6ger, Peter Kunath, Matthias Renz, and Tim Schmidt. 2007. Proximity queries in large traffic networks. In Proceedings of the GIS."},{"key":"e_1_3_3_34_2","first-page":"261","article-title":"Route skyline queries: A multi-preference path planning approach","author":"Kriegel Hans-Peter","year":"2010","unstructured":"Hans-Peter Kriegel, Matthias Renz, and Matthias Schubert. 2010. Route skyline queries: A multi-preference path planning approach. 2010 IEEE 26th International Conference on Data Engineering (2010), 261\u2013272.","journal-title":"2010 IEEE 26th International Conference on Data Engineering"},{"key":"e_1_3_3_35_2","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1109\/TKDE.2010.243","article-title":"ROAD: A new spatial object search framework for road networks","volume":"24","author":"Lee K.","year":"2012","unstructured":"K. Lee, W. Lee, B. Zheng, and Yuan Tian. 2012. ROAD: A new spatial object search framework for road networks. IEEE Transactions on Knowledge and Data Engineering 24, 3 (2012), 547\u2013560.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"12","key":"e_1_3_3_36_2","doi-asserted-by":"crossref","first-page":"3190","DOI":"10.14778\/3476311.3476405","article-title":"Machine learning for databases","volume":"14","author":"Li Guoliang","year":"2021","unstructured":"Guoliang Li, Xuanhe Zhou, and Lei Cao. 2021. Machine learning for databases. Proc. VLDB Endow. 14, 12 (2021), 3190\u20133193.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_3_3_37_2","doi-asserted-by":"crossref","unstructured":"Pengfei Li Hua Lu Rong Zhu Bolin Ding Long Yang and Gang Pan. 2023. DILI: A distribution-driven learned index. Proc. VLDB Endow. 16 9 (2023) 2212\u20132224.","DOI":"10.14778\/3598581.3598593"},{"key":"e_1_3_3_38_2","first-page":"397","article-title":"Skyline cohesive group queries in large road-social networks","author":"Li Qiyan","year":"2020","unstructured":"Qiyan Li, Yuanyuan Zhu, and J. X. Yu. 2020. Skyline cohesive group queries in large road-social networks. 2020 IEEE 36th International Conference on Data Engineering (2020), 397\u2013408. https:\/\/ieeexplore.ieee.org\/abstract\/document\/9101805","journal-title":"2020 IEEE 36th International Conference on Data Engineering"},{"key":"e_1_3_3_39_2","first-page":"268","article-title":"G*-Tree: An efficient spatial index on road networks","author":"Li Zijian","year":"2019","unstructured":"Zijian Li, Lei Chen, and Yue Wang. 2019. G*-Tree: An efficient spatial index on road networks. 2019 IEEE 35th International Conference on Data Engineering (2019), 268\u2013279. https:\/\/ieeexplore.ieee.org\/document\/8731380","journal-title":"2019 IEEE 35th International Conference on Data Engineering"},{"key":"e_1_3_3_40_2","first-page":"949","volume-title":"Proceedings of the ICDE","author":"Liu Yiding","year":"2020","unstructured":"Yiding Liu, Kaiqi Zhao, Gao Cong, and Zhifeng Bao. 2020. Online anomalous trajectory detection with deep generative sequence modeling. In Proceedings of the ICDE. IEEE, 949\u2013960."},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00760-2"},{"key":"e_1_3_3_42_2","first-page":"1553","volume-title":"Proceedings of the SIGMOD Conference","author":"Ma Qingzhi","year":"2019","unstructured":"Qingzhi Ma and Peter Triantafillou. 2019. DBEst: Revisiting approximate query processing engines with machine learning models. In Proceedings of the SIGMOD Conference. ACM, 1553\u20131570."},{"key":"e_1_3_3_43_2","article-title":"Extended graph backbone for motif analysis","author":"Maratea A.","year":"2017","unstructured":"A. Maratea, A. Petrosino, and Mario Manzo. 2017. Extended graph backbone for motif analysis. In Proceedings of the 18th International Conference on Computer Systems and Technologies.","journal-title":"Proceedings of the 18th International Conference on Computer Systems and Technologies."},{"key":"e_1_3_3_44_2","doi-asserted-by":"crossref","unstructured":"Sunil Nishad Shubhangi Agarwal Arnab Bhattacharya and Sayan Ranu. 2021. GraphReach: Position-aware graph neural network using reachability estimations. In (IJCAI\u201921). 1527\u20131533.","DOI":"10.24963\/ijcai.2021\/211"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1177\/2399808319863810"},{"key":"e_1_3_3_46_2","doi-asserted-by":"crossref","DOI":"10.1145\/3318464.3389746","article-title":"Progressive top-k nearest neighbors search in large road networks","author":"Ouyang Dian","year":"2020","unstructured":"Dian Ouyang, Dong Wen, Lu Qin, Lijun Chang, Y. Zhang, and Xuemin Lin. 2020. Progressive top-k nearest neighbors search in large road networks. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data.","journal-title":"Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data."},{"key":"e_1_3_3_47_2","volume-title":"Skyline Queries Constrained by Multi-Cost Transportation Networks","author":"Gong Huiping Cao Qixu","year":"2018","unstructured":"Huiping Cao Qixu Gong and Parth Nagarkar. 2018. Skyline Queries Constrained by Multi-Cost Transportation Networks. Technical Report TR-CS-NMSU-2018-09-02. Department of Computer Science, New Mexico State University, Las Cruces, New Mexico. Retrieved from https:\/\/www.cs.nmsu.edu\/wp\/wp-content\/uploads\/2018\/09\/constrainedSkyline_TR.pdf"},{"key":"e_1_3_3_48_2","first-page":"344","volume-title":"Proceedings of the International Symposium on Experimental Algorithms","author":"Rice Michael N.","year":"2012","unstructured":"Michael N. Rice and Vassilis J. Tsotras. 2012. Exact graph search algorithms for generalized traveling salesman path problems. In Proceedings of the International Symposium on Experimental Algorithms. Springer, 344\u2013355."},{"key":"e_1_3_3_49_2","unstructured":"Ning Ruan Ruoming Jin Crown Guan Wang and Kun Huang. 2012. Network backbone discovery using edge clustering. CoRR abs\/1202.1842 (2012)."},{"key":"e_1_3_3_50_2","first-page":"1782","volume-title":"Proceedings of the ICDE","author":"Sabek Ibrahim","year":"2020","unstructured":"Ibrahim Sabek and Mohamed F. Mokbel. 2020. Machine learning meets big spatial data. In Proceedings of the ICDE. IEEE, 1782\u20131785."},{"key":"e_1_3_3_51_2","volume-title":"Proceedings of the ESA","author":"Sanders Peter","year":"2005","unstructured":"Peter Sanders and Dominik Schultes. 2005. Highway hierarchies hasten exact shortest path queries. In Proceedings of the ESA."},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0808904106"},{"key":"e_1_3_3_53_2","first-page":"459","volume-title":"Proceedings of the ICDE","author":"Shekelyan Michael","year":"2015","unstructured":"Michael Shekelyan, Gregor Joss\u00e9, and Matthias Schubert. 2015. Linear path skylines in multicriteria networks. In Proceedings of the ICDE. IEEE, 459\u2013470."},{"issue":"13","key":"e_1_3_3_54_2","doi-asserted-by":"crossref","first-page":"3950","DOI":"10.14778\/3565838.3565848","article-title":"Learned index benefits: Machine learning based index performance estimation","volume":"15","author":"Shi Jiachen","year":"2022","unstructured":"Jiachen Shi, Gao Cong, and Xiaoli Li. 2022. Learned index benefits: Machine learning based index performance estimation. Proceedings of the VLDB Endowment 15, 13 (2022), 3950\u20133962.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_3_55_2","first-page":"1548","volume-title":"Proceedings of International Joint Conference on Artificial Intelligence.","author":"Shi Yunsheng","year":"2021","unstructured":"Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. 2021. Masked label prediction: Unified message passing model for semi-supervised classification. In Proceedings of International Joint Conference on Artificial Intelligence.Zhi-Hua Zhou (Ed.), ijcai.org, 1548\u20131554. DOI:10.24963\/IJCAI.2021\/214"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594528"},{"key":"e_1_3_3_57_2","volume-title":"Proceedings of the GIS","author":"Tian Yuan","year":"2009","unstructured":"Yuan Tian, K. Lee, and W. Lee. 2009. Finding skyline paths in road networks. In Proceedings of the GIS."},{"key":"e_1_3_3_58_2","unstructured":"Yao Tian Tingyun Yan Xi Zhao Kai Huang and Xiaofang Zhou. 2023. A learned index for exact similarity search in metric spaces. IEEE Trans. Knowl. Data Eng. 35 8 (2023) 7624\u20137638."},{"key":"e_1_3_3_59_2","first-page":"1153","volume-title":"Proceedings of the SIGMOD Conference","author":"Trummer Immanuel","year":"2019","unstructured":"Immanuel Trummer, Junxiong Wang, Deepak Maram, Samuel Moseley, Saehan Jo, and Joseph Antonakakis. 2019. SkinnerDB: Regret-bounded query evaluation via reinforcement learning. In Proceedings of the SIGMOD Conference. ACM, 1153\u20131170."},{"key":"e_1_3_3_60_2","unstructured":"Ulrike von Luxburg Agnes Radl and Matthias Hein. 2010. Hitting times commute distances and the spectral gap for large random geometric graphs. CoRR abs\/1003.1266 (2010)."},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/1064546.1103378"},{"key":"e_1_3_3_62_2","doi-asserted-by":"crossref","unstructured":"Tianfu Wang Chang Ren Yun Luo and Jing Tian. 2019. NS-DBSCAN: A density-based clustering algorithm in network space. ISPRS Int. J. Geo Inf. 8 5 (2019) 218.","DOI":"10.3390\/ijgi8050218"},{"key":"e_1_3_3_63_2","first-page":"313","volume-title":"Proceedings of the ICDE","author":"Wang Yishu","year":"2021","unstructured":"Yishu Wang, Ye Yuan, Hao Wang, Xiangmin Zhou, Congcong Mu, and Guoren Wang. 2021. Constrained route planning over large multi-modal time-dependent networks. In Proceedings of the ICDE. IEEE, 313\u2013324."},{"key":"e_1_3_3_64_2","first-page":"684","volume-title":"Proceedings of the ICDE","author":"Wang Zheng","year":"2021","unstructured":"Zheng Wang, Cheng Long, and Gao Cong. 2021. Trajectory simplification with reinforcement learning. In Proceedings of the ICDE. IEEE, 684\u2013695."},{"issue":"11","key":"e_1_3_3_65_2","doi-asserted-by":"crossref","first-page":"2312","DOI":"10.14778\/3407790.3407827","article-title":"Efficient and effective similar subtrajectory search with deep reinforcement learning","volume":"13","author":"Wang Zheng","year":"2020","unstructured":"Zheng Wang, Cheng Long, Gao Cong, and Yiding Liu. 2020. Efficient and effective similar subtrajectory search with deep reinforcement learning. Proceedings of the VLDB Endowment 13, 11 (2020), 2312\u20132325.","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"6684","key":"e_1_3_3_66_2","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts Duncan J.","year":"1998","unstructured":"Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of \u2018small-world\u2019 networks. Nature 393, 6684 (1998), 440\u2013442.","journal-title":"Nature"},{"key":"e_1_3_3_67_2","article-title":"Architecture-intact oracle for fastest path and time queries on dynamic spatial networks","author":"Wei Victor Junqiu","year":"2020","unstructured":"Victor Junqiu Wei, R. C. Wong, and Cheng Long. 2020. Architecture-intact oracle for fastest path and time queries on dynamic spatial networks. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data.","journal-title":"Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data."},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/3164541.3164634"},{"key":"e_1_3_3_69_2","doi-asserted-by":"crossref","unstructured":"Bin Yang Chenjuan Guo Christian S. Jensen Manohar Kaul and Shuo Shang. 2013. Multi-cost optimal route planning under time-varying uncertainty.","DOI":"10.1109\/ICDE.2014.6816646"},{"key":"e_1_3_3_70_2","doi-asserted-by":"crossref","unstructured":"Bin Yang Chenjuan Guo Christian S. Jensen Manohar Kaul and Shuo Shang. 2014. Stochastic skyline route planning under time-varying uncertainty. In (ICDE\u201914). 136\u2013147. https:\/\/ieeexplore.ieee.org\/abstract\/document\/9835456\/","DOI":"10.1109\/ICDE.2014.6816646"},{"key":"e_1_3_3_71_2","first-page":"1700","volume-title":"Proceedings of the ICDE","author":"Yang Peilun","year":"2022","unstructured":"Peilun Yang, Hanchen Wang, Defu Lian, Ying Zhang, Lu Qin, and Wenjie Zhang. 2022. TMN: Trajectory matching networks for predicting similarity. In Proceedings of the ICDE. IEEE, 1700\u20131713."},{"key":"e_1_3_3_72_2","article-title":"Finding the shortest path with vertex constraint over large graphs","volume":"2019","author":"Yang Yajun","year":"2019","unstructured":"Yajun Yang, Zhongfei Li, Xin Wang, and Qinghua Hu. 2019. Finding the shortest path with vertex constraint over large graphs. Complexity 2019 (2019). https:\/\/www.hindawi.com\/journals\/complexity\/2019\/8728245\/","journal-title":"Complexity"},{"key":"e_1_3_3_73_2","doi-asserted-by":"crossref","unstructured":"Yiding Yang Xinchao Wang Mingli Song Junsong Yuan and Dacheng Tao. 2019. SPAGAN: Shortest path graph attention network. In (IJCAI\u201919). 4099\u20134105.","DOI":"10.24963\/ijcai.2019\/569"},{"key":"e_1_3_3_74_2","unstructured":"Yajun Yang Hang Zhang Hong Gao Qinghua Hu and Xin Wang. 2020. An efficient index method for the optimal route query over multi-cost networks. CoRR abs\/2004.12424 (2020)."},{"key":"e_1_3_3_75_2","volume-title":"Proceedings of the SIGMOD","author":"Yiu Man Lung","year":"2004","unstructured":"Man Lung Yiu and N. Mamoulis. 2004. Clustering objects on a spatial network. In Proceedings of the SIGMOD."},{"key":"e_1_3_3_76_2","first-page":"110","volume-title":"Proceedings of the ICDE","author":"Zeng Juxiang","year":"2022","unstructured":"Juxiang Zeng, Pinghui Wang, Lin Lan, Junzhou Zhao, Feiyang Sun, Jing Tao, Junlan Feng, Min Hu, and Xiaohong Guan. 2022. Accurate and scalable graph neural networks for billion-scale graphs. In Proceedings of the ICDE. IEEE, 110\u2013122."},{"key":"e_1_3_3_77_2","first-page":"336","article-title":"Dynamic hub labeling for road networks","author":"Zhang Mengxuan","year":"2021","unstructured":"Mengxuan Zhang, Lei Li, Wen Hua, Rui Mao, Pingfu Chao, and Xiaofang Zhou. 2021. Dynamic hub labeling for road networks. 2021 IEEE 37th International Conference on Data Engineering (2021), 336\u2013347. https:\/\/ieeexplore.ieee.org\/document\/9458856","journal-title":"2021 IEEE 37th International Conference on Data Engineering"},{"issue":"2","key":"e_1_3_3_78_2","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1109\/TBDATA.2022.3186857","article-title":"Efficient learned spatial index with interpolation function based learned model","volume":"9","author":"Zhang Songnian","year":"2022","unstructured":"Songnian Zhang, Suprio Ray, Rongxing Lu, and Yandong Zheng. 2022. Efficient learned spatial index with interpolation function based learned model. IEEE Transactions on Big Data 9, 2 (2022), 733\u2013745.","journal-title":"IEEE Transactions on Big Data"},{"key":"e_1_3_3_79_2","first-page":"39","volume-title":"Proceedings of the 22nd ACM International Conference on Information and Knowledge Management","author":"Zhong Ruicheng","year":"2013","unstructured":"Ruicheng Zhong, Guoliang Li, Kian-Lee Tan, and Lizhu Zhou. 2013. G-tree: An efficient index for knn search on road networks. In Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. 39\u201348."}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3660632","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3660632","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:21Z","timestamp":1750287021000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3660632"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,23]]},"references-count":78,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3660632"],"URL":"https:\/\/doi.org\/10.1145\/3660632","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2024,10,23]]},"assertion":[{"value":"2023-05-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-08","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}