实验室一项成果(SPFresh)被计算机系统领域国际顶会SOSP 2023接收
Posted on 2023-07-15

北京时间2023715日,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通过仅在分区边界处重新分配向量来实现低开销的向量更新。在高质量的向量索引中,边界向量的数量通常很少。借助LIRESPFresh在十亿规模的基于磁盘的向量索引中,每日向量更新率为1%的情况下,相较于当前最先进的解决方案仅需1%DRAM和不到10%CPU核心,就能提供优越的查询延迟和准确性。

 

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


地址:安徽省合肥市蜀山区复兴路 中国科学技术大学(高新校区)信智大楼 702 703 710室
电话:0551-63602430

Copyright © 2023 先进数据系统实验室 All Rights Reserved

网站制作与维护:卫来科技 提供