【作者】 张辉；

【导师】 刘永山；

【作者基本信息】 燕山大学 ， 计算机应用技术， 2010， 硕士

【摘要】 位置服务技术与无线通信、Internet和时空数据库等技术相融合,形成了一个独具特色、前景无限的新兴产业。移动对象索引技术作为位置服务技术中的一个关键环节,负责管理移动对象的实时信息并提供相关查询,在智能导航、气象监控等应用领域发挥着至关重要的作用。本文对现有的移动对象索引结构、查询方法及相关技术进行了深入比较与分析,提出了一种支持移动对象未来信息查询的索引结构。首先,分析了传统Hilbert曲线技术存在的缺陷,在此基础上进行改进提出了动态Hilbert曲线,即针对移动对象在索引区域分布不均的情况,将整个索引区域进行划分,并用阶不同的多条曲线对每个子区域进行填充。给出了移动对象发生位置更新时曲线阶随之改变的前提条件及过程。其次,采用动态Hilbert曲线技术、时间划分技术并引入Hash辅助表,进一步提出了支持预测范围查询的自适应索引结构SAB~X树,并阐述了SAB~X树的构造原理及更新算法。再次,为实现范围查询,提出了查询效率逐步递增的基本扩展窗口算法、迭代扩展窗口算法和最优扩展窗口算法。文中对三种算法的扩展原理给出了详细描述和实例验证,证实了最优扩展算法可以将查询窗口的扩展范围限制到接近于真实的查询结果。最后,基于上述研究成果,本文通过实验对SAB~X树的存储消耗、动态更新性能、查询性能及三种扩展窗口的查询效率分别进行了验证。更多还原

【Abstract】 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.更多还原