文献类型：期刊文章

作　　者：李兴亮[1] 毛睿[2]

机构地区：[1]中国科学技术大学计算机科学与技术学院,合肥230026 [2]深圳大学计算机与软件学院广东省普及型高性能计算机重点实验室,深圳518060

出　　处：《南京大学学报（自然科学版）》

基　　金：国家863项目(2015AA015305);国家自然科学基金(U1301252;61471243);广东省重点实验室项目(2012A061400024);深圳市基础研究项目(JCYJ20140418095735561;JCYJ20150731160834611;JCYJ20150625101524056);深港创新圈项目(SGLH20131010163759789);广东省教育厅项目(2015KQNCX143)

年　　份：2017

卷　　号：53

期　　号：3

起止页码：483-496

语　　种：中文

收录情况：BDHX、BDHX2014、CAS、CSCD、CSCD2017_2018、JST、MR、RCCSE、ZGKJHX、ZMATH、核心刊

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

关 键 词：度量空间 多样性 支撑点选择  大数据

分 类 号：TP311]