Fetching the paper…
Reading the bibliography…
We study the classical problem of moment estimation of an underlying vector whose $n$ coordinates are implicitly defined through a series of updates in a data stream.
Selection and sorting with limited storage
J. Ian Munro and Mike Paterson · 1980
Earlier work this paper cites.
The space complexity of approximating the frequency moments
Noga Alon, Yossi Matias, and Mario Szegedy · 1999
Earlier work this paper cites.
Frequency estimation of internet packet streams with limited space
Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro · 2002
Earlier work this paper cites.
Near-optimal lower bounds on the multi-party communication complexity of set disjointness
Amit Chakrabarti, Subhash Khot, and Xiaodong Sun · 2003
Earlier work this paper cites.
An information statistics approach to data stream and communication complexity
Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar · 2004
Earlier work this paper cites.
Finding frequent items in data streams
Moses Charikar, Kevin C. Chen, and Martin Farach-Colton · 2004
Earlier work this paper cites.
Optimal space lower bounds for all frequency moments
David P. Woodruff · 2004
Earlier work this paper cites.
Optimal approximations of the frequency moments of data streams
Piotr Indyk and David P. Woodruff · 2005
Earlier work this paper cites.
Simpler algorithm for estimating frequency moments of data streams
Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, and Chandan Saha · 2006
Earlier work this paper cites.
Approximate quantiles and the order of the stream
Sudipto Guha and Andrew McGregor · 2006
Earlier work this paper cites.
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Piotr Indyk · 2006
Earlier work this paper cites.
Lower bounds for quantile estimation in random-order and multi-pass streaming
Sudipto Guha and Andrew McGregor · 2007
Earlier work this paper cites.
Better bounds for frequency moments in random-order streams
Alexandr Andoni, Andrew McGregor, Krzysztof Onak, and Rina Panigrahy · 2008
Earlier work this paper cites.
Tight lower bounds for selection in randomly ordered streams
Amit Chakrabarti, T. S. Jayram, and Mihai Patrascu · 2008
Cited alongside, same era.
Estimators and tail bounds for dimension reduction in ℓ α ( 0 < α ≤ 2 ) \ell_{\alpha}(0<\alpha\leq 2) using stable random projections
Ping Li · 2008
Cited alongside, same era.
Revisiting the direct sum theorem and space lower bounds in random order streams
Sudipto Guha and Zhiyi Huang · 2009
Cited alongside, same era.
Hellinger strikes back: A note on the multi-party information complexity of AND
T. S. Jayram · 2009
Cited alongside, same era.
On the exact space complexity of sketching and streaming small norms
Daniel M. Kane, Jelani Nelson, and David P. Woodruff · 2010
Cited alongside, same era.
1-pass relative-error L p \text{L}_{p} -sampling with applications
Approximating large frequency moments with pick-and-drop sampling
Vladimir Braverman and Rafail Ostrovsky · 2013
Later among the works it cites.
A tight lower bound for high frequency moment estimation with small error
Yi Li and David P. Woodruff · 2013
Later among the works it cites.
An optimal algorithm for large frequency moments using O ( n 1 − 2 / k ) (n^{1-2/k}) bits
Vladimir Braverman, Jonathan Katzman, Charles Seidell, and Gregory Vorsanger · 2014
Later among the works it cites.
Robust lower bounds for communication and stream computation
Amit Chakrabarti, Graham Cormode, and Andrew McGregor · 2016
Later among the works it cites.
High frequency moments via max-stability
Alexandr Andoni · 2017
Later among the works it cites.
Bptree: An ℓ 2 \ell_{2} heavy hitters algorithm using constant memory
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David P. Woodruff · 2017
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Morteza Monemizadeh and David P. Woodruff · 2010
Cited alongside, same era.
Streaming algorithms via precision sampling
Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak · 2011
Cited alongside, same era.
Polynomial estimators for high frequency moments
Sumit Ganguly · 2011
Cited alongside, same era.
Fast moment estimation in data streams in optimal space
Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff · 2011
Cited alongside, same era.
A lower bound for estimating high moments of a data stream
Sumit Ganguly · 2012
Cited alongside, same era.
Maximum matching in semi-streaming with few passes
Christian Konrad, Frédéric Magniez, and Claire Mathieu · 2012
Cited alongside, same era.
Tight bounds for distributed functional monitoring
David P. Woodruff and Qin Zhang · 2012
Cited alongside, same era.
Later among the works it cites.
Continuous monitoring of ℓ p \ell_{p} norms in data streams
Jaroslaw Blasiok, Jian Ding, and Jelani Nelson · 2017
Later among the works it cites.
Revisiting frequency moment estimation in random order streams
Vladimir Braverman, Emanuele Viola, David P. Woodruff, and Lin F. Yang · 2018
Later among the works it cites.
High probability frequency moment sketches
Sumit Ganguly and David P. Woodruff · 2018
Later among the works it cites.
Towards optimal moment estimation in streaming and distributed models
Rajesh Jayaram and David P. Woodruff · 2019
Later among the works it cites.
The coin problem with applications to data streams
Mark Braverman, Sumegha Garg, and David P. Woodruff · 2020
Later among the works it cites.
Tight bounds for adversarially robust streams and sliding windows via difference estimators
David P. Woodruff and Samson Zhou · 2020
Later among the works it cites.