Curator: Efficient Vector Search with Low-Selectivity Filters

• URL: http://arxiv.org/abs/2601.01291v3
• Date: Sat, 10 Jan 2026 20:49:26 GMT
• Title: Curator: Efficient Vector Search with Low-Selectivity Filters
• Authors: Yicheng Jin, Yongji Wu, Wenjun Hu, Bruce M. Maggs, Jun Yang, Xiao Zhang, Danyang Zhuo,
• Abstract summary: Graph-based indexes achieve state-of-the-art performance on unfiltered ANNS but encounter connectivity breakdown on low-selectivity filtered queries.<n>Recent research proposes specialized graph indexes that address this issue by expanding graph degree.<n>We present Curator, a partition-based index that complements existing graph-based approaches for low-selectivity filtered ANNS.
• Score: 12.774238654446032
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Embedding-based dense retrieval has become the cornerstone of many critical applications, where approximate nearest neighbor search (ANNS) queries are often combined with filters on labels such as dates and price ranges. Graph-based indexes achieve state-of-the-art performance on unfiltered ANNS but encounter connectivity breakdown on low-selectivity filtered queries, where qualifying vectors become sparse and the graph structure among them fragments. Recent research proposes specialized graph indexes that address this issue by expanding graph degree, which incurs prohibitively high construction costs. Given these inherent limitations of graph-based methods, we argue for a dual-index architecture and present Curator, a partition-based index that complements existing graph-based approaches for low-selectivity filtered ANNS. Curator builds specialized indexes for different labels within a shared clustering tree, where each index adapts to the distribution of its qualifying vectors to ensure efficient search while sharing structure to minimize memory overhead. The system also supports incremental updates and handles arbitrary complex predicates beyond single-label filters by efficiently constructing temporary indexes on the fly. Our evaluation demonstrates that integrating Curator with state-of-the-art graph indexes reduces low-selectivity query latency by up to 20.9x compared to pre-filtering fallback, while increasing construction time and memory footprint by only 5.5% and 4.3%, respectively.

Related papers

• Filtered Approximate Nearest Neighbor Search in Vector Databases: System Design and Performance Analysis [0.5249805590164902]
  Filtered Approximate Nearest Neighbor Search (FANNS) is used to combine semantic retrieval with metadata constraints.<n>In this work, we systematize the taxonomy of filtering strategies and evaluate their integration into vectors.<n>Our experiments reveal that algorithmic adaptations within the engine often override raw index performance.
  arXiv  Detail & Related papers  (2026-02-11T23:40:26Z)
• DGAI: Decoupled On-Disk Graph-Based ANN Index for Efficient Updates and Queries [14.147837695174722]
  On-disk graph-based indexes are widely used in approximate nearest neighbor (ANN) search systems for large-scale, high-dimensional vectors.<n>Traditional coupled storage methods, which store vectors within the index, are inefficient for index updates.<n>We propose a decoupled storage architecture, while a decoupled architecture reduces query performance.
  arXiv  Detail & Related papers  (2025-10-29T11:20:10Z)
• SIEVE: Effective Filtered Vector Search with Collection of Indexes [11.81573028534193]
  Real-world tasks such as recommending videos with the kids tag can be reduced to finding most similar vectors associated with hard predicates.<n>Prior state-of-the-art graph-based similarity search techniques quickly degenerate when hard constraints are considered.<n>We show superior performance and support on datasets with varying selectivities and forms.
  arXiv  Detail & Related papers  (2025-07-16T04:46:28Z)
• NaviX: A Native Vector Index Design for Graph DBMSs With Robust Predicate-Agnostic Search Performance [7.108581652658526]
  We present NaviX, a native vector index for graphs (GDBMSs)<n> NaviX is built on the Hierarchical Navigable Small-World (HNSW) graph, which itself is a graph-based structure.
  arXiv  Detail & Related papers  (2025-06-29T21:16:07Z)
• Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning [62.640169289390535]
  SPLIT-RAG is a multi-agent RAG framework that addresses the limitations with question-driven semantic graph partitioning and collaborative subgraph retrieval.<n>The innovative framework first create Semantic Partitioning of Linked Information, then use the Type-Specialized knowledge base to achieve Multi-Agent RAG.<n>The attribute-aware graph segmentation manages to divide knowledge graphs into semantically coherent subgraphs, ensuring subgraphs align with different query types.<n>A hierarchical merging module resolves inconsistencies across subgraph-derived answers through logical verifications.
  arXiv  Detail & Related papers  (2025-05-20T06:44:34Z)
• iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search [24.85572470526277]
  Range-filtering approximate nearest neighbor (RFANN) search is attracting increasing attention in academia and industry. Recent study proposes to build $O(n2)$ dedicated graph-based indexes for all possible query ranges. We materialize graph-based indexes, called elemental graphs, for a moderate number of ranges.
  arXiv  Detail & Related papers  (2024-09-04T09:41:52Z)
• Semi-Parametric Retrieval via Binary Bag-of-Tokens Index [71.78109794895065]
  SemI-parametric Disentangled Retrieval (SiDR) is a bi-encoder retrieval framework that decouples retrieval index from neural parameters.<n>SiDR supports a non-parametric tokenization index for search, achieving BM25-like indexing complexity with significantly better effectiveness.
  arXiv  Detail & Related papers  (2024-05-03T08:34:13Z)
• On Exploring Node-feature and Graph-structure Diversities for Node Drop Graph Pooling [86.65151066870739]
  Current node drop pooling methods ignore the graph diversity in terms of the node features and the graph structures, thus resulting in suboptimal graph-level representations. We propose a novel plug-and-play score scheme and refer to it as MID, which consists of a textbfMulti score space with two operations, textiti.e., fltextbfIpscore and textbfDropscore. Specifically, the multidimensional score space depicts the significance of nodes through multiple criteria; the flipscore encourages the maintenance of dissimilar node
  arXiv  Detail & Related papers  (2023-06-22T08:02:01Z)
• End-to-End Learning to Index and Search in Large Output Spaces [95.16066833532396]
  Extreme multi-label classification (XMC) is a popular framework for solving real-world problems. In this paper, we propose a novel method which relaxes the tree-based index to a specialized weighted graph-based index. ELIAS achieves state-of-the-art performance on several large-scale extreme classification benchmarks with millions of labels.
  arXiv  Detail & Related papers  (2022-10-16T01:34:17Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Towards Improving the Consistency, Efficiency, and Flexibility of Differentiable Neural Architecture Search [84.4140192638394]
  Most differentiable neural architecture search methods construct a super-net for search and derive a target-net as its sub-graph for evaluation. In this paper, we introduce EnTranNAS that is composed of Engine-cells and Transit-cells. Our method also spares much memory and computation cost, which speeds up the search process.
  arXiv  Detail & Related papers  (2021-01-27T12:16:47Z)
• The Case for Learned Spatial Indexes [62.88514422115702]
  We use techniques proposed from a state-of-the art learned multi-dimensional index structure (namely, Flood) to answer spatial range queries. We show that (i) machine learned search within a partition is faster by 11.79% to 39.51% than binary search when using filtering on one dimension. We also refine using machine learned indexes is 1.23x to 1.83x times faster than closest competitor which filters on two dimensions.
  arXiv  Detail & Related papers  (2020-08-24T12:09:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.