PathFinder: Efficiently Supporting Conjunctions and Disjunctions for Filtered Approximate Nearest Neighbor Search
Tianming Wu, Dixin Tang · 2025
Read PathFinder: Efficiently Supporting Conjunctions and Disjunctions for Filtered Approximate Nearest Neighbor Search by Tianming Wu, Dixin Tang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00995.txt.
Introduction
Tianming Wu and Dixin Tang present PathFinder, an indexing framework for filtered nearest neighbor search. The task is to find the items most similar to a query among only those whose attributes pass a filter. Filters in real applications combine several attributes with and and or conditions, which breaks indexes tuned for a single attribute.
Borrowing from relational database design, PathFinder lets users build attribute specific indexes and then uses a cost based optimizer to combine them for complex filters. New pieces include a metric balancing speed against accuracy, a two phase plan for mixed filters, and a way to borrow one attribute's index for another. On four real data sets it beat the best baseline by up to nearly ten times in throughput at high recall.
Catalog record
| CREATOR | Tianming Wu, Dixin Tang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-00995
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
PathFinder: Efficiently Supporting Conjunctions and Disjunctions for Filtered Approximate Nearest Neighbor Search Tianming Wu, Dixin Tang Abstract . Filtered approximate nearest neighbor search (ANNS) restricts the search to data objects whose attributes satisfy a given filter and retrieves the top- K K objects that are most semantically similar to the query object. Many graph-based ANNS indexes are proposed to enable efficient filtered ANNS but remain limited in applicability or performance: indexes optimized for a specific attribute achieve high efficiency for filters on that attribute but fail to support complex filters with arbitrary conjunctions and disjunctions over multiple attributes. Inspired by the design of relational databases, this paper presents PathFinder, a new indexing framework that allows users to selectively create ANNS indexes optimized for filters on specific attributes and employs a cost-based optimizer to efficiently utilize them for processing complex filters. PathFinder includes three novel techniques: 1) a new optimization metric that captures the tradeoff between query execution time and accuracy, 2) a two-phase optimization for handling filters with conjunctions and disjunctions, and 3) an index borrowing optimization that uses an attribute-specific index to process filters on another attribute. Experiments on four real-world datasets show that PathFinder outperforms the best baseline by up to 9.8 × \times in query throughput at recall 0.95. † † authors: . PVLDB Reference Format: PathFinder: Efficiently Supporting Conjunctions and Disjunctions for Filtered Approximate Nearest Neighbor Search. PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX † † This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected] . Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at URL_TO_YOUR_ARTIFACTS . 1. Introduction Vector databases are the foundational infrastructure for semantic search and have been adopted to support a broad range of information systems, such as retrieval-augmented generation systems for large language models ( Jiang et al. 2023 ; Guu et al. 2020 ; Jiang et al. 2025a ; Trivedi et al. 2023 ) , recommendation systems ( Wei et al. 2020 ; Rajput et al. 2023 ) , search engines ( Luc 2025 ; Ope 2025 ; Ela 2025 ) , and knowledge bases ( Mohoney et al. 2023 ; Edge et al. 2024 ; Ilyas et al. 2022 ) . Vector databases support semantic search by encoding each data object, such as a document or an image, into a high-dimensional vector, and quickly but approximately finding the top- K data objects that are most semantically similar to a query object (i.e., a similarity query ) based on vector distances ( mil 2025 ; Wang et al. 2021 ; chr 2025 ; wea 2025 ; lan 2025 ; Wei et al. 2020 ; qdr 2025 ; Chen et al. 2024 ; Fu et al. 2019 ; Malkov and Yashunin 2020 ; Jayaram Subramanya et al. 2019 ) , known as approximate nearest neighbor search (ANNS) . When processing a similarity query with a filter on the attributes of the data objects (e.g., searching for the papers in the “DB” field and published after 2025), ANNS restricts the search to the subset of data objects passing the filter, known as filtered ANNS . Efficiently and accurately supporting filtered ANNS remains challenging, as the performance of existing ANNS indexes degrades significantly under complex filters. Graph-based indexes , for example, are widely adopted to support ANNS due to their strong tradeoff between query execution time and accuracy ( Jayaram Subramanya et al. 2019 ; Malkov and Yashunin 2020 ; Fu et al. 2019 ; Malkov et al. 2014 ; Ait Aomar et al. 2025 ) . The core of graph-based indexes is the proximity graph , which represents data objects as vertices and connects each vertex to a bounded number of nearby vertices based on vector distances ( Jayaram Subramanya et al. 2019 ; Malkov and Yashunin 2020 ; Malkov et al. 2014 ) . However, the filter associated with a similarity query can induce a sparse or even disconnected subgraph ( Singh et al. 2021 ) , significantly degrading search efficiency and accuracy. Figure 1 . A tree-based graph index built on a numeric attribute. The attribute range is recursively partitioned, and for each tree node, a proximity graph is built over the data objects whose attribute values fall within the node’s range. Recent studies have proposed new graph-based indexes to address the challenge of sparse graphs in filtered ANNS. However, these approaches remain limited in their applicability or performance. A line of research focuses on indexes optimized for filters on a single attribute of a particular data type ( Zuo et al. 2024 ; Xu et al. 2024 ; Wang et al. 2023 ; Gollapudi et al. 2023 ; Engels et al. 2024 ; Gupta et al. 2023 ; Liang et al. 2025 ; Ait Aomar et al. 2025 ; Cai et al. 2024 ) , referred to as attribute-specific indexes . Their goal is to construct sufficiently dense proximity graphs to process filters on the attribute they are optimized for. As a result, when processing filters on the attributes they are optimized for, they offer substantial performance advantages over graph-based indexes that support general filters ( Patel et al. 2024 ; Malkov and Yashunin 2020 ; Jayaram Subramanya et al. 2019 ) . However, it remains an open challenge to effectively utilize attribute-specific indexes to support filters with arbitrary conjunctions and disjunctions. Our approach. This paper presents PathFinder, a novel graph-based indexing framework for efficient filtered ANNS that supports general filters with conjunctions and disjunctions. The design of PathFinder is guided by a key principle drawn from the practical considerations of relational databases: since it is prohibitively expensive to build indexes for all possible attribute combinations, DBMSs allow administrators to create indexes on selected attributes and rely on a cost-based optimizer to leverage these indexes for efficiently processing general multi-attribute filters. Following this insight, PathFinder allows the vector database administrators to create attribute-specific ANNS indexes on selected attributes and designs a cost-based optimizer to utilize the available indexes to efficiently process similarity queries with complex filters. Specifically, PathFinder models data objects as a database relation, where the columns represent the embedding vector and associated attributes, which may be numeric or categorical. It supports tree-based and hash-based graph indexes optimized for individual attributes. Tree-based graph indexes have shown state-of-the-art search performance for single-attribute range filters ( Engels et al. 2024 ; Jiang et al. 2025b ; Xu et al. 2024 ; Wang et al. 2025 ) and support efficient updates ( Jiang et al. 2025b ; Wang et al. 2025 ) . We adopt a multi-way tree structure ( Jiang et al. 2025b ) and include a new cost-based method for efficiently using this index structure to support both single-attribute and multi-attribute filters. Figure 1 shows an example of this tree-based graph index. It recursively partitions the value range of an attribute, like a B + -tree, and builds a proximity graph for each node