Journal article

Analysis and evaluation of V*-kNN: an efficient algorithm for moving kNN queries

Sarana Nutanong, Rui Zhang, Egemen Tanin, Lars Kulik

VLDB JOURNAL | SPRINGER | Published : 2010


The moving k nearest neighbor (MkNN) query continuously finds the k nearest neighbors of a moving query point. MkNN queries can be efficiently processed through the use of safe regions. In general, a safe region is a region within which the query point can move without changing the query answer. This paper presents an incremental safe-region-based technique for answering MkNN queries, called the V*-Diagram, as well as analysis and evaluation of its associated algorithm, V*-kNN. Traditional safe-region approaches compute a safe region based on the data objects but independent of the query location. Our approach exploits the knowledge of the query location and the boundary of the search space ..

View full abstract


Awarded by Australian Research Council

Funding Acknowledgements

This work is supported under the Australian Research Council's Discovery funding scheme (project number DP0880215).