摘要
在分布式数据流场景中,如何动态维护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.
出处
《计算机应用》
CSCD
北大核心
2008年第B06期169-171,174,共4页
journal of Computer Applications
