Research And Implementation Of Continuous Moving Query Algorithms Based On Covered Area

Spatial queries based on location services have extensive application prospects in many areas, such as traffic navigation, the rescue service, digital battlefield and so on. In recent years, along with the development of wireless communication and global positioning system positioning technology, query technology in moving environment has become a hot spot in the field of mobile database. Since the query objects and objects being queried are constantly changing in mobile environment, the query in the mobile environment is more complex but has less research results. Different from the traditional query that just calculates one times, the continuous query needs to maintain query results for an extended period. Therefore it is more challenging to implement in the mobile environment. The thesis mainly aims at two kinds of spatial queries, respectively, the continuous range query and continuous K nearest neighbor query in the mobile environment.Firstly, the Del-VGQ index, which is a hierarchical index, is constituted by Delaunay triangulation net and Virtual Grid Quadtree (VGQ). It has the quick locating features of VGQ index and the nature of Delaunay triangulation which can express the adjacent objects, and it is suitable for moving queries. However, it can not complete continuous moving query directly, so the thesis extends the Del-VGQ index. Through the analysis of the characteristics of the object in mobile environment, the thesis proposes continuous range query algorithm DelVGQRangeQuery based on Del-VGQ index and proves the accuracy of the algorithm. Then the thesis conducts a simulation experiment to verify the performance of the algorithm. The experimental results show that the cpu time of continuous range query based on covered area is one order of magnitude faster than continuous range query directly with TPR-tree indexing moving objects.Secondly, the thesis proposes two kinds of continuous K nearest neighbor query algorithms VGQKnnQuery and DelVGQKnnQuery based on VGQ index and extended Del-VGQ index respectively, and proves the correctness of two algorithms. Then the thesis conducts simulation experiments to verify the performance of the algorithms. The experimental results show that the response time of VGQKnnQuery is slower than DelVGQKnnQuery, but the update time of the former is faster than the time of the latter. It is decided by index structure and the execution of query algorithm. In addition, DelVGQKnnQuery has a good adaptability in large data size.Finally, the thesis researches continuous K nearest neighbor query in the environment of road network. Aforementioned continuous K nearest neighbor queries use Euclidean distance as the distance between two moving objects, but the distance in road network is the shortest path between two objects. So in this thesis, we firstly make a model of road network, then complete continuous K nearest neighbor query using the model and prove the correctness of the algorithm, finally conduct simulation experiments to verify the performance of the algorithm. The experimental results show that the cpu time of continuous K nearest neighbor query algorithm in this thesis is one order of magnitude faster than the time of traditional IMA algorithm.