TKEP:海量数据上一种有效的Top-K查询处理算法  

TKEP:An Efficient Top-K Query Processing Algorithm on Massive Data

作　　者：韩希先[1] 杨东华[2] 李建中[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001 [2]哈尔滨工业大学基础与交叉科学研究院高性能计算中心,哈尔滨150001

出　　处：《计算机学报》2010年第8期1405-1417,共13页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2006CB303005);国家自然科学基金(60903016;60533110;60773063);新世纪优秀人才支持计划(NCET-05-0333);黑龙江省教育厅科学技术研究项目(11531276);NSFC-RGC of China(60831160525)资助~~

摘　　要：在许多应用领域中,top-k查询是一种十分重要的操作,它根据给定的评分函数在潜在的巨大的数据空间中返回k个最重要的对象.不同于传统的TA算法,NRA算法只需要顺序读就可以处理top-k查询,从而适合于随机读受限或不可能的场合.文中详细地分析了NRA算法的执行行为,确定了增长阶段和收缩阶段中每个文件需要扫描的元组个数.文中发现在海量数据环境中,NRA在增长阶段需要维护大量的候选元组,严重影响了算法的执行效率.所以,文中提出一种新的海量数据上的top-k查询算法TKEP,该算法在查询的增长阶段就执行早剪切,从而大大减少增长阶段需要维护的候选元组.文中给出了早剪切操作的数学分析,确定了早剪切操作的理论和实际剪切效果.据作者所知,该文是第一篇提出在top-k查询的增长阶段执行早剪切的文章.实验结果表明,和传统的NRA相比,TKEP在增长阶段维护的元组数量减少3个数量级,需要的内存量减少1个数量级,TKEP算法获得1个数量级的加速比.In many application fields,top-k is an important operation since it returns k most important objects according to a given ranking function.Different from traditional TA algorithms,NRA only requires sequential access to return top-k results so that it can be used in environment where random access is limited or impossible.This paper analyzes the execution behavior of NRA and determines tuple number to scan in increasing and shrinking phase.It is found that in massive data context,NRA needs to maintain large quantity of candidate tuples in increasing phase which affects algorithm efficiency significantly.This paper proposes a novel top-k algorithm TKEP（Top-K with Early Pruning） on massive data which performs early pruning in increasing phase to prune most of candidate tuples.This paper provides mathematical analysis of early pruning and proves its theoretical and practical pruning effect.To the best of our knowledge,it is the first paper to provide early pruning in top-k processing.The extensive experiments show that compared to NRA,TKEP maintains less tuples by a factor of three orders of magnitude,it consumes less memory by a factor of an order of magnitude and TKEP achieves substantial performance speed-up of an order of magnitude.

关 键 词：海量数据 TOP-K 早剪切 TKEP 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]