Research On K Nearest Neighbor Search For Moving Objects In Road Network Based On Quadtree

With popularity of mobile communication devices and development of wireless location technology,location-based service is widely used.It leads to increasing spatial data and increasingly complex spatial data structures.Spatial databases are faced with increasingly complex search queries.Therefore,it is of great significance to establish a fast and effective query algorithm for moving objects.K-nearest neighbor search,as one of the building blocks of spatial database query technology in the field,has been widely used in various fields and has become a hot research topic in recent year.However,most research are limited to specific environments(such as European space),there are few studies that fully consider the factors such as road network connectivity and moving object property.The road network model is more in line with actual needs,so that has more important research significance.Large amount of data,complex structures,tilted data,and frequently updated data in road network make query expensive.Therefore,how to increase query efficiency becomes a challenge.To solve the problem that how to improve efficiency of k-nearest neighbor search for moving objects with skewed and frequently updated date,this paper proposes the k-nearest neighbor search algorithm based on the quad-tree for moving objects in road networks after analyzing and summarizing related research.The main research work of this paper has the following aspects:(1)Considering that road network is stationary and moving object data is tilted,the R-tree and the quad-tree is used to index road network and moving objects,respectively.Each rectangle stores position information of moving objects,and its hierarchical structure can control the number of objects in each rectangle which facilitates obtaining appropriate search regions in the k-nearest neighbor searchalgorithm.The R-tree is used to index roads,query rectangles overlapping with the search area in R tree,and obtain corresponding roads in leaf nodes of these rectangles,finally load the local roads corresponding to the search area.(2)Establish information update mechanism between rectangular regions of quad-tree.The rectangle will be divided or merged when number of moving objects stored in the rectangular region exceeds a certain threshold.Therefore,it is necessary to design the update mechanisms so that these changed rectangles can also implement efficient neighbor queries.First,the new rectangle obtains its neighbor information by using neighbor information of its original rectangle,and then the new rectangle sends information to its own neighbor rectangles to update its original information.(3)Furthermore,we propose a search area extension method based on rectangle update mechanism and a K-nearest neighbor search algorithm based on the extension method.The incremental extension method which is mainly divided into a method for calculating the new search area after extension and a method for calculating neighbors of the new search area is designed to obtain an appropriate K-nearest neighbor search range by efficiently extending search area.Finally,the K-nearest neighbor search algorithm is designed based on incremental extension method and road index.(4)Comparative analysis of the experimental results.In this paper,the experiments are based on two road network data sets and analyzed from two aspects: query efficiency and update time.The experimental results show that the proposed algorithm can efficiently prune unnecessary objects for skewed data,making the query processing efficiency better than the comparison algorithm,and the algorithm is scalable and extensible.Update mechanism of this algorithm requires low cost and has a good ability to adapt to frequently updated mobile objects.