Research On B~+-Tree Based Indexing Of Moving Objects

As the wireless communications and electronic technology developing, moving objects management has become increasingly important in recent years and has become a hot research area of great theoretical and practical significance.Position of moving objects is updated frequently, the structure of index changes all the time, so the index of moving objects must not only support the frequent queries, more importantly, but also support frequent updates. There are many new query forms in spatio-temporal database. New designed index structure must satisfy the most demands.In this paper, the related work of index of moving objects were compared and analysed. This paper described several typical index structure. Two index of moving objects based on B+ tree (Bx trees and ST2B tree)have been introduced in detail, both of which are based on temporal partitioning and grid, Bx tree based on uniform grids, ST2B divides space into a few regions, for each different region with different grid. But both of two index structures have a few of deficiencies. Aiming at solving the problems of the index structures of moving objects, this paper proposes double-level grids based B+-tree index for moving objects.In practical applications, the moving objects are distributed non-uniformly in space. Double-level grids based B+-tree index for moving objects has good adaptability for the non-uniform distribution of moving objects. Double-level grids based B+-tree index for moving objects (namely DGB tree)divides the entire space using uniform grid into equal cells first, known as the first layer cells, and then divides the first layer cells using secondary gird partitioning according to the number of moving objects in the first layer cells. At the same time, thesis of how to choose the grid size for each layer was studied. Index structure needs to change continuously for adapting the change of moving objects distribution. This makes the maintenance of index structure cost too much. For the sake of reducing the cost, this paper presents a lazy update strategy.Experimental results show that DGB tree for the non-uniform moving objects have a good adaptability, while have high search efficiency.