【摘要】 在分布式数据流场景中,如何动态维护top-k集合并尽可能地降低通信开销是非常重要的。通常的做法是:把大量的数据从分布式节点传送到中央节点,然后在中央节点计算top-k集合。这样的通信开销非常大,在许多场合下是根本无法实现的。提出了一种高效地动态维护分布式环境下top-k集合的近似算法top-k′。在算法中对一个top-k查询,通过动态维护k′(kmax≥k′≥k)个最高积分的元组,可以从中选取积分最高的k个元组返回。实验表明top-显著降低了各节点与中央协调节点之间的通信代价。更多还原

【Abstract】 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.更多还原