Nearest neighbor and reverse nearest neighbor queries for moving objects
- 25 June 2003
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
With the proliferation of wireless communications and the rapid advances in technologies for tracking the positions of continuously moving objects, algorithms for efficiently answering queries about large numbers of moving objects increasingly are needed. One such query is the reverse nearest neighbor (RNN) query that returns the objects that have a query object as their closest object. While algorithms have been proposed that compute RNN queries fornon-moving objects, there have been no proposals for answering RNN queries for continuously moving objects. Another such query is the nearest neighbor (NN) query, which has been studied extensively and in many contexts. Like the RNN query, the NN query has not been explored for moving query and data points.This paper proposes an algorithm for answering RNN queries for continuously moving points in the plane. As a part of the solution to this problem and as a separate contribution, an algorithm for answering NN queries for continuously moving points is also proposed. The results of performance experiments are reported.Keywords
This publication has 18 references indexed in Scilit:
- Indexing of moving objects for location-based servicesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- The effect of buffering on the performance of R-treesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Fast nearest neighbor search in high-dimensional spacePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Indexing the positions of continuously moving objectsPublished by Association for Computing Machinery (ACM) ,2000
- Influence sets based on reverse nearest neighbor queriesPublished by Association for Computing Machinery (ACM) ,2000
- Nearest Neighbor Queries in a Mobile EnvironmentPublished by Springer Nature ,1999
- Enhanced nearest neighbour search on the R-treeACM SIGMOD Record, 1998
- Optimal multi-step k-nearest neighbor searchPublished by Association for Computing Machinery (ACM) ,1998
- The SR-treePublished by Association for Computing Machinery (ACM) ,1997
- Nearest neighbor queriesPublished by Association for Computing Machinery (ACM) ,1995