143-韩希先 tkep：海量数据上一种有效的top-k 查询处理算法

《143-韩希先 tkep：海量数据上一种有效的top-k 查询处理算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、*TKEP：海量数据上一种有效的Top-K查询处理算法121+韩希先,杨东华,李建中1(哈尔滨工业大学计算机科学与技术学院,黑龙江省哈尔滨市150001)2(哈尔滨工业大学基础与交叉科学研究院高性能计算中心,黑龙江省哈尔滨市150001)摘要:在许多应用领域中，top-k查询是一种十分重要的操作，它根据给定的评分函数在潜在的巨大的数据空间中返回k个最重要的对象。不同于传统的TA算法，NRA算法只需要顺序读就可以处理top-k查询，从而适合于随机读受限或不可能的场合。本文详细地分析了NRA算法的执行行为，确定了增长阶段和收缩阶段中每个文件需要扫描的元组个数。本文发现在海量数据环境中，NRA在增

2、长阶段需要维护大量的候选元组，严重影响了算法的执行效率。所以，本文提出一种新的海量数据上的top-k查询算法TKEP(Top-KwithEarlyPruning)，该算法在查询的增长阶段就执行早剪切，从而大大减少增长阶段需要维护的候选元组。本文给出了早剪切操作的数学分析，确定了早剪切操作的理论和实际剪切效果。据我们所知，本文是第一篇提出在top-k查询的增长阶段执行早剪切的文章。实验结果表明，和传统的NRA相比，TKEP在增长阶段维护的元组数量减少3个数量级，需要的内存量减少1个数量级，TKEP算法获得1个数量级的加速比。关键词:海量数据;top-k;早剪切;TKEP中图法分类号:TP311

3、文献标识码:A1引言组数量和返回的结果数量的增大，NRA的增长阶段需要维护的候选元组也越来越多，其维护费用也越来越大。尤其是增在许多应用领域中，例如Web搜索、信息检索、多媒体长阶段维护的数据超过给定的内存容量时，NRA算法将不得数据库和数据挖掘等，top-k查询是一种十分重要的操作，它不把内存中的数据反复输出到磁盘，这必然会引起较高的费根据给定的评分函数在潜在的数据空间中返回k个最重要的用，从而影响top-k查询的执行效率。结果。处理top-k查询时，系统通常根据用户的要求对涉及本文详细地分析了NRA算法的执行行为，确定了增长到的每个对象的属性计算一个数值来反映该属性的特点，然阶段和收缩阶

4、段中每个文件需要扫描的元组数，同时还分析后利用一个单调评分函数聚集多个属性的数值作为该对象的了NRA算法在增长阶段需要维护的候选元组的数量。分析权重，top-k查询返回k个权重最高的对象作为查询的结果。表明，在海量数据上，NRA在增长阶段需要维护大量的候选处理top-k查询的一种方式是利用多维索引，可是当查元组，严重影响了算法的执行效率。基于对NRA行为的分询涉及的属性超过6时，多维索引的查询性能急剧下降(curse析，本文提出一种新的海量数据上的top-k查询处理算法[1]ofdimensionality)。相对于多维索引，另一种更具有扩展性TKEP(Top-KwithEarlyPruni

5、ng)。该算法和现有NRA算法的方法是把数据表列存储化并且按属性值降序排列存储。的最大不同在于，该算法可以在查询的增长阶段就执行早剪[2]Fagin等提出TA算法在多个有序文件上执行top-k查询。切，从而减少增长阶段需要维护的元组数量。本文给出早剪top-k查询处理涉及到两种数据读方式来获得对象x在指定列切操作的数学分析，确定了早剪切的理论和实际剪切效果。文件的数值：顺序读和随机读。顺序读意味着处理完该文件指数间距bloomfilter表(EGBFT)是TKEP算法执行剪切时用中分数比x大的元组后可以获得x的分数，而随机读则直接th到的数据结构，EGBFT的第j个元组是构建在对应文件的1获

6、得该文件中x对应的属性值。在某些情况下，例如数据流jth到(2)元组上的bloomfilter。本文提供了较全面的实验来评和海量数据环境，随机读操作是受限的或过于昂贵的，人们价TKEP的性能，实验结果表明，和传统的NRA相比，TKEP[3,4,5,6]利用NRA算法来处理只支持顺序读的top-k查询。NRA在增长阶段维护的元组数量减少3个数量级，需要的内存量的执行可以分为两个阶段：增长阶段(不断累积top-k候选元减少1个数量级，TKEP算法获得1个数量级的加速比。组直到找到top-k结果的阈值)和收缩阶段(不断剪切候选元本文的主要贡献在于：组直到获得最终top-k结果)。由于属性文件的降序

7、排列和评
本文提出了一种新的海量数据上的top-k算法分函数的单调性，NRA算法通常不需要处理完属性文件所有TKEP。不同于传统的NRA算法，TKEP算法在增数据就可以结束查询并返回结果。随着涉及的属性数量、元长阶段就开始执行早剪切操作，从而大大减少了需*SupportedbytheNationalBasicResearchProgramofChinaunderGrantNo.2006CB303005(国家重