top-k′:Approximate algorithm of maintaining dynamic top-k sets in distributed environment
Jing Yu Zhao · Journal of Computer Applications · 2008
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.