Research And Implementation K-Nearest Neighbor Query Based On Covered Area

In recent years, with the development of technology, location-related technology such as location services, navigation, surveillance technology has been widely into real life. Today a large number of location-enabled portable devices (such as mobile phones, GPS, etc.) have become popular, which makes it easy to track and record the location of moving objects. The k-nearest neighbors query over moving objects is one of the most important applications. For example, in the traffic network a taxi wants to find the first k nearest gas stations or hotels from the current location by global positioning technology, so the taxi driver can choose a short and convenient one from their results; During the war, a soldier wants to check the persons who are around himself; In sailing, a ship need to check the other ones whose location is nearby, etc. Although the K-nearest neighbor queries have been a lot of research results, there are few researches on how to solve k-nearest neighbor query efficiently in highly dynamic environment, especially query point and the point being queried are both moving. Therefore, this paper from the issue as a starting point, give a further study.First, the paper analyzes the difficulty of k-nearest neighbors query in frequent movement environment and then use grid files to solve the frequently updated problem, utilize voronoi diagram to solve the query problem. The paper proposes a novel approach combined Virtual Grid Quadtree (VGQ) and Voronoi diagram called Vor-VGQ index structure. The index is appropriate for kNN query and supports efficient update. It reduces the number of updates through indexing not objects but girds.Secondly, the paper proposes two strategies for kNN query. One id oriented to improve query performance real-time dynamic Voronoi Diagram transformation strategy with the change of grid synchronization changes Voronoi Diagram; the other is oriented to improving the efficiency of monotonous dynamic Voronoi Diagram update strategy, to form a stable structure of Voronoi diagram distribution based on road structure. Using the above two strategies designed range query and KNN query algorithm, and prove the accuracy.Finally, some experiments are conducted to compare and analyze the solutions. Experiment results show that compared with the other algorithms, the efficiency of the K Nearest Neighbor query algorithm is improved more largely. The query time is three orders magnitude faster than the existed work (Bx-Tree).