{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T14:11:34Z","timestamp":1792159894478,"version":"4.4.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100000038","name":"Natural Science and Engineering Research Council of Canada","doi-asserted-by":"crossref","award":["RGPIN-2024-03993"],"award-info":[{"award-number":["RGPIN-2024-03993"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>\n                    Approximate nearest neighbor search (ANNS) on high dimensional vectors is important for numerous applications, such as search engines, recommendation systems, and more recently, large language models (LLMs), where Retrieval Augmented Generation (RAG) is used to add context to an LLM query. Graph-based indexes built on these vectors have been shown to perform best but have challenges. These indexes can either employ refinement-based construction strategies such as K-Graph and NSG, or increment-based strategies such as HNSW. Refinement-based approaches have fast construction times, but worse search performance and do not allow for incremental inserts, requiring a full reconstruction each time new vectors are added to the index. Increment-based approaches have good search performance and allow for incremental inserts, but suffer from slow construction. This work presents MIRAGE-ANNS (\n                    <jats:bold>M<\/jats:bold>\n                    ixed\n                    <jats:bold>I<\/jats:bold>\n                    ncremental\n                    <jats:bold>R<\/jats:bold>\n                    efinement\n                    <jats:bold>A<\/jats:bold>\n                    pproach\n                    <jats:bold>G<\/jats:bold>\n                    raph-based\n                    <jats:bold>E<\/jats:bold>\n                    xploration for Approximate Nearest Neighbor Search) that constructs the index as fast as refinement-based approaches while retaining search performance comparable or better than increment-based ones. It also allows incremental inserts. We show that MIRAGE achieves state of the art construction and query performance, outperforming existing methods by up to 2x query throughput on real-world datasets.\n                  <\/jats:p>","DOI":"10.1145\/3725325","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-27","source":"Crossref","is-referenced-by-count":12,"title":["MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-2602-1586","authenticated-orcid":false,"given":"Sairaj","family":"Voruganti","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8126-1717","authenticated-orcid":false,"given":"M. Tamer","family":"\u00d6zsu","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"[n. d.]. https:\/\/www.cse.cuhk.edu.hk\/systems\/hash\/gqr\/datasets.html. [Accessed 08--10--2024]."},{"key":"e_1_2_2_2_1","unstructured":"[n. d.]. ANNOY library. https:\/\/github.com\/spotify\/annoy. Accessed: 08--10--2024."},{"key":"e_1_2_2_3_1","unstructured":"[n. d.]. Common Crawl - Open Repository of Web Crawl Data - commoncrawl.org. https:\/\/commoncrawl.org\/. [Accessed 08--10--2024]."},{"key":"e_1_2_2_4_1","unstructured":"[n. d.]. Evaluation of Approximate nearest neighbors: large datasets - corpus-texmex.irisa.fr. http:\/\/corpus-texmex.irisa.fr\/. [Accessed 08--10--2024]."},{"key":"e_1_2_2_5_1","unstructured":"[n. d.]. GPT-4. https:\/\/openai.com\/research\/gpt-4"},{"key":"e_1_2_2_6_1","unstructured":"[n. d.]. Open-source vector similarity search for Postgres. https:\/\/github.com\/pgvector\/pgvector"},{"key":"e_1_2_2_7_1","unstructured":"[n. d.]. The vector database to build knowledgeable AI | Pinecone - pinecone.io. https:\/\/www.pinecone.io\/. [Accessed 14--10--2024]."},{"key":"e_1_2_2_8_1","unstructured":"[n. d.]. vespa.ai. https:\/\/vespa.ai\/. [Accessed 14--10--2024]."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3709693"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3227609.3227643"},{"key":"e_1_2_2_11_1","volume-title":"SPTAG: A library for fast approximate nearest neighbor search. https:\/\/github.com\/Microsoft\/SPTAG.","author":"Chen Qi","year":"2018","unstructured":"Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jing-dong Wang. 2018. SPTAG: A library for fast approximate nearest neighbor search. https:\/\/github.com\/Microsoft\/SPTAG."},{"key":"e_1_2_2_12_1","volume-title":"Wortman Vaughan (Eds.)","volume":"34","author":"Chen Qi","year":"2021","unstructured":"Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 5199--5212. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2021\/file\/299dc35e747eb77177d9cea10a802da2-Paper.pdf"},{"key":"e_1_2_2_13_1","volume-title":"Proc. 36th Intl. Conf. on Neural Information Processing Systems (NIPS '22)","author":"Chern Felix","year":"2024","unstructured":"Felix Chern, Blake Hechtman, Andy Davis, Ruiqi Guo, David Majnemer, and Sanjiv Kumar. 2024. TPU-KNN: K nearest neighbor search at peak FLOP\/s. In Proc. 36th Intl. Conf. on Neural Information Processing Systems (NIPS '22). Curran Associates Inc., Article 1127, 13 pages."},{"key":"e_1_2_2_14_1","unstructured":"Matthijs Douze Alexandr Guzhva Chengqi Deng Jeff Johnson Gergely Szilvasy Pierre-Emmanuel Mazar\u00e9 Maria Lomeli Lucas Hosseini and Herv\u00e9 J\u00e9gou. 2024. The Faiss library. https:\/\/github.com\/facebookresearch\/faiss. arXiv:2401.08281 [cs.LG]"},{"key":"e_1_2_2_15_1","volume-title":"EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. arXiv 1609.07228. https:\/\/api.semanticscholar.org\/CorpusID:9041621","author":"Fu Cong","year":"2016","unstructured":"Cong Fu and Deng Cai. 2016. EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. arXiv 1609.07228. https:\/\/api.semanticscholar.org\/CorpusID:9041621"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589282"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671516"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543507.3583552"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5591\/978--1--57735--516--8\/IJCAI11--222"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3652583.3658117"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3489517.3530560"},{"key":"e_1_2_2_27_1","unstructured":"Peng-Cheng Lin and Wan-Lei Zhao. 2019. Graph based Nearest Neighbor Search: Promises and Failures. https:\/\/arxiv.org\/abs\/1904.02077. arXiv:1904.02077 [cs.IR]"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489506"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.3169\/mta.6.2"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589777"},{"key":"e_1_2_2_33_1","unstructured":"Blaise Munyampirwa Vihan Lakshman and Benjamin Coleman. 2024. Down with the Hierarchy: The 'H' in HNSW Stands for ''Hubs''. https:\/\/arxiv.org\/abs\/2412.01940. arXiv:2412.01940 [cs.LG]"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3581783.3612290"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00323"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626246.3654691"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654923"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SISAP.2008.18"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.09.014"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/D14-1162"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_2_42_1","article-title":"Stratified Graph Indexing for efficient search in deep descriptor databases","volume":"13","author":"Mahabubur Rahman M M","year":"2024","unstructured":"M M Mahabubur Rahman and Jelena Te\u0161ic. 2024. Stratified Graph Indexing for efficient search in deep descriptor databases. Int. J. Multimed. Inf. Retr. 13, 3 (2024).","journal-title":"Int. J. Multimed. Inf. Retr."},{"key":"e_1_2_2_43_1","volume-title":"Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri.","author":"Singh Aditi","year":"2021","unstructured":"Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021. FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search. https:\/\/arxiv.org\/abs\/2105.09613. arXiv:2105.09613 [cs.IR]"},{"key":"e_1_2_2_44_1","unstructured":"Martin Skrodzki. 2019. The k-d tree data structure and a proof for neighborhood computation in expected logarithmic time. https:\/\/arxiv.org\/abs\/1903.04936. arXiv:1903.04936 [cs.DS]"},{"key":"e_1_2_2_45_1","volume-title":"Proc. of the 33rd International Conference on Neural Information Processing Systems. Curran Associates Inc., Article 1233","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishaswamy, and Harsha Vardhan Simhadri. 2019. DiskANN: fast accurate billion-point nearest neighbor search on a single node. In Proc. of the 33rd International Conference on Neural Information Processing Systems. Curran Associates Inc., Article 1233, 11 pages."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-031--46994--7_21"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-031--75823--2_21"},{"key":"e_1_2_2_49_1","first-page":"39","article-title":"Approximate Nearest Neighbor Search in High Dimensional Vector Databases: Current Research and Future Directions","volume":"46","author":"Tian Yao","year":"2023","unstructured":"Yao Tian, Ziyang Yue, Ruiyuan Zhang, Xi Zhao, Bolong Zheng, and Xiaofang Zhou. 2023. Approximate Nearest Neighbor Search in High Dimensional Vector Databases: Current Research and Future Directions. IEEE Data Eng. Bull. 46, 3 (2023), 39--54. http:\/\/sites.computer.org\/debull\/A23sept\/p39.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031--3203(80)90066--7"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457550"},{"key":"e_1_2_2_52_1","unstructured":"Mengzhao Wang Lingwei Lv Xiaoliang Xu Yuxiang Wang Qiang Yue and Jiongkang Ni. 2022. Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints. https:\/\/arxiv.org\/abs\/2203.13601. arXiv:2203.13601 [cs.DB]"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476255"},{"key":"e_1_2_2_54_1","first-page":"3","article-title":"Graph- and Tree-based Indexes for High-dimensional Vector Similarity Search: Analyses, Comparisons, and Future Directions","volume":"47","author":"Wang Zeyu","year":"2023","unstructured":"Zeyu Wang, Peng Wang, Themis Palpanas, and Wei Wang. 2023. Graph- and Tree-based Indexes for High-dimensional Vector Similarity Search: Analyses, Comparisons, and Future Directions. IEEE Data Eng. Bull. 47, 3 (2023), 3--21. http:\/\/sites.computer.org\/debull\/A23sept\/issue1.htm","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3698814"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.226"},{"key":"e_1_2_2_57_1","volume-title":"Xiyue Gao, Qianru Wang, Yanguo Peng, and Jiangtao Cui.","author":"Yang Shuo","year":"2024","unstructured":"Shuo Yang, Jiadong Xie, Yingfan Liu, Jeffrey Xu Yu, Xiyue Gao, Qianru Wang, Yanguo Peng, and Jiangtao Cui. 2024. Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search. arXiv:2410.01231 [cs.DB] https:\/\/arxiv.org\/abs\/2410.01231"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/icde53745.2022.00046"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00094"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594527"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725325","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:53:38Z","timestamp":1774983218000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725325"],"URL":"https:\/\/doi.org\/10.1145\/3725325","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}