Continuous nearest neighbor monitoring in road networks

Kyriakos Mouratidis, Man Lung Yiu, Dimitris Papadias, Nikos Mamoulis

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

182 Citations (Scopus)


Recent research has focused on continuous monitoring of nearest neighbors (NN) in highly dynamic scenarios, where he queries and the data objects move frequently and arbi-rarily. 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 par-ticular, 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 ne proposed techniques to continuous monitoring of large data and query sets.
Original languageEnglish
Title of host publicationVLDB 2006 - Proceedings of the 32nd International Conference on Very Large Data Bases
Number of pages12
Publication statusPublished - 1 Dec 2006
Externally publishedYes
Event32nd International Conference on Very Large Data Bases, VLDB 2006 - Seoul, Korea, Republic of
Duration: 12 Sept 200615 Sept 2006


Conference32nd International Conference on Very Large Data Bases, VLDB 2006
Country/TerritoryKorea, Republic of

ASJC Scopus subject areas

  • Hardware and Architecture
  • Information Systems
  • Software
  • Information Systems and Management


Dive into the research topics of 'Continuous nearest neighbor monitoring in road networks'. Together they form a unique fingerprint.

Cite this