A Novel Index Method for K Nearest Object Query over Time-Dependent Road Networks. (24th February 2019)

• Record Type: Journal Article
• Authors: Yang, Yajun; Li, Hanxiao; Wang, Junhu; Hu, Qinghua; Wang, Xin; Leng, Muxi
• Other Names: Xu Jiajie Guest Editor.
• Is Part Of: Complexity. Volume 2019(2019)
• Publication Date: 2019-02-24
• Subjects: Chaotic behavior in systems -- Periodicals; Complexity (Philosophy) -- Periodicals; 003
• DOI: 10.1155/2019/4829164
• Languages: English
• ISSNs: 1076-2787

Abstract

Abstract : K nearest neighbor (k 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 k 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 k 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 V -t r e e, 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.