Research And Implementation Of Mobile Objects Nearest Neighbor Query Algorithm Based On Covered Area

In recent years, with the development and application of wireless network communication technology, global positioning technology (GPS) and geographic information systems, 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 mobile objects. The Nearest neighbor query of mobile objects is one of the most important applications. For example, in the traffic network a taxi wants to find the nearest gas station or hotel from the current location by global positioning technology; in the digital battlefield, a soldier wants to find the nearest comrades through the wireless location devices, etc. Although a lot of work has been done on the nearest neighbor query, there are few researches on how to solve nearest neighbor query efficiently when both the querying objects and queried objects are moving. Therefore, this thesis will make a further study on the issue.Firstly, this thesis analyzes the mobile objects movement in the road network, and then Comprehensive utilization the merits of grid files, compressed quad trees, and voronoi diagrams, a mobile objects index grid quadtree-voronoi (GQV) which is based on covered area is proposed, which can well support nearest neighbor queries. In GQV, the areas covered by mobile objects instead of the location of mobile objects are indexed to reduce the number of update operations of the index structure.Secondly, based on the index of GQV which is based on covered area, this thesis proposes two nearest neighbor query algorithms to the nearest neighbor queries when both the querying objects and queried objects are moving. The first is the best first nearest neighbor query algorithm (BFNN) which is used priority queue; the second is VorNN algorithm which is used grid voronoi diagrams; and then consider to the peculiarity of the two algorithms, GQVPNN algorithm is proposed, thus it can improve the efficiency of nearest neighbor query algorithm effectively.Finally, some experiments are conducted to compare and analyze the index structure and the nearest neighbor algorithms. The experimental results show that, GQV index structure is a stable index structure, and the GQVPNN algorithm which is based on GQV index can solve the nearest neighbor query problems in dynamic environment well and have high efficient query performance.