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: h12b333c9cdff5767
Venue: SIGMOD
Year: 2016
Pagerank: 5.6684547e-05
Overall Rank: 6,832 | 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,415	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB	5.3350162e-05
8,434	Efficient Matrix Sketching over Distributed Data	2017	PODS	5.3350162e-05
9,559	Optimal Matrix Sketching over Sliding Windows	2024	VLDB	5.1571823e-05
10,616	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD	4.9793485e-05
11,828	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.9793485e-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.00052121228
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
456	Mergeable Summaries	2012	PODS	0.0001791284
710	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014608975
1,278	Streaming Pattern Discovery in Multiple Time-Series	2005	VLDB	0.00011231952
2,497	Optimal Multi-scale Patterns in Time Series Streams	2006	SIGMOD	8.3861855e-05
2,807	Sampling Time-Based Sliding Windows in Bounded Space	2008	SIGMOD	7.982663e-05
3,784	Database-friendly Random Projections	2001	PODS	7.0223112e-05
6,833	Continuous Matrix Approximation on Distributed Data	2014	VLDB	5.6684547e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,910	Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix	2021	SIGMOD
2	6,066	Streaming Anomaly Detection Using Randomized Matrix Sketching	2016	VLDB
3	2,624	Optimal Sampling from Sliding Windows	2009	PODS
4	12,919	Variance Estimation over Sliding Windows	2007	PODS
5	8,434	Efficient Matrix Sketching over Distributed Data	2017	PODS
6	7,870	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
7	6,833	Continuous Matrix Approximation on Distributed Data	2014	VLDB
8	10,616	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD
9	8,415	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB
10	9,559	Optimal Matrix Sketching over Sliding Windows	2024	VLDB