On Competitive Algorithms for Approximations of Top-k-Position Monitoring of Distributed Streams

Maecker, Alexander; Malatyali, Manuel; Heide, Friedhelm Meyer Auf Der
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.
Research areas:
Year:
2016
Type of Publication:
Article
Keywords:
Approximation; Continuous computation; Distributed monitoring; Online data streams; Top-k; Tracking
Journal:
Proceedings - 2016 IEEE 30th International Parallel and Distributed Processing Symposium, IPDPS 2016
Number:
317532
Pages:
700-709
DOI:
10.1109/IPDPS.2016.91
Hits: 672

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information