AeroSketch : Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams Journal: PACMMOD Volume: 4 1 (SIGMOD) 8 2 DOI: 10.1145/3786622 CCS: Theory of computation Sketching and sampling CCS: Theory of computation Data compression CCS: Theory of computation Vecto
Hanyan Yin, Dongxie Wen, Jiajun Li, Zhewei Wei, Xiao Zhang, Peng Zhao, Zhi-Hua Zhou · 2026
Read AeroSketch : Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams Journal: PACMMOD Volume: 4 1 (SIGMOD) 8 2 DOI: 10.1145/3786622 CCS: Theory of computation Sketching and sampling CCS: Theory of computation Data compression CCS: Theory of computation Vecto by Hanyan Yin, Dongxie Wen, Jiajun Li, Zhewei Wei, Xiao Zhang, Peng Zhao, Zhi-Hua Zhou (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-02019.txt.
Introduction
Data streams arrive too fast to store, so matrix sketching keeps a compact summary that approximates the whole. Hanyan Yin and six co-authors note that leading sketches pay for their compactness with repeated matrix factorizations that can cost cubic time per update, throttling throughput exactly when error bounds are tight.
AeroSketch applies randomized numerical linear algebra to keep optimal space and communication costs while cutting update time to near-optimal, effectively quadratic under tight error demands. It handles persistent streams, sliding windows that forget old data, and distributed settings where summaries must merge. Experiments on synthetic and real datasets show consistently higher update throughput than state-of-the-art methods at comparable approximation quality.
Catalog record
| CREATOR | Hanyan Yin, Dongxie Wen, Jiajun Li, Zhewei Wei, Xiao Zhang, Peng Zhao, Zhi-Hua Zhou |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 156 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-02019
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
AeroSketch : Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams Journal: PACMMOD Volume: 4 1 (SIGMOD) 8 2 DOI: 10.1145/3786622 CCS: Theory of computation Sketching and sampling CCS: Theory of computation Data compression CCS: Theory of computation Vector / streaming algorithms Hanyan Yin, Dongxie Wen, Jiajun Li, Zhewei Wei, Xiao Zhang, Peng Zhao, Zhi-Hua Zhou Abstract . Many real-world matrix datasets arrive as high-throughput vector streams, making it impractical to store or process them in their entirety. To enable real-time analytics under limited computational, memory, and communication resources, matrix sketching techniques have been developed over recent decades to provide compact approximations of such streaming data. Some algorithms have achieved optimal space and communication complexity. However, these approaches often require frequent time-consuming matrix factorization operations. In particular, under tight approximation error bounds, each matrix factorization computation incurs cubic time complexity, thereby limiting their update efficiency. In this paper, we introduce AeroSketch , a novel matrix sketching framework that leverages recent advances in randomized numerical linear algebra (RandNLA). AeroSketch achieves optimal communication and space costs while delivering near-optimal update time complexity (within logarithmic factors) across persistent, sliding window, and distributed streaming scenarios. Extensive experiments on both synthetic and real-world datasets demonstrate that AeroSketch consistently outperforms state-of-the-art methods in update throughput. In particular, under tight approximation error constraints, AeroSketch reduces the cubic time complexity to the quadratic level. Meanwhile, it maintains comparable approximation quality while retaining optimal communication and space costs. † † cc-license: by 1. Introduction Many types of real-world data—such as computer network traffic ( Xia et al. 2014 ; Kim et al. 2020 ) , online machine learning ( Kuzborskij et al. 2019 ; Chen et al. 2020 ; Wen et al. 2025 ; Chen et al. 2022 ; Wen et al. 2024 ) , and sensor data ( Xie et al. 2023 ; Aquino et al. 2007 ) —are continuously generated as vast, high-velocity streams of vectors ( Zhou 2024 ; Wang et al. 2024 ; Muthukrishnan 2005 ) . Storing even a reasonable portion of these streams in memory is impractical. Therefore, it is necessary to design online algorithms that process one vector at a time and immediately discard it, enabling real-time processing with reduced memory usage at the cost of some precision. Such compact representations are known as matrix sketching ( Cormode and Yi 2020 ; Liberty 2013 ; Woodruff 2014 ; Desai et al. 2016 ; Kacham 2024 ) . Table 1 . Given the dimension d of each row vector (for tracking approximate matrix multiplication over sliding window (Problem 4 ), there are two vector streams with dimensions d_{x} and d_{y} , respectively), the upper bound on the relative covariance error \varepsilon , the norm of each row \left\|\bm{a}_{i}\right\|_{2}^{2}\in\left[1,R\right] , and the number of sites m (in distributed scenarios), this table presents an overview of the communication/space and amortized update time complexities of algorithms addressing a wide range of matrix sketching problems. Here, \delta\in(0,0.01) denotes the upper bound on failure probability; that is, each listed complexity bound holds for an algorithm that returns a matrix sketch satisfying the stated error guarantees with probability at least 1-\delta . ✓ indicates that the asymptotic complexity is optimal; — indicates that it is not optimal; and ✓ * denotes near-optimal complexity (up to a logarithmic factor). Problem Scenarios Methods Space / Communication Amortized Update Time Complexity Full Stream Matrix Sketch (Problem 1 ) Frequent Directions ( Liberty 2013 ; Ghashami et al. 2016 ) O\left(\frac{d}{\varepsilon}\right) ✓ O\left(\frac{d}{\varepsilon}\right) ✓ Tracking Matrix Sketch Problem (Scenario 1) Tracking Matrix Sketch over Sliding Window (Problem 2 ) Fast-DS-FD ( Yin et al. 2024 ) O\left(\frac{d}{\varepsilon}\log R\right) ✓ O\left(\left(\frac{d}{\varepsilon}+\frac{1}{\varepsilon^{3}}\right)\log R\right) — [Theorem 3.1 ] O\left(\frac{d}{\varepsilon}\log R\right) ✓ O\left(\frac{d}{\varepsilon}\log d\log R\right) ✓ * [Corollary 3.2 ] O\left(\frac{d}{\varepsilon}\log R\right) ✓ O\left(\frac{d}{\varepsilon}\log d\log R\log^{2}\frac{1}{\delta}\right) ✓ * Tracking Persistent Matrix Sketch (ATTP, Problem 3 ) ATTP-FD ( Shi et al. 2021 ) O\left(\frac{d}{\varepsilon}\log\|\bm{A}\|_{F}^{2}\right) ✓ O\left(\frac{d}{\varepsilon^{2}}\right) — [Theorem 4.1 ] O\left(\frac{d}{\varepsilon}\log\|\bm{A}\|_{F}^{2}\right) ✓ O\left(\frac{d}{\varepsilon}\log d\log^{2}\frac{1}{\delta}\right) ✓ * Tracking Approximate Matrix Multiplication over Sliding Window (Problem 4 ) ML-SO-COD ( Xian et al. 2025 ) hDS-COD ( Yao et al. 2025 ) O\left(\frac{d_{x}+d_{y}}{\varepsilon}\log R\right) ✓ O\left(\left(\frac{d_{x}+d_{y}}{\varepsilon}+\frac{1}{\varepsilon^{3}}\right)\log R\right) — [Theorem 4.2 ] O\left(\frac{d_{x}+d_{y}}{\varepsilon}\log R\right) ✓ O\left(\frac{d_{x}+d_{y}}{\varepsilon}\log d\log R\log^{2}\frac{1}{\delta}\right) ✓ * Tracking Distributed Matrix Sketch Problem (Scenario 2) Tracking Matrix Sketch over Distributed Sites (Problem 5 ) P2 ( Ghashami et al. 2014 ) O\left(\frac{md}{\varepsilon}\log\left\|\bm{A}\right\|_{F}^{2}\right) ✓ O\left(\frac{d}{\varepsilon^{2}}\right) — [Theorem 4.3 ] O\left(\frac{md}{\varepsilon}\log\left\|\bm{A}\right\|_{F}^{2}\right) ✓ O\left(\frac{d}{\varepsilon}\log d\log^{2}\frac{1}{\delta}\right) ✓ * Tracking Matrix Sketch over Distributed Sliding Window (Problem 6 ) DA2 ( Zhang et al. 2017 ) O\left(\frac{md}{\varepsilon}\log\left\|\bm{A}\right\|_{F}^{2}\right) ✓ O\left(\frac{d}{\varepsilon^{2}}\right) — [Theorem 4.4 ] O\left(\frac{md}{\varepsilon}\log\left\|\bm{A}\right\|_{F}^{2}\right) ✓ O\left(\frac{d}{\varepsilon}\log d\log^{2}\frac{1}{\delta}\right) ✓ * We observe that a range of matrix sketching problems over vector streams—including tracking persistent matrix sketches ( Shi et al. 2021 ) , matrix sketches over sliding windows ( Wei et al. 2016 ; Yin et al. 2024 ) , distributed matrix sketches ( Ghashami et al. 2014 ; Zhang et al. 2017 ) , and approximate matrix multiplication ( Xian et al. 2025 ; Yao et al. 2025 ) —can be reduced to two fundamental tasks: tracking matrix sketch problem with limited memory (Scenario 1) and tracking distributed matrix sketch problem over bandwidth-constrained channels (Scenario 2), as categorized in Table 1 . The primary optimization metrics of matrix sketch algorithms are space cost (for Scenario 1), communication cost (for Scenario 2), and time cost (for both Scenarios 1 and 2). Extensive research has been dedicated to developing efficient matrix sketch algorithms for various problem settings ( Liberty 2013 ; Ghashami et al. 2016 ; Ghashami and Phillips 2014 ; Shi et al. 2021 ; Zhang et al. 2017 ; Ghashami et al. 2014 ; Wei et al. 2016 ; Yin et al. 2024 ; Xian et al. 2025 ; Yao et al. 2025 ) , as well as theoretically analyzing the relationships among approximation quality, space/communication cost, and time complexity ( Huang et al. 2017 ; Huang et al. 2021 ; Ghashami et al. 2016 ; Liberty 2022 ; Yin et al. 2024 ) . ( Huang et al. 2017 ; Huang et al. 2021 ) proved a lower bound on the communication cost for the distributed deterministic matrix sketch problem. In other words, any deterministic matrix sketching algorithm that solves the problem under Scenario 2 must incur a communication cost of at least a certain number of bits. The corresponding lower bounds for the space complexities under Scenario 1 have also been proved by other researchers ( Ghashami et al. 2016 ; Yin et al. 2024 ; Xian et al. 2025 ; Yao et al. 2025 ) . In addition to the theoretical results, numerous specific matrix sketch algorithms have been proposed. Some of them have the same asymptotic communication/space complexity as the theoretical lower bound, indicating that the sketch algorithms have achieved optimal communication/space costs, as listed in Table 1 and marked by ✓ . Despite their superiority in communication/space complexity, these algorithms often suffer from high computational costs, especially under tight approximation error bounds and over high-dimensional vector streams of dimension d . Their asymptotic time complexities are suboptimal compared with the time lower bound proved by Huang ( Huang 2019 ) (marked by — in Table