Paper Info
Title
Matrix Sketching Over Sliding Windows.
Abstract
Large-scale matrix computation becomes essential for many data data applications, and hence the problem of sketching matrix with small space and high precision has received extensive study for the past few years. This problem is often considered in the row-update streaming model, where the data set is a matrix A -- Rn x d, and the processor receives a row (1 x d) of A at each timestamp. The goal is to maintain a smaller matrix (termed approximation matrix, or simply approximation) B -- Rl x d as an approximation to A, such that the covariance error |AT A - BTB| is small and l ll n. This paper studies continuous tracking approximations to the matrix defined by a sliding window of most recent rows. We consider both sequence-based and time-based window. We show that maintaining ATA exactly requires linear space in the sliding window model, as opposed to O(d2) space in the streaming model. With this observation, we present three general frameworks for matrix sketching on sliding windows. The sampling techniques give random samples of the rows in the window according to their squared norms. The Logarithmic Method converts a mergeable streaming matrix sketch into a matrix sketch on time-based sliding windows. The Dyadic Interval framework converts arbitrary streaming matrix sketch into a matrix sketch on sequence-based sliding windows. In addition to proving all algorithmic properties theoretically, we also conduct extensive empirical study with real data sets to demonstrate the efficiency of these algorithms.
Year
DOI
Venue
2016
10.1145/2882903.2915228
SIGMOD/PODS'16: International Conference on Management of Data San Francisco California USA June, 2016
Field
DocType
ISBN
Convergent matrix,Essential matrix,Generator matrix,Computer science,Matrix (mathematics),Augmented matrix,Algorithm,State-transition matrix,Sparse matrix,Block matrix
Conference
978-1-4503-3531-7
Citations 
PageRank 
References 
6
0.39
35
Authors
6
Name
Order
Citations
PageRank
Zhewei Wei121520.07
Xuancheng Liu260.39
Feifei Li32242120.05
Shang Shuo438425.35
Xiaoyong Du5882123.29
Ji-Rong Wen64431265.98