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.
An important class of problems in this model investigated in literature are threshold computations, i.e., the coordinator is supposed to decide whether the current function value has reached some given threshold @math or not. If the function is monotone, e.g., monitoring the number of distinct values or the sum over all values, exact characterizations including matching lower bounds in the deterministic case are known @cite_4 @cite_5 . However, non-monotone functions, e.g., the entropy @cite_6 , turned out to be much more complex to handle.
@cite_5 @cite_4 @cite_6
2001183701 2123430048 1521238083
The notion of distributed functional monitoring was recently introduced by Cormode, Muthukrishnan and Yi to initiate a formal study of the communication cost of certain fundamental problems arising in distributed systems, especially sensor networks. In this model, each of k sites reads a stream of tokens and is in communication with a central coordinator, who wishes to continuously monitor some function f of *** , the union of the k streams. The goal is to minimize the number of bits communicated by a protocol that correctly monitors f (*** ), to within some small error. As in previous work, we focus on a threshold version of the problem, where the coordinator's task is simply to maintain a single output bit, which is 0 whenever f (*** )  *** (1 *** *** ) and 1 whenever f (*** ) *** *** . Following , we term this the (k ,f ,*** ,*** ) functional monitoring problem. In previous work, some upper and lower bounds were obtained for this problem, with f being a frequency moment function, e.g., F 0 , F 1 , F 2 . Importantly, these functions are monotone . Here, we further advance the study of such problems, proving three new classes of results. First, we provide nontrivial monitoring protocols when f is either H , the empirical Shannon entropy of a stream, or any of a related class of entropy functions (Tsallis entropies). These are the first nontrivial algorithms for distributed monitoring of non-monotone functions. Second, we study the effect of non-monotonicity of f on our ability to give nontrivial monitoring protocols, by considering f = F p with deletions allowed, as well as f = H . Third, we prove new lower bounds on this problem when f = F p , for several values of p . We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . We consider the problem of testing whether an unknown Boolean function f : -- 1, 1 n a#x21C6; -- 1, 1 is monotone versus aepsi;-far from every monotone function. The two main results of this paper are a new lower bound and a new algorithm for this well-studied problem. Lower bound: We prove an a#x03A9;(n1 5) lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown Boolean function f is monotone versus constant-far from monotone. This gives an exponential improvement on the previous lower bound of a#x03A9;(log n) due to [1]. We show that the same lower bound holds for monotonicity testing of Boolean-valued functions over hypergrid domains 1,,m n for all m age; 2. Upper bound: We present an O(n5 6) poly(1 aepsi;)-query algorithm that tests whether an unknown Boolean function f is monotone versus aepsi;-far from monotone. Our algorithm, which is non-adaptive and makes one-sided error, is a modified version of the algorithm of Chakrabarty and Seshadhri[2], which makes O(n7 8) poly(1 aepsi;) queries.