Study On Mobile Objects Index And Continuous Range Query Processing Based On Covered Area

The efficiency of the mobile objects index is critical for mobile data management system. Due to the frequent change of large amount mobile objects'positions, the efficiency of the mobile objects index which is built based on the locations of the mobile objects is poor. How to reduce the locations of mobile objects change bringing about the index updates frequently has become a hot research content. In this thesis, the mobile objects index based on covered area and approximate continuous range query algorithms are proposed.Firstly, this thesis analyzes and summarizes the existing works and gives out the mobile date model based on the moving objects current locations. Then based on the observation on mobile objects movement in the road network, where the locations of mobile objects change very frequently and the region covered by the mobile objects changes slow relatively, a mobile objects index based on covered area virtual grid quad-tree(VGQ) is proposed based on the multi-dimensional structures. In VGQ, 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. After that, the related search and update algorithms are introduced and the complexity of algorithm operations are also described in detail, the VGQ index is efficient with regard to the response time and index space in theory.Secondly, the continuous range query is a challenge query type. In contrast to regular queries that are evaluated only once, a continuous range query remains active over a period. This thesis proposes an approximate continuous range query through adding monitoring list to each region grid. At the same time, considering two times continuous queries exist mixed result, the incremental query optimization algorithm is proposed; considering the use of top-down pruning procession increases the cost of the search tree time cost, the bottom-up query optimization algorithm is proposed.Finally, the designed index and related algorithms are evaluated in a simulated enviroement. The experimental results show that, VGQ index is a stable structure, compared with the grid file, VGQ can effectively improve the utilization rate of main memory without significant performance loss.