Skip to main content
Article
Continuous Nearest Neighbor Monitoring in Road Networks
VLDB 2006: Proceedings of the 32nd International Conference on Very Large Data Bases: September 12-15, 2006, COEX, Seoul, Korea
  • Kyriakos MOURATIDIS, Singapore Management University
  • Man Lung YIU, University of Hong Kong
  • Dimitris PAPADIAS, Hong Kong University of Science and Technology
  • Nikos MAMOULIS, University of Hong Kong
Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
9-2006
Abstract

Recent research has focused on continuous monitoring of nearest neighbors (NN) in highly dynamic scenarios, where the queries and the data objects move frequently and arbitrarily. All existing methods, however, assume the Euclidean distance metric. In this paper we study k-NN monitoring in road networks, where the distance between a query and a data object is determined by the length of the shortest path connecting them. We propose two methods that can handle arbitrary object and query moving patterns, as well as °uctuations of edge weights. The ¯rst one maintains the query results by processing only updates that may invalidate the current NN sets. The second method follows the shared execution paradigm to reduce the processing time. In particular, it groups together the queries that fall in the path between two consecutive intersections in the network, and produces their results by monitoring the NN sets of these intersections. We experimentally verify the applicability of the proposed techniques to continuous monitoring of large data and query sets.

Keywords
  • information retrieval,
  • nearest neighbors,
  • data query,
  • road networks,
  • network monitoring,
  • query optimization
ISBN
9781595933850
Publisher
VLDB Endowment
City or Country
New York
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Additional URL
http://www.vldb.org/conf/2006/p43-mouratidis.pdf
Citation Information
Kyriakos MOURATIDIS, Man Lung YIU, Dimitris PAPADIAS and Nikos MAMOULIS. "Continuous Nearest Neighbor Monitoring in Road Networks" VLDB 2006: Proceedings of the 32nd International Conference on Very Large Data Bases: September 12-15, 2006, COEX, Seoul, Korea (2006) p. 43 - 54
Available at: http://works.bepress.com/kyriakos_mouratidis/7/