Consider n nodes connected to a single coordinator. Each node receives an individual online data stream of numbers and, at any point in time, the coordinator has to know the k nodes currently observing the largest values, for a given k between 1 and n. We design and analyze an algorithm that solves this problem while bounding the amount of messages exchanged between the nodes and the coordinator. Our algorithm employs the idea of using filters which, intuitively speaking, leads to few messages to be sent, if the new input is "similar" to the previous ones. The algorithm uses a number of messages that is on expectation by a factor of O((log + k) log n) larger than that of an offline algorithm that sets filters in an optimal way, where is upper bounded by the largest value observed by any node.
In their work @cite_0 , Yi and Zhang were the first to study streaming algorithms with respect to their competitiveness. In their model there is one node and one coordinator and the goal is to keep the coordinator informed about the current value of a multivalued function @math that is observed by the node and changes its value over time, while minimizing the number of messages. Among others, for @math , Yi and Zhang present an algorithm that is @math -competitive if the last value received by the coordinator might deviate by @math from the current value of @math . For arbitrary @math , a competitiveness of @math is shown.
@cite_0
1999582613
We resolve several fundamental questions in the area of distributed functional monitoring, initiated by Cormode, Muthukrishnan, and Yi (SODA, 2008). In this model there are @math sites each tracking their input and communicating with a central coordinator that continuously maintain an approximate output to a function @math computed over the union of the inputs. The goal is to minimize the communication. We show the randomized communication complexity of estimating the number of distinct elements up to a @math factor is @math , improving the previous @math bound and matching known upper bounds up to a logarithmic factor. For the @math -th frequency moment @math , @math , we improve the previous @math communication bound to @math . We obtain similar improvements for heavy hitters, empirical entropy, and other problems. We also show that we can estimate @math , for any @math , using @math communication. This greatly improves upon the previous @math bound of Cormode, Muthukrishnan, and Yi for general @math , and their @math bound for @math . For @math , our bound resolves their main open question. Our lower bounds are based on new direct sum theorems for approximate majority, and yield significant improvements to problems in the data stream model, improving the bound for estimating @math in @math passes from @math to @math , giving the first bound for estimating @math in @math passes of @math bits of space that does not use the gap-hamming problem.