@article{maecker2016competitive,
author = "Alexander Maecker and Manuel Malatyali and Friedhelm Meyer Auf Der Heide",
abstract = "Consider the continuous distributed monitoring model in which {\$}n{\$} distributed nodes, receiving individual data streams, are connected to a designated server. The server is asked to continuously monitor a function defined over the values observed across all streams while minimizing the communication. We study a variant in which the server is equipped with a broadcast channel and is supposed to keep track of an approximation of the set of nodes currently observing the {\$}k{\$} largest values. Such an approximate set is exact except for some imprecision in an {\$}\backslashvarepsilon{\$}-neighborhood of the {\$}k{\$}-th largest value. This approximation of the Top-{\$}k{\$}-Position Monitoring Problem is of interest in cases where marginal changes (e.g.$\backslash$ due to noise) in observed values can be ignored so that monitoring an approximation is sufficient and can reduce communication. This paper extends our results from [IPDPS'15], where we have developed a filter-based online algorithm for the (exact) Top-k-Position Monitoring Problem. There we have presented a competitive analysis of our algorithm against an offline adversary that also is restricted to filter-based algorithms. Our new algorithms as well as their analyses use new methods. We analyze their competitiveness against adversaries that use both exact and approximate filter-based algorithms, and observe severe differences between the respective powers of these adversaries.",
doi = "10.1109/IPDPS.2016.91",
isbn = "9781509021406",
journal = "Proceedings - 2016 IEEE 30th International Parallel and Distributed Processing Symposium, IPDPS 2016",
keywords = "Approximation;Continuous computation;Distributed monitoring;Online data streams;Top-k;Tracking",
number = "317532",
pages = "700--709",
title = "{O}n {C}ompetitive {A}lgorithms for {A}pproximations of {T}op-k-{P}osition {M}onitoring of {D}istributed {S}treams",
year = "2016",
}