学位论文 > 优秀研究生学位论文题录展示

空间数据库中移动对象位置管理技术研究

作　者: 张恒飞
导　师: 王乘; 曾致远
学　校: 华中科技大学
专　业: 空间信息科学与技术
关键词: 移动对象数据库移动对象索引多域划分时间参数化多重近似 kNN查询
分类号: TP311.13
类　型: 博士论文
年　份: 2012年
下　载: 191次
引　用: 1次
阅　读: 论文下载

内容摘要

随着移动技术进步和移动应用深入生活,移动对象规模及由其产生的信息量急速增长,促使移动对象数据库迅猛发展。作为提升移动对象数据库查询效率的关键技术,移动对象索引结构及其相应算法的优劣直接影响到应用的性能表现。由于移动对象新特性使得传统数据库的索引结构不能被直接继承使用,新的移动对象索引结构不断被提出,大致可分为管理移动对象的过去信息历史信息索引和管理移动对象近期及未来信息的预测查询索引两大类别。但是,移动对象索引技术还没有达到可以进行大规模商用的程度,移动对象索引的性能还需要进一步提高。通过对移动对象的数据特性的研究,我们总结了移动对象管理的难点,结合前人的工作,提出了高效的索引结构和相关算法。首先,针对移动对象查询过程中出现的候选查询范围过大问题,提出了基于时间域、速度域和空间域的多域划分技术,其中时间域提供处理移动性的能力,速度域划分负责缩减候选查询范围,空间域划分结合空间填充曲线完成高维位置属性维化。多域划分使得每个划分对应的查询候选范围大幅减小,从而获得较小的移动对象候选集,减小了查询耗费。在多域划分的基础上,设计实现了移动点状对象索引MPB-tree。以该结构为平台,证明了多域划分的可行性和有效性,验证了对于多域划分的定性和定量推理,得到了关于最佳多域划分参数的计算方法。MPB-tree使用空间填充曲线结合空间域划分将高维移动对象一维化,其中空间填充曲线的秩对索引效率有直接影响。通过对查询过程中节点访问问题进行研究,推导出MPB-tree中空间填充曲线秩与多域划分参数之间的关系,设计了自适应的空间填充曲线秩,提出了以此为基础的自适应移动点状对象管理机制。其次,针对移动多边形对象形状不规则、拓扑和距离计算复杂度高的问题,提出使用基于时间参数化外包矩形和时间参数化多重内接圆的多重时间参数化近似表达来分别对移动多边形的内外边界进行拟合。多重时间参数化近似表达能够在索引的叶子节点入口中代替移动对象,参与更新与查询过程,完成组织和过滤任务。提出了基于多重时间参数化近似表达的M2TPR-tree及其相应算法,验证了多重时间参数化近似表达在拟合移动多边形对象方面的优势。多重时间参数化近似表达会引起叶子节点入口尺寸增大,引起索引高度的增长,导致索引结构性能退化。根据时间参数化多重内接圆不参与结构组织的特点,提出使用单独的哈希结构对其进行管理,在不影响查询性能的同时解决了索引退化问题。针对TPR*-tree周期性整体重建引起的服务不连续,采用时间域划分策略,以时间域上的多子树交替更新代替周期性整体重建,提高了索引结构的可用性。另外,本文还针对基于位置服务中最常见的kNN查询进行了特别的研究。在点状移动数据查询方面,提出了基于MPB-tree的半径迭代算法,利用多域划分的优势,提高了点状移动对象kNN查询的效率。移动多边形对象的kNN查询方面,提出基于多重时间参数化近似表达分支界限算法。通过研究移动点、TPBR和TPMultiEC之间的空间关系及距离计算,得到了基于TPBR和TPMultiEC的分支界限查询距离度量。通过低误差的距离度量,索引结构遍历过程中的剪枝效果得到大幅提升,查询过程中的节点访问数量明显下降。本文通过实验性研究,证实了以上理论的正确性和方法的高效性,并通过大量序列对比实验,初步掌握了这些结构和方法的性能规律,为实用推广和更深层次的研究奠定了良好的基础。

全文目录

摘要  4-6
Abstract  6-10
1 绪论  10-26
  1.1 研究背景  10-12
  1.2 国内外研究现状  12-23
  1.3 研究目的与内容  23-24
  1.4 课题来源  24
  1.5 章节安排  24-26
2 移动对象位置管理基础  26-36
  2.1 空间及移动数据特性  26-28
  2.2 空间对象类型  28
  2.3 空间对象近似表达  28-29
  2.4 移动对象模型  29-31
  2.5 两段式查询策略  31-33
  2.6 查询类型及定义  33-35
  2.7 本章小结  35-36
3 移动点状对象索引及其查询  36-65
  3.1 多域划分技术  36-42
  3.2 MPB-tree的结构  42-43
  3.3 更新算法  43-47
  3.4 范围查询算法  47-50
  3.5 理论分析  50-57
  3.6 实验及结果分析  57-64
  3.7 本章小结  64-65
4 移动多边形对象索引及其查询  65-94
  4.1 TPR~*-tree的分支选择策略  65-68
  4.2 多重近似技术  68-74
  4.3 M~2TPR-tree结构  74-81
  4.4 范围查询  81-84
  4.5 实验结果及分析  84-92
  4.6 本章小结  92-94
5 移动对象的kNN查询  94-111
  5.1 分支界限算法  94-96
  5.2 基于M~2TPR的距离度量  96-101
  5.3 基于多重时间参数化近似表达的分支界限算法  101-103
  5.4 移动点状对象的kNN算法  103
  5.5 算法性能分析  103-110
  5.6 本章小结  110-111
6 总结与展望  111-113
  6.1 论文总结  111-112
  6.2 未来工作展望  112-113
致谢  113-114
附录1 攻读学位期间发表的论文目录  114-115
附录2 攻读学位期间参加项目情况  115-116
参考文献  116-125

空间数据库中移动对象位置管理技术研究

内容摘要

全文目录

相似论文