先进数据系统实验室

北京时间2023年7月15日，SOSP 2023公布了论文入选结果，我实验室与微软亚洲研究院联合完成的论文“SPFresh: Incremental In-Place Update for Billion-Scale Vector Search”成功入选 SOSP 2023 会议！本届会议共收到229篇投稿，最终接受43篇，录用率18.8%。向各位参与研究工作的老师、同学、合作者表示祝贺！

论文简介：

近似最近邻搜索（Approximate Nearest Neighbor Search, ANNS）在信息检索、问答系统、推荐系统等领域具有广泛应用。索引是ANNS能高效准确搜索的关键，随着向量数据规模的不断增长，对向量索引更新的支持变得越发重要。

然而，由于向量数据通常具有极高的维度，识别单个新向量的准确最近邻居通常代价很高，而这正是索引更新所必需的过程。为了分担更新的开销，现有系统维护一个辅助索引来累积更新，然后通过全局重建整个索引将其合并到主索引中。但是这种方法的搜索延迟和准确性波动较大，而且需要大量资源，在重新构建时耗时严重。

我们的系统SPFresh是一个支持In-Place更新的系统。SPFresh的核心是LIRE，一种轻量级的增量再平衡协议，用于分割向量分区并重新分配分区中的向量以适应数据分布的变化。LIRE通过仅在分区边界处重新分配向量来实现低开销的向量更新。在高质量的向量索引中，边界向量的数量通常很少。借助LIRE，SPFresh在十亿规模的基于磁盘的向量索引中，每日向量更新率为1%的情况下，相较于当前最先进的解决方案仅需1%的DRAM和不到10%的CPU核心，就能提供优越的查询延迟和准确性。

该项工作是由我实验室博士在读生徐宇鸣、硕士在读生梁恒宇，哈佛大学在读博士生李缙（2020-2022，ADSL实验室实习生），李诚副教授，以及微软亚洲研究院的杨凡，陈琪，徐烁韬，张虔熙等老师联合完成的。