Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm

Modeling by shortest data description

J. Rissanen, J. (1978) · 1978

Earlier work this paper cites.

Probabilistic counting algorithms for data base applications

P. Flajolet and G. Nigel Martin · 1985

Earlier work this paper cites.

Arithmetic coding for data compression

I. Witten, R. Neal, J. Cleary · 1987

Earlier work this paper cites.

A linear-time probabilistic counting algorithm for database applications

K. Whang, B. Vander-Zanden, and H. Taylor · 1990

Earlier work this paper cites.

Counting distinct elements in a data stream

Z. Bar-Yossef, T. Jayram, R. Kumar, D. Sivakumar, and L. Trevisan · 2002

Earlier work this paper cites.

Contemporary Combinatorics

Bela Bollobas · 2002

Earlier work this paper cites.

PhD thesis, École Pol technique, France, 2004

M. Durand. Combinatoire analytique et algorithmique des ensembles de données · 2004

Cited alongside, same era.

Summarizing data using bottom-k sketches

E. Cohen and H. Kaplan · 2007

Cited alongside, same era.

Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm

P. Flajolet, É. Fusy, O. Gandouet, and F. Meunier · 2008

Cited alongside, same era.

Distinct-value synopses for multiset operations

K. Beyer, R. Gemulla, P. J. Haas, B. Reinwald, and Y. Sismanis · 2009

Cited alongside, same era.

Order statistics and estimating cardinalities of massive data sets

F. Giroire · 2009

Cited alongside, same era.

New cardinality estimation algorithms for HyperLogLog sketches

O. Ertl

Cited in the paper.

An optimal algorithm for the distinct elements problem

D. M. Kane, J. Nelson, and D. P. Woodruff · 2010

Later among the works it cites.

Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm

S. Heule, M. Nunkesser, and A. Hall · 2013

Later among the works it cites.

All-distances sketches, revisited: HIP estimators for massive graphs analysis

E. Cohen · 2014

Later among the works it cites.

Streamed approximate counting of distinct elements: Beating optimal batch methods

D. Ting · 2014

Later among the works it cites.

A Framework for Estimating Stream Expression Cardinalities

A. Dasgupta, K. Lang, L. Rhodes, and J. Thaler · 2016

Later among the works it cites.