FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search CCS: Information systems Storage architectures Journal: PACMMOD Volume: 4 1 (SIGMOD) 37 2 DOI: 10.1145/3786651
Zekai Wu, Jiabao Jin, Peng Cheng, Xiaoyao Zhong, Lei Chen, Yongxin Tong, Zhitao Shen, Jingkuan Song, Heng Tao Shen, Xuemin Lin · 2026
Read FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search CCS: Information systems Storage architectures Journal: PACMMOD Volume: 4 1 (SIGMOD) 37 2 DOI: 10.1145/3786651 by Zekai Wu, Jiabao Jin, Peng Cheng, Xiaoyao Zhong, Lei Chen, Yongxin Tong, Zhitao Shen, Jingkuan Song, Heng Tao Shen, Xuemin Lin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21710.txt.
Introduction
Wu and co-authors merge several graph indexes for nearest neighbor search into one. Merging matters when clusters are consolidated or when live vector databases face read and write pressure. Their FGIM framework first converts each proximity graph into a k-nearest neighbor graph by cross-querying. A refinement step then finds missed high-quality neighbors and keeps the graph connected. A final conversion restores easy navigation. On six real datasets, FGIM merged up to 3.5 times faster than building HNSW step by step, with search quality kept or improved.
Catalog record
| CREATOR | Zekai Wu, Jiabao Jin, Peng Cheng, Xiaoyao Zhong, Lei Chen, Yongxin Tong, Zhitao Shen, Jingkuan Song, Heng Tao Shen, Xuemin Lin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75933 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.21710
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search CCS: Information systems Storage architectures Journal: PACMMOD Volume: 4 1 (SIGMOD) 37 2 DOI: 10.1145/3786651 Zekai Wu, Jiabao Jin, Peng Cheng, Xiaoyao Zhong, Lei Chen, Yongxin Tong, Zhitao Shen, Jingkuan Song, Heng Tao Shen, Xuemin Lin Abstract . As the state-of-the-art methods for high-dimensional data retrieval, Approximate Nearest Neighbor Search (ANNS) approaches with graph-based indexes have attracted increasing attention and play a crucial role in many real-world applications, e.g., retrieval-augmented generation (RAG) and recommendation systems. Unlike the extensive works focused on designing efficient graph-based ANNS methods, this paper delves into merging multiple existing graph-based indexes into a single one, which is also crucial in many real-world scenarios (e.g., cluster consolidation in distributed systems and read-write contention in real-time vector databases). We propose a Fast Graph-based Indexes Merging (FGIM) framework with three core techniques: (1) Proximity Graphs (PGs) to k k Nearest Neighbor Graph ( k k -NNG) transformation used to extract potential candidate neighbors from input graph-based indexes through cross-querying , (2) k k -NNG refinement designed to identify overlooked high-quality neighbors and maintain graph connectivity, and (3) k k -NNG to PG transformation aimed at improving graph navigability and enhancing search performance. Then, we integrate our FGIM framework with the state-of-the-art ANNS method, HNSW, and other existing mainstream graph-based methods to demonstrate its generality and merging efficiency. Extensive experiments on six real-world datasets show that our FGIM framework is applicable to various mainstream graph-based ANNS methods, achieves up to 3.5 × \times speedup over HNSW’s incremental construction and an average of 7.9 × \times speedup for methods without incremental support, while maintaining comparable or superior search performance. † † cc-license: by-nc-nd 1. Introduction Approximate Nearest Neighbor Search (ANNS) ( 5 ; 4 ) is a fundamental problem across various fields such as machine learning ( 16 ; 55 ) , information retrieval ( 54 ; 71 ) , recommendation systems ( 17 ; 38 ) , vector databases ( 53 ) , and Large Language Models (LLMs) ( 18 ; 6 ) . Recent deep-learning methods have revolutionized data representation by embedding unstructured data (e.g., images and texts) into high-dimensional vectors that preserve semantic relationships, which are crucial for similarity-based retrieval and various downstream machine-learning tasks. ANNS can efficiently retrieve semantically related data points from large-scale vectorized datasets, and is indispensable for modern AI applications ( 6 ; 30 ; 35 ) . Given a vector dataset \mathcal{X} and a query vector \vec{x}_{q}\in\mathbb{R}^{d} , ANNS aims to efficiently and effectively retrieve a vector \vec{x}_{r} from \mathcal{X} with the minimum distance to \vec{x}_{q} . According to recent studies ( 40 ; 7 ; 33 ; 56 ) , graph-based indexes have emerged as one of the most effective techniques for ANNS in view of their superior search accuracy. Despite the good performance of graph-based approaches, their practical deployment in industrial settings remains challenging. Industrial applications often involve massive datasets (e.g., 1B~10B vectors), where distance computation across candidate vectors dominates query latency. For small indexes constructed from data shards, merging them into a larger index can improve computational efficiency (e.g., Hierarchical Navigable Small World (HNSW) ( 36 ) consumes O(\log{n}) time for search ( 56 ) , and since \sum\log{n_{i}}<\log{\sum n_{i}} , a larger index enables faster search than partitioned ones). Moreover, real-world systems often operate in dynamic environments, where both data and device conditions change frequently. As a result, merging multiple indexes into a single one is required in various scenarios, which poses significant challenges. We first consider a cost-effective and high-performance scenario of real-time industrial applications (e.g., Retrieval-Augmented Generation (RAG) ( 30 ; 6 ) ), where indexing must be performed online to support continuous data writes. While HNSW ( 36 ) is widely adopted as a real-time indexing solution for its incremental insertion capability, its memory-intensive multi-layer structure motivates complementary SSD-based solutions (e.g., DiskANN ( 27 ) ), which trade query speed for cost efficiency. An industrial hybrid approach, adopted by Milvus ( 53 ) and VSAG ( 70 ) illustrated in Figure 1 , follows a Log-Structured Merge (LSM) architecture ( 44 ) : a size-bounded HNSW index (typically 1M–5M vectors) handles real-time writes, with periodic offloading to disk-based indexes. However, accumulating disk-based indexes requires background reconstruction to preserve search quality. This process is computationally expensive, thus difficult to be applied in online scenarios. In another distributed scenario illustrated in Figure 2 , to handle large-scale data efficiently, distributed storage and indexing systems ( 31 ; 64 ) have become increasingly prevalent. In these systems, each node constructs its index based on locally available data. As the distributed system evolves, scaling requirements may arise due to cluster consolidation ( 24 ; 34 ) or resource reallocation ( 29 ) . Specifically, computing nodes within a cluster are often merged to reduce costs and simplify management, which requires merging the existing indexes into a single one. The existing methods ( 22 ; 45 ; 19 ) rely on dataset-oriented merging operations (i.e., rebuilding the index from scratch) due to their unique construction strategies, which incurs substantial computational overhead and limited scalability. Figure 1. A hybrid engine for ANNS. Figure 2. An illustration of cluster consolidation. Challenges. To the best of our knowledge, no existing studies ( 36 ; 22 ; 27 ; 45 ; 19 ; 20 ) can meet the aforementioned requirements of industrial deployment to efficiently merge the graph-based indexes. To bridge this gap, we develop a practical approach to significantly reduce the time overhead of the merging process assuming the involved graph-based indexes fit in main memory, which is realistic in modern systems. While vectors may reside on SSDs, merging is typically performed on bounded, memory-resident graph shards ( 70 ) , and growing DRAM capacity makes such in-memory consolidation increasingly feasible ( 56 ; 8 ) . Our work focuses on the efficient merging of multiple existing graph indexes into a single one, which is non-trivial and has two key challenges. Challenge I: How can the neighbor relationships stored in the existing indexes be used to facilitate the construction of the merged graph-based index? Intuitively, an effective merging approach should extract valuable information (e.g., neighborhood relationship) from the existing multiple indexes to avoid as many computational overheads as possible, which is particularly important for high-dimensional datasets (e.g., GloVe ( 46 ) , Gist ( 28 ) and Crawl ( 3 ) ). However, different ANNS indexing structures employ different graph construction strategies and pruning techniques ( 56 ) . To ensure that, our approach is compatible with various indexing structures, it is necessary to map these heterogeneous structures into a unified merged structure in the preprocessing step, which facilitates high scalability and enables more efficient downstream procedures. Challenge II: How can the merged index achieve good search performance? The merging process must preserve the structural properties that are crucial for efficient ANNS. The state-of-the-art (SOTA) graph-based methods (e.g., HNSW ( 36 ) and Vamana ( 22 ) ) achieve high performance through careful edge selection and pruning strategies, which optimize the search path length and thus reduce distance computations. During index merging, we need to ensure the combined graph-based index maintains similar