近日，中國人民大學高瓴人工智能學院魏哲巍教授團隊與復旦大學教授黃增峰、阿里巴巴集團博士李飛飛合作的論文被數據庫領域國際學術會議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在各種滑動窗口模型中的通用性和最優性。這最終回答了滑動窗口上的矩陣略圖算法的最優空間復雜度下界的開放性問題。此外，我們還利用合成數據集和真實數據集進行了大量實驗，驗證了我們的理論分析，從而從理論和實驗兩方面證實了我們算法的正確性和有效性。