{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T21:04:20Z","timestamp":1775595860104,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"NSF &#x28;National Science Foundation&#x29;","award":["2337806"],"award-info":[{"award-number":["2337806"]}]},{"name":"Google","award":["Google ML and Systems Junior Faculty Award"],"award-info":[{"award-number":["Google ML and Systems Junior Faculty Award"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>Vector databases have become a cornerstone of modern data science and AI applications, powering recommendation systems, semantic search, retrieval-augmented generation, and more. This paper focuses on vector index merging (particularly HNSW merging), which merges two (or more) vector indexes. This is a key operation in vector databases with many use cases in vector index construction and vector index updates. While there are a few early approaches to solve the problem, the index merging performance remains slow. In this work, we propose HNSW-Merger, a new algorithm for merging two (or more) HNSW indexes that fully exploits the proximity information in existing indexes. It is a novel two-stage, search-based algorithm that relies on forward HNSW search and lazy backward direct-connect to efficiently connect potential edges. HNSW-Merger is optimized for multi-core parallelism and memory efficiency. It also supports efficient merging of multiple indexes. Extensive experiments show that HNSW-Merger achieves significantly faster merging performance than prior approaches while maintaining similar or even higher index quality.<\/jats:p>","DOI":"10.1145\/3786645","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Vector Index Merging in Vector Databases"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-2310-2973","authenticated-orcid":false,"given":"Chenzhe","family":"Jin","sequence":"first","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-4906-7946","authenticated-orcid":false,"given":"Yunan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-4769-8141","authenticated-orcid":false,"given":"Jiayi","family":"Liu","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3039-1175","authenticated-orcid":false,"given":"Jianguo","family":"Wang","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. AlloyDB AI (https:\/\/cloud.google.com\/alloydb\/ai)."},{"key":"e_1_2_1_2_1","unstructured":"[n.d.]. ANN-Benchmarks (https:\/\/ann-benchmarks.com\/index.html)."},{"key":"e_1_2_1_3_1","unstructured":"[n.d.]. Billion-Scale Approximate Nearest Neighbor Search Challenge (https:\/\/big-ann-benchmarks.com\/)."},{"key":"e_1_2_1_4_1","unstructured":"[n.d.]. Cohere (https:\/\/huggingface.co\/datasets\/Cohere\/wikipedia-22--12\/tree\/main\/en\/)."},{"key":"e_1_2_1_5_1","unstructured":"[n.d.]. Datasets for Approximate Nearest Neighbor Search (http:\/\/corpus-texmex.irisa.fr\/)."},{"key":"e_1_2_1_6_1","unstructured":"[n.d.]. Elasticsearch Vector Search (https:\/\/www.elastic.co\/lp\/vector-database)."},{"key":"e_1_2_1_7_1","unstructured":"[n.d.]. HNSW Search Complexity (https:\/\/milvus.io\/ai-quick-reference\/what-is-the-typical-time-complexityof-popular-ann-approximate-nearest-neighbor-search-algorithms-and-how-does-this-complexity-translate-topractical-search-speed-as-the-dataset-grows)."},{"key":"e_1_2_1_8_1","unstructured":"[n.d.]. HNSWlib (https:\/\/github.com\/nmslib\/hnswlib)."},{"key":"e_1_2_1_9_1","unstructured":"[n.d.]. Lucene (https:\/\/github.com\/apache\/lucene)."},{"key":"e_1_2_1_10_1","unstructured":"[n.d.]. Overview of Oracle AI Vector Search (https:\/\/docs.oracle.com\/en\/database\/oracle\/oracle-database\/23\/vecse\/overview-ai-vector-search.html)."},{"key":"e_1_2_1_11_1","unstructured":"[n.d.]. pgvector (https:\/\/github.com\/pgvector\/pgvector)."},{"key":"e_1_2_1_12_1","unstructured":"[n.d.]. Pinecone (https:\/\/www.pinecone.io\/)."},{"key":"e_1_2_1_13_1","unstructured":"[n.d.]. Weaviate (https:\/\/weaviate.io\/)."},{"key":"e_1_2_1_14_1","unstructured":"2024. Speeding Up Multi-graph Vector Search (https:\/\/www.elastic.co\/search-labs\/blog\/multi-graph-vector-search)."},{"key":"e_1_2_1_15_1","unstructured":"2025. Speeding Up Merging of HNSW Graphs (https:\/\/www.elastic.co\/search-labs\/blog\/hnsw-graphs-speed-upmerging)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583166"},{"key":"e_1_2_1_17_1","volume-title":"Efficient Indexing of Billion-Scale Datasets of Deep Descriptors. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2055--2063","author":"Babenko Artem","unstructured":"Artem Babenko and Victor S. Lempitsky. 2016. Efficient Indexing of Billion-Scale Datasets of Deep Descriptors. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2055--2063."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3685800.3685805"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725413"},{"key":"e_1_2_1_21_1","volume-title":"International Conference on Very Large Data Bases (VLDB). 518--529","author":"Gionis Aristides","year":"1999","unstructured":"Aristides Gionis, Piotr Indyk, and Rajeev Motwani. 1999. Similarity Search in High Dimensions via Hashing. In International Conference on Very Large Data Bases (VLDB). 518--529."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-99-8964-5"},{"key":"e_1_2_1_24_1","volume-title":"Cosine Threshold Querying with Optimality Guarantees. In International Conference on Database Theory (ICDT). 11:1--11:20","author":"Li Yuliang","year":"2019","unstructured":"Yuliang Li, Jianguo Wang, Benjamin S. Pullman, Nuno Bandeira, and Yannis Papakonstantinou. 2019. Index-Based, High-Dimensional, Cosine Threshold Querying with Optimality Guarantees. In International Conference on Database Theory (ICDT). 11:1--11:20."},{"key":"e_1_2_1_25_1","volume-title":"Fast Vector Search in PostgreSQL: A Decoupled Approach. In Conference on Innovative Data Systems Research (CIDR).","author":"Liu Jiayi","year":"2026","unstructured":"Jiayi Liu, Yunan Zhang, Chenzhe Jin, Aditya Gupta, Shige Liu, and Jianguo Wang. 2026. Fast Vector Search in PostgreSQL: A Decoupled Approach. In Conference on Innovative Data Systems Research (CIDR)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3722212.3724456"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627535.3638475"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE65448.2025.00325"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626246.3654691"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-024-00864-x"},{"key":"e_1_2_1_32_1","volume-title":"Three Algorithms for Merging Hierarchical Navigable Small World Graphs. CoRR abs\/2505.16064","author":"Ponomarenko Alexander","year":"2025","unstructured":"Alexander Ponomarenko. 2025. Three Algorithms for Merging Hierarchical Navigable Small World Graphs. CoRR abs\/2505.16064 (2025)."},{"key":"e_1_2_1_33_1","volume-title":"Suhas Jayaram Subramanya, and Jingdong Wang","author":"Simhadri Harsha Vardhan","year":"2021","unstructured":"Harsha Vardhan Simhadri, George Williams, Martin Aum\u00fcller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Jayaram Subramanya, and Jingdong Wang. 2021. Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search. In NeurIPS Competitions and Demonstrations Track. 177--189."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654990"},{"key":"e_1_2_1_35_1","volume-title":"Annual Conference on Neural Information Processing Systems (NeurIPS). 13748--13758","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, and Rohan Kadekodi. 2019. Rand-NSG: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In Annual Conference on Neural Information Processing Systems (NeurIPS). 13748--13758."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725325"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3685800.3685911"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the ACM International Conference on Management of Data (SIGMOD). 2614--2627","author":"Yi Xiaomeng","year":"2021","unstructured":"JianguoWang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, XiangyuWang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 2614--2627."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639269"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415541"},{"key":"e_1_2_1_41_1","unstructured":"Muazma Zahid. 2023. Vector Search with Azure SQL Database (https:\/\/devblogs.microsoft.com\/azure-sql\/vectorsearch-with-azure-sql-database\/)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00280"},{"key":"e_1_2_1_43_1","first-page":"1496","article-title":"On the Merge of k-NN Graph","volume":"8","author":"Zhao Wan-Lei","year":"2022","unstructured":"Wan-Lei Zhao, HuiWang, Peng-Cheng Lin, and Chong-Wah Ngo. 2022. On the Merge of k-NN Graph. IEEE Transactions on Big Data (TBD) 8, 6 (2022), 1496--1510.","journal-title":"IEEE Transactions on Big Data (TBD)"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3685800.3685905"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786645","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:01:10Z","timestamp":1775592070000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786645"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786645"],"URL":"https:\/\/doi.org\/10.1145\/3786645","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}