Research On The Method Of Distributed Reverse Nearest Neighbors Query Based On Voronoi Diagram

Spatial data describes the basic information about the location, shape and properties of objects in the real world. With the rapid development of cloud computing, big data and mobile Internet technology, a large amount of spatial data are brought together in traffic, environment, social networking and other fields. Especially with the popularity of location-based services, people put forward higher requirements on the diversity and efficiency of spatial information services. Spatial query is the basis of spatial information service, and its processing efficiency is the key factor to affect the service performance. In a large number of spatial queries, the reverse nearest neighbor query is mainly used to search for the data objects which regard the query point as their nearest neighbor. And the reverse nearest neighbor query is widely used in the field of geographic information, decision support and so on. However, when faced with the massive spatial data, the performance of traditional reverse nearest neighbor query algorithm has been difficult to meet the needs of users' query requirements. Therefore, it is necessary to provide a method to adapt to the nearest neighbor query for large scale spatial data.Compared with the traditional reverse nearest neighbor query algorithms based on tree index, this paper uses the spatial index method based on Voronoi diagram. When faced with the construction difficulties and complex computing problems of the existing Voronoi construction algorithms for large scale spatial data, a parallel Voronoi diagram construction method with MapReduce is proposed. This method uses an improved incremental insertion algorithm to construct the Delaunay triangulation mesh rapidly, and then transforms it to the Voronoi diagram through dual operations of the Quad-Edge structure. For the problems of reverse nearest neighbor query for large scale spatial data, this paper proposes a processing framework based on SpatialHadoop for the reverse nearest neighbor query, which has the advantages of high parallelism and scalability. Then, the distance between the neighboring points in the given data set are pre-computed by the constructed Voronoi diagram to generate the neighbor point distance list. Finally, this paper proposes a MR-RNN algorithm based on MapReduce and the neighbor point distance list, which are suitable for processing the reverse nearest neighbor queries for large scale spatial data.Experiments and analysis are made on both real and synthetic data set on a SpatialHadoop cluster consisting of 9 nodes. The experimental results show that the parallel Voronoi diagram construction method and the reverse nearest neighbor query method proposed in this paper have a good performance, which can meet the requirements of the reverse nearest neighbor query for the large scale spatial data.