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.
Following the idea of studying competitive algorithms for monitoring streams and the notion of filters, @cite_1 present an algorithm for online dominance tracking of distributed streams. In this problem a coordinator always has to be informed about the dominance relationship between @math distributed nodes each observing an online stream of @math -dimensional values. Here, the dominance relation of two nodes @math and @math currently observing @math and @math , respectively, both from @math , is defined as @math dominates @math if @math for some @math and @math for all other @math . Their algorithm is based on the idea of assigning filters to the nodes and they show that a mid-point strategy, which basically sets filters to be the mid-point between neighboring nodes, is @math -competitive with respect to the number of messages sent in comparison to an offline algorithm that sets filters optimally.
@cite_1
1604641903
We consider the online problem for a root (or a coordinator) to maintain a set of filters for the purpose of keeping track of the dominance relationship of some distributed multi-dimensional data. Such data keep changing from time to time. The objective is to minimize the communication between the root and the distributed data sources. Assume that data are chosen from the d-dimensional grid 1, 2, ..., U d, we give an O(d log U)-competitive algorithm for this online problem. The competitive ratio is asymptotically tight as it is relatively easy to show an Ω(d log U) lower bound.