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

TPR-树在基于位置服务系统中的应用研究

作　者: 金泽锋
导　师: 薛安荣
学　校: 江苏大学
专　业: 计算机应用技术
关键词: 时空数据库索引空间位置预测查询 R-树 TPR-树基于位置服务
分类号: TP311.13
类　型: 硕士论文
年　份: 2008年
下　载: 154次
引　用: 2次
阅　读: 论文下载

内容摘要

时空数据库技术是计算机科学的新兴领域。面对着海量的数据,如何在给定的空间及时间范围内实现对移动对象快速有效地查询,是实现定位服务、智能交通、数字化战争等诸多应用中迫切需要解决的问题。时空索引技术是解决上述问题的关键技术。TPR-树是一种可以对移动对象当前位置及未来位置进行有效索引的时空索引技术。TPR-树用TPBR(Time-Parameterized Bounding Rectangle)来近似表示对象,其基本算法和R~*-树类似。TPR-树不但支持对移动对象将来位置的预测查询,而且数据存储量和数据更新频率都相对较低。但TPR-树并没有得到广泛的应用,主要是因为其存在以下不足:对移动对象预测查询的精确度不高:TPBR之间的重叠随着时间的推移而越发严重,从而影响TPR-树的查询性能:算法的时间花费较高,不利于系统作出快速的响应。本文对TPR-树的性能优化进行了研究。首先介绍了时空索引技术研究方面的成果。接着,根据TPR-树的特性,设计一种可以实现实时查询以及预测查询的基于位置服务系统。然后分别从四个方面对TPR-树进行研究以及改进:(1)通过引入记录的生命期,过期记录(expired entries)不再被真正删除,只是简单记载过期的时刻,从而使TPR-树可以应答对移动对象历史信息的查询;(2)对TPR-树所索引的数据对象进行扩展,使得TPR-树可以管理更为一般的数据对象;(3)提出一种同时考虑移动对象的空间属性和速度属性的结点分裂算法,算法在投影定积分值最大的轴上进行分裂,并把某段时间内子结点周长的定积分作为代价函数,不但降低了算法的计算时间,而且使用此算法所建立的TPR-树的查询速度也得到了一定的提高;(4)一种可以限制TPBR之间无限重叠的基于距离的结构调整策略,该算法通过强制重插在某个方向上的移动距离超过阈值的移动对象所对应的记录,从而达到调整TPR-树整体结构的目的。实验表明,与原TPR-树结点分裂算法相比,改进后的结点分裂算法的计算时间降低了5～8倍,查询速度至少提高了50%:而且,在此基础上应用基于距离的结构调整策略使查询速度进一步提高约10%。

全文目录

摘要  5-6
ABSTRACT  6-9
第一章绪论  9-15
  1.1 研究背景  9-12
  1.2 研究内容与目标  12-13
  1.3 论文组织结构  13-15
第二章时空索引技术  15-30
  2.1 时空索引技术概述  15-17
  2.2 基于离散数据表示的时空索引  17-19
    2.2.1 3DR-树  17-18
    2.2.2 RT-树  18
    2.2.3 HR-树  18-19
  2.3 基于连续数据表示的时空索引  19-29
    2.3.1 TPR-树  19-26
    2.3.2 FNR-树  26-28
    2.3.3 PMR-四叉树  28-29
    2.3.4 Q+R树  29
  2.4 本章小节  29-30
第三章 LBS系统的设计  30-38
  3.1 LBS概述  30-31
  3.2 基于手机平台的位置服务  31
  3.3 LBS的关键技术  31-35
    3.3.1 空间定位技术  31-34
    3.3.2 地理信息系统  34-35
    3.3.3 空间数据库技术  35
  3.4 基于手机平台的位置服务系统的设计  35-37
  3.5 本章小结  37-38
第四章 TPR-树的性能优化研究  38-68
  4.1 TPR-树的改进之路  38-45
    4.1.1 R~(EXP)-tree  38-39
    4.1.2 TPR*-树  39-44
    4.1.3 MVTPR-树  44-45
  4.2 TPR-树对历史数据的索引  45-49
    4.2.1 引入TPR-树记录的生命期  46
    4.2.2 记录的逻辑删除  46-48
    4.2.3 历史数据的精度修正  48-49
  4.3 TPR-树索引对象的扩展  49-54
    4.3.1 索引对象的分类  49-50
    4.3.2 扩展TPR-树的索引对象  50-52
    4.3.3 扩展索引对象后TPR-树的性能分析  52-54
  4.4 TPR-树结点分裂算法的改进  54-62
    4.4.1 R*树结点分裂算法的讨论  54-57
    4.4.2 TPR-树结点分裂算法的讨论  57-61
    4.4.3 改进的TPR-树结点分裂算法  61-62
  4.5 结构调整策略  62-67
    4.5.1 关于TPBRs之间重叠的分析  63-65
    4.5.2 基于距离的结构调整策略  65-67
    4.5.3 基于距离的结构调整策略的性能分析  67
  4.6 本章小结  67-68
第五章 TPR-树的实验与分析  68-72
  5.1 实验环境与参数设置  68
  5.2 实验结果与分析  68-71
  5.3 本章小结  71-72
第六章 LBS原型系统的架构  72-85
  6.1 LBS原型系统构造  72-80
    6.1.1 GPS定位系统  72-73
    6.1.2 客户端模块  73-74
    6.1.3 LBS服务器端模块  74-75
    6.1.4 LBS信息数据库  75-76
    6.1.5 基于TPR-树索引的时空数据库  76-78
    6.1.6 GIS系统平台  78-79
    6.1.7 有线和无线通信模块  79-80
  6.2 LBS系统的软件体系架构  80-83
    6.2.1 C/S结构  81
    6.2.2 B/S结构  81-82
    6.2.3 LBS系统的软件架构设计  82-83
  6.3 LBS系统的功能  83-84
  6.4 本章小节  84-85
第七章总结与展望  85-87
  7.1 主要研究工作  85
  7.2 主要贡献  85-86
  7.3 未来方向  86-87
致谢  87-88
参考文献  88-90
攻读硕士学位期间发表的学术论文  90

TPR-树在基于位置服务系统中的应用研究

内容摘要

全文目录

相似论文