FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search
Proceedings of the ACM on Management of Data · 02.04.2026 · 4 (1) · 1-27
DOI: 10.1145/3786651 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 07.04.2026. Verfasst von Zekai Wu und 9 weiteren Autor:innen. Die Arbeit nennt 71 Literaturangaben. Gefördert von: Fundamental Research Funds for the Central Universities, Ant Group, National Science Foundation of China.
Abstract (Originalsprache)
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× speedup over HNSW's incremental construction and an average of 7.9× speedup for methods without incremental support, while maintaining comparable or superior search performance.
Förderung
- Fundamental Research Funds for the Central Universities
- Ant Group
- National Science Foundation of China
- Beijing Natural Science Foundation
- Shanghai Central and Local Science and Technology Development Fund Project
- National Key Research and Development Program of China
- Guangdong-Hong Kong Technology Innovation Joint Funding Scheme Project
- Hong Kong RGC GRF Project
Zitieren
APA
Wu, Z., Jin, J., Cheng, P., Zhong, X., Chen, L., Tong, Y., Shen, Z., Song, J., Shen, H. T., & Lin, X. (2026). FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data, 4(1), 1-27. https://doi.org/10.1145/3786651
Vancouver
Wu Z, Jin J, Cheng P, Zhong X, Chen L, Tong Y, et al. FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data. 2026;4(1):1-27. doi:10.1145/3786651
BibTeX
@article{Wu2026,
author = {Wu, Zekai and Jin, Jiabao and Cheng, Peng and Zhong, Xiaoyao and Chen, Lei and Tong, Yongxin and Shen, Zhitao and Song, Jingkuan and Shen, Heng Tao and Lin, Xuemin},
title = {FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {1},
pages = {1--27},
doi = {10.1145/3786651}
}
EUVIMED