JAG: Joint Attribute Graphs for Filtered Nearest Neighbor Search

• URL: http://arxiv.org/abs/2602.10258v1
• Date: Tue, 10 Feb 2026 20:00:51 GMT
• Title: JAG: Joint Attribute Graphs for Filtered Nearest Neighbor Search
• Authors: Haike Xu, Guy Blelloch, Laxman Dhulipala, Lars Gottesbüren, Rajesh Jayaram, Jakub Łącki,
• Abstract summary: JAG (Joint Attribute Graphs) is a graph-based algorithm designed to deliver robust performance across the entire selectivity spectrum.<n>Our experimental results demonstrate that JAG significantly outperforms existing state-of-the-art baselines in both throughput and recall robustness.
• Score: 8.398505388767248
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite filtered nearest neighbor search being a fundamental task in modern vector search systems, the performance of existing algorithms is highly sensitive to query selectivity and filter type. In particular, existing solutions excel either at specific filter categories (e.g., label equality) or within narrow selectivity bands (e.g., pre-filtering for low selectivity) and are therefore a poor fit for practical deployments that demand generalization to new filter types and unknown query selectivities. In this paper, we propose JAG (Joint Attribute Graphs), a graph-based algorithm designed to deliver robust performance across the entire selectivity spectrum and support diverse filter types. Our key innovation is the introduction of attribute and filter distances, which transform binary filter constraints into continuous navigational guidance. By constructing a proximity graph that jointly optimizes for both vector similarity and attribute proximity, JAG prevents navigational dead-ends and allows JAG to consistently outperform prior graph-based filtered nearest neighbor search methods. Our experimental results across five datasets and four filter types (Label, Range, Subset, Boolean) demonstrate that JAG significantly outperforms existing state-of-the-art baselines in both throughput and recall robustness.

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)
• Curator: Efficient Vector Search with Low-Selectivity Filters [12.774238654446032]
  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.
  arXiv  Detail & Related papers  (2026-01-03T21:35:01Z)
• Learning Filter-Aware Distance Metrics for Nearest Neighbor Search with Multiple Filters [7.493563348124023]
  Filtered Approximate Nearest Neighbor (ANN) search retrieves the closest vectors for a query vector from a dataset.<n>Existing graph-based methods typically incorporate filter awareness by assigning fixed penalties.<n>We propose a principled alternative that learns the optimal trade-off between vector distance and filter match directly from the data.
  arXiv  Detail & Related papers  (2025-11-06T05:24:41Z)
• Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectors [18.796661826646616]
  Filtered Approximate Nearest Neighbor Search is a problem known as Filtered Approximate Nearest Neighbor Search (FANNS)<n>We present a comprehensive survey and taxonomy of FANNS methods and analyze how they are benchmarked in the literature.<n>We introduce a novel dataset consisting of embedding vectors for the abstracts of over 2.7 million research articles from the arXiv repository, accompanied by 11 real-world attributes such as authors and categories.
  arXiv  Detail & Related papers  (2025-07-29T16:39:54Z)
• 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)
• Billion-scale Similarity Search Using a Hybrid Indexing Approach with Advanced Filtering [49.1574468325115]
  This paper presents a novel approach for similarity search with complex filtering capabilities on billion-scale datasets, optimized for CPU inference.<n>Our method extends the classical IVF-Flat index structure to integrate multi-dimensional filters.<n>The proposed algorithm combines dense embeddings with discrete filtering attributes, enabling fast retrieval in high-dimensional spaces.
  arXiv  Detail & Related papers  (2025-01-23T07:47:00Z)
• Learning Versatile Convolution Filters for Efficient Visual Recognition [125.34595948003745]
  This paper introduces versatile filters to construct efficient convolutional neural networks. We conduct theoretical analysis on network complexity and an efficient convolution scheme is introduced. Experimental results on benchmark datasets and neural networks demonstrate that our versatile filters are able to achieve comparable accuracy as that of original filters.
  arXiv  Detail & Related papers  (2021-09-20T06:07:14Z)
• Message Passing in Graph Convolution Networks via Adaptive Filter Banks [81.12823274576274]
  We present a novel graph convolution operator, termed BankGCN. It decomposes multi-channel signals on graphs into subspaces and handles particular information in each subspace with an adapted filter. It achieves excellent performance in graph classification on a collection of benchmark graph datasets.
  arXiv  Detail & Related papers  (2021-06-18T04:23:34Z)
• Graph Neural Networks with Adaptive Frequency Response Filter [55.626174910206046]
  We develop a graph neural network framework AdaGNN with a well-smooth adaptive frequency response filter. We empirically validate the effectiveness of the proposed framework on various benchmark datasets.
  arXiv  Detail & Related papers  (2021-04-26T19:31:21Z)
• Data Agnostic Filter Gating for Efficient Deep Networks [72.4615632234314]
  Current filter pruning methods mainly leverage feature maps to generate important scores for filters and prune those with smaller scores. In this paper, we propose a data filter pruning method that uses an auxiliary network named Dagger module to induce pruning. In addition, to help prune filters with certain FLOPs constraints, we leverage an explicit FLOPs-aware regularization to directly promote pruning filters toward target FLOPs.
  arXiv  Detail & Related papers  (2020-10-28T15:26:40Z)
• Dependency Aware Filter Pruning [74.69495455411987]
  Pruning a proportion of unimportant filters is an efficient way to mitigate the inference cost. Previous work prunes filters according to their weight norms or the corresponding batch-norm scaling factors. We propose a novel mechanism to dynamically control the sparsity-inducing regularization so as to achieve the desired sparsity.
  arXiv  Detail & Related papers  (2020-05-06T07:41:22Z)

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.