2014/10/29 by Alexander Mäcker, Mäcker, Alexander, Manuel Malatyali +3
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #F.1.2 #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1410.7912
openalex publication_date 2014/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.