Fetching the paper…
Reading the bibliography…
In turnstile $\ell_p$ $\varepsilon$-heavy hitters, one maintains a high-dimensional $x\in\mathbb{R}^n$ subject to $\texttt{update}(i,\Delta)$ causing $x_i\leftarrow x_i + \Delta$, where $i\in[n]$, $\Delta\in\mathbb{R}$.
Universal classes of hash functions
Larry Carter and Mark N. Wegman · 1979
Earlier work this paper cites.
Finding repeated elements
Jayadev Misra and David Gries · 1982
Earlier work this paper cites.
Isoperimetric inequalities for graphs, and superconcentrators
Noga Alon and Vitali Milman · 1985
Earlier work this paper cites.
Eigenvalues and expanders
Noga Alon · 1986
Earlier work this paper cites.
Explicit construction of linear sized tolerant networks
Noga Alon and Fan R. K. Chung · 1988
Earlier work this paper cites.
An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms
Tom Leighton and Satish Rao · 1988
Earlier work this paper cites.
Approximative counting, uniform generation and rapidly mixing Markov chains
Alistair J. Sinclair and Mark R. Jerrum · 1989
Earlier work this paper cites.
Linear-time encodable and decodable error-correcting codes
Daniel A. Spielman · 1996
Earlier work this paper cites.
Computing iceberg queries efficiently
Min Fang, Narayanan Shivakumar, Hector Garcia-Molina, Rajeev Motwani, and Jeffrey D. Ullman · 1998
Earlier work this paper cites.
Normalized cuts and image segmentation
Jianbo Shi and Jitendra Malik · 2000
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.
Entropy waves, the zig-zag graph product, and new constant-degree expanders
Omer Reingold, Salil Vadhan, and Avi Wigderson · 2002
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 Chen, and Martin Farach-Colton · 2004
Earlier work this paper cites.
Holistic UDAFs at streaming speeds
Graham Cormode, Theodore Johnson, Flip Korn, S. Muthukrishnan, Oliver Spatscheck, and Divesh Srivastava · 2004
Earlier work this paper cites.
On clusterings: Good, bad and spectral
Ravi Kannan, Santosh Vempala, and Adrian Vetta · 2004
Earlier work this paper cites.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A Spielman and Shang-Hua Teng · 2004
Earlier work this paper cites.
An improved data stream summary: the count-min sketch and its applications
Graham Cormode and S. Muthukrishnan · 2005
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.
Data streams: Algorithms and applications
S. Muthukrishnan · 2005
Earlier work this paper cites.
Interpreting the data: Parallel analysis with Sawzall
Rob Pike, Sean Dorward, Robert Griesemer, and Sean Quinlan · 2005
Earlier work this paper cites.
An elementary construction of constant-degree expanders
Noga Alon, Oded Schwartz, and Asaf Shapira · 2008
Earlier work this paper cites.
Finding frequent items in data streams
Graham Cormode and Marios Hadjieleftheriou · 2008
Cited alongside, same era.
Sketching and streaming entropy via approximation theory
Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak · 2008
Cited alongside, same era.
Finding sparse cuts locally using evolving sets
Reid Andersen and Yuval Peres · 2009
Cited alongside, same era.
Expander flows, geometric embeddings and graph partitioning
Sanjeev Arora, Satish Rao, and Umesh Vazirani · 2009
Cited alongside, same era.
Noise-resilient group testing: Limitations and constructions
Mahdi Cheraghchi · 2009
Cited alongside, same era.
Hierarchical sampling from sketches: Estimating functions over data streams
Sumit Ganguly and Lakshminath Bhuvanagiri · 2009
Cited alongside, same era.
Approximating the expansion profile and almost optimal local graph clustering
Shayan Oveis Gharan and Luca Trevisan · 2012
Later among the works it cites.
Approximation algorithms for semi-random partitioning problems
Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan · 2012
Later among the works it cites.
On deterministic sketching and streaming for sparse recovery and norm estimation
Jelani Nelson, Huy L. Nguy e ^ ~ \tilde{\hat{\mbox{e}}} n, and David P. Woodruff · 2012
Later among the works it cites.
Efficiently decodable compressed sensing by list-recoverable codes and recursion
Hung Q. Ngo, Ely Porat, and Atri Rudra · 2012
Later among the works it cites.
Approximating the exponential, the lanczos method and an O ~ ( m ) \tilde{O}(m) -time spectral algorithm for balanced separator
Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi · 2012
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Finding duplicates in a data stream
Parikshit Gopalan and Jaikumar Radhakrishnan · 2009
Cited alongside, same era.
The data stream space complexity of cascaded norms
T. S. Jayram and David P. Woodruff · 2009
Cited alongside, same era.
Space-optimal heavy hitters with strong error bounds
Radu Berinde, Piotr Indyk, Graham Cormode, and Martin J. Strauss · 2010
Cited alongside, same era.
Zero-one frequency laws
Vladimir Braverman and Rafail Ostrovsky · 2010
Cited alongside, same era.
A near-optimal algorithm for estimating the entropy of a stream
Amit Chakrabarti, Graham Cormode, and Andrew McGregor · 2010
Cited alongside, same era.
Bounded independence fools degree-2 threshold functions
Ilias Diakonikolas, Daniel M. Kane, and Jelani Nelson · 2010
Cited alongside, same era.
Approximating large frequency moments with pick-and-drop sampling
Vladimir Braverman and Rafail Ostrovsky · 2013
Later among the works it cites.
ℓ 2 / ℓ 2 \ell_{2}/\ell_{2} -foreach sparse recovery with low risk
Anna C. Gilbert, Hung Q. Ngo, Ely Porat, Atri Rudra, and Martin J. Strauss · 2013
Later among the works it cites.
Identifying high-cardinality hosts from network-wide traffic measurements
Yang Liu, Wenji Chen, and Yong Guan · 2013
Later among the works it cites.
Compressed matrix multiplication
Rasmus Pagh · 2013
Later among the works it cites.
An optimal algorithm for large frequency moments using O ( n 1 − 2 / k ) O(n^{1-2/k}) bits
Vladimir Braverman, Jonathan Katzman, Charles Seidell, and Gregory Vorsanger · 2014
Later among the works it cites.
For-all sparse recovery in near-optimal time
Anna C. Gilbert, Yi Li, Ely Porat, and Martin J. Strauss · 2014
Later among the works it cites.
Partitioning into expanders
Shayan Oveis Gharan and Luca Trevisan · 2014
Later among the works it cites.
Constant factor approximation for balanced cut in the PIE model
Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan · 2014
Later among the works it cites.
Universal sketches for the frequency negative moments and other decreasing streaming sums
Vladimir Braverman and Stephen R. Chestnut · 2015
Later among the works it cites.
Taylor polynomial estimator for estimating frequency moments
Sumit Ganguly · 2015
Later among the works it cites.
Linear-time list recovery of high-rate expander codes
Brett Hemenway and Mary Wootters · 2015
Later among the works it cites.
Time lower bounds for nonadaptive turnstile streaming algorithms
Kasper Green Larsen, Jelani Nelson, and Huy L. Nguy e ^ ~ \tilde{\hat{\mbox{e}}} n · 2015
Later among the works it cites.
Partitioning well-clustered graphs: Spectral clustering works!
Richard Peng, He Sun, and Luca Zanetti · 2015
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, David P Woodruff, and Zhengyu Wang · 2016
Closest in time.
Beating CountSketch for heavy hitters in insertion streams
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, and David P. Woodruff · 2016
Closest in time.
An optimal algorithm for ℓ 1 \ell_{1} -heavy hitters in insertion streams and related problems
Arnab Bhattacharyya, Palash Dey, and David P. Woodruff · 2016
Closest in time.