Monitoring path nearest neighbor in road networks

Chen, Zaiben, Shen, Heng Tao, Zhou, Xiaofang and Yu, Jeffrey Xu (2009). Monitoring path nearest neighbor in road networks. In: Carsten Binnig and Benoit Dageville, Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. ACM SIGMOD/PODS Conference: Providence, 2009, Providence, RI, USA, (591-602). 29 June - 2 July 2009. doi:10.1145/1559845.1559907

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads

Author Chen, Zaiben
Shen, Heng Tao
Zhou, Xiaofang
Yu, Jeffrey Xu
Title of paper Monitoring path nearest neighbor in road networks
Conference name ACM SIGMOD/PODS Conference: Providence, 2009
Conference location Providence, RI, USA
Conference dates 29 June - 2 July 2009
Proceedings title Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data
Place of Publication New York, NY, United States
Publisher Association for Computing Machinery
Publication Year 2009
Sub-type Fully published paper
DOI 10.1145/1559845.1559907
Open Access Status
ISBN 9781605585543
Editor Carsten Binnig
Benoit Dageville
Start page 591
End page 602
Total pages 12
Collection year 2010
Language eng
Formatted Abstract/Summary
This paper addresses the problem of monitoring the k nearest neighbors to a dynamically changing path in road networks. Given a destination where a user is going to, this new query returns the k-NN with respect to the shortest path connecting the destination and the user's current location, and thus provides a list of nearest candidates for reference by considering the whole coming journey. We name this query the k-Path Nearest Neighbor query (k-PNN). As the user is moving and may not always follow the shortest path, the query path keeps changing. The challenge of monitoring the k-PNN for an arbitrarily moving user is to dynamically determine the update locations and then refresh the k-PNN efficiently. We propose a three-phase Best-first Network Expansion (BNE) algorithm for monitoring the k- PNN and the corresponding shortest path. In the searching phase, the BNE finds the shortest path to the destination, during which a candidate set that guarantees to include the k-PNN is generated at the same time. Then in the verification phase, a heuristic algorithm runs for examining candidates' exact distances to the query path, and it achieves significant reduction in the number of visited nodes. The monitoring phase deals with computing update locations as well as refreshing the k-PNN in different user movements. Since determining the network distance is a costly process, an expansion tree and the candidate set are carefully maintained by the BNE algorithm, which can provide efficient update on the shortest path and the k-PNN results. Finally, we conduct extensive experiments on real road networks and show that our methods
Subjects 0806 Information Systems
890399 Information Services not elsewhere classified
Keyword Path nearest neighbor
Road networks
Spatial databases
Q-Index Code E1
Q-Index Status Confirmed Code
Institutional Status UQ

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 17 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 40 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Mon, 19 Apr 2010, 14:14:13 EST by Marie Walker on behalf of School of Information Technol and Elec Engineering