text: 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.
  @cite_0: We propose and study a new class of online problems, which we call online tracking. Suppose an observer, say Alice, observes a multivalued function f: Z+ r Zd over time in an online fashion, that is, she only sees f(t) for t≤tnow where tnow is the current time. She would like to keep a tracker, say Bob, informed of the current value of f at all times. Under this setting, Alice could send new values of f to Bob from time to time, so that the current value of f is always within a distance of Δ to the last value received by Bob. We give competitive online algorithms whose communication costs are compared with the optimal offline algorithm that knows the entire f in advance. We also consider variations of the problem where Alice is allowed to send predictions to Bob, to further reduce communication for well-behaved functions. These online tracking problems have a variety of application, ranging from sensor monitoring, location-based services, to publish subscribe systems.
summary: 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.