HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/2986
Title: Continuous nearest neighbor monitoring in road networks
Authors: Mouratidis, Kyriakos
Yiu, Man Lung
Papadias, Dimitris
Mamoulis, Nikos
Keywords: Query formulation
Network monitoring
Query processing performance evaluation
Issue Date: Sep-2006
Citation: Proceedings 32nd International Conference on Very Large Data Bases, Seoul, Korea, 12-15 September 2006, p. 43-54
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 fluctuations of edge weights. The first 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.
Rights: © ACM, 2006. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings 32nd International Conference on Very Large Data Bases, Seoul, Korea, 12-15 September 2006, p. 43-54
URI: http://hdl.handle.net/1783.1/2986
Appears in Collections:CSE Conference Papers

Files in This Item:

File Description SizeFormat
VLDB06CNN.pdf243KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.