Quake: Adaptive Indexing for Vector Search

一、论文概述

项目	内容
标题	Quake: Adaptive Indexing for Vector Search
作者	Jason Mohoney, Devesh Sarda, Mengze Tang, Shihabur Rahman Chowdhury, Anil Pacaci, Ihab F. Ilyas, Theodoros Rekatsinas, Shivaram Venkataraman
机构	UW-Madison
论文	arXiv:2506.03437
代码	未明确
发布	2025-06
领域	Systems, Vector Search

二、核心思想

问题定义

向量搜索是许多机器学习应用的基础组件，包括检索增强生成、推荐系统和信息检索。然而，现有近似最近邻（ANN）方法在动态和倾斜工作负载下表现不佳，数据分布会随时间演变。

解决方案概述

Quake是一个自适应索引系统，在动态环境中保持低延迟和高召回率。核心创新：

1. 多级分区方案：适应更新和变化的访问模式
2. 成本模型：基于分区大小和访问频率预测查询延迟
3. 召回率估计模型：动态设置查询执行参数
4. NUMA感知并行性：提高内存带宽利用率

三、技术架构

核心设计

组件	说明	关键特点
多级分区	适应数据变化	动态调整
成本模型	预测查询延迟	指导分区决策
召回率估计	动态参数设置	满足召回目标
NUMA感知并行	内存带宽优化	提高搜索效率

关键技术

多级分区方案：

• 适应数据更新和访问模式变化
• 动态调整分区策略
• 保持索引效率

成本模型：

• 基于分区大小和访问频率
• 预测查询延迟
• 指导分区决策

召回率估计模型：

• 动态设置查询执行参数
• 满足召回率目标
• 适应不同查询模式

NUMA感知并行性：

• 优化内存带宽利用
• 提高搜索效率
• 适应现代多核架构

四、核心创新

创新点	说明	理论/实验依据
自适应索引	适应动态工作负载	1.5-38×延迟降低
多级分区	动态调整分区	适应数据变化
成本模型	预测查询延迟	指导优化决策
NUMA感知	内存带宽优化	提高搜索效率

五、实验结果

性能提升

指标	vs SVS, DiskANN, HNSW, SCANN	说明
查询延迟	1.5-38× 降低	动态工作负载
更新延迟	4.5-126× 降低	动态工作负载

关键发现

• 自适应索引在动态工作负载下显著优于静态索引
• 多级分区方案有效适应数据变化
• NUMA感知并行性提高搜索效率

六、相关工作

方向	代表工作	Quake的优势
向量搜索	HNSW, DiskANN	自适应，动态工作负载优化
索引优化	各种ANN方法	多级分区，成本模型
并行搜索	并行ANN	NUMA感知优化

七、总结

核心贡献

1. 自适应索引系统：适应动态和倾斜工作负载
2. 多级分区方案：动态调整分区策略
3. 成本模型和召回率估计：指导优化决策
4. 1.5-38×延迟降低：显著性能提升

技术影响

• 动态工作负载优化：解决现有ANN方法的局限
• 自适应索引：为向量搜索提供新思路
• NUMA感知优化：适应现代多核架构

局限性

• 需要工作负载特征建模
• 可能增加索引维护开销
• 对某些静态工作负载可能收益有限

八、参考资源

• 论文: arXiv:2506.03437
• 机构: UW-Madison
• 应用场景: 向量搜索、RAG、推荐系统