4R-TPUT:结构化对等网络中的高效top-k查询算法  

4R-TPUT:An efficient top-k query algorithm for structured peer-to-peer systems

作　　者：方启明[1,2] 杨广文[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]杭州电子科技大学计算机学院,杭州310018

出　　处：《清华大学学报（自然科学版）》2014年第4期480-484,共5页Journal of Tsinghua University(Science and Technology)

基　　金：国家"八六三"高技术项目(2010AA012400);国家自然科学基金面上项目(61272539);浙江省自然科学基金项目(LQ14F020013);浙江省重点科技创新团队项目(2009R50046)

摘　　要：top-k查询要求查找出最符合需求的前k个结果,是对等网络中的重要数据处理技术。该文研究了结构化对等网络中数据在各节点上垂直划分的精确top-k查询处理,在3通信回合的三阶段阈值(TPUT)算法基础上提出了4回合阈值算法4R-TPUT。它由下界估计、剪枝和结果查找3个阶段组成,通过在TPUT的下界估计阶段增加一个通信回合来获取更多的数据信息以得到更准确的top-k下界估计和剪枝阈值,从而减少查询处理过程中的数据访问和传输量。实验表明:4R-TPUT相比于TPUT较大幅度降低了数据传输量,减小了查询响应时间,是一种更高效的top-k查询算法。The Top-k query returns to users the k best match results and is an important data processing technique in peer-to-peer systems. This paper focuses on accurate top-k query processing in structured peer to-peer systems in which the data is vertically partitioned among peers. The three communication round-trip algorithm TPUT is expanded into a 4R TPUT threshold algorithm involving 4 round-trip communications. The algorithm has lower bound estimation, pruning and results lookup phases. TPUT introduces an additional round-trip communication in the first phase to get more information on the data to obtain a better top-k lower bound estimation and pruning threshold which can reduce data accesses and transmissions in the query processing. Tests show that 4R TPUT greatly reduces data transmissions compared with TPUT and, thus, requires less query response time, so 4R-TPUT is a more efficient top k query algorithm.

关 键 词：对等网络 TOP-K查询 TPUT 4R-TPUT 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]