Research And Implementation Of Nearest Neighbor Queries For Moving Objects With Keyword Based On Covered Area

The popular of device with location-based information services (Location BaseService, LBS) makes location-based services coming into people’s daily life. Forexample, mobile phone, laptop (PDA), GPS of vehicle and other electronic productscan provide location queries. Today, the popularity of LBS devices require LBS morepopular and diversity, and the nearest neighbor query for moving objects withkeyword including is one of location-based information services. For example, in theroad network, a vehicle traveling on the highway uses GPS system to query thenearest go to " Anshan city "; in the digital battlefield, a tank queries the nearest "enemy "headquarters; pedestrian queries the nearest"11Road " bus stop or " Tesco "supermarket and so on. At present, although the work for nearest neighbor withkeyword in temporal database has made a lot of achievements, but most of them aresimple queries, the function in the situation that moving objects are high-frequencymove is poor. Therefore, this paper mainly proceed from this problem for a morein-depth study and research.Firstly, according to characteristics of the movement and distribution of movingobjects with keyword in the road network, uses grid files and compressed quadtree todeal with the problem of moving objects’ frequently update, and then uses Voronoidiagram to deal with the problem of nearest keyword index, we propose a Vor-KVGQindex structure based on covered area that combined virtual grid quadtree withkeyword (Keyword Virtual Grid Quadtree, KVGQ) with the Voronoi diagram. Theindex use the advantage of grid files, compressed quadtree and Voronoi diagram,support nearest keyword index and support dynamic index in maximum. Vor-KVGQindex queries the grid cell where the moving object exists instead of queries themoving object itself, so greatly reduced the update of the index structure caused bymoving objects’ frequent updates.Secondly, we propose a nearest neighbor query can improve query’s efficiencybased on Vor-KVGQ, according to the distribution of grid file to establish thecorresponding Voronoi diagram. Uses the above ideas to design a nearest neighborquery algorithm and prove its correctness and efficiency.Finally, in order to prove the performance of Vor-KVGQ index structure and thenearest neighbor query algorithm, we did a simulation experiment, and results showthat the Vor-KVGQ is an efficient method of spatio-temporal database, and the nearestneighbor query algorithm based on Vor-KVGQ index structure has good performance, greatly improved the efficiency of spatio-temporal database query.