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

路网中基于RQN树的移动对象索引与查询

作　者: 张彦满
导　师: 余建桥
学　校: 西南大学
专　业: 计算机软件与理论
关键词: RQN树路网移动对象索引结构
分类号: TP311.13
类　型: 硕士论文
年　份: 2011年
下　载: 32次
引　用: 0次
阅　读: 论文下载

内容摘要

移动对象数据库技术是计算机科学的新兴研究领域,主要用来管理随时间连续变化的移动对象,有着广泛的应用需求。随着计算机网络、无线定位等技术的快速发展,移动信息服务越来越受到用户青睐。为了有效管理移动对象数据库中随着时间不断积累的海量数据,移动对象索引技术应运而生,它能够在保证索引更新性能的前提下,有效地对移动对象进行管理、查询以满足实际应用的需求,移动对象索引技术是移动对象数据库领域的核心内容。目前针对移动对象建立的索引大多考虑移动对象在欧氏自由空间中运动,而现实生活中,移动对象的运动往往被限制在一定的拓扑网络(即路网)中,如汽车行驶在公路网中。通过对现有移动对象索引技术与现实应用需求的研究,深入分析了建立路网索引的基本要求,在R树和QUAD树的基础上提出更加适合索引路网的RQN树。结合R树森林和HASH结构提出路网中基于RQN树的移动对象索引方法。RQN树根据路段分布情况把路网空间划分成多级子索引空间,叶子结点存储实际路段信息,每个叶子结点包含若干条数据记录,每一条记录存储一条路段,每条路段对应一棵R树；R树对该路段中的移动对象依据时间段建立索引,随着时间的不断积累,在R树中动态地插入数据记录；HASH结构由HASH表和单向动态链表构成,按时间顺序把每个移动对象被时间区间分割的时空轨迹连接起来,HASH表的结点存储移动对象标识符,每一个结点都指向一个动态链表,链表中的结点按时间顺序存放着移动对象轨迹的地址信息。使用T Brinkhoff的移动对象数据生成器,通过加载真实的交通路网图,产生路网和移动对象实验数据集进行模拟实验。以索引更新和查询中的结点访问次数为性能参考,对基于RQN树的移动对象索引方法同动态组合索引方法进行性能比较。结果表明：基于RQN树的移动对象索引方法提高了索引的稳定性和可调整性,同时,道路查询、窗口查询方面性能有所提高。

全文目录

摘要  6-7
Abstract  7-8
第1章绪论  8-13
  1.1 研究背景及意义  8-9
    1.1.1 研究背景  8
    1.1.2 研究意义  8-9
  1.2 国内外研究现状  9-11
    1.2.1 移动对象数据库国内外研究现状  9-10
    1.2.2 移动对象索引国内外研究现状  10-11
  1.3 研究的内容及目标  11-12
  1.4 本文的组织  12-13
第2章移动对象数据库技术  13-26
  2.1 移动对象数据库的产生  13
  2.2 移动对象及其特点  13-15
    2.2.1 移动对象概述  13
    2.2.2 路网中移动对象空间维特点  13-14
    2.2.3 路网中移动对象时问维特点  14-15
  2.3 路网模型和移动对象模型  15-18
    2.3.1 路网模型  15-17
    2.3.2 移动对象模型  17-18
  2.4 移动对象数据库索引技术  18-23
    2.4.1 R树  18-19
    2.4.2 四叉树  19
    2.4.3 散列表  19
    2.4.4 移动对象数据库索引分类  19-20
    2.4.5 几种经典的移动对象索引  20-23
  2.5 移动对象数据库查询  23-25
    2.5.1 常用时空查询  23-24
    2.5.2 时空查询特点  24-25
  2.6 小结  25-26
第3章路网中基于RQN树的移动对象索引结构  26-34
  3.1 建立路网索引的要求分析  26-27
  3.2 索引路网的RQN树  27-30
    3.2.1 RQN树定义  27
    3.2.2 RQN树的有效性分析  27-28
    3.2.3 RQN树索引路网的分析  28-30
  3.3 路网中基于RQN树的移动对象索引方法  30-32
  3.4 基于RQN树的移动对象索引数据结构  32-33
  3.5 小结  33-34
第4章基于RQN树的移动对象索引操作算法  34-42
  4.1 RQN树操作算法  34-36
    4.1.1 RQN树生成算法  34-35
    4.1.2 RQN树结点插入算法  35-36
    4.1.3 RQN树搜索算法  36
  4.2 移动对象插入算法  36-38
    4.2.1 R树插入算法  36-37
    4.2.3 HASH结构插入算法  37-38
  4.3 更新算法  38
  4.4 查询算法  38-41
    4.4.1 道路查询  38-39
    4.4.2 轨迹查询  39
    4.4.3 窗口查询  39-40
    4.4.4 交通堵塞查询  40-41
  4.5 小结  41-42
第5章实验与性能分析  42-47
  5.1 实验方案  42
  5.2 实验环境与实验数据  42-44
  5.3 实验结果与性能分析  44-46
  5.4 小结  46-47
第6章结束语  47-49
  6.1 完成的主要研究内容  47
  6.2 本文的创意  47
  6.3 未来工作  47-49
参考文献  49-52
致谢  52-53
作者在学习期间取得的学术成果  53

路网中基于RQN树的移动对象索引与查询

内容摘要

全文目录

相似论文