{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:12:43Z","timestamp":1753884763754,"version":"3.41.2"},"reference-count":33,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T00:00:00Z","timestamp":1550966400000},"content-version":"vor","delay-in-days":54,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61402323","61572353","U1736103"],"award-info":[{"award-number":["61402323","61572353","U1736103"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Complexity"],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p><jats:italic>K<\/jats:italic> nearest neighbor (<jats:italic>k<\/jats:italic>NN) search is an important problem in\u2009 <jats:italic>location-based services<\/jats:italic> (LBS) and has been well studied on static road networks. However, in real world, road networks are often time\u2010dependent; i.e., the time for traveling through a road always changes over time. Most existing methods for <jats:italic>k<\/jats:italic>NN query build various indexes maintaining the shortest distances for some pairs of vertices on static road networks. Unfortunately, these methods cannot be used for the time\u2010dependent road networks because the shortest distances always change over time. To address the problem of <jats:italic>k<\/jats:italic>NN query on time\u2010dependent road networks, we propose a novel voronoi\u2010based index in this paper. Furthermore, we propose a novel balanced tree, named \u2010, which is a secondary level index on voronoi\u2010based index to make our querying algorithm more efficient. Moreover, we propose an algorithm for preprocessing time\u2010dependent road networks such that the waiting time is not necessary to be considered. We confirm the efficiency of our method through experiments on real\u2010life datasets.<\/jats:p>","DOI":"10.1155\/2019\/4829164","type":"journal-article","created":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T23:31:16Z","timestamp":1551051076000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Novel Index Method for K Nearest Object Query over Time\u2010Dependent Road Networks"],"prefix":"10.1155","volume":"2019","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0824-2931","authenticated-orcid":false,"given":"Yajun","family":"Yang","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6732-6417","authenticated-orcid":false,"given":"Hanxiao","family":"Li","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2962-1604","authenticated-orcid":false,"given":"Junhu","family":"Wang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7765-8095","authenticated-orcid":false,"given":"Qinghua","family":"Hu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9651-0651","authenticated-orcid":false,"given":"Xin","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Muxi","family":"Leng","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2019,2,24]]},"reference":[{"key":"e_1_2_14_1_2","doi-asserted-by":"crossref","unstructured":"AbeywickramaT. CheemaM. A. andTaniarD. k-nearest neighbors on road networks: A journey in experimentation and in memory implementation 9 no. 6 Proceedings of the 42nd International Conference on Very Large Data Bases VLDB 2016 September 2016 492\u2013503 2-s2.0-84976562256.","DOI":"10.14778\/2904121.2904125"},{"key":"e_1_2_14_2_2","doi-asserted-by":"crossref","unstructured":"LeeK. C. LeeW. andZhengB. Fast object search on road networks Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology March 2009 Saint Petersburg Russia https:\/\/doi.org\/10.1145\/1516360.1516476.","DOI":"10.1145\/1516360.1516476"},{"key":"e_1_2_14_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177736"},{"key":"e_1_2_14_4_2","doi-asserted-by":"crossref","unstructured":"Wei-KleinerF. Finding nearest neighbors in road networks: a tree decomposition method Proceedings of the the Joint EDBT\/ICDT 2013 Workshops March 2013 Genoa Italy 233\u2013240 https:\/\/doi.org\/10.1145\/2457317.2457355.","DOI":"10.1145\/2457317.2457355"},{"key":"e_1_2_14_5_2","doi-asserted-by":"crossref","unstructured":"ChucreM. R. R. B. do NascimentoS. M. de Mac\u00eadoJ. A.et al. Taxi please! a nearest neighbor query in time-dependent road networks Proceedings of the 2016 17th IEEE International Conference on Mobile Data Management (MDM) June 2016 180\u2013185 https:\/\/doi.org\/10.1109\/MDM.2016.36.","DOI":"10.1109\/MDM.2016.36"},{"key":"e_1_2_14_6_2","first-page":"191","article-title":"Time-aggregated graphs for modeling spatio-temporal networks","volume":"11","author":"George B.","year":"2006","journal-title":"Journal on Data Semantics"},{"key":"e_1_2_14_7_2","doi-asserted-by":"crossref","unstructured":"KanoulasE. DuY. XiaT. andZhangD. Finding fastest paths on a road network with speed patterns Proceedings of the 22nd International Conference on Data Engineering April 2006 https:\/\/doi.org\/10.1109\/ICDE.2006.71 2-s2.0-33749609313.","DOI":"10.1109\/ICDE.2006.71"},{"key":"e_1_2_14_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/cplx.20384"},{"key":"e_1_2_14_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15364-8_36"},{"key":"e_1_2_14_10_2","unstructured":"CruzL. A. LettichF. J\u00faniorL. S. Magalh\u00e3esR. P. andde Mac\u00eadoJ. A. F. Finding the nearest service provider on time-dependent road networks Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery 2017 21\u201331."},{"key":"e_1_2_14_11_2","doi-asserted-by":"crossref","unstructured":"KomaiY. NguyenD. H. HaraT. andNishioS. KNN search utilizing index of the minimum road travel time in time-dependent road networks Proceedings of the 2014 IEEE 33rd International Symposium on Reliable Distributed Systems Workshops SRDSW 2014 October 2014 131\u2013137 2-s2.0-84932101867.","DOI":"10.1109\/SRDSW.2014.17"},{"key":"e_1_2_14_12_2","first-page":"211","article-title":"k-nearest neighbors queries in time-dependent road networks","volume":"3","author":"Cruz L. A.","year":"2012","journal-title":"JIDM"},{"key":"e_1_2_14_13_2","doi-asserted-by":"crossref","unstructured":"DingB. YuJ. X. andQinL. Finding time-dependent shortest paths over large graphs Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology March 2008 Nantes France 205\u2013216 https:\/\/doi.org\/10.1145\/1353343.1353371.","DOI":"10.1145\/1353343.1353371"},{"key":"e_1_2_14_14_2","doi-asserted-by":"crossref","unstructured":"ZhongR. LiG. TanK. andZhouL. G-tree: an efficient index for KNN search on road networks Proceedings of the 22nd ACM international conference on Information & Knowledge Management October 2013 San Francisco Calif USA 39\u201348 https:\/\/doi.org\/10.1145\/2505515.2505749.","DOI":"10.1145\/2505515.2505749"},{"key":"e_1_2_14_15_2","doi-asserted-by":"crossref","unstructured":"Abou-RjeiliA.andKarypisG. Multilevel algorithms for partitioning power-law graphs Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium IPDPS 2006 April 2006 2-s2.0-33847103633.","DOI":"10.1109\/IPDPS.2006.1639360"},{"key":"e_1_2_14_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1115"},{"key":"e_1_2_14_17_2","doi-asserted-by":"crossref","unstructured":"XuX. YurukN. FengZ. andSchweigerT. A. SCAN: a structural clustering algorithm for networks Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery And Data Mining August 2007 San Jose Calif USA 824\u2013833 https:\/\/doi.org\/10.1145\/1281192.1281280.","DOI":"10.1145\/1281192.1281280"},{"key":"e_1_2_14_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_14"},{"key":"e_1_2_14_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_5"},{"key":"e_1_2_14_20_2","doi-asserted-by":"crossref","unstructured":"KolahdouzanM. R.andShahabiC. Voronoi-based K nearest neighbor search for spatial network databases Proceedings of the Thirtieth International Conference on Very Large Data Bases 2004 840\u2013851.","DOI":"10.1016\/B978-012088469-8.50074-7"},{"key":"e_1_2_14_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2014.01.001"},{"key":"e_1_2_14_22_2","doi-asserted-by":"publisher","DOI":"10.1155\/2018\/2067065"},{"key":"e_1_2_14_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0445-2"},{"key":"e_1_2_14_24_2","doi-asserted-by":"crossref","unstructured":"ZhengY. GuoQ. TungA. K. H. andWuS. Lazylsh: approximate nearest neighbor search for multiple distance functions with a single index Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data SIGMOD 2016 July 2016 2023\u20132037 2-s2.0-84979658587.","DOI":"10.1145\/2882903.2882930"},{"key":"e_1_2_14_25_2","unstructured":"ZhuH. YangX. WangB. andLeeW.-C. Range-based obstructed nearest neighbor queries Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data SIGMOD 2016 July 2016 2053\u20132068 2-s2.0-84979704147."},{"key":"e_1_2_14_26_2","doi-asserted-by":"crossref","unstructured":"CostaC. F. NascimentoM. A. MacedoJ. A. andMachadoJ. A\u204e-based solutions for KNN queries with operating time constraints in time-dependent road networks Proceedings of the 2014 15th IEEE International Conference on Mobile Data Management (MDM) July 2014 Brisbane Australia 23\u201332 https:\/\/doi.org\/10.1109\/MDM.2014.9.","DOI":"10.1109\/MDM.2014.9"},{"key":"e_1_2_14_27_2","doi-asserted-by":"crossref","unstructured":"CostaC. F. MachadoJ. NascimentoM. A. andMac\u00eadoJ. A. Aggregate k-nearest neighbors queries in time-dependent road networks Proceedings of the the 4th ACM SIGSPATIAL International Workshop November 2015 3\u201312 https:\/\/doi.org\/10.1145\/2834126.2834129.","DOI":"10.1145\/2834126.2834129"},{"key":"e_1_2_14_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2013.07.009"},{"key":"e_1_2_14_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2808495"},{"key":"e_1_2_14_30_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732941"},{"key":"e_1_2_14_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0457-6"},{"key":"e_1_2_14_32_2","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137638"},{"key":"e_1_2_14_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0499-4"}],"container-title":["Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2019\/4829164.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2019\/4829164.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2019\/4829164","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T11:43:18Z","timestamp":1723030998000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2019\/4829164"}},"subtitle":[],"editor":[{"given":"Jiajie","family":"Xu","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1155\/2019\/4829164"],"URL":"https:\/\/doi.org\/10.1155\/2019\/4829164","archive":["Portico"],"relation":{},"ISSN":["1076-2787","1099-0526"],"issn-type":[{"type":"print","value":"1076-2787"},{"type":"electronic","value":"1099-0526"}],"subject":[],"published":{"date-parts":[[2019,1]]},"assertion":[{"value":"2018-11-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-28","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"4829164"}}