基于时空数据库的移动对象索引技术研究与实现

摘要

时空数据库技术是计算机科学的新兴领域，用来存储和管理空间位置或空间范围随着时间变化的时空对象。随着移动通信、无线定位等技术的迅速发展，移动信息服务受到越来越多地关注，因此，追踪移动对象位置变得可行和必需。为了有效管理时空数据库中的海量数据，移动对象的索引技术应运而生，它能够有效地对移动对象进行查询、管理以及提供准确的基于位置的服务等，在时空数据库的研究中具有重要的意义。
　　 本文在介绍时空数据库技术和移动对象索引的基础上，对已有的移动对象索引技术进行了分类、比较，研究了离散情况下移动对象索引模式的特点，并着重对Kwon等人的LUR-tree进行了分析。LUR-tree(Lazy Update R-tree)是基于R-tree的移动对象索引结构，在对象更新时采用懒惰更新算法，仅当对象移出相应MBR时才更新索引结构来减小更新代价，同时引入可扩展的MBR(EMBR)来减少更多的更新代价，但这种方法会使得内部结点重叠面积增大，导致查询效率的下降；LUR-tree只关心对象当前位置，一旦对象更新了位置，则删除该对象旧记录，插入新的记录，因此，对于最近时间段历史查询需求不能满足。
　　 本文对离散情况下移动对象索引进行改进，提出轨迹连续的空间存储技术，能够同时实现对象的空间及时间存储。并提出一种离散情况下的移动对象索引机制QLUR+-tree(Quad Lazy Update R+-tree)，可以索引对象历史及当前时刻位置信息，该索引是基于R+-tree与四叉树(Quadtree)的混合结构，使用R+-tree索引移动对象实时信息，四叉树采用轨迹连续空间存储技术，存储并索引移动对象历史信息。实时树的更新结合LUR-tree的懒惰更新并对其进行了改进，提出动态收缩与扩充MBR的更新策略。同时，引入辅助的索引结构，实现对象叶结点直接操作及信息过渡，并对实时树及历史树的插入、更新和查询算法进行了相应的改进。通过分析和实验证明，该索引结构在保持较低的更新代价和磁盘开销的同时，对整个空间的点查询和域查询等具有很高的查询效率。

目录

文摘

英文文摘

声明

第一章 绪论

1.1 研究背景

1.2 国内外研究现状

1.2.1 时空数据库国内外研究现状

1.2.2 移动对象索引研究现状

1.3 研究内容与目标

1.4 本文结构

第二章 时空数据库技术

2.1 时空数据库概述

2.2 时空数据的特点

2.2.1 时空数据的时间维特点

2.2.2 时空数据的空间属性

2.3 时空数据模型的分类

2.3.1 基于时间的时空数据模型

2.3.2 基于事件的时空模型

2.3.3 面向对象的时空模型

2.4 时空数据的索引

2.4.1 基于R-tree索引

2.4.2 基于Quadtree索引

2.5 时空数据的查询

2.6 本章小结

第三章 离散的移动对象索引技术

3.1 移动对象数据的离散表示

3.2 对时间维的处理

3.3 离散的移动对象索引改进

3.3.1 轨迹连续的空间存储技术

3.3.2 对象当前及历史信息索引结构

3.4 本章小结

第四章 动态的QLUR+-TREE索引机制

4.1 QLUR+-tree索引的建立

4.1.1 数据结构

4.1.2 懒惰更新算法

4.1.3 辅助索引

4.2 QLUR+-tree的优化

4.2.1 动态更新策略

4.2.2 对象的插入

4.3 QLUR+-tree的操作

4.3.1 更新算法

4.3.2 查询算法

4.4 本章小结

第五章 QLUR+-TREE的实现与性能分析

5.1 QLUR+-TREE的实现

5.2 实验数据集的生成

5.3 实验结果与性能分析

5.4 本章小结

第六章 结束语

6.1 结论

6.2 未来工作

参考文献

附录

致谢

攻读硕士学位期间发表的文章