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
This work is supported under the Australian Research Council's Discovery funding scheme (project number DP0880215).