Online Top-k-Position Monitoring of Distributed Data Streams

A. Mäcker, M. Malatyali, F. Meyer auf der Heide, ArXiv:1410.7912 (2014).

Download
No fulltext has been uploaded.
Preprint | English
Author
; ;
Abstract
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 {\Delta} + k) log n) larger than that of an offline algorithm that sets filters in an optimal way, where {\Delta} is upper bounded by the largest value observed by any node.
Publishing Year
Journal Title
arXiv:1410.7912
LibreCat-ID

Cite this

Mäcker A, Malatyali M, Meyer auf der Heide F. Online Top-k-Position Monitoring of Distributed Data Streams. arXiv:14107912. 2014.
Mäcker, A., Malatyali, M., & Meyer auf der Heide, F. (2014). Online Top-k-Position Monitoring of Distributed Data Streams. ArXiv:1410.7912.
@article{Mäcker_Malatyali_Meyer auf der Heide_2014, title={Online Top-k-Position Monitoring of Distributed Data Streams}, journal={arXiv:1410.7912}, author={Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm}, year={2014} }
Mäcker, Alexander, Manuel Malatyali, and Friedhelm Meyer auf der Heide. “Online Top-k-Position Monitoring of Distributed Data Streams.” ArXiv:1410.7912, 2014.
A. Mäcker, M. Malatyali, and F. Meyer auf der Heide, “Online Top-k-Position Monitoring of Distributed Data Streams,” arXiv:1410.7912. 2014.
Mäcker, Alexander, et al. “Online Top-k-Position Monitoring of Distributed Data Streams.” ArXiv:1410.7912, 2014.

Export

Marked Publications

Open Data LibreCat

Sources

arXiv 1410.7912

Search this title in

Google Scholar