| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | TKEP：海量数据上一种有效的Top-K查询处理算法 |
| 作者 | 韩希先1) 杨东华2) 李建中1) |
| 作者单位 | 1)(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001) 2)(哈尔滨工业大学基础与交叉科学研究院高性能计算中心 哈尔滨 150001) |
| 发表年份 | 2010 |
| 发表月份 | 8期(1405—1417) |
| 文章摘要 | 摘要 在许多应用领域中，top-k查询是一种十分重要的操作，它根据给定的评分函数在潜在的巨大的数据空间中返回k个最重要的对象.不同于传统的TA算法，NRA算法只需要顺序读就可以处理top-k查询，从而适合于随机读受限或不可能的场合.文中详细地分析了NRA算法的执行行为，确定了增长阶段和收缩阶段中每个文件需要扫描的元组个数.文中发现在海量数据环境中，NRA在增长阶段需要维护大量的候选元组，严重影响了算法的执行效率.所以，文中提出一种新的海量数据上的top-k查询算法TKEP，该算法在查询的增长阶段就执行早剪切，从而大大减少增长阶段需要维护的候选元组.文中给出了早剪切操作的数学分析，确定了早剪切操作的理论和实际剪切效果.据作者所知，该文是第一篇提出在top-k查询的增长阶段执行早剪切的文章.实验结果表明，和传统的NRA相比，TKEP在增长阶段维护的元组数量减少3个数量级，需要的内存量减少1个数量级，TKEP算法获得1个数量级的加速比. 关键词 海量数据;top-k;早剪切;TKEP 中图法分类号 TP311 DOI号：10.3724/SP.J.1016.2010.01405 |