Fetching the paper…
Reading the bibliography…
We initiate the study of numerical linear algebra in the sliding window model, where only the most recent $W$ updates in a stream form the underlying data set.
On tail probabilities for martingales
David A. Freedman · 1975
Earlier work this paper cites.
Finite dimensional subspaces of ℓ p \ell_{p}
D Lewis · 1978
Earlier work this paper cites.
Models and issues in data stream systems
Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, and Jennifer Widom · 2002
Earlier work this paper cites.
Maintaining stream statistics over sliding windows
Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani · 2002
Earlier work this paper cites.
Online learning in online auctions
Avrim Blum, Vijay Kumar, Atri Rudra, and Felix Wu · 2003
Earlier work this paper cites.
What’s new: finding significant differences in network data streams
Graham Cormode and S. Muthukrishnan · 2005
Earlier work this paper cites.
Matrix approximation and projective clustering via volume sampling
Amit Deshpande, Luis Rademacher, Santosh Vempala, and Grant Wang · 2006
Earlier work this paper cites.
Adaptive sampling and fast low-rank matrix approximation
Amit Deshpande and Santosh S. Vempala · 2006
Earlier work this paper cites.
A simpler and more efficient deterministic scheme for finding frequent items over sliding windows
Lap-Kei Lee and H. F. Ting · 2006
Earlier work this paper cites.
Optimal multi-scale patterns in time series streams
Spiros Papadimitriou and Philip S. Yu · 2006
Earlier work this paper cites.
Smooth histograms for sliding windows
Vladimir Braverman and Rafail Ostrovsky · 2007
Earlier work this paper cites.
The sliding-window computation model and results
Mayur Datar and Rajeev Motwani · 2007
Earlier work this paper cites.
Streaming in a connected world: querying and tracking distributed data streams
Graham Cormode and Minos N. Garofalakis · 2008
Earlier work this paper cites.
Sampling algorithms and coresets for ℓ p \ell_{p} regression
Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W. Mahoney · 2008
Earlier work this paper cites.
Numerical linear algebra in the streaming model
Kenneth L. Clarkson and David P. Woodruff · 2009
Earlier work this paper cites.
CUR matrix decompositions for improved data analysis
Michael W. Mahoney and Petros Drineas · 2009
Earlier work this paper cites.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2011
Earlier work this paper cites.
Freedman’s inequality for matrix martingales
Joel Tropp · 2011
Earlier work this paper cites.
Twice-ramanujan sparsifiers
Joshua Batson, Daniel A Spielman, and Nikhil Srivastava · 2012
Earlier work this paper cites.
Fast approximation of matrix coherence and statistical leverage
Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, and David P. Woodruff · 2012
Cited alongside, same era.
Approximate frequency counts over data streams
Gurmeet Singh Manku and Rajeev Motwani · 2012
Cited alongside, same era.
Eigenvalues of a matrix in the streaming model
Alexandr Andoni and Huy L. Nguyen · 2013
Cited alongside, same era.
The continuous distributed monitoring model
Graham Cormode · 2013
Cited alongside, same era.
Spectral sparsification in the semi-streaming setting
Jonathan A. Kelner and Alex Levin · 2013
Cited alongside, same era.
How to catch ℓ 2 \ell_{2} -heavy-hitters on sliding windows
Vladimir Braverman, Ran Gelles, and Rafail Ostrovsky · 2014
Cited alongside, same era.
Submodular maximization over sliding windows
Jiecao Chen, Huy L. Nguyen, and Qin Zhang · 2016
Later among the works it cites.
The computational power of optimization in online learning
Elad Hazan and Tomer Koren · 2016
Later among the works it cites.
Beyond matroids: secretary problem and prophet inequality with general constraints
Aviad Rubinstein · 2016
Later among the works it cites.
Matrix sketching over sliding windows
Zhewei Wei, Xuancheng Liu, Feifei Li, Shuo Shang, Xiaoyong Du, and Ji-Rong Wen · 2016
Later among the works it cites.
Input sparsity time low-rank approximation via ridge leverage score sampling
Michael B. Cohen, Cameron Musco, and Christopher Musco · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Real-time detection, tracking and monitoring of automatically discovered events in social media
Miles Osborne, Sean Moran, Richard McCreadie, Alexander Von Lunen, Martin Sykora, Elizabeth Cano, Neil Ireson, Craig MacDonald, Iadh Ounis, Yulan He, Tom Jackson, Fabio Ciravegna, and Ann O’Brien · 2014
Cited alongside, same era.
Fast randomized kernel ridge regression with statistical guarantees
Ahmed El Alaoui and Michael W. Mahoney · 2015
Cited alongside, same era.
Online principal components analysis
Christos Boutsidis, Dan Garber, Zohar Shay Karnin, and Edo Liberty · 2015
Cited alongside, same era.
Clustering on sliding windows in polylogarithmic space
Vladimir Braverman, Harry Lang, Keith Levin, and Morteza Monemizadeh · 2015
Cited alongside, same era.
Dimensionality reduction for k-means clustering and low rank approximation
Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu · 2015
Cited alongside, same era.
Uniform sampling for matrix approximation
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2015
Cited alongside, same era.
Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh · 2017
Later among the works it cites.
Submodular optimization over sliding windows
Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghaddam · 2017
Later among the works it cites.
Dispersion for data-driven algorithm design, online learning, and private optimization
Maria-Florina Balcan, Travis Dick, and Ellen Vitercik · 2018
Closest in time.
Nearly optimal distinct elements and heavy hitters on sliding windows
Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, and Samson Zhou · 2018
Closest in time.
Randomized online matching in regular graphs
Ilan Reuven Cohen and David Wajc · 2018
Closest in time.
Prophet secretary for combinatorial auctions and matroids
Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla · 2018
Closest in time.
Near-optimum online ad allocation for targeted advertising
Joseph (Seffi) Naor and David Wajc · 2018
Closest in time.
Improved algorithms for time decay streams
Vladimir Braverman, Harry Lang, Enayat Ullah, and Samson Zhou · 2019
Closest in time.
Residual based sampling for online low rank approximation
Aditya Bhaskara, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghaddam · 2019
Closest in time.
Tight bounds for online edge coloring
Ilan Reuven Cohen, Binghui Peng, and David Wajc · 2019
Closest in time.
Online matching with general arrivals
Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc · 2019
Closest in time.
Sublinear space private algorithms under the sliding window model
Jalaj Upadhyay · 2019
Closest in time.
Non-adaptive adaptive sampling on turnstile streams
Sepideh Mahabadi, Ilya Razenshteyn, David P. Woodruff, and Samson Zhou · 2020
Closest in time.