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

Complexity 2019:1-18 (2019)
  Copy   BIBTEX


Knearest neighbor search is an important problem in location-based services 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 forkNN 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 ofkNN query on time-dependent road networks, we propose a novel voronoi-based index in this paper. Furthermore, we propose a novel balanced tree, namedV-tree, 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.



    Upload a copy of this work     Papers currently archived: 76,215

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Wang Chuan-Shan on the Relationship between Ying-Yang and Dao.Chi-chu Chen - 2002 - Philosophy and Culture 29 (11):1032-1039.
In defence of object-dependent thoughts.Sean Crawford - 1998 - Proceedings of the Aristotelian Society 98 (2):201-210.
Querying linguistic treebanks with monadic second-order logic in linear time.Stephan Kepser - 2004 - Journal of Logic, Language and Information 13 (4):457-470.
Object‐Dependent Thought Without Illusion.Solveig Aasen - 2017 - European Journal of Philosophy 25 (1):68-84.
Do object-dependent properties threaten physicalism?Chris Daly & David Liggins - 2010 - Journal of Philosophy 107 (11):610-614.
Asymmetrism about Desire Satisfactionism and Time.Eden Lin - 2017 - In Mark Timmons (ed.), Oxford Studies in Normative Ethics, vol. 7. Oxford, UK: Oxford University Press. pp. 161-183.


Added to PP

4 (#1,239,133)

6 months
1 (#449,220)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

No citations found.

Add more citations