{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T17:36:03Z","timestamp":1791912963680,"version":"4.3.4"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T00:00:00Z","timestamp":1658880000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T00:00:00Z","timestamp":1658880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001794","name":"The University of Queensland","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001794","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    In this paper, we study the Time-Dependent\n                    <jats:italic>k<\/jats:italic>\n                    Nearest Neighbor (TD-\n                    <jats:italic>k<\/jats:italic>\n                    NN) query on moving objects that aims to return\n                    <jats:italic>k<\/jats:italic>\n                    objects arriving at the query location with the least traveling cost departing at a given time\n                    <jats:italic>t<\/jats:italic>\n                    . Although the\n                    <jats:italic>k<\/jats:italic>\n                    NN query on moving objects has been widely studied in the scenario of the static road network, the TD-\n                    <jats:italic>k<\/jats:italic>\n                    NN query tends to be more complicated and challenging because under the time-dependent road network, the cost of each edge is measured by a cost function rather than a fixed distance value. To tackle such difficulty, we adopt the framework of GLAD and develop an advanced index structure to support efficient fastest travel cost query on time-dependent road network. In particular, we propose the Time-Dependent H2H (TD-H2H) index, which pre-computes the aggregated weight functions between each node to some specific nodes in the decomposition tree derived from the road network. Additionally, we establish a grid index on moving objects for candidate object retrieval and location update. To further accelerate the TD-\n                    <jats:italic>k<\/jats:italic>\n                    NN query, two pruning strategies are proposed in our solution. Apart from that, we extend our framework to tackle the time-dependent approachable\n                    <jats:italic>k<\/jats:italic>\n                    NN (TD-A\n                    <jats:italic>k<\/jats:italic>\n                    NN) query on moving objects targeting for the application of taxi-hailing service, where the moving object might have been occupied. Extensive experiments with different parameter settings on real-world road network show that our solutions for both TD-\n                    <jats:italic>k<\/jats:italic>\n                    NN and TD-A\n                    <jats:italic>k<\/jats:italic>\n                    NN queries are superior to the competitors in orders of magnitude.\n                  <\/jats:p>","DOI":"10.1007\/s00778-022-00758-w","type":"journal-article","created":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T21:38:22Z","timestamp":1658957902000},"page":"575-594","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["Efficient kNN query for moving objects on time-dependent road networks"],"prefix":"10.1007","volume":"32","author":[{"given":"Jiajia","family":"Li","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cancan","family":"Ni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9064-566X","authenticated-orcid":false,"given":"Dan","family":"He","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lei","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiufeng","family":"Xia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,7,27]]},"reference":[{"key":"758_CR1","unstructured":"Didichuxing. https:\/\/gaia.didichuxing.com\/"},{"key":"758_CR2","unstructured":"Uber. https:\/\/www.uber.com\/"},{"key":"758_CR3","doi-asserted-by":"crossref","unstructured":"Yuan, J., Zheng, Y., Xie, X., Sun, G.: Driving with knowledge from the physical world. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 316\u2013324 (2011)","DOI":"10.1145\/2020408.2020462"},{"key":"758_CR4","doi-asserted-by":"crossref","unstructured":"Yuan, N.J., Yu, Z., Zhang, C., Xie, W., Xing, X., Sun, G., Yan, H.: T-drive: driving directions based on taxi trajectories. In: ACM SIGSPATIAL GIS 2010;ACM SIGSPATIAL International Conference on Advances in Geographic Information systems (2011)","DOI":"10.1145\/1869790.1869807"},{"issue":"5","key":"758_CR5","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 k nn queries on road networks. Proc. VLDB Endow. 11(5), 594\u2013606 (2018)","journal-title":"Proc. VLDB Endow."},{"key":"758_CR6","first-page":"1","volume":"99","author":"D He","year":"2019","unstructured":"He, D., Wang, S., Zhou, X., Cheng, R.: Glad: a grid and labeling framework with scheduling for conflict-aware knn queries. IEEE Trans. Knowl. Data Eng. 99, 1\u20131 (2019)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"758_CR7","doi-asserted-by":"crossref","unstructured":"He, D., Wang, S., Zhou, X., Cheng, R.: An efficient framework for correctness-aware knn queries on road networks. In: 2019 IEEE 35th International Conference on Data Engineering (ICDE) (2019)","DOI":"10.1109\/ICDE.2019.00118"},{"key":"758_CR8","doi-asserted-by":"crossref","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: Data Engineering (ICDE), 2017 IEEE 33rd International Conference on, pp. 609\u2013620. IEEE (2017)","DOI":"10.1109\/ICDE.2017.115"},{"issue":"8","key":"758_CR9","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 Trans. Knowl. Data Eng. 27(8), 2175\u20132189 (2015)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"758_CR10","doi-asserted-by":"crossref","unstructured":"Ding, B., Yu, J.X., Qin, L.: Finding time-dependent shortest paths over large graphs. In: Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, pp. 205\u2013216 (2008)","DOI":"10.1145\/1353343.1353371"},{"key":"758_CR11","doi-asserted-by":"crossref","unstructured":"Kanoulas, E., Yang, D., Tian, X., Zhang, D.: Finding fastest paths on a road network with speed patterns. In: 2006 IEEE 22nd International Conference on Data Engineering (ICDE), p.\u00a010 (2006)","DOI":"10.1109\/ICDE.2006.71"},{"key":"758_CR12","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.cor.2015.06.001","volume":"64","author":"M Gendreau","year":"2015","unstructured":"Gendreau, M., Ghiani, G., Guerriero, E.: Time-dependent routing problems: a review. Comput. Oper. Res. 64, 189\u2013197 (2015)","journal-title":"Comput. Oper. Res."},{"key":"758_CR13","doi-asserted-by":"crossref","unstructured":"Wang, Y., Li, G., Tang, N.: Querying shortest paths on time dependent road networks. PVLDB pp. 1249\u20131261 (2019)","DOI":"10.14778\/3342263.3342265"},{"issue":"3","key":"758_CR14","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/79147.214078","volume":"37","author":"A Orda","year":"1990","unstructured":"Orda, A., Rom, R.: Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J. ACM 37(3), 607\u2013625 (1990)","journal-title":"J. ACM"},{"key":"758_CR15","doi-asserted-by":"crossref","unstructured":"Li, L., Wang, S., Zhou, X.: Time-dependent hop labeling on road network. In: 2019 IEEE 35th International Conference on Data Engineering (ICDE), pp. 1\u201312. IEEE (2019)","DOI":"10.1109\/ICDE.2019.00085"},{"key":"758_CR16","doi-asserted-by":"crossref","unstructured":"Batz, G.V., Delling, D., Sanders, P., Vetter, C.: Time-dependent contraction hierarchies. In: Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX), p. 97-105 (2009)","DOI":"10.1137\/1.9781611972894.10"},{"issue":"11","key":"758_CR17","doi-asserted-by":"publisher","first-page":"1274","DOI":"10.14778\/3137628.3137638","volume":"10","author":"L Li","year":"2017","unstructured":"Li, L., Hua, W., Du, X., Zhou, X.: Minimal on-road time route scheduling on time-dependent graphs. Proc. VLDB Endow. 10(11), 1274\u20131285 (2017)","journal-title":"Proc. VLDB Endow."},{"issue":"3","key":"758_CR18","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s00778-018-0499-4","volume":"27","author":"L Li","year":"2018","unstructured":"Li, L., Zheng, K., Wang, S., Hua, W., Zhou, X.: Go slow to go fast: minimal on-road time route scheduling with parking facilities using historical trajectory. VLDB J. 27(3), 321\u2013345 (2018)","journal-title":"VLDB J."},{"issue":"1","key":"758_CR19","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/3231541.3231545","volume":"10","author":"L Li","year":"2018","unstructured":"Li, L., Kim, J., Xu, J., Zhou, X.: Time-dependent route scheduling on road networks. SIGSPATIAL Spec. 10(1), 10\u201314 (2018)","journal-title":"SIGSPATIAL Spec."},{"key":"758_CR20","doi-asserted-by":"crossref","unstructured":"Li, L., Wang, S., Zhou, X.: Fastest path query answering using time-dependent hop-labeling in road network. IEEE Trans. Knowl. Data Eng. (2020)","DOI":"10.1109\/TKDE.2020.2981062"},{"key":"758_CR21","doi-asserted-by":"crossref","unstructured":"Chen, D., Yuan, Y., Du, W., Cheng, Y., Wang, G.: Online route planning over time-dependent road networks. In: 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 325\u2013335. IEEE (2021)","DOI":"10.1109\/ICDE51399.2021.00035"},{"key":"758_CR22","doi-asserted-by":"crossref","unstructured":"Demiryurek, U., Banaei-Kashani, F., Shahabi, C.: Towards k-nearest neighbor search in time-dependent spatial network databases. In: International Conference on Databases in Networked Information Systems, pp. 296\u2013310 (2010)","DOI":"10.1007\/978-3-642-12038-1_20"},{"key":"758_CR23","doi-asserted-by":"crossref","unstructured":"Komai, Y., Nguyen, D.H., Hara, T., Nishio, S.: Knn search utilizing index of the minimum road travel time in time-dependent road networks. Proceedings of the IEEE Symposium on Reliable Distributed Systems pp. 131\u2013137 (2014)","DOI":"10.1109\/SRDSW.2014.17"},{"key":"758_CR24","doi-asserted-by":"crossref","unstructured":"Kolahdouzan, M., Shahabi, C.: Voronoi-based k nearest neighbor search for spatial network databases. In: Proceedings of the Thirtieth international conference on Very large data bases-Volume 30, pp. 84\u2013851. VLDB Endowment (2004)","DOI":"10.1016\/B978-012088469-8.50074-7"},{"key":"758_CR25","doi-asserted-by":"crossref","unstructured":"Demiryurek, U., Kashani, F., Shahabi, C.: Efficient k-nearest neighbor search in time-dependent spatial networks. In: Database and Expert Systems Applications, International Conference, Dexa, Bilbao, Spain, August 30-Sept., p. 432-449 (2010)","DOI":"10.1007\/978-3-642-15364-8_36"},{"key":"758_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1155\/2019\/8385426","volume":"2019","author":"Y Yang","year":"2019","unstructured":"Yang, Y., Li, H., Wang, J., Hu, Q., Wang, X., Leng, M.: A novel index method for k nearest object query over time-dependent road networks. Complexity 2019, 1\u201318 (2019)","journal-title":"Complexity"},{"issue":"3","key":"758_CR27","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1287\/opre.17.3.395","volume":"17","author":"SE Dreyfus","year":"1969","unstructured":"Dreyfus, S.E.: An appraisal of some shortest-path algorithms. Oper. Res. 17(3), 395\u2013412 (1969)","journal-title":"Oper. Res."},{"key":"758_CR28","doi-asserted-by":"crossref","unstructured":"Ouyang, D., Qin, L., Chang, L., Lin, X., Zhang, Y., Zhu, Q.: When hierarchy meets 2-hop-labeling: Efficient shortest distance queries on road networks. In: SIGMOD, pp. 709\u2013724 (2018)","DOI":"10.1145\/3183713.3196913"},{"issue":"3","key":"758_CR29","first-page":"547","volume":"24","author":"KCK 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 TKDE 24(3), 547\u2013560 (2012)","journal-title":"IEEE TKDE"},{"key":"758_CR30","doi-asserted-by":"crossref","unstructured":"Abeywickrama, T., Cheema, M.A., Taniar, D.: K-nearest neighbors on road networks: a journey in experimentation and in-memory implementation. VLDB Endowment (2016)","DOI":"10.14778\/2904121.2904125"},{"key":"758_CR31","doi-asserted-by":"crossref","unstructured":"Ouyang, D., Wen, D., Qin, L., Chang, L., Lin, X.: Progressive top-k nearest neighbors search in large road networks. In: SIGMOD\/PODS \u201920: International Conference on Management of Data (2020)","DOI":"10.1145\/3318464.3389746"},{"key":"758_CR32","doi-asserted-by":"crossref","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-Volume 29, pp. 802\u2013813. VLDB Endowment (2003)","DOI":"10.1016\/B978-012722442-8\/50076-8"},{"key":"758_CR33","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., Kawarabayashi, K., Kawata, Y.: Fast shortest-path distance queries on road networks by pruned highway labeling. Society for Industrial and Applied Mathematics (2014)","DOI":"10.1145\/2463676.2465315"},{"key":"758_CR34","doi-asserted-by":"crossref","unstructured":"Demiryurek, U., Banaei-Kashani, F., Shahabi, C., Ranganathan, A.: Online computation of fastest path in time-dependent spatial networks. In: International Symposium on Spatial and Temporal Databases (SSTD), pp. 92\u2013111 (2011)","DOI":"10.1007\/978-3-642-22922-0_7"},{"key":"758_CR35","doi-asserted-by":"crossref","unstructured":"Bidirectional a* search on time-dependent road networks. Networks 59(2), 240\u2013251 (2012)","DOI":"10.1002\/net.20438"},{"key":"758_CR36","doi-asserted-by":"crossref","unstructured":"Foschini, L., Hershberger, J., Suri, S.: On the complexity of time-dependent shortest paths. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 327\u2013341. SIAM (2011)","DOI":"10.1137\/1.9781611973082.27"},{"key":"758_CR37","doi-asserted-by":"crossref","unstructured":"D, D.: Time-dependent sharc-routing. Algorithmica 60, 60-94 (2011)","DOI":"10.1007\/s00453-009-9341-0"},{"issue":"11","key":"758_CR38","doi-asserted-by":"publisher","first-page":"2127","DOI":"10.14778\/3476249.3476267","volume":"14","author":"M Zhang","year":"2021","unstructured":"Zhang, M., Li, L., Zhou, X.: An experimental evaluation and guideline for path finding in weighted dynamic network. Proc. VLDB Endow. 14(11), 2127\u20132140 (2021)","journal-title":"Proc. VLDB Endow."},{"key":"758_CR39","doi-asserted-by":"crossref","unstructured":"Zhang, M., Li, L., Hua, W., Zhou, X.: Efficient 2-hop labeling maintenance in dynamic small-world networks. In: 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 133\u2013144. IEEE (2021)","DOI":"10.1109\/ICDE51399.2021.00019"},{"key":"758_CR40","doi-asserted-by":"crossref","unstructured":"Zhang, M., Li, L., Hua, W., Mao, R., Chao, P., Zhou, X.: Dynamic hub labeling for road networks. In: 2021 IEEE 37th International Conference on Data Engineering (ICDE), pp. 336\u2013347. IEEE (2021)","DOI":"10.1109\/ICDE51399.2021.00036"},{"key":"758_CR41","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth acta cybern (1993)"},{"key":"758_CR42","doi-asserted-by":"crossref","unstructured":"Li, M., He, D., Zhou, X.: Efficient knn search with occupation in large-scale on-demand ride-hailing (2020)","DOI":"10.1007\/978-3-030-39469-1_3"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-022-00758-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-022-00758-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-022-00758-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,19]],"date-time":"2023-04-19T01:07:27Z","timestamp":1681866447000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-022-00758-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,27]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["758"],"URL":"https:\/\/doi.org\/10.1007\/s00778-022-00758-w","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,27]]},"assertion":[{"value":"16 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 April 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 July 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}