Research On Moving Objects Indexing Methods In Moving Objects Databases

The rapid development in positioning technologies such as GPS and wireless communications enable new data management applications such as location-based services (LBS) and traffic management which store and manage continuously changing positions of moving objects. Traditional database management systems (DBMS) could not efficiently handle continuously changing data such as the dynamic position of moving objects. Moving Objects Databases (MOD) management systems is thus proposed to manage continuously changing positions data and support moving query.The index method of moving object is a difficult and hot point in the moving objects databases. Many new applications such as traffic management system and military management system produce a large number of data beyond our imagination. In order to improve query processing efficiency, spatio-temporal access methods should be developed. Index method of moving object is very important to reduce the search space and improve the respond speed. Currently, most indexing methods of moving objects are focused on the past position, or on the present and future one, and the indexing supporting querying the collection of past, present and future positions of moving objects is less studied. On the other hand, most existing work assumes that the movement of the objects is unconstrained on the Euclidean spaces. However, in the real world, objects move within spatially constrained networks, e.g. vehicles move in road networks. To address these issues, we have studied the following indexing and building methods:1. Moving object indexing method that supports partial history queryThe TPR*-tree is the most useful indexing method which index the current and future position of moving object through Time-Parameterized Rectangles. In the TPR*-tree, the partial history trajectory of objects which do not update at present is implicit and it can not be queried. In order to exploit the history trajectory in the TPR*-tree, the HTPR*-tree is proposed which not only support predictive queries but also partial history trajectory queries.2. Indexing method to support frequent updateBecause HTPR*-tree update procedures work in a top-down manner, one index traversal is needed to locate and delete the data item to be updated for each update. Then a separate index traversal is carried out to insert the new data item. Update performance is lower in HTPR*-tree using top-down manner with frequent updates condition. Motivate by the bottom-up strategy of R-tree, BU_HTPR*-tree (which is based on HTPR*-tree and supplemented by a hash index and two compact main memory summary structure) is shown to improve update and query performance. 3. Method for index-building of HTPR*-treeBecause the method for index-building of HTPR*-tree works in a top-down insertion, the index performance of HTPR*-tree is relatively lower. In order to improve it, four kinds of method for index-building are proposed. The most optimal one is the velocity histogram-based bottom-up bulk loading algorithm which works as follows. First, for the two dimensional velocity space, packing all moving points into tree nodes corresponds to partitioning this space into bounding rectangles. Then, the HBU builds the subtree of HTPR*-tree root in the bottom-up fashion. At the same time, lazy update is used in the insertion of HTPR*-tree. The records of moving objects are stored by using overflow bucket at root node level and the index of HTPR*-tree is inserted and updated with a batch, which decreases the cost of insertion maintenance.4. Indexing the Past, Present and Future Positions of Moving Objects on Fixed NetworksAim at moving objects on fixed network, we propose an novel indexing method named PPFN-tree to store past trajectories, present positions, and predict near future positions of moving objects. PPFN-tree is a hybrid indexing structure which consists of a 2D R*-tree which is built on polylines describing road sectors for managing the fixed networks, a set of TB-trees indexing objects’movement history trajectory along the polylines, and a set of HTPR*-tree indexing the position of moving objects after recent update. PPFN-tree can not only support past trajectory query, present position query, but also support future predictive query. According to the range query time, query in PPFN-tree can be implemented only in the TB-tree, or only in the HTPR*-tree, or both of them.