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

基于道路分布的移动对象动态组合索引研究

作　者: 曾倩
导　师: 金敏；张忠怀
学　校: 湖南大学
专　业: 软件工程
关键词: PMR quad树 索引 道路网络 移动对象 数据更新 交通管理
分类号: TP311.13
类　型: 硕士论文
年　份: 2009年
下　载: 73次
引　用: 0次
阅　读: 论文下载
 

内容摘要


移动对象索引技术是移动对象管理中的核心内容,移动对象管理技术是支撑起移动对象数据库的基础。目前大多数移动对象建立的索引没有考虑移动对象运动受限的情况,而现实生活中,移动对象的运动往往限制在一定的拓扑网络中。本文针对基于路网的FNR树索引方法的不足,提出一种基于道路分布的移动对象动态组合索引方法,通过对其性能进行分析,表明此方法能有效地管理路网受限移动对象的历史轨迹信息和当前位置信息。通过对现有移动对象索引技术的分析与路网受限的移动对象应用需求的研究,提出基于道路分布的动态组合索引结构。本文提出的动态组合结构由PMR QUAD树、R树和HASH结构三层结构组成。采用了PMR QUAD树结构对移动对象的道路网络空间实行粗略的层分割,将整个索引空间划分成多级子索引空间,最底层的叶结点根据空间划分包含多条道路的路段,并一一对应一棵R树。R树管理着经过某一路段的所有移动对象的时间信息,随着时间信息的不断增长,R树中动态地插入时间段操作。HASH结构存储了每个移动对象的时空轨迹信息,它由HASH表和动态链表构成,HASH表中存储了移动对象的标识,每一个移动对象都指向一个链表结构,链表中的结点存放着按时间顺序存储的移动对象位置信息。在动态组合索引结构的基础上,还在PMR QUAD树的结点中采用路段连接指针,将属于同一条道路的路段与路段之间指针连接,实现全道路时空搜索。采用PMR QUAD树结点处祖先结点信息与路段指针信息,实现自中向下的动态更新算法。本文采用了T Brinkhoff的基于路网的移动对象数据产生器和真实的道路网络图,产生道路移动对象实验数据。通过对动态组合索引和FNR树索引方法在操作中的结点存取次数为性能参考,进行性能比较。结果表明,基于道路分布的移动对象动态组合索引在动态更新、窗口查询、特别是轨迹查询方面性能有提高。

全文目录


摘要  5-6
ABSTRACT  6-11
第1章 绪论  11-26
  1.1 移动数据库概述  11-14
    1.1.1 移动数据库  11
    1.1.2 移动数据库系统结构  11-12
    1.1.3 移动数据库的关键技术  12-14
  1.2 移动对象管理概述  14-18
    1.2.1 移动对象的特点  14-15
    1.2.2 移动对象数据库与空间数据库、时空数据库间的联系  15-16
    1.2.3 移动对象数据库应用系统典型体系结构  16-17
    1.2.4 移动对象管理的关键技术  17-18
  1.3 移动对象索引技术的国内外研究现状  18-22
  1.4 论文的主要研究内容  22-23
  1.5 研究意义  23-25
  1.6 论文的组织结构  25-26
第2章 路网模型与移动对象模型分析  26-34
  2.1 道路网络分析  26-28
  2.2 路网模型构成  28-30
  2.3 移动对象模型分析  30-33
  2.4 本章小结  33-34
第3章 基于道路分布的动态组合索引方法  34-46
  3.1 FNR 树索引方法  34-38
    3.1.1 FNR 树索引结构  34-36
    3.1.2 FNR 树索引结构的分析  36-38
  3.2 路网索引改进的原则  38
  3.3 动态组合索引方法  38-43
    3.3.1 PMR 四叉树  38-41
    3.3.2 动态组合索引模型  41-43
  3.4 动态组合索引的数据结构  43-45
  3.5 本章小结  45-46
第4章 动态组合索引结构的操作算法  46-56
  4.1 插入算法  46-50
    4.1.1 PMR QUAD 树的搜索算法  46-47
    4.1.2 R 树插入算法  47-48
    4.1.3 HASH 结构插入算法  48
    4.1.4 动态组合索引插入算法的执行过程  48-50
  4.2 更新算法  50-53
    4.2.1 更新策略  50-53
    4.2.2 更新算法执行过程  53
  4.3 查询算法  53-55
    4.3.1 道路查询  54
    4.3.2 轨迹查询  54
    4.3.3 窗口查询  54-55
  4.4 本章小结  55-56
第5章 实验评估与性能分析  56-60
  5.1 测试环境与测试数据介绍  56-57
  5.2 更新性能分析  57
  5.3 查询性能分析  57-59
  5.4 本章小结  59-60
总结与展望  60-62
  1. 本文完成的主要研究工作  60
  2. 本文的创新点  60-61
  3. 进一步的研究工作  61-62
参考文献  62-65
致谢  65-66
附录A 攻读学位期间所发表的论文  66

相似论文

  1. 支持XML数据查询的F&B索引结构的研究,TP311.13
  2. 大规模稀疏关系数据索引技术研究,TP311.132.3
  3. 面向动态文档集的大规模文本索引构建技术的研究,TP391.3
  4. 动态环境下移动对象导航系统相关技术的研究,TP301.6
  5. 面向海量邮件的检索系统研究与实现,TP393.098
  6. Bicluster数据分析软件设计与实现,TP311.52
  7. 网络搜索引擎的相关技术研究,G354
  8. 大理州公安局机动车和驾驶人属地化信息管理系统的设计与实现,TP311.52
  9. 虹膜识别算法的研究与实现,TP391.41
  10. 辽宁省交通管理部门预算管理制度改革的问题与对策研究,F506.72
  11. 基于SMP的内存数据库查询处理优化研究,TP311.13
  12. 数据空间下的索引策略研究,TP311.13
  13. 低成本RFID系统安全协议研究,TP391.44
  14. 存储系统中多维元数据索引的高效更新方法研究,TP333
  15. 基于P2P的空间矢量数据快速索引机制的研究,TP391.3
  16. 大规模图像检索中局部特征聚合与索引方法研究,TP391.3
  17. 基于熵的音乐声纹检索算法的研究与实现,TP391.3
  18. 在线备份系统中存储服务器的研究与实现,TP333
  19. 分布式搜索引擎索引安全及缓存策略研究,TP333
  20. 外包数据库模式下中文文档密文检索研究,TP391.3
  21. 构件垂直搜索引擎的关键技术研究,TP391.3

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机软件 > 程序设计、软件工程 > 程序设计 > 数据库理论与系统
© 2012 www.xueweilunwen.com