We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Analysis and evaluation of V*- kNN: an efficient algorithm for moving kNN queries.
- Authors
Nutanong, Sarana; Rui Zhang; Tanin, Egemen; Kulik, Lars
- Abstract
The moving k nearest neighbor (M kNN) query continuously finds the k nearest neighbors of a moving query point. M kNN 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 M kNN 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 in addition to the data objects. As a result, V*- kNN has much smaller I/O and computation costs than existing methods. We further provide cost models to estimate the number of data accesses for V*- kNN and a competitive technique, RIS- kNN. The V*-Diagram and V*- kNN are also applicable to the domain of spatial networks and we present algorithms to construct a spatial-network V*-Diagram. Our experimental results show that V*- kNN significantly outperforms the competitive technique. The results also verify the accuracy of the cost models.
- Subjects
SPATIAL data infrastructures; QUERY (Information retrieval system); ALGORITHMS; MATHEMATICAL models; COMPUTER input-output equipment
- Publication
VLDB Journal International Journal on Very Large Data Bases, 2010, Vol 19, Issue 3, p307
- ISSN
1066-8888
- Publication type
Article
- DOI
10.1007/s00778-009-0163-0