Matrix Sketching Over Sliding Windows

Summary: Matrix sketching over sliding windows: time- and sequence-based continuous tracking of A^T A with l<<n. Shows linear-space needs for exact covariance in sliding windows vs O(d^2) streaming; proposes three frameworks—norm-sampling, Logarithmic Method, Dyadic Interval—with empirical validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5317
Venue: SIGMOD
Year: 2016
Pagerank: 5.7985588e-05
Overall Rank: 6,696 | 54.07%
DOI: 10.1145/2882903.2915228

Incoming Non-self Citations Over Time

Authors

1. Zhewei Wei (Renmin University of China)
2. Xuancheng Liu (Renmin University of China)
3. Feifei Li (University of Utah)
4. Shuo Shang (Renmin University of China)
5. Xiaoyong Du (Renmin University of China)
6. Ji-Rong Wen (Renmin University of China)

BibTeX Citation

@inproceedings{wei_sigmod16,
        title = {{Matrix Sketching Over Sliding Windows}},
        author = {Wei, Zhewei and Liu, Xuancheng and Li, Feifei and Shang, Shuo and Du, Xiaoyong and Wen, Ji-Rong},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915228},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915228},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,247	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB	5.4574671e-05
8,268	Efficient Matrix Sketching over Distributed Data	2017	PODS	5.4574671e-05
9,374	Optimal Matrix Sketching over Sliding Windows	2024	VLDB	5.2755515e-05
10,427	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD	5.093636e-05
11,519	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
451	Mergeable Summaries	2012	PODS	0.00018151445
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
1,252	Streaming Pattern Discovery in Multiple Time-Series	2005	VLDB	0.00011483752
2,441	Optimal Multi-scale Patterns in Time Series Streams	2006	SIGMOD	8.5779023e-05
2,753	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	8.1647557e-05
3,721	Database-friendly Random Projections	2001	PODS	7.1736703e-05
6,697	Continuous Matrix Approximation on Distributed Data	2014	VLDB	5.7985588e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,793	Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix	2021	SIGMOD
2	5,946	Streaming Anomaly Detection Using Randomized Matrix Sketching	2016	VLDB
3	2,576	Optimal Sampling from Sliding Windows	2009	PODS
4	12,629	Variance Estimation over Sliding Windows	2007	PODS
5	8,268	Efficient Matrix Sketching over Distributed Data	2017	PODS
6	7,713	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
7	6,697	Continuous Matrix Approximation on Distributed Data	2014	VLDB
8	10,427	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD
9	8,247	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB
10	9,374	Optimal Matrix Sketching over Sliding Windows	2024	VLDB