Built on

Probabilistic counting algorithms for data base applications
P. Flajolet and G. N. Martin · 1985
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.

Similar

Tabulation based 4-universal hashing with applications to second moment estimation
Original
M. Thorup and Y. Zhang · 2004
Cited alongside, same era.
On the exact space complexity of sketching and streaming small norms
D. M. Kane, J. Nelson, and D. P. Woodruff · 2010
Cited alongside, same era.

Then

Beating the direct sum theorem in communication complexity with implications for sketching
M. Molinaro, D. P. Woodruff, and G. Yaroslavtsev · 2013
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2014

Tracking the Frequency Moments at All Times

Huang, Zengfeng, Tai, Wai Ming, Yi, Ke

Understand

The traditional requirement for a randomized streaming algorithm is just {\em one-shot}, i.e., algorithm should be correct (within the stated $\eps$-error bound) at the end of the stream.

In this paper, we study the {\em tracking} problem, where the output should be correct at all times.
The standard approach for solving the tracking problem is to run $O(\log m)$ independent instances of the one-shot algorithm and apply the union bound to all $m$ time instances.
In this paper, we study if this standard approach can be improved, for the classical frequency moment problem.