Back

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

Mocheng LiXiao YanBaotong LuYue ZhangJames ChengChenhao Ma

article2025Proc. ACM Manag. Data21 citations

Presents a unified taxonomy and large-scale experimental evaluation of filtered approximate nearest neighbor search algorithms across datasets with up to ten million vectors, delivering actionable guidelines on how indexing strategies and attribute selectivity govern retrieval performance.

Listen

Modern artificial intelligence applications, including recommendation systems and search engines, increasingly require retrieving unstructured vector data while simultaneously applying relational database filters, such as price ranges or category tags. While numerous algorithms for this hybrid task—termed Filtering Approximate Nearest Neighbor (Filtering ANN) search—have emerged recently, they rely on divergent designs, lack standardized evaluation, and present unclear performance trade-offs for production deployment.

The article provides a systematic experimental survey and unified benchmarking framework to evaluate 12 Filtering ANN methods across 10 recent algorithms. It aims to clarify the structural mechanics of these methods, assess their practical performance across diverse filtering workloads, and identify design guidelines for system architects and developers.

The authors established a standardized benchmarking interface and evaluated state-of-the-art methods on four standard datasets scaling up to 10 million vectors, using both synthetic and real attributes. The evaluation assessed search throughput (queries per second) and navigation efficiency while strictly maintaining a 90% recall target across selectivity levels ranging from 0.1% (highly restrictive filters) to 100% (unrestricted search). The study also conducted detailed component breakdowns focusing on indexing structures, graph pruning mechanisms, and entry point selection strategies.

The key findings reveal critical performance trade-offs across different query conditions. First, for numerical range filtering, segmented subgraph structures organized as binary search trees (such as iRangeGraph) achieve superior search speeds and robustness under highly restrictive filters (0.1% selectivity), whereas segmented edge methods (such as SeRF) fail at low selectivity because graph connectivity breaks down during index construction. Second, label filtering algorithms remain underdeveloped and unstable across datasets; stitching specialized subgraphs improves recall but can still fail depending on underlying graph quality, while joint-distance methods suffer severe performance degradation below 1% selectivity. Third, for arbitrary and multi-predicate filtering, standard single-index graphs (such as Faiss-HNSW) dominate when selectivity exceeds 50%, whereas dataset partitioning strategies (such as Milvus-HNSW) maintain reliable query execution at selectivities under 1% by falling back to efficient localized scans. Fourth, hierarchical multi-layer graphs provide minimal benefit over single-layer graphs under moderate-to-low selectivity, while increasing the number of entry points at the base layer (from 3 to 30 or 300) consistently reduces required vector comparisons across all methods.

These findings have direct operational implications for database architecture, memory sizing, and query latency. Highly specialized filtering indexes incur substantial index construction time and memory overheads compared to traditional vector indexes. Furthermore, the standard geometric pruning techniques used in vector search fail under sparse filtering constraints, meaning systems that rely on naive graph traversal risk severe query failures or unacceptable latency spikes under strict filters.

For practitioners, the source supports concrete architectural recommendations: deploy segmented subgraph methods (such as UNIFY or iRangeGraph) for numerical range filtering, utilize partition-based scanning (such as Milvus) for arbitrary filters with selectivity below 1%, and rely on standard unpartitioned graph indexes for queries passing more than 50% of the dataset. For label filtering, Filtered-DiskANN is recommended for single-label constraints, while simpler KGraph-based pruning is preferred when multiple labels are queried. Prior to production rollout, engineering teams should optimize entry point selection by sampling broader sets at the base layer rather than relying on complex multi-layer hierarchies.

The conclusions carry high confidence within static, uniformly distributed benchmark environments. However, decision-makers should note key limitations: most evaluated algorithms do not support real-time incremental updates, exhibit high sensitivity to manual hyperparameter tuning, and rely on uniform attribute distributions that may not fully reflect real-world data skew. Further research is necessary to develop robust arbitrary filtering indexes and adaptive tuning mechanisms for dynamic production databases.

Institute for Math & AI, WuhanMicrosoftThe Chinese University of Hong KongWuhan Universityanngenetic selectionindex structureApproximate nearest neighbor searchAttribute filteringLabel-covered pruning
arXiv: 2508.16263lmcccc/FANNBench

