2016

Coresets and Sketches

Phillips, Jeff M.

Understand

Geometric data summarization has become an essential tool in both geometric approximation algorithms and where geometry intersects with big data problems.

In linear or near-linear time large data sets can be compressed into a summary, and then more intricate algorithms can be run on the summaries whose results approximate those of the full data set.
Coresets and sketches are the two most important classes of these summaries.
We survey five types of coresets and sketches: shape-fitting, density estimation, high-dimensional vectors, high-dimensional point sets / matrices, and clustering.

Built on

An algorithm for quadratic programming
M. Frank and P. Wolfe · 1956
Earlier work this paper cites.
On the uniform convergence of relative frequencies of events to their probabilities
V. Vapnik and A. Chervonenkis · 1971
Earlier work this paper cites.
Decomposable searching problems I: Static-to-dynamic transformations
J.L. Bentley and J.B. Saxe · 1980
Earlier work this paper cites.
Finding repeated elements
J. Misra and D. Gries · 1982
Earlier work this paper cites.
Finding least-distance lines
N. Meggido and A. Tamir · 1983
Earlier work this paper cites.
Extensions of Lipschitz mappings into a Hilbert space
W.B. Johnson and J. Lindenstrauss · 1984
Earlier work this paper cites.
Probabilistic counting algorithms for data base applications
P. Flajolet and G.N. Martin · 1985
Earlier work this paper cites.
Clustering to minimize the maximum intercluster distance
T.F. Gonzalez · 1985
Earlier work this paper cites.
Epsilon nets and simplex range queries
D. Haussler and E. Welzl · 1987
Earlier work this paper cites.
How to net a lot with a little: small
J. Matoušek, R. Seidel, and E. Welzl · 1990
Earlier work this paper cites.
On linear-time deterministic algorithms for optimization problems in fixed dimensions
B. Chazelle and J. Matoušek · 1996
Earlier work this paper cites.
Approximation Algorithms for NP-Hard problems
D. Hochbaum · 1997
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.
The Discrepancy Method
B. Chazelle · 2000
Earlier work this paper cites.
Space-efficient online computation of quantile summaries
M. Greenwald and S. Khanna · 2001
Earlier work this paper cites.
Improved bounds on the samples complexity of learning
Y. Li, P. Long, and A. Srinivasan · 2001
Earlier work this paper cites.
Exact and approximate algorithms for clustering
P.K. Agarwal and C.M. Procopiuc · 2002
Earlier work this paper cites.
Frequency estimation of internet packet streams with limited space
E.D. Demaine, A. Lopez-Ortiz, and J.I. Munro · 2002
Earlier work this paper cites.
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
D. Achlioptas · 2003
Earlier work this paper cites.
Smaller core-sets for balls
M. Bădoiu and K.L. Clarkson · 2003
Earlier work this paper cites.
Loglog counting of large cardinalities
M. Durand and P. Flajolet · 2003
Earlier work this paper cites.
An elementary proof of a theorem of Johnson and Lindenstrauss
S. Dasgupta and A. Gupta · 2003
Earlier work this paper cites.
A simple algorithm for finding frequent elements in streams and bags
R.M. Karp, S. Shenker, and C.H. Papadimitriou · 2003
Earlier work this paper cites.
Approximating extent measure of points
P.K. Agarwal, S. Har-Peled, and K. Varadarajan · 2004
Earlier work this paper cites.
Finding frequent items in data streams
M. Charikar, K. Chen, and M. Farach-Colton · 2004
Earlier work this paper cites.
Clustering large graphs via the singular value decomposition
P. Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay · 2004
Earlier work this paper cites.
Fast Monte-Carlo algorithms for finding low-rank approximations
A. Frieze, R. Kannan, and S. Vempala · 2004
Earlier work this paper cites.
Clustering motion
S. Har-Peled · 2004
Earlier work this paper cites.
No coreset, no cry
S. Har-Peled · 2004
Earlier work this paper cites.
High-dimensional shape fitting in linear time
S. Har-Peled and K. Varadarajan · 2004
Earlier work this paper cites.
Shape fitting with outliers
S. Har-Peled and Y. Wang · 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.
Data streams: Algorithms and applications
S. Muthukrishnan · 2005
Earlier work this paper cites.
Core vector machines: Fast SVM training on very large data sets
I.W. Tsang, J.T. Kwok, and P.-M. Cheung · 2005
Earlier work this paper cites.
Faster core-set constructions and data-stream algorithms in fixed dimensions
T.M. Chan · 2006
Earlier work this paper cites.
Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix
P. Drineas, R. Kannan, and M.W. Mahoney · 2006
Earlier work this paper cites.
Adaptive sampling and fast low-rank matrix approximation
A. Deshpande and S. Vempala · 2006
Earlier work this paper cites.
Coresets for discrete integration and clustering
S. Har-Peled · 2006
Earlier work this paper cites.

Similar

An integrated efficient solution for computing frequent and top-
A. Metwally, D. Agrawal, and A. Abbadi · 2006
Cited alongside, same era.
Improved approximation algorithms for large matrices via random projections
T. Sarlos · 2006
Cited alongside, same era.
Range counting over multidimensional data streams
S. Suri, C.D. Tóth, and Y. Zhou · 2006
Cited alongside, same era.
Geometric approximations via coresets
P.K. Agarwal, S. Har-Peled, and K. Varadarajan · 2007
Cited alongside, same era.
A space-optimal data-stream algorithm for coresets in the plane
P.K. Agarwal and H. Yu · 2007
Cited alongside, same era.
Deterministic sampling and range counting in geometric data streams
A. Bagchi, A. Chaudhary, D. Eppstein, and M. Goodrich · 2007
Cited alongside, same era.
Improved approximation algorithms for geometric set cover
K.L. Clarkson and K. Varadarajan · 2007
Cited alongside, same era.
A PTAS for
D. Feldman, M. Monemizedah, and C. Sohler · 2007
Cited alongside, same era.
Smaller coresets for
S. Har-Peled and A. Kushal · 2007
Cited alongside, same era.
Robust shape fitting via peeling and grating coresets
P.K. Agarwal, S. Har-Peled, and H. Yu · 2008
Cited alongside, same era.
Optimal coresets for balls
M. Bădoiu and K.L. Clarkson · 2008
Cited alongside, same era.
Relative-error CUR matrix decompositions
P. Drineas, M.W. Mahoney, and S. Muthukrishnan · 2008
Cited alongside, same era.

