Distributed Top-k query algorithm based on uncertain data

Top-k query based on uncertain data has quickly attracted a lot of interested users, however, none of them has addressed himself to that the algorithm works in a distributed setting. A distributed Top-k algorithm based on uncertain data(UDTopk) is therefore presented to save the communication bandwidths. A data structure called candidate set is designed and proposed, where only the minimum amount of data is contained and the tuples that have been removed from the set will not affect the answer to a Top-k query. This algorithm presented can be dynamically maintained with new tuples being added, and only small amount of data is required to transmit, thus reducing the data transmission in the network. The experimental results showed that the UDTopk algorithm can effectively reduce the communication cost.