基于区域覆盖的移动对象索引及连续范围查询处理研究

作     者：陈贺 

作者单位：东北大学 

学位级别：硕士

导师姓名：王国仁

授予年度：2009年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：移动对象 空间索引 连续范围查询 区域覆盖 

摘      要：移动对象索引的效率是移动数据管理系统的核心问题。由于大量移动对象位置的频繁改变,导致基于移动对象位置的索引执行效率非常低下。如何降低移动对象位置改变而带来的索引结构频繁更新成为一个新的研究热点。本文主要针对这一问题,提出了基于区域覆盖的移动对象索引及近似连续范围查询算法。 首先,本文在对现有工作进行分析与总结的基础上,介绍了基于移动对象当前位置的数据模型,接着通过分析移动对象在路网中的移动规律,虽然移动对象的位置变化很频繁,但其大量频繁移动所覆盖的区域变化相对缓慢,结合空间多维索引结构的复合使用,提出了一种基于区域覆盖的移动对象索引结构虚拟网格四分树（VGQ）,通过索引移动对象所在区域而非移动对象本身来减少由于移动对象位置改变而引起的索引结构的更新,并对其基本思想、数据结构以及基本操作进行了详细描述,最后分析了操作的复杂度,理论上分析了VGQ索引结构能较好地处理索引频繁更新的问题。 其次,连续范围查询是移动对象管理中一个具有挑战性的查询类型,与传统范围查询只需要计算一次不同,它需要在一段时间内处于持续计算状态。本文在VGQ索引结构基础上通过在每个网格单元中加入监控链表,给出了近似连续范围查询算法。同时,在查询移动较慢时,考虑到移动对象位置改变前后两次查询结果存在交集,给出了增量查询优化算法;在查询范围较小时,考虑到采用自顶向下的剪枝过程增加了查树的开销,给出了自底向上查询优化算法。 最后,本文进行了实验对比与分析。实验结果表明,VGQ是一种稳定的索引结构,与网格文件相比,基于VGQ索引结构的连续范围查询算法在不显著降低查询性能的同时有效地提高了主存空间利用率。