Optimal Approximate Matrix Multiplication over Sliding Windows

vldb26-1063 · Regular Research · Haoming Xian, Qintian Guo, Jun Zhang, Sibo Wang
Abstract

Matrix multiplication is a core operation in numerous applications, yet its exact computation becomes prohibitively expensive as data scales, especially in streaming environments where timeliness is critical. In many real-world scenarios, data arrives continuously, making it essential to focus on recent information via sliding windows. While existing approaches offer approximate solutions, they often suffer from suboptimal space complexities when extended to the sliding-window setting. In this work, we introduce SO-COD, a novel algorithm for approximate matrix multiplication (AMM) in the sliding-window streaming setting, where only the most recent data is retained for computation. Inspired by frequency estimation over sliding windows, our method tracks significant contributions, referred to as ``snapshots'', from incoming data and efficiently updates them as the window advances. Given matrices \(\boldsymbol{X} \in \mathbb{R}^{d_x \times n}\) and \(\boldsymbol{Y} \in \mathbb{R}^{d_y \times n}\) for computing \(\boldsymbol{X} \boldsymbol{Y}^T\), we analyze two data settings. In the \emph{normalized} setting, where each column of the input matrices has a unit \(L_2\) norm, SO-COD achieves an optimal space complexity of \( O\left(\frac{d_x+d_y}{\epsilon}\right) \). In the \emph{unnormalized} setting, where the square of column norms vary within a bounded range \([1, R]\), we show that the space requirement is \( O\left(\frac{d_x+d_y}{\epsilon}\log R\right) \), which matches the theoretical lower bound for an \(\epsilon\)-approximation guarantee. Time complexity analysis further shows that our SO-COD has comparable update time and superior query time compared to existing methods. Extensive experiments on synthetic and real-world datasets demonstrate that SO-COD effectively balances space cost and approximation error, making it a promising solution for large-scale streaming matrix multiplication.

Assigned reviewers

No reviewers assigned yet.

Candidates from the panel ranked by taxonomy affinity

#ReviewerMatchLoadWhy