Research On Location Management For Moving Objects In Spatial Database

With mobile technology deepening and applications developing, quantity of moving objects is increasing explosively, which impels development of moving objects database (MOD). As critical technology of MOD, moving objects indexing structure and its accessory algorithms affect performance of applications directly. Since traditional indexing structures cannot be transplanted into MOD straightforward as characteristics of moving objects, large amount of novel indexing structures have been presenting continuously, which have been classified into two categories named as historical index and predictive index respectively. However, moving object index technology needs further performance improving to come into large-scale business applications. Through studying characteristics of moving objects, two efficient indexing structures and accessory algorithms for moving objects management are proposed based on previous works.Firstly, multi-domains partitioning is presented to reduce excessive enlargement of query window caused by location changing of moving object follow time. Size of candidate-results set is decreased with multi-domains partitioning, which cuts down disk I/O number and CPU time cost of queries. Based on multi-domains partitioning, MPB-tree, an indexing structure for moving point objects, is designed and implemented. Space-filling curve is used to map moving objects into one dimensional data, whose order is critical to space-partitioning structure. Considering theoretical analysis, computational methods for optimized partitioning parameters and space-filling curve order are derived. Then, self-tuning space-filling curve order is designed with its computational method to enhance adaptability of MPB-tree. Through extensive experimental studies implemented on MPB-tree, efficiency of multi-domains partitioning and self-tuning space-filling curve order is verified.Secondly, aiming at irregular shape and high computing complexity on distance and topological relationship of moving polygon objects, multiple time-parameterized approximations (MTPA) is presented to describe a moving object approximately. MTPA is preserved in leaf node entry and involved into updating and querying algorithm instead of moving object. M2TPR-tree is presented based on TPR*-tree with MTPA and certify that MTPA has remarkable advantage on fitting moving polygon object. MTPAs will incur size increment of leaf node entries, and then increase height of M2TPR-tree, and cause performance degradation finally. It is observed that interior approximations are not involved in organization of moving objects, so an individual hash table is designed to preserve them, which can prevent performance degradation without extra space and time cost.Additionally, we conduct specific study on kNN query which is the most important query type in location-based service. MPB-tree based radius iterative algorithm is adopted for kNN query on moving point object database. Advantage of multi-domain partitioning is utilized to improve efficiency of kNN query. For moving polygon objects, Multiple Time-Parameterized Approximation based Branch-and-Bound (MTPABB) algorithm is presented with more accurate distance metrics. As a result, effect of branch pruning is enhanced and node visiting quantity is reduced dramatically by MTPABB algorithm.Extensive experimental studies are conducted to verify theories and methods proposed in this thesis. Meanwhile, performance characteristics of these structures and algorithms are discussed and summarized, which provides a well foundation for further researches and applications.