Fetching the paper…
Reading the bibliography…
A technique introduced by Indyk and Woodruff [STOC 2005] has inspired several recent advances in data-stream algorithms.
Finding repeated elements
J. Misra and D. Gries · 1982
Earlier work this paper cites.
Lower bounds for sampling algorithms for estimating the average
R. Canetti, G. Even, and O. Goldreich · 1995
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.
Finding frequent items in data streams
M. Charikar, K. Chen, and M. Farach-Colton · 2002
Earlier work this paper cites.
Near-optimal lower bounds on the multi-party communication complexity of set disjointness
A. Chakrabarti, S. Khot, and X. Sun · 2003
Earlier work this paper cites.
An information statistics approach to data stream and communication complexity
Z. Bar-Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar · 2004
Earlier work this paper cites.
An improved data stream summary: the count-min sketch and its applications
G. Cormode and S. Muthukrishnan · 2005
Earlier work this paper cites.
Space efficient mining of multigraph streams
G. Cormode and S. Muthukrishnan · 2005
Earlier work this paper cites.
Optimal approximations of the frequency moments of data streams
P. Indyk and D. Woodruff · 2005
Earlier work this paper cites.
Data Streams: Algorithms and Aplications
M. Muthukrishnan · 2005
Earlier work this paper cites.
Estimating entropy over data streams
L. Bhuvanagiri and S. Ganguly · 2006
Earlier work this paper cites.
Simpler algorithm for estimating frequency moments of data streams
L. Bhuvanagiri, S. Ganguly, D. Kesh, and C. Saha · 2006
Cited alongside, same era.
Stable distributions, pseudorandom generators, embeddings and data stream computation
P. Indyk · 2006
Cited alongside, same era.
The dlt priority sampling is essentially optimal
M. Szegedy · 2006
Cited alongside, same era.
Priority sampling for estimation of arbitrary subset sums
N. G. Duffield, C. Lund, and M. Thorup · 2007
Cited alongside, same era.
On estimating frequency moments of data streams
S. Ganguly and G. Cormode · 2007
Cited alongside, same era.
Estimating hybrid frequency moments of data streams
S. Ganguly, M. Bansal, and S. Dube · 2008
Cited alongside, same era.
Measuring independence of datasets
V. Braverman and R. Ostrovsky · 2010
Closest in time.
Recursive sketching for frequency moments
V. Braverman and R. Ostrovsky · 2010
Closest in time.
Zero-one frequency laws
V. Braverman and R. Ostrovsky · 2010
Closest in time.
Count-min sketch
G. Cormode and M. Muthukrishnan · 2010
Closest in time.
Improved consistent sampling, weighted minhash and l1 sketching
S. Ioffe · 2010
Closest in time.
Tight bounds for lp samplers, finding duplicates in streams, and related problems
H. Jowhari, M. Saglam, and G. Tardos · 2010
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Estimators and tail bounds for dimension reduction in l p l_{p} ( 0 < p ≤ 2 ) (0<p\leq 2) using stable random projections
P. Li · 2008
Cited alongside, same era.
Efficient sketches for Earth-Mover Distance, with applications
A. Andoni, K. Do Ba, P. Indyk, and D. Woodruff · 2009
Cited alongside, same era.
Stream sampling for variance-optimal estimation of subset sums
E. Cohen, N. G. Duffield, H. Kaplan, C. Lund, and M. Thorup · 2009
Cited alongside, same era.
The data stream space complexity of cascaded norms
T. Jayram and D. Woodruff · 2009
Cited alongside, same era.
Polylogarithmic approximation for edit distance and the asymmetric query complexity
A. Andoni, R. Krauthgamer, and K. Onak · 2010
Cited alongside, same era.
On the exact space complexity of sketching small norms
D. M. Kane, J. Nelson, and D. P. Woodruff · 2010
Closest in time.
1-pass relative-error l p l_{p} -sampling with applications
M. Monemizadeh and D. Woodruff · 2010
Closest in time.
Fast manhattan sketches in data streams
J. Nelson and D. Woodruff · 2010
Closest in time.
Personal communication
S. Ganguly · 2011
Closest in time.
Fast moment estimation in data streams in optimal space
D. M. Kane, J. Nelson, E. Porat, and D. P. Woodruff · 2011
Closest in time.