Multiple Index Merge for Approximate Nearest Neighbor Search

• URL: http://arxiv.org/abs/2602.17099v1
• Date: Thu, 19 Feb 2026 05:50:34 GMT
• Title: Multiple Index Merge for Approximate Nearest Neighbor Search
• Authors: Liuchang Jing, Mingyu Yang, Lei Li, Jianbin Qin, Wei Wang,
• Abstract summary: This paper focuses on efficient two-index merging and the merge order of multiple indexes for AKNN search.<n>We propose a reverse neighbor sliding merge (RNSM) that exploits structural information to boost merging efficiency.<n> Experiments show that our approach yields up to a 5.48$times$ speedup over existing index merge methods and 9.92$times$ speedup over index reconstruction.
• Score: 14.386466486046814
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Approximate $k$ nearest neighbor (AKNN) search in high-dimensional space is a foundational problem in vector databases with widespread applications. Among the numerous AKNN indexes, Proximity Graph-based indexes achieve state-of-the-art search efficiency across various benchmarks. However, their extensive distance computations of high-dimensional vectors lead to slow construction and substantial memory overhead. The limited memory capacity often prevents building the entire index at once when handling large-scale datasets. A common practice is to build multiple sub-indexes separately. However, directly searching on these separated indexes severely compromises search efficiency, as queries cannot leverage cross-graph connections. Therefore, efficient graph index merging is crucial for multi-index searching. In this paper, we focus on efficient two-index merging and the merge order of multiple indexes for AKNN search. To achieve this, we propose a reverse neighbor sliding merge (RNSM) that exploits structural information to boost merging efficiency. We further investigate merge order selection (MOS) to reduce the merging cost by eliminating redundant merge operations. Experiments show that our approach yields up to a 5.48$\times$ speedup over existing index merge methods and 9.92$\times$ speedup over index reconstruction, while maintaining expected superior search performance. Moreover, our method scales efficiently to 100 million vectors with 50 partitions, maintaining consistent speedups.

Related papers

• Multi-Vector Index Compression in Any Modality [73.7330345057813]
  Late interaction has emerged as a dominant paradigm for information retrieval in text, images, visual documents, and videos.<n>We introduce four approaches for index compression: sequence resizing, memory tokens, hierarchical pooling, and a novel attention-guided clustering (AGC)<n>AGC uses an attention-guided mechanism to identify the most semantically salient regions of a document as cluster centroids and to weight token aggregation.
  arXiv  Detail & Related papers  (2026-02-24T18:57:33Z)
• Rethinking ANN-based Retrieval: Multifaceted Learnable Index for Large-scale Recommendation System [46.70111672855811]
  MultiFaceted Learnable Index (MFLI) is a scalable, real-time retrieval paradigm that learns multifaceted item embeddings and indices within a unified framework.<n>MFLI improves recall on engagement tasks by up to 11.8%, cold-content delivery by up to 57.29%, and semantic relevance by 13.5% compared with prior state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-02-18T01:31:29Z)
• DGAI: Decoupled On-Disk Graph-Based ANN Index for Efficient Updates and Queries [14.147837695174722]
  On-disk graph-based indexes are widely used in approximate nearest neighbor (ANN) search systems for large-scale, high-dimensional vectors.<n>Traditional coupled storage methods, which store vectors within the index, are inefficient for index updates.<n>We propose a decoupled storage architecture, while a decoupled architecture reduces query performance.
  arXiv  Detail & Related papers  (2025-10-29T11:20:10Z)
• HAKES: Scalable Vector Database for Embedding Search Service [16.034584281180006]
  We build a vector database that achieves high throughput and high recall under concurrent read-write workloads.<n>Our index outperforms index baselines in the high recall region and under concurrent read-write workloads.<n>namesys is scalable and achieves up to $16times$ higher throughputs than the baselines.
  arXiv  Detail & Related papers  (2025-05-18T19:26:29Z)
• MINT: Multi-Vector Search Index Tuning [11.309615417231498]
  We develop algorithms to find indexes that minimize latency and meet storage and recall constraints.<n>Compared to the baseline, our latency achieves 2.1X to 8.3X speedup.
  arXiv  Detail & Related papers  (2025-04-28T17:36:06Z)
• Operational Advice for Dense and Sparse Retrievers: HNSW, Flat, or Inverted Indexes? [62.57689536630933]
  We provide experimental results on the BEIR dataset using the open-source Lucene search library. Our results provide guidance for today's search practitioner in understanding the design space of dense and sparse retrievers.
  arXiv  Detail & Related papers  (2024-09-10T12:46:23Z)
• Semi-Parametric Retrieval via Binary Bag-of-Tokens Index [71.78109794895065]
  SemI-parametric Disentangled Retrieval (SiDR) is a bi-encoder retrieval framework that decouples retrieval index from neural parameters.<n>SiDR supports a non-parametric tokenization index for search, achieving BM25-like indexing complexity with significantly better effectiveness.
  arXiv  Detail & Related papers  (2024-05-03T08:34:13Z)
• Compact Neural Graphics Primitives with Learned Hash Probing [100.07267906666293]
  We show that a hash table with learned probes has neither disadvantage, resulting in a favorable combination of size and speed. Inference is faster than unprobed hash tables at equal quality while training is only 1.2-2.6x slower.
  arXiv  Detail & Related papers  (2023-12-28T18:58:45Z)
• Towards Improving the Consistency, Efficiency, and Flexibility of Differentiable Neural Architecture Search [84.4140192638394]
  Most differentiable neural architecture search methods construct a super-net for search and derive a target-net as its sub-graph for evaluation. In this paper, we introduce EnTranNAS that is composed of Engine-cells and Transit-cells. Our method also spares much memory and computation cost, which speeds up the search process.
  arXiv  Detail & Related papers  (2021-01-27T12:16:47Z)
• The Case for Learned Spatial Indexes [62.88514422115702]
  We use techniques proposed from a state-of-the art learned multi-dimensional index structure (namely, Flood) to answer spatial range queries. We show that (i) machine learned search within a partition is faster by 11.79% to 39.51% than binary search when using filtering on one dimension. We also refine using machine learned indexes is 1.23x to 1.83x times faster than closest competitor which filters on two dimensions.
  arXiv  Detail & Related papers  (2020-08-24T12:09:55Z)
• Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads [29.223401893397714]
  We introduce Tsunami, which achieves up to 6X faster query performance and up to 8X smaller index size than existing learned multi-dimensional indexes.
  arXiv  Detail & Related papers  (2020-06-23T19:25:51Z)

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.