Algorithm of the Nearest Neighbor Query for Road Network Data Based on Quad-tree Structure

Aiming at the problem that the amount of data stored in road network is large and the efficiency of conventional query algorithm is low, combining storage technology and query algorithm, a nearest neighbor query algorithm was proposed to divide road network data uniformly by using quad-tree structure. Firstly, according to the points of interest, the space was divided into several adjacent spatial units by Voronoi diagram, and the whole spatial region was partitioned by means of spatial mean partition method, so that each partition contained several spatial units. The quad-tree structure was then used to create in-memory index data to reduce the range of data in the nearest neighbor query. Finally, the road network data of OSM (open street map) official website was used to verify the partition query. The results show that compared with the traditional iterative division between points method and half split method, the nearest-neighbor query algorithm based on structured partition can greatly improve the query efficiency of road network data.