Jul 2026· International Conference on Supercomputing· pp. 551-564· 0 citations· 57 references
Computer Science
TL;DR
GAAF, a frequency-aware Graph Ensemble framework that decouples the handling of high- and low-frequency labels, is proposed, a frequency-aware Graph Ensemble framework that significantly outperforms state-of-the-art baselines.
Abstract
In many practical scenarios, vector retrieval is frequently coupled with keyword constraints, particularly under Any-Match semantics. Filtered Approximate Nearest Neighbor Search (Filtered ANNS) has emerged as a widely adopted solution. Within this domain, state-of-the-art methods often utilize graph-based indices that enforce constraints via runtime filtering on a monolithic graph. However, real-world label skew degrades this monolithic design: frequent labels waste computation on largely valid neighborhoods, while rare labels suffer from graph sparsity in locating limited candidates. To address this, we propose GAAF, a frequency-aware Graph Ensemble framework that decouples the handling of high- and low-frequency labels. GAAF partitions the dataset into specialized graphs: utilizing dedicated indexes for high-frequency labels to eliminate redundant comparisons, while consolidating the rest of the labels into shared graphs to restore connectivity. Leveraging the fine-grained control afforded by this ensemble, we introduce NUMA-aware data placement to minimize remote access, and Adaptive Inter-graph Pruning to bypass redundant traversals. Experiments on diverse datasets demonstrate that GAAF significantly outperforms state-of-the-art baselines.
Filtered Approximate Nearest Neighbor Search (FANNS) augments vector retrieval with categorical label predicates and is now standard in vector databases. Existing label-integrated graph indices, however, lose substantial recall on queries whose label is rare—the long-tail regime that dominates real workloads. We trace this failure to construction: distance-greedy neighbor selection and pruning systematically under-allocate edges to low-frequency labels, leaving their subgraphs poorly connected. Meanwhile, high-frequency labels accumulate redundant edges—slack that can be reallocated with limited impact on their search quality. Building on this insight, we propose LBGraph, which replaces both construction phases with label-balanced counterparts: a per-label round-robin candidate pool during exploration, and a label-then-distance rule during pruning. On low-frequency-label queries, LBGraph raises recall@10 by up to 71 percentage points (from 20% to 91%) over FilteredVamana on synthetic-label SIFT1M and GIST, with smaller gains on real-label LAION1M. Against ACORN-γ and StitchedVamana, it achieves up to 4 × their QPS at 90% recall@10 on low-frequency-label workloads while staying competitive on mixed workloads.
Hanchao Zheng, Yang Chen, Zhe Wu· International Conference on...· 0 citations
A Spectral-Aware Feature Alignment module to unify feature dimensionality and align cross-domain semantics in a community-aware manner and a Graph Diffusion Tokenized Transformer that constructs hybrid token sequences from local and global structural contexts for Transformer encoding, and applies diffusion-based refinement to mitigate distribution shifts on unseen graphs.
Mo Li, Zhaosong Zhao, Linlin Ding et al.· Annual International ACM SIG...· 0 citations
Approximate nearest neighbor search (ANNS) is increasingly essential for AI-driven applications. In practice, ANNS is often coupled with label filtering to improve accuracy, relevance, and efficiency, a variant known as filtered ANNS or FANNS. Existing FANNS methods fall short in efficiency or accuracy. This is because, first, searching on a label-mixed index often converges to local minima due to label interference. Second, isolating and duplicating labels in the index inflates the index and incurs prohibitive memory overhead. Third, current join-based strategies for multi-filter search perform substantial wasted computation on unpromising candidates.
We present BigFANN, a label-aware FANNS framework that achieves high speed and space efficiency, while retaining high accuracy. Our framework features a hybrid indexing scheme that introduces heterogeneous edge types and flexible IVF-graph indexing. Specifically, we construct graph indices with tunable combinations of
exclusive
and
shared
edges based on label characteristics. This method effectively minimizes label interference for single-filter search under a certain memory budget, ensuring high search accuracy and speed. In addition to heterogeneous edges, we adopt a hybrid of graph and IVF indices to deal with single- and multi-filter queries. Particularly, for multi-filter searches, we propose a join-free search strategy to eliminate wasted computation in the existing join-based strategy. Experimental results on various datasets show that BigFANN significantly outperforms state-of-the-art FANNS frameworks, UNG and ParlayIVF
2
, by up to 786× and 4× respectively, while achieving the same or better accuracy.
Zixiang Zhou, Xuhao Chen· Proceedings of the VLDB Endo...· 0 citations
Graph-based approximate nearest neighbor search (ANNS) is widely used in vector databases and retrieval systems. Most existing methods typically rely on structure-driven index construction and tuning, building graph topologies that approximate idealized geometric archetypes to promote navigability. However, geometric proximity is often an indirect proxy for search efficiency: static graph structures may fail to reflect actual traversal dynamics, leading to redundant distance evaluations such as low-yield node expansions and unnecessary local detours. These inefficiencies can significantly hinder high-recall performance. To address this limitation, we introduce PIGR (Post-hoc Iterative Graph Refinement), a trace-driven framework that explicitly aligns efficiency with observed search behavior. Instead of relying on coarse-grained construction parameter tuning, PIGR leverages self-queries to analyze search traces and identify inefficient traversal behaviors. It further performs iterative index optimization via trace-guided, budgeted prune-and-add edge edits without modifying the deployed search procedure. As a post-construction plug-in, PIGR delivers 1.3x-2.5x speedups at near-exact recall across diverse datasets and index families, consistently outperforming the best build-time tuned baselines.
Zhiwei Zhang, Weiguo Zheng· Proceedings of the 32nd ACM...· 0 citations
Graph-based indexes have become the dominant approach to approximate nearest neighbor search (ANNS) over high-dimensional data and play a crucial role in real-world applications such as retrieval-augmented generation, recommendation systems, and vector databases. Despite extensive progress in static graph construction and search, efficient in-place deletion remains challenging because obsolete vectors must be removed without allowing stale incoming edges to consume search capacity or expensive graph-wide maintenance to interrupt online services, e.g., retrieval-augmented generation (RAG) and recommendation platforms. To address this problem, we propose MERIT (MST-based Efficient Repair with In-place updaTes), an in-place update framework with three core techniques: (1) bounded search-based recovery that combines a deleted vertex's outgoing neighbors with its readily searchable in-neighbors, (2) $k_r$-Minimum Spanning Tree (MST) local repair that promotes local connectivity while retaining multiple routing choices for graph search, and (3) versioned-edge invalidation that immediately filters all stale incoming edges to the deleted vertex and progressively removes them as adjacency lists are rewritten. Its integration with the hierarchical HNSW index and the single-layer Vamana index demonstrates applicability across distinct graph structures. Extensive experiments on multiple real-world datasets show that MERIT processes deletion at nearly the cost of inserting one vector, achieves up to $3.02\times$--$18.87\times$ faster deletion than state-of-the-art (SOTA) methods, and keeps search recall stable or even improves it as deletions accumulate.
Zekai Wu, Jiabao Jin, Peng Cheng et al.· 0 citations
This paper addresses both $k-Nearest Neighbor Graph (kNNG) construction on 1024-dimensional BGE-M3 embeddings and Maximum Inner Product Search (MIPS) on unnormalized Llama-3.2-8B features, and introduces a 1D presorting mechanism via Fast Linear Assignment Sorting (FLAS) prior to graph construction.
Nico Hezel, Kai Barthel, Bruno Schilling et al.· 0 citations