基于近期最远遍历的支撑点选择

• 作者: 李兴亮 毛睿
• 来源期刊: 南京大学学报（自然科学版）
• 学科: 工学
• 关键词: 度量空间 多样性 支撑点选择 大数据
• 年，卷（期）: 2017,（3）
• 所属期刊栏目: 硅基纳电子和光电子专栏
• 页码范围: 483-496
• 页数: 14页
• 分类号: TP311
• 字数: 10282字
• 语种: 中文
• DOI: 10.13232/j.cnki.jnju.2017.03.013

摘要

度量空间数据管理分析方法把数据抽象成度量空间中的点,具有高度的通用性,是应对大数据多样性挑战的有效手段之一.由于度量空间没有坐标,很多数学工具无法直接使用,一般以数据到参考点(也称作支撑点)的距离作为坐标.支撑点的好坏对于度量空间数据管理分析的性能发挥着关键性的影响.最远优先遍历(Farthest First Traversal,FFT)可以选出数据拐角的点,具有线性的时间复杂度和空间复杂度,是使用最广泛的支撑点选取算法之一.但是,实验表明最好的支撑点往往不是最拐角的点,故FFT很难选出最好的支撑点.提出近期最远遍历(Recent Farthest Traversal,RFT)算法,只以近期的几个支撑点来选择下一个支撑点,能够更快地选出性能更优的支撑点.同时,实验表明FFT还可以在数据内部均匀抽样.提出支撑点集合选择算法(Pivot Set Selection,PSS),可以一次性选出所有支撑点.以RFT选择候选集,以FFT选择评价集,选出支撑点并构建相似性索引,PSS使得索引构建代价大大降低,索引性能得到一定提升.实验表明,RFT选出好的支撑点的速度远快于FFT,准确率高于FFT,而FFT的抽样效果良好.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	毛睿	深圳大学计算机与软件学院广东省普及型高性能计算机重点实验室	18	81	5.0	8.0
2	李兴亮	中国科学技术大学计算机科学与技术学院	1	0	0.0	0.0