Optimal Approximate Matrix Multiplication over Sliding Windows

Summary: SO-COD performs approximate matrix multiplication over sliding-window streams by tracking and updating influential “snapshots.” It achieves optimal space: O((d_x+d_y)/ε) normalized and O((d_x+d_y)log R/ε) unnormalized, with competitive updates and faster queries. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14533
Venue: VLDB
Year: 2026
Pagerank: 5.4574671e-05
Overall Rank: 8,247 | 43.42%
DOI: 10.14778/3778092.3778105

Incoming Non-self Citations Over Time

Authors

1. Haoming Xian (Chinese University of Hong Kong)
2. Qintian Guo (Hong Kong University of Science and Technology)
3. Jun Zhang (Bitlink Capital Limited)
4. Sibo Wang (Chinese University of Hong Kong)

BibTeX Citation

@article{xian_vldb26,
        title = {{Optimal Approximate Matrix Multiplication over Sliding Windows}},
        author = {Xian, Haoming and Guo, Qintian and Zhang, Jun and Wang, Sibo},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {3},
        pages = {455--467},
        doi = {10.14778/3778092.3778105},
        url = {https://doi.org/10.14778/3778092.3778105},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,427	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD	5.093636e-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
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
885	Finding Frequent Items in Data Streams	2008	VLDB	0.00013419017
1,968	Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank	2020	VLDB	9.3752727e-05
2,808	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	8.1006881e-05
3,599	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.2710351e-05
3,896	Scaling Attributed Network Embedding to Massive Graphs	2021	VLDB	7.0406415e-05
3,989	Real-Time Influence Maximization on Dynamic Social Streams	2017	VLDB	6.9716774e-05
4,714	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.5497309e-05
5,364	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	6.2472125e-05
6,696	Matrix Sketching Over Sliding Windows	2016	SIGMOD	5.7985588e-05
8,603	Stream Frequency over Interval Queries	2019	VLDB	5.4041343e-05
9,373	Efficient and Accurate PageRank Approximation on Large Graphs	2024	SIGMOD	5.2755515e-05
9,374	Optimal Matrix Sketching over Sliding Windows	2024	VLDB	5.2755515e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,123	Streaming Algorithms with Few State Changes	2024	PODS
2	10,427	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD
3	9,766	On Efficient Large Sparse Matrix Chain Multiplication	2024	SIGMOD
4	7,797	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS
5	691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS
6	8,617	Improving Matrix-vector Multiplication via Lossless Grammar-Compressed Matrices	2022	VLDB
7	12,629	Variance Estimation over Sliding Windows	2007	PODS
8	6,697	Continuous Matrix Approximation on Distributed Data	2014	VLDB
9	9,374	Optimal Matrix Sketching over Sliding Windows	2024	VLDB
10	6,696	Matrix Sketching Over Sliding Windows	2016	SIGMOD