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

141 Citations (Scopus)

Abstract

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
Volume15
Issue number3
Pages (from-to)22-
ISSN1066-8888
Publication statusPublished - 2006

Fingerprint

Communication
Experiments

Cite this

@article{d91e3690a9f111dbb942000ea68e967b,
title = "Nearest and reverse nearest neighbor queries for moving objects",
abstract = "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.",
author = "R. Benetis and Jensen, {Christian S{\o}ndergaard} and G. Karciauskas and Simonas Saltenis",
year = "2006",
language = "English",
volume = "15",
pages = "22--",
journal = "V L D B Journal",
issn = "1066-8888",
publisher = "Springer",
number = "3",

}

Nearest and reverse nearest neighbor queries for moving objects. / Benetis, R.; Jensen, Christian Søndergaard; Karciauskas, G.; Saltenis, Simonas.

In: VLDB Journal, Vol. 15, No. 3, 2006, p. 22-.

Research output: Contribution to journalJournal articleCommunication

TY - JOUR

T1 - Nearest and reverse nearest neighbor queries for moving objects

AU - Benetis, R.

AU - Jensen, Christian Søndergaard

AU - Karciauskas, G.

AU - Saltenis, Simonas

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

M3 - Journal article

VL - 15

SP - 22-

JO - V L D B Journal

JF - V L D B Journal

SN - 1066-8888

IS - 3

ER -