Nearest and reverse nearest neighbor queries for moving objects

R. Benetis, Christian Søndergaard Jensen, G. Karciauskas, Simonas Saltenis

Research output: Contribution to journalJournal articleCommunication

158 Citations (Scopus)


With the continued proliferation of wireless communications and advances in positioning technologies, algorithms for efficiently answering queries about large populations of moving objects are gaining in interest. This paper proposes algorithms for k nearest and reverse k nearest neighbor queries on the current and anticipated future positions of points moving continuously in the plane. The former type of query returns k objects nearest to a query object for each time point during a time interval, while the latter returns the objects that have a specified query object as one of their k closest neighbors, again for each time point during a time interval. In addition, algorithms for so-called persistent and continuous variants of these queries are provided. The algorithms are based on the indexing of object positions represented as linear functions of time. The results of empirical performance experiments are reported.
Original languageEnglish
JournalVLDB Journal
Issue number3
Pages (from-to)22-
Publication statusPublished - 2006


Dive into the research topics of 'Nearest and reverse nearest neighbor queries for moving objects'. Together they form a unique fingerprint.

Cite this