No sufficiently relevant recommendations were found.

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

Abstract

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: this https URL.

Topics

anngenetic selectionindex structurenearest neighbor searchtaxonomysearch process

Keywords

Approximate nearest neighbor searchAttribute filteringLabel-covered pruningRNG pruningNavigable small world graphsCross-subgraph edges

Table of Contents

  • 1 Introduction
  • 1.1 Filtering ANN Search
  • 1.2 Our Contributions
  • 2 Preliminaries
  • 2.1 Vector Quantization
  • 2.2 Inverted File
  • 2.3 Graph-Based ANN Search
  • 2.4 Filtering ANN Search
  • 3 Overview of Filtering ANN Algorithms
  • 3.1 Range Filtering ANN Search
  • 3.2 Label Filtering ANN Search
  • 3.3 Arbitrary Filtering ANN Search
  • 4 Detailed Analysis of Key Components
  • 4.1 Attribute Index
  • 4.2 Pruning Techniques
  • 4.3 Entry Point Strategies
  • 5 Experiments
  • 5.1 Setup
  • 5.2 Range Filtering: Performance and Analysis
  • 5.3 Label Filtering: Performance and Analysis
  • 5.4 Arbitrary Filtering Analysis
  • 5.5 Index Analysis
  • 5.6 Pruning Strategy Evaluation
  • 5.7 Entry Point Selection Analysis
  • 5.8 Edge Filtering Overhead Analysis
  • 6 Lessons Learned
  • 6.1 Insights
  • 6.2 Tool Selection
  • 6.3 Open Problems
  • 7 Related Work
  • 8 Conclusion
  • References

