OrchANN在内存不足时高效处理十亿级向量搜索,提升速度并保持精度。
OrchANN: Hierarchical Orchestration for Skewed Out-of-Core Vector Search
- 用分层图抽象实现逻辑重叠,减少冗余数据存储
- 在严格内存限制下,最高提升17.2倍查询吞吐量,延迟降低25倍
- 适合大规模向量搜索场景,尤其适用于内存受限系统
在十亿规模下,近似最近邻搜索(ANNS)常成为超出内存容量的问题:完整的向量集合与索引结构无法放入内存,导致查询性能主要受SSD访问和内存-固态盘间数据传输影响。现有系统难以在精度与效率间取得平衡:物理重叠方法在分区间复制向量或索引条目,扩大了驻留于SSD的索引并增加额外I/O;基于量化的方法虽减少内存占用,但其近似距离可靠性差,通常需从SSD重新检索原始向量以维持召回率,代价高昂。我们提出OrchANN(协同式近似最近邻搜索),一种在严苛内存约束下协调查询路由、分区访问与执行的离线核心ANNS引擎。OrchANN将每个聚类存储为不相交的SSD分区,并采用尺度感知索引;同时,内存中的图抽象提供逻辑重叠,在访问前优化查询路径。服务期间,OrchANN利用图抽象中的查询热度与聚类优先级,剪枝低价值聚类,提升访问局部性。在五个数据集上,严格内存约束下,OrchANN相比当前最优基线,最高实现17.2倍更高每秒查询数(QPS),延迟降低25.0倍,且保持精度不变。
原文摘要 · Abstract (English)
At billion scale, approximate nearest neighbor search (ANNS) often becomes an out-of-core problem: the full vector collection and index structures exceed memory capacity, making query performance dominated by SSD accesses and DRAM-SSD data movement. Existing systems struggle to strike a balance between accuracy and efficiency: physical-overlap methods replicate vectors or index entries across partitions, enlarging the SSD-resident index and incurring extra I/O; quantization-based methods reduce memory usage, but their approximate distances are less reliable and often require costly raw-vector reranking from SSD to preserve recall. We present OrchANN (Orchestrated ANN Search), an out-of-core ANNS engine that orchestrates query routing, partition access, and query execution under tight memory constraints. OrchANN stores each cluster as a disjoint SSD partition with scale-aware indexes, while a memory-resident graph abstraction provides logical overlap before SSD access. During serving, OrchANN uses query hotness and cluster priorities from the graph abstraction to prune low-value clusters and improve access locality. Across five datasets under strict memory constraints, OrchANN delivers up to 17.2x higher QPS and 25.0x lower latency than state-of-the-art baselines, while preserving accuracy.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。