CS Paper Radar

HorizANN: Elastically Scaling Vector Search with Ghost Edges

Talika Gupta, Yunqi Li, Aditya Kunte, Claire Lin, Supawit Chockchowwat, Daniel Waddington, Hubertus Franke, Yongjoo Park

cs.DB ·submitted 2026-11-14 01:26 UTC · v1

Abstract

Approximate nearest neighbor search (ANNS) is fundamental to modern data-intensive AI applications such as retrieval-augmented generation, recommendation systems, and semantic search. Among existing indexing methods, graph-based indexes emerge as the state of the art due to their superior recall-throughput tradeoffs. Scaling these indexes to multiple machines requires partitioning the data and building indexes on each. However, when new machines are added or removed, the data must be repartitioned and the indexes reconstructed from scratch, making horizontal scaling costly at billion scale. In this work, we present HorizANN, a distributed graph-based ANNS system that scales horizontally without requiring full index reconstruction. To achieve this, we introduce ghost edges, a mechanism for preserving cross-partition connectivity as partition boundaries change during repartitioning. By reusing the structural information that would otherwise be discarded during repartitioning, HorizANN avoids costly full index reconstruction. As the index grows from 100M vectors on one worker to 1B vectors on ten workers, HorizANN inserts each 100M vectors within 2.5 hours and sustains 3.4--3.5K queries per second at 0.998 Recall@10.

Comment
14 pages, 11 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Turbocharging PiPNN for Proximity and $k$-NN Graph Building

cs.DB cs.IR ·2026-11-03 ·Tobias Rubel, Richard Wen, Guy Blelloch, Laxman Dhulipala, Lars Gottesbüren +2 more
similarity 0.68
Abstract

Graph-based Approximate Nearest Neighbor Search (ANNS) indexes such as HNSW and Vamana deliver state-of-the-art query performance at the cost of large indexing times. The recently introduced PiPNN method drastically accelerated index construction by way of a partitioning-based algorithm leveraging dense matrix multiplication and top-$K$ aggregation kernels. In this paper, we unlock the full potential of PiPNN's hardware-friendly algorithm design. We introduce PiPNN II, which optimizes multiple steps of the PiPNN recipe, giving up to $8\times$ speedups for graph-based ANNS index construction. In addition, we present GPiPNN, a GPU implementation which builds comparable ANNS indices up to $43.7\times$ faster than Jasper and up to $50\times$ faster than CAGRA. We also extend PiPNN II and GPiPNN to compute high-quality $k$-NN graphs directly, which unlocks massive speedups over methods used in many existing systems for clustering, anomaly detection, and more. For 10-NN graph building at $90\%$ recall, we obtain up to a $13\times$ speedup on CPUs and $6.6\times$ on GPUs as compared to the prior best methods. PiPNN II can build a billion-scale 10-NN graph in under 16 minutes. Common to both PiPNN II and GPiPNN is the use of quantization to reduce memory traffic and leverage fast low-precision matrix operations. Top-$K$ emerges as a new bottleneck, which we optimize with specialized code for specific $K$, and by fusing with the matrix kernel to avoid materializing the distance matrix to memory. On CPUs, we demonstrate further performance improvements by leveraging our matrix kernels in the RobustPrune procedure proposed in Vamana and used in PiPNN. On GPUs, we flatten recursive partitioning into segmented batches, use one fused top-$K$ abstraction for partitioning and leaf scoring, and prune with already-witnessed direct edges rather than new candidate-to-candidate scoring passes.

0.49

Recast: Refinement-Centered Approximate Nearest Neighbor Search Optimized for Storage

cs.DB ·2026-11-02 ·Zehai Yang, Fengyi Tao, Wenzhuo Dong, Shimin Chen
similarity 0.67
Abstract

Large-scale ANNS systems often exploit storage in addition to DRAM for supporting vector search. The central question is how to divide the work between memory and storage for achieving both high query throughput-recall and good index maintenance performance. Existing storage-optimized ANNS paradigms fall short of providing a complete answer: disk-resident graph indexes have difficulty in supporting efficient vector deletions, while posting-list systems often incur more disk I/Os for queries. In this paper, we introduce a refinement-centered paradigm for storage-optimized ANNS systems. We propose Recast as a concrete design of this paradigm. Recast stores raw vectors on disk and keeps an IVF index with our RecastQ quantization encoding in memory. For an ANNS query, Recast selects nprobe inverted lists and performs SIMD-based FastScan on their RecastQ codes to identify refinement candidates in memory. It then retrieves candidate vectors from disk, computes exact distances, and refines the top-K result. To reduce disk I/Os, RecastQ computes uncertainty intervals containing true distances with high probability. Our QUIC policy selects a minimal refinement set based on these intervals, minimizing candidate-retrieval I/Os. Both the on-disk raw vectors and the in-memory IVF structure support insertions and deletions. Experiments on real-world data sets show that Recast processes batched insertions and deletions 3.10-37.27x faster than SPFresh and OdinANN, while its QPS at 0.99 recall changes by at most 6.9% after updating 50% of the corpus. For static queries at 0.99 recall, Recast achieves 1.56-2.01x the QPS of the strongest baseline with the matched memory budget on each data set, while requiring 1.22-6.75x less external storage than the evaluated systems. At matched in-memory space, RecastQ also provides a better Recall-refinement frontier than RaBitQ.

