2014 StreamedApproximateCountingofDi

• (Ting, 2014) ⇒ Daniel Ting. (2014). “Streamed Approximate Counting of Distinct Elements: Beating Optimal Batch Methods.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623669

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+Streamed+Approximate+Counting+of+Distinct+Elements%3A+Beating+Optimal+Batch+Methods
• http://dl.acm.org/citation.cfm?id=2623330.2623669&preflayout=flat#citedby

Quotes

Author Keywords

• Cardinality estimation; data mining; distinct elements; markov processes; martingale; probabilistic algorithms; randomized algorithms

Abstract

Counting the number of distinct elements in a large dataset is a common task in web applications and databases. This problem is difficult in limited memory settings where storing a large hash table table is intractable. This paper advances the state of the art in probabilistic methods for estimating the number of distinct elements in a streaming setting New streaming algorithms are given that provably beat the "optimal" errors for Min-count and HyperLogLog while using the same sketch.

This paper also contributes to the understanding and theory of probabilistic cardinality estimation introducing the concept of an area cutting process and the martingale estimator. These ideas lead to theoretical analyses of both old and new sketches and estimators and show the new estimators are optimal for several streaming settings while also providing accurate error bounds that match those obtained via simulation. Furthermore, the area cutting process provides a geometric intuition behind all methods for counting distinct elements which are not affected by duplicates. This intuition leads to a new sketch, Discrete Max-count, and the analysis of a class of sketches, self-similar area cutting decompositions that have attractive properties and unbiased estimators for both streaming and non-streaming settings.

Together, these contributions lead to multi-faceted advances in sketch construction, cardinality and error estimation, the theory, and intuition for the problem of approximate counting of distinct elements for both the streaming and non-streaming cases.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 StreamedApproximateCountingofDi	Daniel Ting			Streamed Approximate Counting of Distinct Elements: Beating Optimal Batch Methods				10.1145/2623330.2623669		2014