Towards Generic and Efficient Distributed Top-k Monitoring

Monitoring data streams in a distributed system is the focus of much research in recent years. This paper addresses the generic and efficient processing of distributed top-k monitoring, which is continuously reporting the k largest values according to a user-specified aggregation function over distributed data streams. In practice, the user-specified aggregation function would be arbitrary function. Unfortunately, state-of-art distributed top-k monitoring approaches only support the sum function as the aggregation function. In this paper, we present a generic algorithm for distributed top-k monitoring, which supports not only the sum function but also min, max, count, average, and their compounds. These functions are the most general aggregation functions. In our algorithm, two kinds of arithmetic constraints are maintained at remote stream sources to ensure that the most recently provided top-k answer remains valid to within a user-specified error tolerance. Theoretical analyses results show that, in our algorithm, distributed communication is only necessary on occasion and few objects are necessary transmitted, when constraints are violated, and the communication cost is independent of k.