AVR-Tree: Speeding Up the NN and ANN Queries on Location Data

Publisher:
Springer
Publication Type:
Conference Proceeding
Citation:
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:
2013-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013005453OK.pdf371.6 kB
Adobe PDF
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: