Towards A Massive-scale Distributed Neighborhood Graph Construction
Open Access
- 12 November 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 730-738
Abstract
Graph-based approximate nearest neighbor algorithms have shown high performance and quality. However, such approaches require a large amount of memory and still take a long time to construct high-quality nearest neighbor graphs (NNGs). Using distributed memory systems is important when data is large or a shorter indexing time is desired. We develop a distributed memory version of NN-Descent, a widely known graph-based ANN algorithm, closely following algorithmic advances by PyNN-Descent authors. Our distributed NN-Descent (DNND) is built on top of MPI and leverages two existing high-performance computing libraries: YGM (an asynchronous communication library) and Metall (a persistent memory allocator). We evaluate the performance of DNND on an HPC system using billion-scale datasets, demonstrating that our approach shows high performance and strong scaling and has great potential for developing massive-scale NNG frameworks.Keywords
This publication has 18 references indexed in Scilit:
- Fast Distributed k NN Graph Construction Using Auto-tuned Locality-sensitive HashingACM Transactions on Intelligent Systems and Technology, 2020
- ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithmsInformation Systems, 2020
- Pyramid: A General Framework for Distributed Similarity Search on Large-scale Datasets2019
- Billion-Scale Similarity Search with GPUsIEEE Transactions on Big Data, 2019
- Fast approximate nearest neighbor search with the navigating spreading-out graphProceedings of the VLDB Endowment, 2019
- Towards a Distributed Large-Scale Dynamic Graph Data Store2016
- Efficient K-Nearest Neighbor Graph Construction Using MapReduce for Large-Scale Data SetsIEICE Transactions on Information and Systems, 2014
- Efficient k-nearest neighbor graph construction for generic similarity measures2011
- Product Quantization for Nearest Neighbor SearchIEEE Transactions on Pattern Analysis and Machine Intelligence, 2010
- MapReduceCommunications of the ACM, 2008