Research On Indexing Methods Of Moving Objects In Two-Dimensional Space

In recent years, the location-based services are combining the technique of wireless communication, Internet and spatio-temporal database, thus have been becoming a unique and promising new field. Indexing technique of moving objects is a pivotal tache, which is in charge of managing real time information of moving objects and providing relational queries. Therefore, the indexing technique plays an important role in many application fileds such as intelligent navigation and weather monitoring.This paper gives in-depth studies on the existing indexing methods and query techniques, and then proposes a new indexing structure for current and future positions of moving objects.Firstly, the limitation of the traditional Hilbert space-filling curve is analyzed based on which a dynamic Hilbert curve is proposed. In allusion to the different distribution of moving objects in the indexingt area, the whole area is partitioned and each subregion is filled with the curve of different orders. The indispensable conditions and update process about how to change the curve orders along with the moving objects'updates are reasonedly elaborated in this paper.Secondly, using the dynamic Hilbert curve, time-partitioned technology, and the assistant Hash table, the Self-Adapt B~X-tree is further presented which supports predicted range query. In this thesis the construction principle and update algorithm of the SAB~X-tree are expounded in detail.Then, in order to optimize the range query, this paper develops three efficiently-increasing algorithms which are OriginalExpand algorithm, IterativeExpand algorithm and the OptimalExpand algorithm. The expansion methods are introduced respectively and an example is validated. It is the conclusive evidence that the OptimalExpand algorithm can further precisely restrict the query window to the verge of the real query results by expanding each cell of indexing area.Finally, due to the above achievements, the experiments we do validate the dynamic update and query performance of the SAB~X-tree.