RVANNS is presented, an RVV-oriented ANNS engine that jointly optimizes vector representation and graph locality and achieves 3.39x and 4.94x speedups over scalar execution on real 128-bit and 256-bit RVV processors, respectively.
Abstract
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.
GrAND (GPU-based Dynamic Graph Indexes for Approximate Nearest Neighbour Search) is presented, a GPU-native collection of dynamic-update algorithms for two popular graph indexes, Vamana and CAGRA, that improves overall workload throughput and maintains high search throughput and recall over sustained updates.
Karthik Venkatasubba, Shivendra Deshpande, S. Shivram 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.· arXiv.org· 0 citations
Scaling Approximate Nearest Neighbor Search (ANNS) to massive datasets exposes fundamental bottlenecks in PCIe bandwidth and random I/O. Computational storage devices (CSDs) promise to mitigate these constraints by enabling near-storage computation, but existing CSD-based ANNS engines employ only coarse-grained producer-consumer pipelines and underutilize heterogeneous on-device computational resources. We present Mario, a hierarchically pipelined ANNS framework for CSDs that couples a centroid-shard data organization with fine-grained coordination between the flash translation layer (FTL) and an on-board Field-Programmable Gate Array (FPGA). Mario introduces a speculative inter-shard pipeline that overlaps centroid-graph traversal, shard prefetching, and result aggregation with FPGA processing, and a stall-free intra-shard pipeline that streams vectors through parallel distance units and a streaming top-k updater. We prototype Mario on a Daisy+ OpenSSD platform and evaluate it on 100M-scale datasets, where it achieves 3.49× higher performance than existing ANNS architectures in average QPS, while maintaining a Recall@10 above 90%.
Kaijiang Deng, Shengan Zheng, Penghao Sun et al.· Proceedings of the 19th ACM...· 0 citations
FROG is a GPU-oriented RFANNS index that replaces multiple locally optimal substructure building with a globally aware, vertex-centric design and organizes diverse expansion neighbor candidates for each vertex in a GPU-friendly structure and rapidly identifies the expansion neighbors used for computation at query time.
Xiao-Kun Cui, Peng Liu, Jiadong Xie et al.· 0 citations
Local subgraph counting computes the exact number of occurrences of a query graph around every vertex in a data graph. By capturing local higher-order structure, it supports extensive applications in network analysis and graph learning. The fastest existing method, SCOPE, accelerates counting through query graph decomposition, but it is designed for single-threaded CPU execution. As a result, it struggles on large graphs and cannot take advantage of modern GPU hardware. A naïve GPU adaptation is also ineffective: as the number of parallel GPU threads grows, the memory footprint of their intermediate results quickly drains the device memory.
We develop a high-performance GPU solution for local subgraph counting that preserves SCOPE's tree-decomposition framework while explicitly resolving the tension between massive GPU parallelism and limited device memory. Our approach compresses the intermediate join-and-aggregate results and proposes an insert-failure restart mechanism that guarantees correctness under bounded memory. We further design a key-mapping strategy that enables lock-free hash tables for higher throughput, eventually integrating these components into a complete GPU execution framework capable of handling arbitrarily complex queries. Experiments show that our GPU-accelerated method achieves up to a 35× speedup over a multi-threaded SCOPE implementation, reducing the processing time for a million-scale graph from days to about 20 minutes and making local subgraph counting practical at large scale.
Qiao He, Yi-Ran Li, M. Yiu et al.· Proceedings of the VLDB Endo...· 0 citations
PIGR (Post-hoc Iterative Graph Refinement), a trace-driven framework that explicitly aligns efficiency with observed search behavior, is introduced, which 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
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
