BPTree: an $\ell_2$ heavy hitters algorithm using constant memory

The sizes of compact subsets of Hilbert space and continuity of Gaussian processes

R. M. Dudley · 1967

Earlier work this paper cites.

A bound on tail probabilities for quadratic forms in independent random variables

D. L. Hanson and F. T. Wright · 1971

Earlier work this paper cites.

Universal classes of hash functions

L. Carter and M. N. Wegman · 1979

Earlier work this paper cites.

A fast majority vote algorithm

R. S. Boyer and J. S. Moore · 1981

Earlier work this paper cites.

The best constants in the Khintchine inequality

U. Haagerup · 1982

Earlier work this paper cites.

Finding repeated elements

J. Misra and D. Gries · 1982

Earlier work this paper cites.

MJRTY: A fast majority vote algorithm

R. S. Boyer and J. S. Moore · 1991

Earlier work this paper cites.

The space complexity of approximating the frequency moments

N. Alon, Y. Matias, and M. Szegedy · 1999

Earlier work this paper cites.

Models and issues in data stream systems

B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom · 2002

Earlier work this paper cites.

Frequency estimation of Internet packet streams with limited space

E. D. Demaine, A. López-Ortiz, and J. I. Munro · 2002

Earlier work this paper cites.

A simple algorithm for finding frequent elements in streams and bags

R. M. Karp, S. Shenker, and C. H. Papadimitriou · 2003

Earlier work this paper cites.

Finding frequent items in data streams

M. Charikar, K. C. Chen, and M. Farach-Colton · 2004

Cited alongside, same era.

Tabulation based 4-universal hashing with applications to second moment estimation

M. Thorup and Y. Zhang · 2004

Cited alongside, same era.

An improved data stream summary: the count-min sketch and its applications

G. Cormode and S. Muthukrishnan · 2005

Cited alongside, same era.

Optimal approximations of the frequency moments of data streams

P. Indyk and D. P. Woodruff · 2005

Cited alongside, same era.

Efficient computation of frequent and top-k elements in data streams

A. Metwally, D. Agrawal, and A. El Abbadi · 2005

Cited alongside, same era.

Data streams: Algorithms and applications

S. Muthukrishnan · 2005

Cited alongside, same era.

1-pass relative-error L p L_{p} -sampling with applications

M. Monemizadeh and D. P. Woodruff · 2010

Later among the works it cites.

On the power of adaptivity in sparse recovery

P. Indyk, E. Price, and D. P. Woodruff · 2011

Later among the works it cites.

Tight bounds for Lp samplers, finding duplicates in streams, and related problems

H. Jowhari, M. Sağlam, and G. Tardos · 2011

Later among the works it cites.

Approximate frequency counts over data streams

G. S. Manku and R. Motwani · 2012

Later among the works it cites.

Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation

Original

M. Thorup and Y. Zhang · 2012

Later among the works it cites.

Approximating large frequency moments with pick-and-drop sampling

V. Braverman and R. Ostrovsky · 2013