一种基于异步I/O的磁盘向量检索算法
An Asynchronous I/O-Based Disk Vector Retrieval Algorithm
DOI: 10.12677/CSA.2024.141008, PDF,   
作者: 吴松林, 田春岐：同济大学电子与信息工程学院，上海；毕枫林：华东师范大学数据科学与工程学院，上海
关键词: 向量检索；异步I/O；Vector Search； Asynchronous I/O
摘要: 在机器学习与深度学习等领域中，近似最近邻搜索(ANNS)扮演着至关重要的角色，在近十多年来受到越来越多研究者的关注。传统的ANNS算法需要将向量原始数据和索引数据全部存储在内存中，这限制了其处理大数据的能力。本文提出了一种创新的基于异步I/O的磁盘向量近似最近邻搜索算法(AIO-ANN)，该算法通过生成非阻塞I/O请求并即刻处理完成的请求，有效提升了搜索效率并降低了高延迟I/O请求的负面影响。在搜索过程中，AIO-ANN生成一批非阻塞I/O请求，并立即处理每个完成的I/O请求，而不是等待整批请求完成。同时为了最大化I/O等待时间的利用，算法将大部分计算任务转移到了I/O等待期间。此外，算法还整合了其他优化措施，如数据缓存与结果初始化。在大规模数据集上的实验，证明了AIO-ANN在搜索速度上超越了主流的ANNS算法DiskANN。
Abstract: In the fields of machine learning and deep learning, Approximate Nearest Neighbor Search (ANNS) plays a crucial role and has garnered increasing attention from researchers over the past decade. Traditional ANNS algorithms require storing all vector raw data and index data in memory, limiting their ability to process large datasets. This paper introduces an innovative Asynchronous I/O-based Disk Vector Approximate Nearest Neighbor Search algorithm (AIO-ANN), which enhances search ef-ficiency and reduces the negative impact of high-latency I/O requests by generating non-blocking I/O requests and immediately processing completed requests. During the search process, AIO-ANN generates a batch of non-blocking I/O requests and processes each completed request immediately, rather than waiting for the entire batch to complete. To maximize the utilization of I/O waiting time, the algorithm shifts the majority of computational tasks to these waiting periods. Additionally, the algorithm incorporates other optimization measures, such as data caching and result initialization. Experiments on large-scale datasets have proven that AIO-ANN surpasses mainstream ANNS algo-rithms like DiskANN in search speed.
文章引用：吴松林, 田春岐, 毕枫林. 一种基于异步I/O的磁盘向量检索算法[J]. 计算机科学与应用, 2024, 14(1): 68-77. https://doi.org/10.12677/CSA.2024.141008

参考文献

[1] Wang, M., Xu, X., Yue, Q. and Wang, Y. (2022) A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search. Proceedings of the VLDB Endowment, 14, 1964-1978.
[2] Jayaram Subramanya, S., Devvrit, F., Simhadri, H.V., Krishnawamy, R. and Kadekodi, R. (2019) DiskANN: Fast Accurate Billion-Point Nearest Neigh-bor Search on a Single Node. Proceedings of the 33rd International Conference on Neural Information Processing Systems, Vancouver, 8-14 December 2019, 13766-137760
[3] Chen, Q., et al. (2021) SPANN: Highly-Efficient Billion-Scale Ap-proximate Nearest Neighborhood Search. Advances in Neural Information Processing Systems, New York, USA, 21 December 2021, 5199-5212.
[4] Zhang, M. and He, Y. (2018) Zoom: SSD-Based Vector Search for Optimizing Accuracy, Latency and Memory.
https://arxiv.org/abs/1809.04067
[5] Zhang, M. and He, Y. (2019) GRIP: Multi-Store Capacity-Optimized High-Performance Nearest Neighbor Search for Vector Search Engine. Proceedings of the 28th ACM International Conference on Information and Knowledge Management, Beijing, 3-7 November 2019, 1673-1682.
[6] Muja, M. and Lowe, D. (2009) Flann-Fast Library for Approximate Nearest Neighbors User Manual. Computer Science Department, University of British Co-lumbia, Vancouver.
[7] Wang, J., Shen, H.T., Song, J., et al. (2014) Hashing for Similarity Search: A Survey.
https://arxiv.org/abs/1408.2927
[8] Wang, J., Liu, W., Kumar, S. and Chang, S.F. (2015) Learning to Hash for Indexing Big Data—A Survey. Proceedings of the IEEE, 104, 34-57. [Google Scholar] [CrossRef] 
[9] Gersho, A. and Gray, R.M. (2012) Vector Quantization and Signal Compression. Springer, New York.
[10] Jegou, H., Douze, M. and Schmid, C. (2010) Product Quantization for Nearest Neighbor Search. IEEE Transactions on Pattern Analysis and Machine In-telligence, 33, 117-128. [Google Scholar] [CrossRef] 
[11] Ge, T., He, K., Ke, Q. and Sun, J. (2013) Optimized Product Quantization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36, 744-755. [Google Scholar] [CrossRef] 
[12] Kalantidis, Y. and Avrithis, Y. (2014) Locally Optimized Product Quanti-zation for Approximate Nearest Neighbor Search. Proceedings of the IEEE Conference on Computer Vision and Pattern Recog-nition, Columbus, 23-28 June 2014, 2329-2336. [Google Scholar] [CrossRef] 
[13] Klein, B. and Wolf, L. (2019) End-to-End Supervised Product Quantization for Image Search and Retrieval. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, Long Beach, 15-20 June 2019, 5036-5045. [Google Scholar] [CrossRef] 
[14] Johnson, J., Douze, M. and Jégou, H. (2019) Billion-Scale Similarity Search with GPUs. IEEE Transactions on Big Data, 7, 535-547. [Google Scholar] [CrossRef] 
[15] Baranchuk, D., Babenko, A. and Malkov, Y. (2018) Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors. In: Ferrari, V., Hebert, M., Sminchisescu, C. and Weiss, Y., Eds., Computer Vision—ECCV 2018, Springer, Cham, 202-216. [Google Scholar] [CrossRef] 
[16] Guo, R., Sun, P., Lindgren, E., et al. (2020) Accelerating Large-Scale Inference with Anisotropic Vector Quantization. Proceedings of the 37th International Conference on Machine Learning, 13-18 July 2020, 3887-3896.
[17] Toussaint, G.T. (1980) The Rela-tive Neighbourhood Graph of a Finite Planar Set. Pattern Recognition, 12, 261-268. [Google Scholar] [CrossRef] 
[18] Malkov, Y., Ponomarenko, A., Logvinov, A. and Krylov, V. (2014) Approximate Nearest Neighbor Algorithm Based on Navigable Small World Graphs. Information Systems, 45, 61-68. [Google Scholar] [CrossRef] 
[19] Malkov, Y.A. and Yashunin, D.A. (2018) Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Ma-chine Intelligence, 42, 824-836. [Google Scholar] [CrossRef] 
[20] Fu, C., Xiang, C., Wang, C. and Cai, D. (2019) Fast Approximate Nearest Neighbor Search with the Navigating Spreading-Out Graph. Proceedings of the VLDB Endowment, 12, 461-474. [Google Scholar] [CrossRef] 
[21] Simhadri, H.V., et al. (2022) Results of the NeurIPS’21 Challenge on Billion-Scale Approximate Nearest Neighbor Search. Proceedings of the NeurIPS 2021 Competitions and Demonstrations Track, New York, USA, 6-14 December 2021, 177-189.