arXiv:2508.16263cs.DBcs.IR2025-08中稿 · SIGMOD 2026被引 15

对比10种向量搜索算法,找出带属性过滤时的最优选择。

Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study

  • 统一接口评测最新属性过滤搜索算法。
  • 在4个数据集上测试,最高达千万级数据量。
  • 揭示剪枝、入口点等设计对性能的影响。

随着结构化与非结构化数据融合,基于向量相似性搜索并满足结构化属性约束的新方法应运而生,即过滤近似最近邻(Filtering ANN)搜索。由于近年涌现多种算法,且适配不同索引方式与过滤策略,亟需统一分析以识别核心技术并实现有效比较。本文提出一个涵盖最新算法的统一过滤ANN接口,从多角度开展系统评估:首先基于属性类型与过滤策略构建全面分类体系;其次分析索引结构、剪枝策略与入口点选择等关键组件的设计差异与权衡;随后在4个数据集(最多含1000万条记录)上对10种算法和12种方法进行广泛实验,涵盖合成与真实属性,选择性范围从0.1%至100%;最后通过深入组件分析,揭示剪枝、入口点选择及边过滤开销对整体性能的影响。基于结果,总结各方法优劣,提供选型指南,并指出未来研究方向。代码开源:https://github.com/lmccccc/FANNBench。

原文摘要 · Abstract (English)

With the growing integration of structured and unstructured data, new methods have emerged for performing similarity searches on vectors while honoring structured attribute constraints, i.e., a process known as Filtering Approximate Nearest Neighbor (Filtering ANN) search. Since many of these algorithms have only appeared in recent years and are designed to work with a variety of base indexing methods and filtering strategies, there is a pressing need for a unified analysis that identifies their core techniques and enables meaningful comparisons. In this work, we present a unified Filtering ANN search interface that encompasses the latest algorithms and evaluate them extensively from multiple perspectives. First, we propose a comprehensive taxonomy of existing Filtering ANN algorithms based on attribute types and filtering strategies. Next, we analyze their key components, i.e., index structures, pruning strategies, and entry point selection, to elucidate design differences and tradeoffs. We then conduct a broad experimental evaluation on 10 algorithms and 12 methods across 4 datasets (each with up to 10 million items), incorporating both synthetic and real attributes and covering selectivity levels from 0.1% to 100%. Finally, an in-depth component analysis reveals the influence of pruning, entry point selection, and edge filtering costs on overall performance. Based on our findings, we summarize the strengths and limitations of each approach, provide practical guidelines for selecting appropriate methods, and suggest promising directions for future research. Our code is available at: https://github.com/lmccccc/FANNBench.

近邻搜索属性过滤算法评测

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