Research On Voronoi-based Aggregate Nearest Neighbor Query In Road Networks

With the rapid development of Mobile Computing, Wireless Communications and Positioning Technology, storing and managing a variety of space objects become the real demands. A large number of application areas are urgent to effectively query these data objects. However, the mass and complexity of spatial data makes that traditional database query processing techniques can not or can not effectively evaluate these queries. It need be new query processing techniques. Therefore, how to provide a variety of efficient spatial object query processing technology is one of the focuses of current research in the field of spatial database.Spatial database queries are based on the Euclidean space and road network. Usually, queries in the road network are more meaningful. This is because it limits the objects on the road, and query points and spatial objects can only move on the path. Queries in a road network are more appropriate to our lives. For example, a person would like find the nearest gas station or restaurant to him. Although many scholars study queries on road network, and have got a lot of achievements, meeting complex and diverse needs of persons still need further study.This paper mainly studies the Aggregation Nearest Neighbor (ANN) query in road networks. The current work on ANN query in road network[1] has two drawbacks:1. The best algorithm only applies to case that the weights of edges are proportional to their length.2. The performance of algorithms is poor with large number of query points. View of this, we solve ANN queries on the Network Voronoi diagram (NVD). The proposed algorithm solves the above shortcomings, and the performance of algorithm is superior to the-state-of-art in most cases. The main contributions of this paper are as follows:1. We are the first work to solve ANN queries based on the NVD according to our knowledge.2. We design efficient pruning strategies for different aggregate functions.3. We propose VANN algorithm, prove its correctness and its time complexity.4. We propose the AANN algorithm to solve ANN queries with large number of query points.5. We propose k-VANN algorithm to solve the k-ANN queries, it can be incremental obtain the next ANN.6. We conduct extensive experiments with real data sets to demonstrate VANN algorithm and k-VANN algorithm are better than the-state-of-art in most cases.