arXiv:2507.11907cs.DBcs.IR2025-07被引 24

通过构建多索引集合,高效实现带复杂条件的向量搜索。

SIEVE: Effective Filtered Vector Search with Collection of Indexes

  • 构建多个针对不同查询条件的索引,避免遍历受限
  • 在低至1%构建时间下实现最高8.06倍加速
  • 适合需要高灵活性和快速响应的推荐系统

许多实际任务(如查找带有‘儿童’标签的视频)可归结为在满足硬约束条件下寻找最相似的向量。这类过滤向量搜索挑战极大,因现有基于图的相似性搜索技术在引入复杂约束后性能迅速下降:其依赖足够连通性以在少数跳数内到达最相似项。现有方法尝试修改图遍历仅访问可能满足约束的项,但对多数约束无法保持少跳特性,要么限制约束形式,要么效率骤降。本文提出反向思路:不约束遍历,而是构建多个服务不同约束形式的索引。为高效构建,设计三维分析模型,捕捉索引大小、搜索时间和召回率间关系,采用工作负载感知策略将尽可能多的有效索引打包成集合。查询时再次利用该模型,选择在给定召回率下最快搜索的索引。实验表明,在不同选择性和约束形式的数据集上均表现优越:相比其他索引,构建时间低至1%,速度提升达8.06倍,内存开销低于标准HNSW图的2.15倍,且仅需少量历史工作负载知识。

原文摘要 · Abstract (English)

Many real-world tasks such as recommending videos with the kids tag can be reduced to finding most similar vectors associated with hard predicates. This task, filtered vector search, is challenging as prior state-of-the-art graph-based (unfiltered) similarity search techniques quickly degenerate when hard constraints are considered. That is, effective graph-based filtered similarity search relies on sufficient connectivity for reaching the most similar items within just a few hops. To consider predicates, recent works propose modifying graph traversal to visit only the items that may satisfy predicates. However, they fail to offer the just-a-few-hops property for a wide range of predicates: they must restrict predicates significantly or lose efficiency if only a small fraction of items satisfy predicates. We propose an opposite approach: instead of constraining traversal, we build many indexes each serving different predicate forms. For effective construction, we devise a three-dimensional analytical model capturing relationships among index size, search time, and recall, with which we follow a workload-aware approach to pack as many useful indexes as possible into a collection. At query time, the analytical model is employed yet again to discern the one that offers the fastest search at a given recall. We show superior performance and support on datasets with varying selectivities and forms: our approach achieves up to 8.06x speedup while having as low as 1% build time versus other indexes, with less than 2.15x memory of a standard HNSW graph and modest knowledge of past workloads.

向量搜索索引优化推荐系统

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。