AVR-Tree: Speeding Up the NN and ANN Queries on Location Data
- Publication Type:
- Conference Proceeding
- LNCS - Database Systems for Advanced Applications - Proceedings, Part I of the 18th International Conference on Database Systems for Advanced Applications, 2013, 7825 pp. 116 - 130
- Issue Date:
In the paper, we study the problems of nearest neighbor queries (NN) and all nearest neighbor queries (ANN) on location data, which have a wide range of applications such as Geographic Information System (GIS) and Location based Service (LBS). We propose a new structure, termed AVR-Tree, based on the R-tree and Voronoi diagram techniques. Compared with the existing indexing techniques used for NN and ANN queries on location data, AVR-Tree can achieve a better trade-off between the pruning effectiveness and the index size for NN and ANN queries. We also conduct a comprehensive performance evaluation for the proposed techniques based on both real and synthetic data, which shows that AVR-Tree based NN and ANN algorithms achieve better performance compared with their best competitors in terms of both CPU and I/O costs.
Please use this identifier to cite or link to this item: