Optimal streaming and tracking distinct elements with high probability
Jarosław Błasiok · Society for Industrial and Applied Mathematics eBooks · 2018
The distinct elements problem is one of the fundamental problems in streaming algorithms — given a stream of integers in the range {1, … n}, we wish to provide a (1+ε) approximation of the number of distinct elements in the input. After a long line of research optimal solution for this problem with constant probability of success, using bits of space, was given by Kane, Nelson and Woodruff in [KNW10]. The standard approach used in order to achieve low failure probability δ, is to take a median of 1g δ–1 parallel repetitions of the original algorithm. We show that such a multiplicative space blow-up is unnecessary: we provide an optimal algorithm using bits of space — matching known lower bounds for this problem. That is, the lg δ–1 factor does not multiply the lg n term. This settles completely the space complexity of the distinct elements problem with respect to all standard parameters. Recently some attention in streaming algorithms has turned into continuously reporting the estimate of the statistic of interest, as opposed to reporting it only at the end of the stream. In this scenario, we want an algorithm which provides a (1 + ε) multiplicative approximation of the number of distinct elements at all times with probability 1 – δ, we call this strong tracking or continuous monitoring. The traditional way to achieve this kind of guarantee is to use a low failure probability algorithm, and union bound over carefully chosen subset of positions — this method, using as black-box the optimal streaming algorithm for distinct elements with low failure probability, would require bits of space. We show that this approach can be improved upon: we propose a stronger analysis of the algorithm, with space complexity . Finally, we show the matching lower bound for the strong tracking of the number of distinct elements with accuracy (1 + ε), proving optimality of our algorithm in terms of space usage.