【作者】 张林；

【导师】 汤大权；

【作者基本信息】 国防科学技术大学 ， 管理科学与工程， 2009， 硕士

【摘要】 随着定位技术与无线通信技术的迅速发展,跟踪与定位移动对象成为可能,如何有效地对移动对象进行管理、查询及提供准确的基于位置的服务是移动对象数据库研究面临的挑战。移动对象信息管理在交通监测、舰船导航、移动计算、气象预测、电子战场等许多领域有着广泛的应用。移动对象索引技术具有重要的理论和实际意义。目前移动对象数据库的研究处于初步阶段,理论和实际应用上还不成熟,存在许多问题需要新技术来解决。移动对象索引技术得到了国内外研究者的广泛关注。对现有相关工作的分析与比较发现:越来越多的应用要求数据管理系统能够查询移动对象过去、现在和将来信息。为了满足统一查询的需求,提出了一种面向时态查询的索引结构FT树,支持全时态信息的查询,适应频繁更新的环境。本文首先综述了移动对象索引的演变与发展历史,全面地总结和对比分析了国内外移动对象索引的研究工作。然后提出了面向时态查询的索引结构FT树:将多版本思想引入TPR树中,对支持将来查询的TPR树进行了改进,有效地保存TPR树的各个版本,支持全时态查询;同时,引入重叠技术,避免了结点的复制,节省磁盘存储空间。为了适应频繁更新的环境,采用批量更新技术,有效地利用不同对象位置更新之间的空间相关性,降低了更新代价。引入一个二级索引结构,实现叶结点的直接存取。接着建立了代价模型和选择性估计的数学模型,从理论角度评价FT树的性能,模型的优点是只采用了树的基本属性和数据本身的特点,实验证实了模型有较高的准确率。最后采用实验方法评价FT树的性能,生成移动对象数据,以索引大小、查询性能及更新性能等指标与其它的索引结构进行比较。实验表明,FT树索引占用磁盘空间较小,磁盘利用率较高,时间片查询性能很好,时间段查询性能一般,更新性能有显著提高,在不同的数据集上表现稳定,从而验证了索引技术的有效性。更多还原

【Abstract】 With the rapid development of positioning and wireless communication technique, it is possible to track and position moving objects. What the challenge that moving object databases face is how to effectively manage and query moving objects and offer exact location based services. Managing moving objects’information is widely used in many fields, such as traffic monitoring, ship navigation, moving computing, weather forecasting, electronic battle, etc. Moving object indexing technique has vital theoretic and practical sense. It is immature and has many problems to solve.Researchers pay much attention to moving object index. Based on the analysis of existing work, there are increasing demands in data management systems to support querying the past, present and future information of moving objects. To satisfy the unified query demand, propose an index structure named FT-tree towards temporal query, which supports full temporal information query and is adaptive in frequently updating environment.Summarize and analyze the evolvement and progress of moving object indices. Then propose index towards temporal query. FT-tree introduces the multi-version idea into TPR-tree, effectively preserves each edition of TPR-tree and supports full temporal query, which introduces the overlapping technique, avoids node replication and saves disk storage. FT-tree adopts bulk-loading updating technique, which effectively uses the space relativity of various objects, reduces updating cost, and introduces a secondary index for directly reading and writing leaf nodes. Construct cost model and selectivity estimation for theoretic analysis. The model’s advantage is only using tree’s attribute and data’s property. Generate moving objects data and compare the FT-tree with other indices by index size, query and updating performance. Experiments show FT-tree’s validity. It occupies less disk space, uses higher disk space, has better timeslice query, but has common time interval query, remarkably enhances updating performance, and performs well on various data set.更多还原