TKEP:海量数据上一种有效的Top-K查询处理算法
在许多应用领域中,top-k查询是一种十分重要的操作,它根据给定的评分函数在潜在的巨大的数据空间中返回k个最重要的对象.不同于传统的TA算法,NRA算法只需要顺序读就可以处理top-k查询,从而适合于随机读受限或不可能的场合.文中详细地分析了NRA算法的执行行为,确定了增长阶段和收缩阶段中每个文件需要扫描的元组个数.文中发现在海量数据环境中,NRA在增长阶段需要维护大量的候选元组,严重影响了算法的执行效率.所以,文中提出一种新的海量数据上的top-k查询算法TKEP,该算法在查询的增长阶段就执行早剪切,从而大大减少增长阶段需要维护的候选元组.文中给出了早剪切操作的数学分析,确定了早剪切操作的理论和实际剪切效果.据作者所知,该文是第一篇提出在top-k查询的增长阶段执行早剪切的文章.实验结果表明,和传统的NRA相比,TKEP在增长阶段维护的元组数量减少3个数量级,需要的内存量减少1个数量级,TKEP算法获得1个数量级的加速比.
海量数据、top-k、早剪切、TKEP
33
TP311(计算技术、计算机技术)
国家"九七三"重点基础研究发展规划项目基金2006CB303005;国家自然科学基金60903016, 60533110, 60773063;新世纪优秀人才支持计划NCET-05-0333;黑龙江省教育厅科学技术研究项目11531276;NSFC-RGC of China60831160525
2010-10-28（万方平台首次上网日期，不代表论文的发表时间）
共13页
1405-1417
