A Novel Index Method for K Nearest Object Query over Time-Dependent Road Networks

Yajun Yang, Hanxiao Li, Junhu Wang, Qinghua Hu, Xin Wang and Muxi Leng

Complexity, 2019, vol. 2019, 1-18

Abstract:

nearest neighbor ( NN) search is an important problem in  location-based services (LBS) and has been well studied on static road networks. However, in real world, road networks are often time-dependent; i.e., the time for traveling through a road always changes over time. Most existing methods for 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-dependent road networks because the shortest distances always change over time. To address the problem of NN query on time-dependent road networks, we propose a novel voronoi-based index in this paper. Furthermore, we propose a novel balanced tree, named - , which is a secondary level index on voronoi-based index to make our querying algorithm more efficient. Moreover, we propose an algorithm for preprocessing time-dependent road networks such that the waiting time is not necessary to be considered. We confirm the efficiency of our method through experiments on real-life datasets.

Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/8503/2019/4829164.pdf (application/pdf)
http://downloads.hindawi.com/journals/8503/2019/4829164.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:complx:4829164

DOI: 10.1155/2019/4829164

Access Statistics for this article

More articles in Complexity from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().