Counting Distinct Elements in a Data Stream

By Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan. International Workshop Randomization and Approximation Techniques in Computer Science, 2002

578 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/54ab2344541738dd600b9b37463e5e52e8eeb9bd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Software Defined Traffic Measurement with OpenSketch (2013, unknown): “For example, the OpenSketch data plane does not provide complex data structures (e.g, binary search tree used in some sketches [9]) or directly support all measurement algorithms (e.g., flow size distribution ).”
Efficient Differentially Private F0 Linear Sketching (2020, background): “In the absence of privacy constraints, seminal estimators for (unweighted) set cardinality that support merging sketches (to produce a sketch of the union) are HyperLogLog [19], FM-sketches [20], and bottom-k (aka. k -minimum values) sketches [6].”
Space efficient mining of multigraph streams (2005, methodology): “This is a key problem in data streams, and several methods have been proposed [16, 20, 19, 5, 9].”
HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm (2013, methodology): “In particular, our users value the property of the previously implemented MinCount algorithm [2] that can provide near exact results up to a threshold and becomes approximate beyond that threshold.”
Differentially-Private Multi-Party Sketching for Large-Scale Statistics (2020, methodology): “This can be achieved through the median technique [8].”
Cardinality Estimators do not Preserve Privacy (2018, methodology): “– K-Minimum Values [6] – Bloom ﬁlters can also be used for cardinality estimation [36].”
SketchVisor: Robust Network Measurement for Software Packet Processing (2017, methodology): “Cardinality estimation FM [20] kMin [2] Linear Counting (LC) [55]”
The Power of Linear Estimators (2011, background): “There has been much work on estimating the support size (and the general problem of estimating frequency moments) and estimating the entropy in the setting of streaming, in which one has access to very little memory and can perform only a single pass over the data [1], [2], [12], [17], [18], [19].”
A sample-and-clean framework for fast and accurate query processing on dirty data (2014, background): “Distinct Value Estimation: Distinct value estimation has been an open problem in stream processing and database research [6,8,15,27].”
Mash: fast genome and metagenome distance estimation using MinHash (2015, background): “known, and total number of k-mers in the genome, which can be estimated from the sketch [47].”
Optimal approximations of the frequency moments of data streams (2005, methodology): “For simplicity, we assume k ≥ 2 is a constant (for k < 2, space-optimal algorithms already exist [1, 3]) , while m, n, 1/ may be growing.”
Approximate aggregation techniques for sensor databases (2004, background): “Since then, there has been much work developing and generalizing counting sketches (e.g. [1] [6] [10] [3] [9] [2]).”