Then

Fast approximation of matrix coherence and statistical leverage
P. Drineas, M. Magdon-Ismail, M.W. Mahoney, and D.P. Woodruff · 2012
Later among the works it cites.
Data reduction for weighted and outlier-resistant clustering
D. Feldman and L.J. Schulman · 2012
Later among the works it cites.
Sparse quadratic forms and their geometric applications (after Batson, Spielman and Srivastava)
A. Naor · 2012
Later among the works it cites.
On the sensitivity of shape fitting problems
K. Varadarajan and X. Xiao · 2012
Later among the works it cites.
Mergeable summaries
P.K. Agarwal, G. Cormode, Z. Huang, J. Phillips, Z. Wei, and K. Yi · 2013
Later among the works it cites.
Near-optimal coresets for least-squares regression
C. Boutsidis, P. Drineas, and M. Magdon-Ismail · 2013
Later among the works it cites.
Deterministic discrepancy minimization
N. Bansal and J. Spencer · 2013
Later among the works it cites.
Low rank approximation and regression in input sparsity time
K. L. Clarkson and D.P. Woodruff · 2013
Later among the works it cites.
Turning big data into tiny data: Constant-size coresets for
D. Feldman, M. Schmidt, and C. Sohler · 2013
Later among the works it cites.
Simple and deterministic matrix sketching
E. Liberty · 2013
Later among the works it cites.
OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
J. Nelson and H.L. Nguyen · 2013
Later among the works it cites.
ε \varepsilon -Samples for kernels
J.M. Phillips · 2013
Later among the works it cites.
Tight lower bounds for the size of epsilon-nets
J. Pach and G. Tardos · 2013
Later among the works it cites.
Subspace embeddings and lp regression using exponential random variables
D.P. Woodruff and Q. Zhang · 2013
Later among the works it cites.
Near optimal column-based matrix reconstruction
C. Boutsidis, P. Drineas, and M. Magdon-Ismail · 2014
Later among the works it cites.
Twice-Ramanujan sparsifiers
J.D. Batson, D.A. Spielman, and N. Srivastava · 2014
Later among the works it cites.
Optimal CUR decompositions
C. Boutsidis and D.P. Woodruff · 2014
Later among the works it cites.
The fast Cauchy transform and faster robust linear regression
Original
K.L. Clarkson, P. Drineas, M. Magdon-Ismail, M.W. Mahoney, X. Meng, and D.P. Woodruff · 2014
Later among the works it cites.
Relative errors for deterministic low-rank matrix approximations
M. Ghashami and J.M. Phillips · 2014
Later among the works it cites.
(Nearly) Space-optimal sparse Fourier transform
P. Indyk, M. Kapralov, and E. Price · 2014
Later among the works it cites.
On range searching in the group model and combinatorial discrepancy
K.G. Larsen · 2014
Later among the works it cites.
Smallest enclosing ball for probabilistic data
A. Munteanu, C. Sohler, and D. Feldman · 2014
Later among the works it cites.
Sketching as a tool for numerical linear algebra
D.P. Woodruff · 2014
Later among the works it cites.
Streaming algorithms for extent problems in high dimensions
P.K. Agarwal and R. Sharathkumar · 2015
Later among the works it cites.
Dimensionality reduction for
M.B. Cohen, S. Elder, C. Musco, C. Musco, and M. Persu · 2015
Later among the works it cites.
Uniform sampling for matrix approximation
M.B. Cohen, Y.T. Lee, C. Musco, C. Musco, R. Peng, and A. Sidford · 2015
Later among the works it cites.
Input sparsity and hardness for robust subspace approximation
K.L. Clarkson and D.P. Woodruff · 2015
Later among the works it cites.
Sketching for M-estimators: A unified approach to robust regression
K.L. Clarkson and D.P. Woodruff · 2015
Later among the works it cites.
More constraints, smaller coresets: Constrained matrix approximation of sparse big data
D. Feldman and T. Tassa · 2015
Later among the works it cites.
Dimensionality reduction of massive sparse datasets using coresets
Original
D. Feldman, M. Volkov, and D. Rus · 2015
Later among the works it cites.
Frequent directions: Simple and deterministic matrix sketching
Original
M. Ghashami, E. Liberty, J.M. Phillips, and D.P. Woodruff · 2015
Later among the works it cites.
Factorization norms and hereditary discrepancy
Original
J. Matoušek, A. Nikolov, and K. Talwar · 2015
Later among the works it cites.
Subsampling in smooth range spaces
J.M. Phillips and Y. Zheng · 2015
Later among the works it cites.
Sparse approximation via generating point sets
A. Blum, S. Har-Peled, and B. Raichel · 2016
Closest in time.
The optimal sample complexity of PAC learning
S. Hanneke · 2016
Closest in time.
ε \varepsilon -Kernel coresets for stochastic points
L. Huang, J. Li, J.M. Phillips, and H. Wang · 2016
Closest in time.
Optimal quantile approximation in streams
Original
Z. Karnin, K. Lang, and E. Liberty · 2016
Closest in time.

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…