Optimal Approximate Matrix Multiplication over Sliding Windows

Summary: SO-COD: sliding-window AMM that tracks frequency-estimation style “snapshots” of incoming columns to maintain X Y^T with efficient updates. Provable optimal space O((d_x+d_y)/ε) (normalized) and O(((d_x+d_y)/ε)·log R) (unnormalized), matching lower bounds and offering faster queries. (summarized by gpt-5-mini on Mar 13 2026)

Paper ID: 14332
Venue: VLDB
Year: 2026
Pagerank: 4.613363e-05
Overall Rank: 7,929 | 44.84%
DOI: 10.14778/3778092.3778105

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,138	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
166	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00039361552
835	Finding Frequent Items in Data Streams	2008	VLDB	0.00016109621
848	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.0001597308
1,474	Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank	2020	VLDB	0.00011825229
2,759	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	8.1636123e-05
3,803	Scaling Attributed Network Embedding to Massive Graphs	2021	VLDB	6.7550628e-05
4,080	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	6.4652983e-05
4,371	Real-Time Influence Maximization on Dynamic Social Streams	2017	VLDB	6.2459569e-05
5,655	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	5.387631e-05
6,647	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	4.9772122e-05
6,774	Matrix Sketching Over Sliding Windows	2016	SIGMOD	4.9299348e-05
8,594	Stream Frequency over Interval Queries	2019	VLDB	4.4891331e-05
9,214	Efficient and Accurate PageRank Approximation on Large Graphs	2024	SIGMOD	4.3716847e-05
9,215	Optimal Matrix Sketching over Sliding Windows	2024	VLDB	4.3716847e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,901	Streaming Algorithms with Few State Changes	2024	PODS	4.1945683e-05
10,138	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD	4.1945683e-05
9,670	On Efficient Large Sparse Matrix Chain Multiplication	2024	SIGMOD	4.3066148e-05
6,755	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	4.9383139e-05
848	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.0001597308
8,657	Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices	2022	VLDB	4.4730648e-05
12,435	Variance Estimation over Sliding Windows	2007	PODS	4.1945683e-05
6,602	Continuous Matrix Approximation on Distributed Data	2014	VLDB	4.9971153e-05
9,215	Optimal Matrix Sketching over Sliding Windows	2024	VLDB	4.3716847e-05
6,774	Matrix Sketching Over Sliding Windows	2016	SIGMOD	4.9299348e-05