0.13

Exploiting Residual Reachability for Cross-Model Migration of Graph-Based Indexes in Approximate Nearest Neighbor Search

cs.DB ·2026-09-19 ·Baoyuan Gu, Xiaoyao Zhong, Jiabao Jin, Peng Cheng, Wangze Ni +3 more
similarity 0.67
Abstract · VLDB 2027 under review

Approximate nearest neighbor search (ANNS) underpins large-scale vector retrieval in search, recommendation, and retrieval-augmented generation. Graph-based indexes have demonstrated state-of-the-art search performance for ANNS. They connect each corpus vector to a small set of nearby or navigationally useful vertices and answer queries by traversing the resulting graph. Because these edges are selected using construction-time distances, the graph index is tied to the embedding model. Re-encoding a corpus with a new model may change distances and neighborhoods of the vectors. Reconstructing the graph for the new embedding vectors incurs substantial construction cost and delays deployment. When the embedding model changes, we observe a phenomenon in the old graph index that we call residual reachability. Specifically, although derived from different models, the vectors describe the same underlying objects and often retain part of their similarity structure. These shared relations are reflected in the connectivity of the old graph index, leaving many exact new-model neighbors reachable within a few hops in the old graph index. Motivated by this observation, we develop an index-migration approach that utilize the residual reachability in the old graph index to faster construct the new graph index for the new embedding vectors. Our method, Drift-Guided Migration (DGM), provides two migration paths. DGM-Local performs parallel shallow expansion over the inherited graph index and screens second-hop candidates with packed position sign codes before exact evaluation. DGM-Search uses hop-bounded beam traversal to explore beyond shallow expansion. Across eight text and image migrations, our DGM methods can achieve up to 17.43 times speedup on constructing the new graph index than the fastest degree-matched reconstruction method while keeping competitive recalls.

0.06

UBASE: An AI Search Engine for Trillion-Scale Vector Data Management at ByteDance

cs.DB ·2026-08-31 ·Yao Tian, Yuncheng Lu, Liyao Xiong, Yuming Xu, Hao Zhang +7 more
similarity 0.67
Abstract · ATC26 UBASE with Appendix

Since 2016, UBASE has been the foundation of ByteDance's search infrastructure, scaling to more than 7,000 clusters and 300 PB of indexed data. Driven by the demands of AI workloads, UBASE has evolved from a text search engine into a unified AI search system supporting vector retrieval, lexical matching, and predicate filtering. Its largest deployment indexes nearly one trillion high-dimensional vectors. This scale exposes two central bottlenecks in AI-era retrieval: memory-intensive graph-index construction under sustained ingestion, and the prohibitive cost of keeping vector indexes entirely in memory. UBASE addresses these bottlenecks with two techniques. First, it introduces a quantization-aware vector kernel based on SymRaBitQ, a new symmetric quantization scheme with tight theoretical guarantees that allows index construction to run directly in the quantized space accurately and efficiently without retaining a copy of full-precision vectors. Second, it provides a hybrid storage engine that supports memory-resident, hybrid, and SSD-resident deployments, with fine-grained record-level caching to trade memory for latency under operational control. On large-scale benchmarks, UBASE improves throughput by up to 3x, reduces indexing memory by 80%, and lowers serving cost by up to 99.4% compared with prior systems, while supporting trillion-vector scale, write-heavy or latency-sensitive workloads in production.

0.24

ACTIVE: A Dynamic Pareto-Frontier-Based Unified Index for Dual-Vector Query

cs.DB ·2026-10-26 ·Shengyuan Lin, Shufeng Gong, Zheng Wang, Feng Yao, Shifu Li +2 more
similarity 0.67
Abstract

Existing approximate nearest neighbor search (ANNS) methods generally assume that each entity has a single vector. In many real-world applications, however, an entity is associated with more than one vector, and queries may jointly consider two attributes. With different queries assigning different weights to each attribute, Pareto-frontier-based indices provide an effective solution for dual-vector retrieval by connecting to approximate nearest neighbors under all possible query preferences. However, existing Pareto-frontier-based approaches suffer from substantial inefficiencies in both index construction and dynamic updates, limiting their practical applicability. To address these issues, we propose ACTIVE, a dynamic Pareto-frontier-based DVQ index that supports efficient construction and updates while maintaining high retrieval performance under varying query preferences. It employs angle-constrained active-range computation and connectivity-loss-driven adaptive repair strategies to accelerate node insertion and deletion, respectively. Extensive experiments show that, at comparable (or slightly below) search accuracy, ACTIVE improves insertion throughput by $1.20$--$1.43\times$ over DEG, and deletion throughput by $1.64$--$2.06\times$ over neighbor-reconnection-based repair and by $22.64$--$39.51\times$ over reinsertion-based repair.

