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