移动点对象Hash-R索引及反向最近邻查询

摘要

移动对象是目前广泛研究的—个分支，本文主要研究移动点对象，针对时空数据库中移动点对象的索引结构及查询技术两方面做了重点介绍，因为它们在日常生活中应用较广泛，而且具有很深的研究价值。
　　 本文针对索引结构所做的工作主要有：第一，从基于离散数据表示的索引结构和基于连续数据表示的索引结构两方面详细介绍了几种时空数据库索引技术；第二，在R树基础上提出了Hash-R树索引结构，对所提出的索引结构分析了构建、插入及删除思想，设计了构建算法、插入算法及删除算法；第三，在Hash-R树索引结构中引入了两个分别建于叶结点和根结点之上的Hash辅助索引结构来提高更新及查询操作性能；第四，在创建算法中引入聚类算法，提高了索引结构的质量。
　　 本研究针对查询所做的工作主要有：第一，从不同角度对移动对象的查询方法进行了分类，并澄清了各自的概念；第二，提出了一种针对移动对象Hash-R索引结构的动态反向最近邻查询，在算法中引入时间戳概念，分三种情况进行向前窗口扩展或向后窗口扩展，把时间范围缩小得到窗口范围，从而达到预先剪除超出一定生命期的对象信息，提高查询效率；第三，抓住反向最近邻查询的定义，通过一个验证结果集的正确性与否算法来验证所提出的反向最近邻算法的正确性、有效性、可分析性和可读性；第四，通过实验验证了反向最近邻算法的可伸缩性及I/O更新代价，并对比分析了Hash-R树和TPR树的查询效率和磁盘访问次数。

目录

文摘

英文文摘

第1章 绪论

1.1 本课题研究背景

1.2 国内外研究现状

1.2.1 移动对象索引结构的研究

1.2.2 移动对象近邻查询技术的研究

1.3 课题来源、主要研究内容及创新点

1.3.1 课题来源

1.3.2 主要研究内容

1.3.3 本课题的贡献及创新点

第2章 时空数据库及移动对象

2.1 空间数据库

2.2 空间数据

2.3 时空数据库

2.4 移动对象

2.5 本章小结

第3章 时空数据库索引结构

3.1 基于离散数据表示的索引结构

3.1.1 3DR-树索引

3.1.2 RT-树索引

3.1.3 HR-树(History R-树)索引

3.2 基于连续数据表示的索引结构

3.2.1 TPR-树索引

3.2.2 PMR-Quadtree索引

3.2.3 Q+R树索引

3.2.4 IMORS索引

3.3 移动点对象Hash-R索引结构

3.3.1 基于哈希的索引技术

3.3.2 聚类思想的引入

3.3.3 Hash-R索引结构

3.3.4 Hash-R索引的插入算法

3.3.5 Hash-R索引的删除算法

3.4 本章小结

第4章 移动对象查询技术

4.1 基于目标近似的空间查询介绍

4.2 查询分类介绍

4.3 查询优化

4.4 基于Hash-R索引结构的反向最近邻查询

4.4.1 算法实现

4.4.2 验证算法

4.5 本章小结

第5章 实验

5.1 引言

5.2 验证Hash-R索引结构的反向最近邻查询

5.2.1 实验设置

5.2.2 实验结果及分析

5.3 本章小结

总结

参考文献

攻读学位期间发表的学术论文

致谢