近日，中国人民大学高瓴人工智能学院魏哲巍教授团队与复旦大学教授黄增峰、阿里巴巴集团博士李飞飞合作的论文被数据库领域国际学术会议VLDB 2024录用。魏哲巍担任本文通讯作者，其指导的硕士生尹涵燕、博士生文东勰和李家郡分别为第一、二、三作者。VLDB（International Conference on Very Large Data Bases）会议是数据管理与数据库领域的三大国际顶尖学术会议之一，被中国计算机学会（CCF）推荐为A类国际会议。VLDB 2024会议将于8月26-30日在广州召开。

论文介绍

论文题目：Optimal Matrix Sketching over Sliding Windows

论文作者：尹涵燕，文东勰，李家郡，魏哲巍，张骁，黄增峰，李飞飞

通讯作者：魏哲巍

论文概述：矩阵略图旨在用较小的矩阵近似较大的矩阵，流数据上的矩阵略图旨在用一个较小的矩阵维护对不断到来的向量流组成的矩阵的近似，在大规模数据分析和机器学习等领域获得了越来越多的关注。一个著名的确定性矩阵略图算法是Frequent Directions算法，它实现了最优的O(d/ε)空间复杂度，并提供了一个协方差误差保证，即ε=||A⊤A-B⊤B||2/||A||F2。滑动窗口的场景下的矩阵略图的目标是维护对向量流中由最近时间窗口内的输入向量形成的矩阵的近似。尽管过往的研究提出了很多滑动窗口的场景下的矩阵略图算法，但能否在滑动窗口上实现最优的O(d/ε)空间复杂度仍是一个悬而未决的问题。

在本文中，我们介绍了DS-FD算法，它可以在行归一化、基于序列的滑动窗口上实现矩阵略图的最优的O(d/ε)空间复杂度。我们还为基于时间和非归一化的滑动窗口证明了相匹配的空间复杂度的上界和下界，说明了DS-FD在各种滑动窗口模型中的通用性和最优性。这最终回答了滑动窗口上的矩阵略图算法的最优空间复杂度下界的开放性问题。此外，我们还利用合成数据集和真实数据集进行了大量实验，验证了我们的理论分析，从而从理论和实验两方面证实了我们算法的正确性和有效性。