度量空间索引支撑点选择问题研究

摘要

大数据的几个特性中，关于数据多样性的研究较少。度量空间数据管理分析方法把数据抽象成度量空间中的点，具有高度的通用性，是应对大数据多样性挑战的有效手段之一。由于度量空间没有坐标，一般以数据到参考点（也称支撑点）的距离作为坐标，从度量空间中选择一些支撑点，用它们来划分数据，递归地建立索引树。支撑点的好坏对索引性能有着关键性的影响。支撑点的选择，可以从目标函数和选择算法两个方面进行研究。目前，较为常用的目标函数为均值目标函数，较为常用的支撑点选择算法有FarthestFirstTraversal(FFT)和Incremental。均值目标函数笼统地将距离均值作为目标函数，没有考虑到查询半径对排除效果的影响。FFT算法很难选出最优的支撑点，Incremental算法存在局部最优的问题。
　　本文的研究内容主要有以下三个方面:
　　针对均值目标函数的不足，提出了半径敏感目标函数。半径敏感目标函数以距离大于查询半径的数据对的个数作为函数值，充分考虑了查询半径对排除效果的影响。实验证明，半径敏感目标函数能够选出更好的支撑点，与索引性能具有更强的一致性。
　　针对FFT算法的不足，提出了RecentFarthestTraversal(RFT)算法。实验证明，RFT在选点速度和选点命中率上均优于FFT算法。同时，FFT具有按空间均匀抽样的特性，更适合用于数据的抽样。提出的PivotSetSelection(PSS)算法，有效避免了Incremental的局部最优问题。实验显示，以RFT选择候选集，以FFT选择评价集，PSS性能良好，索引构建代价大大降低。
　　探索支撑点对索引性能影响的理论上限。目前的支撑点选取方法在索引性能方面的差别不是很大，用复杂的数学工具以很高的构建计算代价选择的支撑点带来的索引性能提升往往相对较少，整个领域的研究处于一个性能瓶颈中。本文探究了支撑点选取性能可提升的空间，为后续的研究方向提供了参考。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 国内外研究概况

1．3 研究内容和组织结构

1．4 相关概念和实验数据

1．4．1 索引结构

1．4．2 索引性能的衡量标准

1．4．3 查询半径的确定标准

1．4．4 实验数据

1．5 本章小结

第2章 半径敏感目标函数

2．1 两个目标函数

2．1．1 均值目标函数

2．1．2 半径敏感目标函数

2．1．3 两个目标函数在小数据量上的比较

2．1．4 两个目标函数在大数据量上的比较

2．2 Incremental抽样优化

2．2．1 Incremental算法

2．2．2 Incremental抽样优化

2．3 本章小结

第3章 支撑点选择算法

3．1 RFT算法

3．1．1 FFT算法

3．1．2 RFT算法

3．1．3 比较FFT与RFT

3．2 PSS算法

3．2．1 PSS算法

3．2．2 索引构建代价大大降低

3．2．3 索引性能的提升

3．3 本章小结

第4章 支撑点选择的性能上限

4．1．1 基本算法设计

4．1．2 并行算法设计

4．1．3 实验数据及运行环境

4．2 实验结果

4．2．1 最优支撑点分布情况

4．2．2 最差支撑点分布情况

4．2．3 最优与最差支撑点的内在表现

4．2．4 支撑点性能的总体情况

4．3 各类算法的可提升空间

4．4 本章小结

第5章 总结与展望

5．1 总结

5．2 不足与展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果