文献类型：会议

作　　者：韩希先 杨东华 李建中

作者单位：[1]哈尔滨工业大学计算机科学与技术学院 [2]哈尔滨工业大学基础与交叉科学研究院高性能计算中心

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

会议文献：NDBC2010第27届中国数据库学术会议论文集A辑一

会议名称：NDBC2010第27届中国数据库学术会议

会议日期：20101013

会议地点：中国北京

主办单位：中国计算机学会数据库专业委员会

出版单位：科学出版社(SciencePress)

出版日期：20100800

学会名称：中国计算机学会数据库专业委员会

语　　种：中文

摘　　要：在许多应用领域中,top-k查询是一种十分重要的操作,它根据给定的评分函数在潜在的巨大的数据空间中返回k个最重要的对象.不同于传统的TA算法,NRA算法只需要顺序读就可以处理top-k查询,从而适合于随机读受限或不可能的场合.文中详细地分析了NRA算法的执行行为,确定了增长阶段和收缩阶段中每个文件需要扫描的元组个数.文中发现在海量数据环境中,NRA在增长阶段需要维护大量的候选元组,严重影响了算法的执行效率.所以,文中提出一种新的海量数据上的top-k查询算法TKEP,该算法在查询的增长阶段就执行早剪切,从而大大减少增长阶段需要维护的候选元组.文中给出了早剪切操作的数学分析,确定了早剪切操作的理论和实际剪切效果.据作者所知,该文是第一篇提出在top-k查询的增长阶段执行早剪切的文章.实验结果表明,和传统的NRA相比,TKEP在增长阶段维护的元组数量减少3个数量级,需要的内存量减少1个数量级,TKEP算法获得1个数量级的加速比.

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

分 类 号：TP311.13]