Nearest and reverse nearest neighbor queries for moving objects |
| |
Authors: | Rimantas Benetis Christian S Jensen Gytis Kar?iauskas Simonas ?altenis |
| |
Affiliation: | 1. Department of Computer Science, Aalborg University, Aalborg ?st, Denmark
|
| |
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 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. |
| |
Keywords: | Continuous queries Incremental update Location-based services Mobile objects Neighbor queries Persistent queries |
本文献已被 SpringerLink 等数据库收录! |