RRTA：一种基于顺序读取的有效Top-K查询算法-论文.pdf

《RRTA：一种基于顺序读取的有效Top-K查询算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1162013，49(17)ComputerEngineeringandApplications计算机工程与应用RRTA：一种基于顺序读取的有效Top-K查询算法周腾腾，陈林祥，胡奥ZHOUTengteng，CHENLinxiang，HUAo1．中国矿业大学计算机科学与技术学院计算机科学与技术系，江苏徐州2210002冲国矿业大学理学院数学系，江苏徐州2210001．DepartmentofComputerScienceandTechnology，CollegeofComputerScienceandTechnology，

2、ChinaUniversityofMiningandTechnology,Xuzhou，Jiangsu221000，China2．DepartmentofMathematics，CollegeofScience，ChinaUniversityofMiningandTechnology,Xuzhou，Jiangsu221000，ChinaZHOUTengteng，CHENLinxiang，HUAo．RRTA：eficientTop-Kqueryprocessingalgorithmbasedonround-robin．Com

3、puterEngineeringandApplications，2013，49(17)：116-120．Abstract：Top—Kqueryisawidelyusedoperation，whichcanreturnthehighestscoreofthetupleinspecializedmassivedata—bases，accordingtothegivenmonotoneaggregationfunction．TraditionalTAalgorithmrequirestheabilitytosupportrand

4、omaccess，NRAalgorithmalthoughrelaxestherestrictionsontherandomaccess，itisfoundthatinmassivedatacontext，NRAneedstomaintainlargequantityofcandidatetuplesinmemoryintheincreasingphase，itwillalsouseupalotofmemoryresourcesinruntime．ComparedwiththeNRAalgorithm．theRRTA(Ro

5、und—RobinThresholdAlgorithm)whichproposedinthispaperreplantsthedatastoragemode，whichcreatsanewtabletoswitchthememoryoverheadtothecheaperexternalmemoryover—head，SOjustsortedaccessisalsoabletodoefficienttop—kquery．Meanwhile，thetablehasbeendivided，whichmakesthealgo—r

6、ithmmoreeficientandsmootherevenwithlimitedmemory，inthecaseofparallelprocessing．Keywords：massivedata；Top—K；Round-RobinThresholdAlgorithm(RRTA)；sortedaccess；limitedmemory摘要：Top-K查询是一种被广泛应用的操作，它根据给定的评分函数在潜在的海量数据中返回k个分值最高的元组。传统的TA算法要求能够支持随机读，NRA算法虽然放宽了对随机读的限制，但是增长阶段需要

7、在内存中维护大量的元组，运行时将占用大量的内存资源。提出的RRTA算法相比NRA算法对数据的存储进行了重新的规划，创建一个新的表将内存上的开销转换到较廉价的外存开销，只需顺序读取就可以进行有效的Top-K查询，同时将表进行了划分，在并行处理的情况下更能提高程序的效率，能够很好地运行在内存有限的环境中关键词：海量数据；Top—K；循环阈值算法(RRTA)；顺序读取；有限内存文献标志码：A中图分类号：TP311doi：10．3778／j．issn．1002—8331．1111-05581引言Stream—Combine算法改进

8、NRA算法，有限读取使得算法阈在现实世界中，Top-K查询被应用到许多领域中，并得值下降最快的链表。Mamoulis等通过对NRA算法的分到了研究人员的广泛关注u，它根据给定的评分函数在潜析，把NRA的执行过程分为增长和收缩两个阶段，并且提在的数据空间返回后个分值最高的元组，例如在Web搜索、出LARA