一种动态维护分布式环境下top-k集合的近似算法  

top-k′:Approximate algorithm of maintaining dynamic top-k sets in distributed environment

作　　者：田海生[1] 陈立军[2] 邱海艳[2] 赵静[2] 

机构地区：[1]中国科学院研究生院,北京100039 [2]北京大学计算机系,北京100871

出　　处：《计算机应用》2008年第B06期169-171,174,共4页journal of Computer Applications

摘　　要：在分布式数据流场景中,如何动态维护top-k集合并尽可能地降低通信开销是非常重要的。通常的做法是:把大量的数据从分布式节点传送到中央节点,然后在中央节点计算top-k集合。这样的通信开销非常大,在许多场合下是根本无法实现的。提出了一种高效地动态维护分布式环境下top-k集合的近似算法top-k′。在算法中对一个top-k查询,通过动态维护k′(kmax≥k′≥k)个最高积分的元组,可以从中选取积分最高的k个元组返回。实验表明top-显著降低了各节点与中央协调节点之间的通信代价。It is very important to maintain top-k aggregate dynamically and reduce the cost of communications, in a typical distributed data stream scenario. In general, we need to continuously transmit data from many different branches to central coordinator, and then calculate the results of top- k. But it costs a great deal of communications, and it is unacceptable in many cases. In this article, according to other＇s results, a new high effective approximate algorithm top-k＇ was proposed which was able to maintain a dynamic top-k aggregate in distributed data environment. According to our algorithm, by dynamically keeping k＇（kmax≥ k＇≥ k） data elements which had the highest scores, the highest scores of the k data elements from those could be chosen as a result of top- k query. The tests indicate that our method dramatically reduces the cost of communications between branches and central coordinator.

关 键 词：top-k’ TOP-K 分布式数据流 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]