基于半度量路网的高效查询算法

摘要

空间数据库已成为数据库领域中的热点研究方向，路网作为空间数据库领域中重要的一部分，目前在各个地图服务、商用在线导航系统以及基于位置的查询应用软件中有着广泛的应用，路网中的查询得到了越来越广泛的关注。由于路网具有道路数量多、密度大、交叉频繁、路况复杂等特性，如何在路网中高效的查询至关重要。
　　路网中利用网络距离作为距离的度量方式，广泛存在不满足三角不等式关系的情况，称这样的路网为半度量路网。由于半度量路网不满足三角不等式关系，常见的度量空间中的索引结构无法有效工作，目前已提出的预计算的方法存在查询速度慢、计算代价慢的问题，如何在半度量路网中高效的查询是本文的研究重点和难点。
　　为了解决半度量路网中的查询速度慢、计算代价大的问题，本文提出了半度量路网中的高效查询方法。首先，由于直接在半度量路网中查询代价大，本文提出了两种方法将半度量路网转化为度量路网来降低查询代价。一种方法为随机删除边算法将半度量路网转化为度量路网，该方法简单，容易实现，但转化过程中信息损失比较大。为了进一步降低查询代价，以最小化的信息损失将半度量路网转化为度量路网，这是一个NP-hard问题，因此本文提出了另一种启发式的排序删除边算法以近似最小化的信息损失完成度量化。其次，提出了QM-树索引结构，在查询中利用三角不等式关系剪枝不可能包含查询结果的子树，有效的减少了查询时间。最后，本文提出了半度量路网中的范围查询方法以及K近邻查询方法。这两种查询方法都包括查询和验证两部分，查询部分利用三角不等式关系来剪枝不可能为查询结果的子树，快速的找出查询结果，有效的加速查询;验证部分对找到的查询结果节点和查询点中指针指向的包含信息损失的链表中的元素分别进行验证，有效的保证了查询的正确性。
　　最后，本文在真实的数据集上进行了大量的测试研究，通过对实验结果的分析与总结，证明了排序删除边算法能够以近似最小化的信息损失将半度量路网转化为度量路网;基于QM-树索引结构的半度量路网中的范围查询算法以及K近邻查询算法有效的降低了查询代价并保证了查询结果的准确性。

目录

声明

摘要

第1章 引言

1．1 研究背景

1．2 本文的研究内容及面临的挑战

1．3 本文贡献

1．4 本文的组织结构

第2章 相关工作

2．1 基于欧式距离的查询方法

2．2 路网中基于网络距离的查询方法

2．2．1 增量网络扩展方法

2．2．2 基于预计算的Voronoi的网络最近邻方法

2．2．3 预计算与网络扩展结合方法

2．3 半度量空间到度量空间的转化方法

2．3．1 距离映射技术

2．3．2 聚类技术

2．3．3 空间植入技术

2．4 本章小结

第3章 背景知识和问题定义

3．1 相关定义

3．2 问题定义

3．3 M-树索引结构

3．3．1 M-树结构

3．3．2 基于M-树的查询算法

3．4 本章小结

第4章 半度量路网到度量路网的转化方法

4．1 相关定义及结构描述

4．1．1 相关定义

4．1．2 结构描述

4．2 度量化策略

4．2．1 随机删除边策略

4．2．2 排序删除边策略

4．3 本章小结

第5章 基于转化后的度量路网的查询

5．1 QM-树索引的数据结构

5．2 半度量路网中的查询处理

5．2．1 半度量路网中的范围查询处理

5．2．2 半度量路网中的K近邻查询处理

5．3 QM-树的构造

5．4 利用QM-树的查询举例

5．5 本章小结

第6章 实验与分析

6．1 实验设置与数据集

6．2 半度量路网到度量路网的转化方法性能对比及分析

6．3 基于半度量路网高效查询方法性能对比及分析

6．3．1 范围查询算法的性能分析

6．3．2 K近邻查询算法的性能分析

6．3．3 QM-树索引结构的性能分析

6．4 本章小结

第7章 结束语

7．1 本文总结

7．2 工作展望

参考文献

致谢

攻硕期间发表论文、参加项目及获奖情况