空间数据的聚集最远邻居查询研究

摘要

在这篇文章中，研究一种新型的空间查询，叫做聚集k最远邻居查询(简称AkFN Query)。给定一个数据点集P和一个查询点集Q，AkFN查询返回P里面离Q中所有点的聚集距离最大的k个点。例如，要在一个城市里新开一间旅馆，希望选一个地点到所有现有的旅馆聚集距离最大，以此最大限度的降低竞争。
　　 主要讨论三种聚集函数，和(Sum)、最大值(Max)和最小值(Min)。假设数据集是R树索引的，针对查询集为内存存储时，提出了两个高效解决所有三种AkFN查询的算法，最小界定(简称MB)算法和最好优先(简称BF)算法。其中BF算法是增量式的，而且可以证明是IO开销最优的算法。另外，提出一种基于凸包(简称CHB)的算法来解决聚集函数为Sum和Max的情况，它利用到了数据集的凸包。另外，对于查询集很大为磁盘存储时，对以上三种算法进行扩展分别提出了磁盘最小界定(简称DMB)算法、磁盘最好优先(简称DBF)算法和磁盘基于凸包(简称DCHB)的算法。
　　 在合成数据集和真实数据集上的大量实验表明，这些算法不仅高效而且有效。其中BF算法在几乎所有情形下都是最优的。

目录

文摘

英文文摘

图目录

表目录

第1章 绪论

1.1 研究背景及意义

1.2 本文工作及贡献

1.3 本文组织

第2章 相关工作

2.1 R树

2.2 空间填充曲线

2.3 在R树上的kNN查询算法

2.3.1 DF-kNN算法

2.3.2 BF-kNN算法

2.4 聚集最近邻居查询

2.5 最远邻居查询

2.6 用R树动态维护凸包

2.7 本章小结

第3章 问题定义和距离度量

3.1 聚集距离

3.2 聚集k最远邻居查询

3.3 最大距离

3.4 最大聚集距离

3.5 本文符号

3.6 本章小结

第4章 AkFN查询处理

4.1 最小界定算法

4.2 最好优先算法

4.2.1 计算MaxAsumDist和MaxAmaxDist

4.2.2 计算MaxAminDist

4.2.3 主算法优化及IO最优证明

4.3 基于凸包的算法

4.4 AkFN查询处理算法讨论

4.5 本章小结

第5章 磁盘存储查询集的AkFN查询处理

5.1 磁盘最小界定算法

5.2 磁盘最好优先算法

5.2.1 延迟计算技术处理Sum和Max函数

5.2.2 最好优先算法对Min函数不可解

5.3 磁盘基于凸包的算法

5.4 磁盘存储查询集的AkFN查询处理算法讨论

5.5 本章小结

第6章 实验结果

6.1 实验环境

6.2 实验设计和衡量方法

6.3 实验结果与分析

6.3.1 结果集大小k的影响

6.3.2 查询集大小m的影响

6.3.3 数据集大小n的影响

6.4 本章小结

第7章 总结与展望

7.1 本文工作

7.2 本文贡献

7.3 未来展望

参考文献

攻读硕士学位期间主要的研究成果

致谢