0.25

Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search

cs.IR ·2026-10-27 ·Francesco Benocci, Leonard Dahlmann, Francesco Gargiulo, Tobias Heuer, Silvio Martinico +3 more
top venuecode/data similarity 0.67
Abstract · 7 pages, 5 figures, Accepted at CIKM 2026. Code: https://github.com/TusKANNy/kannolo. Reproducibility: https://github.com/tusKANNy/papers_re…

Graph-based Approximate Nearest Neighbor (ANN) indexes, such as HNSW, are the backbone of modern vector search. However, their massive memory footprint creates a severe infrastructure bottleneck. While vector quantization is widely adopted to reduce the memory required to store data vectors, the graph's edge structure increasingly dominates total memory usage. Compressing these adjacency lists for online search presents a critical system challenge: because decompression occurs during query processing, i.e., while navigating the graph, memory savings cannot come at the expense of query latency. In this paper, we present a compression technique explicitly tailored for live HNSW routing. By applying offline graph permutations to artificially induce structural locality, we enable the use of SIMD-accelerated integer compressors, such as Stream VByte, for rapid on-the-fly decompression. Evaluated across diverse real-world workloads, we significantly outperform the current state of the art in both compression ratio and query latency. Our experimental results show that we achieve compression ratios up to 52.7% with negligible penalties in latency compared to the uncompressed baseline. Furthermore, our technique has been effectively deployed in production at eBay, achieving up to 44.3% reduction in edge storage with no degradation in query latency.

0.73

Index-Free Dynamic Edge Retrieval with Energy-Tail-Aware Partial Scans

cs.IR ·2026-09-01 ·Mohammad Arif Rasyidi, Omar Alhussein
publishedcode/data similarity 0.67
Abstract · Accepted for presentation at the 2026 IEEE 12th World Forum on Internet of Things (WF-IoT)

Dynamic maximum inner-product search (MIPS) returns the $K$ stored vectors with the largest dot products with a query while allowing the dataset to change through insertions, replacements, and deletions. For edge retrieval, the challenge is to achieve high recall and fast queries without making updates expensive. Full-vector scanning keeps updates simple but compares each query with every stored vector, while indexed methods reduce query cost at the expense of maintaining additional structures during updates. We propose ETAR, an index-free method that reduces query work while preserving simple updates. ETAR keeps the query coordinates with the largest squared values until they cover most of its total squared magnitude and treats the rest as a low-magnitude tail. It estimates similarity from the retained coordinates using a compact lower-precision representation, corrects for skipped coordinates, and reranks a fixed number of candidates using full-precision vectors. Across five runs on nine static datasets, ETAR averages 99.2% Recall@10, the fraction of exact top-10 results recovered, while running over 4$\times$ faster than exact scanning at a representative setting. This speedup also extends to an ARM-based mobile device, where ETAR is up to 6.9$\times$ faster across four synthetic distributions. Under five streaming workloads, it maintains 100% Recall@10 at every measured point without index rebuilds. Overall, ETAR offers a practical middle ground for dynamic MIPS by reducing query cost while retaining simple, index-free updates. Code is available at https://github.com/arasyi/etar-mips.

0.47

ConStore: Search-Overlapped Prefetch and Co-Retrieval-Aware Content Storage for Disk-Based ANNS

cs.DB ·2026-10-15 ·Zhutao Zhuang, Nong Xiao, Zhiguang Chen, Yue Yu
similarity 0.67
Abstract

Disk-based approximate nearest-neighbor search (ANNS) supports retrieval-augmented generation (RAG), search, recommendation, and advertising over corpora that exceed memory capacity. Existing ANNS research often focuses on vector search at small top-K, whereas industrial-scale applications require larger retrieval sets. Fetching the corresponding content from storage remains comparatively underexplored. Our profiling across million- to billion-vector corpora shows that, at large K, content fetch latency can match or exceed vector-search latency and cannot be ignored in end-to-end retrieval. We present ConStore, a content storage engine combining two complementary techniques to reduce end-to-end retrieval latency. Speculative Inline Content Prefetch (SICP) commonly abstracts graph-based and cluster-based ANNS as progressive SSD I/O that refines an in-flight candidate queue. It prefetches content for stable leading candidates under a bounded I/O budget, overlapping content reads with search without changing the final top-K results. Co-Retrieval-Pattern-Aware Grouping (RPAG) uses query logs to place frequently co-retrieved documents in contiguous segments. Workload-Adaptive Segment Reorganization (WASR) adapts this layout to workload shifts by selectively regrouping segments under a bounded rewrite budget. Group Content Fetch (GCF) exploits this layout to coalesce per-document random reads into batched, page-aware I/O requests. SICP works independently of the content layout, while RPAG and GCF reduce fetch cost even without prefetching. Across three multi-hop QA workloads with K from 10 to 1600, ConStore reduces end-to-end retrieval latency over the best per-document-read baseline by up to 48% on DiskANN and 25% on SPANN. Separate experiments on 100M- and billion-vector indexes demonstrate SICP's applicability at larger scales.

0.40