通过利用向量流的连续性,显著提升图索引在实时搜索中的插入效率。
Slipstream: Locality-Aware Graph Index Construction for Streaming Approximate Nearest Neighbor Search

- 新插入点从上一次的候选集开始搜索,而非从入口点重搜。
- 在五个数据集上实现最高30.8倍吞吐提升,召回率保持0.95以上。
- 适用于实时向量流场景,如推荐系统、在线相似性检索。
图索引广泛用于高召回率近似最近邻搜索(ANNS),但在实时应用中需支持流式ANNS。此类场景下,新到达的嵌入向量需在更新图边前搜索现有图以获取候选邻居,导致频繁重建索引成为流式数据摄入的瓶颈。本文提出Slipstream,一种显著降低图索引中频繁插入计算开销的新方法。其核心思想是利用向量流的连续性:新点从上一次插入时发现的优质候选集出发,而非从入口点重新搜索。技术上,Slipstream评估不同起始候选子集,并由自适应控制器根据流稳定性动态调整搜索范围。我们进一步证明Slipstream非纯启发式:构建抽象模型分析其性能并推导理论边界。已在Faiss和HNSWLib两个主流开源库中实现,与四种基线方法在五个流式向量数据集上对比。实验表明,Slipstream在维持至少0.95召回率@10的前提下,端到端吞吐最高提升30.8倍。
原文摘要 · Abstract (English)
Graph indexes are widely used for high-recall approximate nearest neighbor search (ANNS), but many real-time applications require streaming ANNS. In these real-time applications, continuously arriving embeddings must search the existing graph for candidate neighbors before updating graph edges, which makes repeated index construction a bottleneck for streaming ingestion workloads. We propose Slipstream, a new method that significantly reduces the computational cost of frequent insertions in graph indexes for ANNS. The core idea of Slipstream is exploiting the continuity in vector streams: the newly arrived point starts from promising candidates found during the previous insertion rather than searching from the entry point. More technically, Slipstream evaluates distinct subsets of starting candidates followed by an adaptive controller that narrows or widens the range according to the stream's stability. We further show that Slipstream is beyond heuristic: We derive an abstract model to characterize Slipstream's performance and analyze its theoretical bounds. We have implemented Slipstream in two popular open-source libraries (Faiss, HNSWLib) and compared it with four baseline methods on five streaming vector datasets. Experimental results show that Slipstream achieves up to 30.8$\times$ higher end-to-end throughput than baselines while maintaining at least 0.95 recall@10.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。