Fetching the paper…
Reading the bibliography…
We give a space-optimal algorithm with update time O(log^2(1/eps)loglog(1/eps)) for (1+eps)-approximating the pth frequency moment, 0 < p < 2, of a length-n vector updated in a data stream.
The best constants in the Khintchine inequality
Uffe Haagerup · 1982
Earlier work this paper cites.
Storing a sparse table with 0(1) worst case access time
Michael L. Fredman, János Komlós, and Endre Szemerédi · 1984
Earlier work this paper cites.
One-dimensional Stable Distributions
Vladimir Mikhailovich Zolotarev · 1986
Earlier work this paper cites.
Pseudorandom generators for space-bounded computation
Noam Nisan · 1992
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.
Sparse representations for image decompositions
Davi Geiger, Tyng-Luh Liu, and Michael J. Donahue · 1999
Earlier work this paper cites.
Modern Computer Algebra
Joachim von zur Gathen and Jürgen Gerhard · 1999
Earlier work this paper cites.
On the surprising behavior of distance metrics in high dimensional spaces
Charu C. Aggarwal, Alexander Hinneburg, and Daniel A. Keim · 2001
Earlier work this paper cites.
Tracking join and self-join sizes in limited storage
Noga Alon, Phillip B. Gibbons, Yossi Matias, and Mario Szegedy · 2002
Earlier work this paper cites.
The Complexity of Massive Data Set Computations
Ziv Bar-Yossef · 2002
Earlier work this paper cites.
Finding frequent items in data streams
Moses Charikar, Kevin Chen, and Martin Farach-Colton · 2002
Earlier work this paper cites.
Fast mining of massive tabular data via approximate distance computations
Graham Cormode, Piotr Indyk, Nick Koudas, and S. Muthukrishnan · 2002
Earlier work this paper cites.
An approximate L1-difference algorithm for massive data streams
Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan · 2002
Earlier work this paper cites.
Space lower bounds for distance approximation in the data stream model
Michael E. Saks and Xiaodong Sun · 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.
Sketch-based change detection: methods, evaluation, and applications
Balachander Krishnamurthy, Subhabrata Sen, Yin Zhang, and Yan Chen · 2003
Cited alongside, same era.
An information statistics approach to data stream and communication complexity
Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar · 2004
Cited alongside, same era.
Estimating frequency moments of data streams using random linear combinations
Sumit Ganguly · 2004
Cited alongside, same era.
Tabulation based 4-universal hashing with applications to second moment estimation
Mikkel Thorup and Yin Zhang · 2004
Cited alongside, same era.
Optimal space lower bounds for all frequency moments
David P. Woodruff · 2004
Cited alongside, same era.
An improved data stream summary: the count-min sketch and its applications
Graham Cormode and S. Muthukrishnan · 2005
Sketching and streaming entropy via approximation theory
Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak · 2008
Later among the works it cites.
The one-way communication complexity of hamming distance
T. S. Jayram, Ravi Kumar, and D. Sivakumar · 2008
Later among the works it cites.
Estimators and tail bounds for dimension reduction in l p l_{p} ( 0 < p ≤ 2 CLOSE (0<p\leq 2 ) using stable random projections
Ping Li · 2008
Later among the works it cites.
Uniform hashing in constant time and linear space
Anna Pagh and Rasmus Pagh · 2008
Later among the works it cites.
Complex Analysis
M.W. Wong · 2008
Later among the works it cites.
Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness
Andre Gronemeier · 2009
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Summarizing and mining inverse distributions on data streams via dynamic inverse sampling
Graham Cormode, S. Muthukrishnan, and Irina Rozenbaum · 2005
Cited alongside, same era.
Optimal approximations of the frequency moments of data streams
Piotr Indyk and David P. Woodruff · 2005
Cited alongside, same era.
Simpler algorithm for estimating frequency moments of data streams
Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, and Chandan Saha · 2006
Cited alongside, same era.
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Piotr Indyk · 2006
Cited alongside, same era.
IITK Workshop on Algorithms for Data Streams, 2006
Open Problems in Data Streams and Related Topics · 2006
Cited alongside, same era.
Efficient and Private Distance Approximation in the Communication and Streaming Models
David P. Woodruff · 2007
Cited alongside, same era.
Later among the works it cites.
Hellinger strikes back: A note on the multi-party information complexity of AND
T. S. Jayram · 2009
Later among the works it cites.
A near-optimal algorithm for L1-difference
Jelani Nelson and David P. Woodruff · 2009
Later among the works it cites.
Bounded independence fools degree-2 threshold functions
Ilias Diakonikolas, Daniel M. Kane, and Jelani Nelson · 2010
Closest in time.
A derandomized sparse Johnson-Lindenstrauss transform
Daniel M. Kane and Jelani Nelson · 2010
Closest in time.
On the exact space complexity of sketching and streaming small norms
Daniel M. Kane, Jelani Nelson, and David P. Woodruff · 2010
Closest in time.
1 1 -pass relative-error l p l_{p} sampling with applications
Morteza Monemizadeh and David P. Woodruff · 2010
Closest in time.
Fast Manhattan sketches in data streams
Jelani Nelson and David Woodruff · 2010
Closest in time.
Stable Distributions - Models for Heavy Tailed Data
John P. Nolan · 2010
Closest in time.