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

发布时间：2017-12-18 20:07

  本文关键词：度量空间索引支撑点选择问题研究

  更多相关文章： 多样性 度量空间 支撑点选择 半径敏感目标函数 RFT算法 PSS算法 理论上限

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

【参考文献】

中国期刊全文数据库 前1条

1 王国仁;黄健美;王斌;韩东红;乔百友;于戈;;基于最大间隙空间映射的高维数据索引技术[J];软件学报;2007年06期

，

本文编号：1305440