Knowls

  1. Knowl 1 — Filtering ANN task and taxonomy

    definition

    Filtering approximate nearest-neighbor (Filtering ANN) search returns the kk vectors nearest to a query vector qq, subject to an attribute predicate. Formally, for a dataset DD of vector–attribute records, the eligible set is Dr={o∈D:r(o.a)}D_r = \{o \in D : r(o.a)\}, where o.ao.a is the record’s attribute and rr is the query restriction; the exact answer consists of the kk records in DrD_r with smallest distance to qq. Filtering ANN methods approximate this result. The study considers numerical range predicates, categorical-label predicates, and arbitrary user-defined predicates.

    The paper classifies how filtering is combined with similarity search in three ways: pre-filtering restricts the search space before ANN search; post-filtering removes nonmatching candidates after ANN search; and joint-filtering incorporates the restriction into search itself. Selectivity is the fraction of dataset records satisfying the predicate: low selectivity means few records match, and high selectivity means many match. Pre-filtering can reduce work but may disrupt graph traversal; post-filtering is more attractive when many candidates pass; joint-filtering can prune invalid paths during traversal.

  2. Knowl 2 — Range-filtering index designs

    model/method

    The study distinguishes two ways to encode numerical range constraints in graph indexes.

    • Segmented edges: SeRF and DSG annotate graph edges with ranges so that edges can guide searches for different attribute intervals. SeRF orders records by attribute and inserts them in that order; for each new vector it progressively searches successively narrower ranges and selects up to MM neighbors for each distinct range, reusing distance computations and skipping ranges with unchanged neighbors. SeRF chooses multiple valid bottom-layer entry points for a query rather than relying on HNSW hierarchy. DSG retains the segmented-edge idea but supports dynamic insertion without requiring pre-sorting; its additional edge-validity work can add query overhead.
    • Segmented subgraphs: β\beta-WST and iRangeGraph organize range-specific subgraphs in a binary search tree (BST). The tree can represent up to log⁡(n)\log(n) layers and 2n−12n-1 subgraphs for a dataset of nn records, enabling fine-grained range combinations. iRangeGraph combines entry points from matching subgraphs for traversal rather than independently searching subgraphs and merging results. UNIFY instead builds a fixed set of disjoint attribute segments on a unified HNSW index and connects them with cross-subgraph edges. Its fixed segmentation offers fewer range combinations than the BST design, so narrow queries may require post-filtering or a skip-table scan.

  3. Knowl 3 — Experimental benchmark and conditions

    experimental setup

    The authors evaluate Filtering ANN methods on four L2-distance datasets: SIFT (128 dimensions, 10 million vectors), SpaceV (100 dimensions, 10 million), Redcaps (512 dimensions, 1 million), and Youtube-RGB (1,024 dimensions, 1 million). Each query task contains 10,000 queries. Redcaps and Youtube-RGB use real labels when specified; synthetic numerical attributes are integers from 0 to 100,000, and synthetic categorical attributes use 500 possible integer labels. The study also evaluates arbitrary filtering with combined numerical and categorical predicates.

    The benchmark compares range methods (SeRF, DSG, β\beta-WST variants, iRangeGraph, and UNIFY configurations), label methods (Filtered-DiskANN variants and NHQ with NSW or KGraph), and arbitrary-filtering methods (Faiss, Milvus, and ACORN variants). Range and label experiments target 90% recall@10 across selectivities including 0.1%, 1%, 10%, and 50%; query hyperparameters are tuned to reach that target, and missing results indicate a method did not meet it under the tested index configuration. The reported measures are queries per second (QPS) and, for graph methods, comparisons per query. Graph indexes use degree limit M=40M=40 and ef_construction=1000ef\_construction=1000; indexing uses 128 threads, queries use one thread, and results average three runs. Experiments ran on a 128-core Intel Xeon Platinum 8358 system with 2 TB memory.

  4. Knowl 4 — Range-filtering performance depends on selectivity

    empirical result

    At the 90% recall@10 target, fine-grained range-specific subgraphs are particularly effective for narrow numerical filters. iRangeGraph and β\beta-WST’s Vamana configuration perform strongly at 0.1% selectivity, while Milvus partitioning also provides reliable service in this regime. UNIFY’s default eight-segment configuration loses QPS at 0.1% and can fall behind its skip-table scan. By contrast, SeRF and DSG fail at 0.1%: their graph construction can fail to connect useful neighbors for extremely narrow ranges, leaving subsequent queries with inadequate traversal paths.

    At 1% and 10% selectivity, UNIFY-hybrid, β\beta-WST’s optimized post-filtering variant, iRangeGraph, SeRF, and DSG are among the strongest methods. The results indicate that segmented-edge and segmented-subgraph approaches can both work well at these selectivities. At broader selectivity, traditional ANN methods become more competitive because filtering excludes fewer candidates; Faiss-HNSW performs competitively at the tested 50% selectivity. Faiss-IVFPQ generally has lower QPS than Faiss-HNSW but handles 0.1% selectivity reliably across the datasets, unlike Faiss-HNSW post-filtering and ACORN in many such cases.

  5. Knowl 5 — Label filtering remains fragile at selectivity extremes

    empirical result

    In label-filtering experiments targeting 90% recall@10, Filtered-DiskANN’s stitched-graph variant (FDiskANN-SVG) performs well across selectivities on SpaceV, Redcaps, and Youtube-RGB, but does not meet the target on SIFT, which the authors associate with the quality of its underlying Vamana graph. Thus, the stitched design is effective but dataset-dependent.

    Both NHQ configurations—NHQ-KGraph and NHQ-NSW—lose substantial performance below 1% selectivity. The paper attributes this to difficulty maintaining graph connectivity between sparse same-label nodes under NHQ’s joint vector-and-attribute distance. NHQ-KGraph performs better than NHQ-NSW in the comparison because retaining nearest-neighbor connections preserves more connectivity than the NSW-style pruning used in the latter. The overall results show no evaluated label method is reliable across all datasets and selectivity regimes.

  6. Knowl 6 — Arbitrary-filter performance varies by selectivity

    empirical result

    The arbitrary-filter experiment combines categorical and numerical predicates. For example, the authors obtain about 50% overall selectivity by assigning one label to 60% of vectors and applying a range predicate with 83% selectivity; under a uniform distribution, the combined selectivity is approximately 0.60×0.830.60 \times 0.83.

    Above 10% selectivity, ACORN and Faiss-HNSW achieve strong QPS, with Faiss-HNSW best when selectivity exceeds 50%. At 0.1% selectivity, Faiss-HNSW and ACORN struggle to find sparse matching candidates, whereas Milvus-HNSW performs strongly. The authors interpret the latter’s insensitivity to changes in ef_searchef\_search as evidence that it scans within its attribute-partitioned subset rather than traversing the graph in this setting. For uniformly distributed attributes, Faiss and ACORN handle multiple predicates similarly to a single predicate at the same overall selectivity; Milvus-HNSW behaves differently when multiple predicates change its internal search strategy.

  7. Knowl 7 — Pruning strategy should match selectivity

    empirical result

    The pruning analysis compares ACORN’s two-hop pruning with KGraph-style pruning, which retains nearest neighbors directly, and RNG-style pruning. The authors measure graph comparisons at 90% recall@10; fewer comparisons indicate more efficient search. In ACORN, all tested pruning variants fail at 0.1% selectivity. Between 1% and 100%, ACORN’s original two-hop pruning performs best at low selectivity, while RNG pruning performs better above 50%; KGraph-style pruning is similar to the original ACORN strategy in the low-selectivity cases.

    For SeRF, replacing RNG-style pruning with KGraph-style pruning improves comparisons below 5% selectivity, but does not make SeRF effective at 0.1%. The results therefore qualify the usefulness of RNG pruning: it can preserve graph quality at moderate-to-high selectivity, but is less suitable for extremely selective filtering.

  8. Knowl 8 — More bottom-layer entry points can beat hierarchy

    empirical result

    On SIFT, the study compares hierarchical UNIFY with UNIFY-B, which keeps only UNIFY’s bottom layer, and varies the number of entry points for UNIFY-B, SeRF, and DSG. The comparison metric is graph comparisons per query, with lower values indicating more efficient search. Removing UNIFY’s hierarchy has little effect at low selectivity, while hierarchy becomes more helpful as selectivity increases. However, increasing the number of bottom-layer entry points from 3 to 30 or 300 consistently reduces comparisons for the single-layer indexes across the tested selectivities, without recall loss.

    For example, SeRF with 300 entry points reduces comparisons by 3.85% at 50% selectivity relative to its default three-entry-point configuration, corresponding to a reported 5.3% QPS increase. The finding suggests that a larger set of bottom-layer starting points can improve search across selectivities and may outperform relying on hierarchical navigation alone.

  9. Knowl 9 — DSG’s edge filtering can bottleneck query time

    empirical result

    At 10% selectivity on SIFT, DSG makes fewer graph comparisons per query than SeRF but achieves lower QPS. The authors attribute this mismatch to the time spent checking which edges are valid during neighbor selection: DSG spends a substantial fraction of query time on this work, whereas SeRF spends almost none. The edge-checking cost increases with ef_searchef\_search, because a larger candidate set requires more work to locate matching neighbors. Thus, comparison counts alone do not capture the query cost of graph-based Filtering ANN when edge-validity checks are expensive.

  10. Knowl 10 — Workload-based method selection and unresolved limits

    limitation

    The study’s practical recommendations are workload-dependent. For numerical range filtering, UNIFY and iRangeGraph are strong choices; iRangeGraph offers high query performance but has expensive construction, while SeRF is a faster-construction alternative that should be avoided at very low selectivity. The authors advise against β\beta-WST’s optimized variant when memory is a concern because of its high storage use. For label filtering, they recommend FDiskANN-SVG when queries specify one label and NHQ-KGraph when query label cardinality exceeds one. For arbitrary predicates, ACORN is the flexible option, Faiss-HNSW is attractive above 50% selectivity, and Milvus-HNSW is recommended below 1% selectivity.

    The paper identifies important limits on generalization and deployment: most generated attributes follow a uniform distribution, so performance under varied vector–attribute correlations is insufficiently studied; DSG is the only evaluated range method described as supporting dynamic index updates; and performance is sensitive to construction and query hyperparameters, which vary with data and workload. The authors also identify broader arbitrary-filter support and integration of specialized filtering indexes into general-purpose vector databases as open problems.

