FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908906772496384 |
|---|---|
| author | Wu, Zekai Jin, Jiabao Cheng, Peng Zhong, Xiaoyao Chen, Lei Tong, Yongxin Shen, Zhitao Song, Jingkuan Shen, Heng Tao Lin, Xuemin |
| author_facet | Wu, Zekai Jin, Jiabao Cheng, Peng Zhong, Xiaoyao Chen, Lei Tong, Yongxin Shen, Zhitao Song, Jingkuan Shen, Heng Tao Lin, Xuemin |
| contents | 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$ Nearest Neighbor Graph ($k$-NNG) transformation used to extract potential candidate neighbors from input graph-based indexes through cross-querying, (2) $k$-NNG refinement designed to identify overlooked high-quality neighbors and maintain graph connectivity, and (3) $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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_21710 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search Wu, Zekai Jin, Jiabao Cheng, Peng Zhong, Xiaoyao Chen, Lei Tong, Yongxin Shen, Zhitao Song, Jingkuan Shen, Heng Tao Lin, Xuemin Databases 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$ Nearest Neighbor Graph ($k$-NNG) transformation used to extract potential candidate neighbors from input graph-based indexes through cross-querying, (2) $k$-NNG refinement designed to identify overlooked high-quality neighbors and maintain graph connectivity, and (3) $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. |
| title | FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search |
| topic | Databases |
| url | https://arxiv.org/abs/2603.21710 |