Jul 2026· 2026 International Conference on Electronics, Computing, Communication and Control Technology (ICECCC)· pp. 1-5· 0 citations· 11 references
Abstract
Approximate Nearest Neighbor (ANN) search at scale exposes a structural trade-off between routing accuracy, memory footprint, and query latency. Graph-based indices such as HNSW provide high recall but incur significant memory overhead due to full-dataset connectivity, while centroid-based IVF variants remain memory-efficient yet degrade under highdimensional, non-convex cluster manifolds. This trade-off forces system designers to choose between recall and storage cost, and no existing single-index design resolves both simultaneously at scale. The need for an index that delivers graph-level recall at IVF-level memory cost therefore motivates this work. We present a density-aware hybrid indexing architecture that explicitly decouples routing from storage. The system extracts manifold representatives via a robust Lloyd refinement and constructs a lightweight HNSW graph over this reduced set, preserving topological routing precision while avoiding fullgraph memory costs. Candidate selection is performed through a dual-path routing mechanism combining geometric centroids and density-aware graph traversal. The search pipeline then diverges into two execution regimes: (1) an uncompressed, SIMD-optimized L2 path achieving hardware-bound latency, and (2) a compressed OPQ-based residual reconstruction path for memory-constrained deployment. On SIFT1M, the uncompressed configuration achieves 0.09 ms/query with 0.974 Recall@10, while the 32-byte/vector OPQ configuration attains 0.341 ms/query with 0.997 Recall@10. Integrated into a gRPC scatter-gather framework, the distributed system sustains 0.9975 Recall@10 across sharded partitions. These results demonstrate that density-aware routing enables graph-level recall with IVF-level storage cost, providing a scalable foundation for high-dimensional vector retrieval.
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
Graph-based Approximate Nearest Neighbor Search (ANNS) has become fundamental to modern data-intensive applications, yet supporting efficient vector updates while maintaining index quality remains a critical challenge. Existing approaches face a tough dilemma: extensive reconstruction ensures connectivity but incurs unpredictable overhead, while restricting update scope improves efficiency but degrades search accuracy. In this paper, we reveal that graph-based ANNS indexes inherently comprise backbone nodes that dictate global navigation capability and expansion nodes that provide local refinement. This insight motivates Hope, a Host-CSD (Computational Storage Device) cooptimized update framework that optimizes both index quality and update efficiency with a differentiated update design. For efficient vector categorization, we propose an in-storage sketcher that leverages per-dimension correlation with the bitmap-based flip mechanism to dynamically identify backbone and expansion vectors with minimal overhead. For asymmetric update handling, Hope employs the host-CPU for computation-intensive backbone updates with multi-hop neighbor gathering to preserve connectivity, while delegating I/O-intensive expansion updates to in-storage computing for immediate local manipulations. Our evaluation demonstrates that Hope achieves superior update efficiency and index quality compared to state-of-the-art baselines, providing stable performance for both vector updates and ANNS queries in dynamic environments.
Kecheng Huang, Jiaxian Chen, Chenlin Ma et al.· IEEE Non-Volatile Memory Sys...· 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
Latency-aware node discovery is a fundamental task in edge–cloud systems, where a node must identify nearby resources without comparing itself with every other node in the system. This paper addresses the latency range query problem, that is, finding all nodes whose latency to a given query node is below a specified threshold. The proposed method uses Vivaldi network coordinates, maps the coordinates to Hilbert keys, and stores the resulting keys in a B-tree index. Query processing then combines Hilbert-based range search with a pruning step that removes regions that cannot satisfy the latency bound. Experiments on an emulated 162-node FTTH topology show that, relative to Hilbert indexing alone, the pruning-enhanced method preserves the same true-positive and false-negative counts while greatly reducing false positives. As a result, precision and Jaccard similarity improve substantially, whereas recall remains unchanged. These findings show that Hilbert-based indexing, when paired with pruning, provides an effective way to support latency range queries in edge–cloud environments.
Urwah Muslim, H.L.C. Nanayakkara, Stephan Recker· International Conference on...· 0 citations
Approximate nearest neighbor search (ANNS) on CPUs is increasingly constrained by candidate-vector movement and decoding rather than peak arithmetic throughput. Although the RISC-V Vector Extension (RVV) provides vector-length-agnostic execution and LMUL-based register grouping, generic low-precision decoding still incurs conversion overhead, while irregular graph traversal generates scattered accesses that degrade cache locality and memory-level parallelism. We present RVANNS, an RVV-oriented ANNS engine that jointly optimizes vector representation and graph locality. Its Mixed-Precision Multi-Layer Index (MPMI) represents each vector with a dense 8-bit affine base and sparse FP16/FP32 residuals, fusing reconstruction with distance accumulation and aligning widening with LMUL-sized register groups. ROrder co-locates likely co-visited graph nodes and sorts remapped adjacency lists, transforming scattered payload probes into denser, predominantly forward-moving address streams. Integrated into Milvus, RVANNS achieves 3.39x and 4.94x speedups over scalar execution on real 128-bit and 256-bit RVV processors, respectively. Under controlled HNSW configurations, it improves throughput by 2.27--2.76x over RVV SIMD+FP32 and by 1.18--1.59x over the corresponding AVX-512 and SVE baselines. On Cohere10M, it further delivers 1.82--2.27x higher QPS/W than the evaluated GPU baselines.
Chengying Huan, Yudong Liu, Jianguo Wang et al.· 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