Coverage note — Detailed per-dataset index-size, memory-use, and construction-time values are omitted because they are secondary to the benchmark’s main filtering-performance and component findings; the study’s excluded related systems and algorithms are also not catalogued.

References

  1. 1.
    1. PostgreSQL. https://www.postgresql.org/
  2. 2.
    1. Yahoo. Nearest neighbor search with neighborhood graph and tree for high-dimensional data. https://github.com/yahoojapan/NGT
  3. 3.
    1. Weaviate:Vector database for contextual queries. https://github.com/semitechnologies/weaviate
  4. 4.
    1. Sptag: A library for fast approximate nearest neighbor search. https://github.com/microsoft/SPTAG
  5. 5.
    1. Vearch: A Distributed System for Embedding-based. https://github.com/vearch/vearch
  6. 6.
    1. pgvector. https://github.com/pgvector/pgvector
  7. 7.
    1. Pinecone. https://www.pinecone.io/
  8. 8.
    1. qdrant. http://qdrant.tech/
  9. 9.
    1. The technical report is available in our supplementary material and the anonymous repository. https://anonymous.4open.science/r/FANNBench-41C0
  10. 10.Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya. 2018. Hd-index: Pushing the scalability-accuracy boundary for approximate knn search in high-dimensional spaces. arXiv preprint arXiv:1804.06829 (2018).
  11. 11.Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems 87 (2020), 101374.
  12. 12.Franz Aurenhammer, Rolf Klein, and Der-Tsai Lee. 2013. Voronoi diagrams and Delaunay triangulations. World Scientific Publishing Company.
  13. 13.BigANN Benchmark. 2021. Billion-Scale Approximate Nearest Neighbor Search Challenge: NeurIPS’21 competition track.
  14. 14.Thomas Cover and Peter Hart. 1967. Nearest neighbor pattern classification. IEEE transactions on information theory 13, 1 (1967), 21–27.
  15. 15.Steve Dai, Rangha Venkatesan, Mark Ren, Brian Zimmer, William Dally, and Brucek Khailany. 2021. Vs-quant: Per-vector scaled quantization for accurate low-precision neural network inference. Proceedings of Machine Learning and Systems 3 (2021), 873–884.
  16. 16.Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry. 253–262.
  17. 17.Karan Desai, Gaurav Kaul, Zubin Aysola, and Justin Johnson. 2021. Redcaps: Web-curated image-text data created by the people, for the people. arXiv preprint arXiv:2111.11431 (2021).
  18. 18.Wei Dong, Charikar Moses, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th international conference on World wide web. 577–586.
  19. 19.Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024. The faiss library. arXiv preprint arXiv:2401.08281 (2024).
  20. 20.Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, and Jonathan Larson. 2024. From local to global: A graph rag approach to query-focused summarization. arXiv preprint arXiv:2404.16130 (2024).
  21. 21.Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, and Julian Shun. 2024. Approximate Nearest Neighbor Search with Window Filters. arXiv preprint arXiv:2402.00943 (2024).
  22. 22.Cong Fu and Deng Cai. 2016. Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph. arXiv preprint arXiv:1609.07228 (2016).
  23. 23.Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2017. Fast approximate nearest neighbor search with the navigating spreading-out graph. arXiv preprint arXiv:1707.00143 (2017).
  24. 24.Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–27.
  25. 25.Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization. IEEE transactions on pattern analysis and machine intelligence 36, 4 (2013), 744–755.
  26. 26.Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, et al. 2023. Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters. In Proceedings of the ACM Web Conference 2023. 3406–3416.
  27. 27.Long Gong, Huayi Wang, Mitsunori Ogihara, and Jun Xu. 2020. iDEC: indexable distance estimating codes for approximate nearest neighbor search. Proceedings of the VLDB Endowment 13, 9 (2020).
  28. 28.Bernal Jiménez Gutiérrez, Yiheng Shu, Yu Gu, Michihiro Yasunaga, and Yu Su. 2024. HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Models. arXiv preprint arXiv:2405.14831 (2024).
  29. 29.Xiaoxin He, Yijun Tian, Yifei Sun, Nitesh V Chawla, Thomas Laurent, Yann LeCun, Xavier Bresson, and Bryan Hooi. 2024. G-retriever: Retrieval-augmented generation for textual graph understanding and question answering. arXiv preprint arXiv:2402.07630 (2024).
  30. 30.Elias Jääsaari, Ville Hyvönen, and Teemu Roos. 2024. LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search. Advances in Neural Information Processing Systems 37 (2024), 102121–102153.
  31. 31.Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. Diskann: Fast accurate billion-point nearest neighbor search on a single node. Advances in Neural Information Processing Systems 32 (2019).
  32. 32.Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33, 1 (2010), 117–128.
  33. 33.Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. 2011. Searching in one billion vectors: re-rank with source coding. In 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 861–864.
  34. 34.Atsutake Kosuge and Takashi Oshima. 2019. An object-pose estimation acceleration technique for picking robot applications by using graph-reusing k-nn search. In 2019 First International Conference on Graph Computing (GC). IEEE, 68–74.
  35. 35.Joseph B Kruskal. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical society 7, 1 (1956), 48–50.
  36. 36.Jie Li, Haifeng Liu, Chuanghua Gui, Jianyu Chen, Zhenyuan Ni, Ning Wang, and Yuan Chen. 2018. The design and implementation of a real time visual search system on JD E-commerce platform. In Proceedings of the 19th International Middleware Conference Industry. 9–16.
  37. 37.Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2019. Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering 32, 8 (2019), 1475–1488.
  38. 38.Anqi Liang, Pengcheng Zhang, Bin Yao, Zhongpu Chen, Yitong Song, and Guangxu Cheng. 2024. UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search. arXiv preprint arXiv:2412.02448 (2024).
  39. 39.J MacQueen. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability/University of California Press.
  40. 40.Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45 (2014), 61–68.
  41. 41.Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence 42, 4 (2018), 824–836.
  42. 42.Yusuke Matsui, Ryota Hinami, and Shin’ichi Satoh. 2018. Reconfigurable Inverted Index. In Proceedings of the 26th ACM international conference on Multimedia. 1715–1723.
  43. 43.Yitong Meng, Xinyan Dai, Xiao Yan, James Cheng, Weiwen Liu, Jun Guo, Benben Liao, and Guangyong Chen. 2020. Pmd: An optimal transportation-based user distance for recommender systems. In Advances in Information Retrieval: 42nd European Conference on IR Research, ECIR 2020, Lisbon, Portugal, April 14–17, 2020, Proceedings, Part II 42. Springer, 272–280.
  44. 44.Jason Mohoney, Anil Pacaci, Shihabur Rahman Chowdhury, Ali Mousavi, Ihab F Ilyas, Umar Farooq Minhas, Jeffrey Pound, and Theodoros Rekatsinas. 2023. High-throughput vector similarity search in knowledge graphs. Proceedings of the ACM on Management of Data 1, 2 (2023), 1–25.
  45. 45.Lushuai Niu, Zhi Xu, Longyang Zhao, Daojing He, Jianqiu Ji, Xiaoli Yuan, and Mian Xue. 2023. Residual vector product quantization for approximate nearest neighbor search. Expert Systems with Applications 232 (2023), 120832.
  46. 46.Shumpei Okura, Yukihiro Tagami, Shingo Ono, and Akira Tajima. 2017. Embedding-based news recommendation for millions of users. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining. 1933–1942.
  47. 47.James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Survey of vector database management systems. The VLDB Journal 33, 5 (2024), 1591–1615.
  48. 48.Zhibin Pan, Liangzhuang Wang, Yang Wang, and Yuchen Liu. 2020. Product quantization with dual codebooks for approximate nearest neighbor search. Neurocomputing 401 (2020), 59–68.
  49. 49.Rodrigo Paredes and Edgar Chávez. 2005. Using the k-nearest neighbor graph for proximity searching in metric spaces. In String Processing and Information Retrieval: 12th International Conference, SPIRE 2005, Buenos Aires, Argentina, November 2-4, 2005. Proceedings 12. Springer, 127–138.
  50. 50.Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–27.
  51. 51.Arkadiusz Paterek. 2007. Improving regularized singular value decomposition for collaborative filtering. In Proceedings of KDD cup and workshop, Vol. 2007. 5–8.
  52. 52.Zhencan Peng, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. [n. d.]. Dynamic Range-Filtering Approximate Nearest Neighbor Search. ([n. d.]).
  53. 53.Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. 2021. Learning transferable visual models from natural language supervision. In International conference on machine learning. PMLR, 8748–8763.
  54. 54.Patrick Schäfer, Jakob Brand, Ulf Leser, Botao Peng, and Themis Palpanas. 2024. Fast and Exact Similarity Search in less than a Blink of an Eye. arXiv preprint arXiv:2411.17483 (2024).
  55. 55.Chanop Silpa-Anan and Richard Hartley. 2008. Optimised KD-trees for fast image descriptor matching. In 2008 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 1–8.
  56. 56.Godfried T Toussaint. 1980. The relative neighbourhood graph of a finite planar set. Pattern recognition 12, 4 (1980), 261–268.
  57. 57.A Vaswani. 2017. Attention is all you need. Advances in Neural Information Processing Systems (2017).
  58. 58.Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. 2021. Milvus: A purpose-built vector data management system. In Proceedings of the 2021 International Conference on Management of Data. 2614–2627.
  59. 59.Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2024. An efficient and robust framework for approximate nearest neighbor search with attribute constraint. Advances in Neural Information Processing Systems 36 (2024).
  60. 60.Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. arXiv preprint arXiv:2101.12631 (2021).
  61. 61.Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: a hybrid analytical engine towards query fusion for structured and unstructured data. Proceedings of the VLDB Endowment 13, 12 (2020), 3152–3165.
  62. 62.Yuexuan Xu, Jianyang Gao, Yutong Gou, Cheng Long, and Christian S Jensen. 2024. iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search. Proceedings of the ACM on Management of Data 2, 6 (2024), 1–26.
  63. 63.Shuo Yang, Jiadong Xie, Yingfan Liu, Jeffrey Xu Yu, Xiyue Gao, Qianru Wang, Yanguo Peng, and Jiangtao Cui. 2024. Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search. arXiv preprint arXiv:2410.01231 (2024).
  64. 64.Wen Yang, Tao Li, Gai Fang, and Hong Wei. 2020. Pase: Postgresql ultra-high-dimensional approximate nearest neighbor search extension. In Proceedings of the 2020 ACM SIGMOD international conference on management of data. 2241–2253.
  65. 65.Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, et al. 2023. {VBASE}: Unifying Online Vector Similarity Search and Relational Queries via Relaxed Monotonicity. In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). 377–395.
  66. 66.Weijie Zhao, Shulong Tan, and Ping Li. 2022. Constrained approximate similarity search on proximity graph. arXiv preprint arXiv:2210.14958 (2022).
  67. 67.Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2024. SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 2, 1 (2024), 1–26.

Citation

MLA
Li, M., et al. “Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study”. Proceedings of the ACM on Management of Data, vol. 3, no. 6, 2025, pp. 1–6, https://doi.org/10.1145/3769763.
APA
Li, M., Yan, X., Lu, B., Zhang, Y., Cheng, J., & Ma, C. (2025). Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study. Proceedings of the ACM on Management of Data, 3(6), 1–26. https://doi.org/10.1145/3769763
Chicago
Li, M., X. Yan, B. Lu, Y. Zhang, J. Cheng, and C. Ma. 2025. “Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study”. Proceedings of the ACM on Management of Data 3 (6): 1–26. https://doi.org/10.1145/3769763.
Harvard
Li, M. et al. (2025) “Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study”, Proceedings of the ACM on Management of Data, 3(6), pp. 1–26. Available at: https://doi.org/10.1145/3769763.
Vancouver
1. Li M, Yan X, Lu B, Zhang Y, Cheng J, Ma C (2025) Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study. Proceedings of the ACM on Management of Data 3:1–26

BibTeX

@article{Li_2025, title={Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study}, volume={3}, ISSN={2836-6573}, url={http://dx.doi.org/10.1145/3769763}, DOI={10.1145/3769763}, number={6}, journal={Proceedings of the ACM on Management of Data}, publisher={Association for Computing Machinery (ACM)}, author={Li, Mocheng and Yan, Xiao and Lu, Baotong and Zhang, Yue and Cheng, James and Ma, Chenhao}, year={2025}, month=Dec, pages={1–26} }
Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by/4.0/