Efficient Computation of k-Nearest Neighbour Graphs for Large High-Dimensional Data Sets on GPU Clusters
Open Access
- 23 September 2013
- journal article
- research article
- Published by Public Library of Science (PLoS) in PLOS ONE
- Vol. 8 (9) , e74113
Abstract
This paper presents an implementation of the brute-force exact k-Nearest Neighbor Graph (k-NNG) construction for ultra-large high-dimensional data cloud. The proposed method uses Graphics Processing Units (GPUs) and is scalable with multi-levels of parallelism (between nodes of a cluster, between different GPUs on a single node, and within a GPU). The method is applicable to homogeneous computing clusters with a varying number of nodes and GPUs per node. We achieve a 6-fold speedup in data processing as compared with an optimized method running on a cluster of CPUs and bring a hitherto impossible -NNG generation for a dataset of twenty million images with 15 k dimensionality into the realm of practical possibility.Keywords
This publication has 25 references indexed in Scilit:
- GPU-FS-kNN: A Software Tool for Fast and Scalable kNN Computation Using GPUsPLOS ONE, 2012
- Randomized approximate nearest neighbors algorithmProceedings of the National Academy of Sciences, 2011
- Mapping the conformations of biological assembliesNew Journal of Physics, 2010
- Optimal construction of -nearest-neighbor graphs for identifying noisy clustersTheoretical Computer Science, 2009
- Inferring missing genotypes in large SNP panels using fast nearest-neighbor searches over sliding windowsBioinformatics, 2007
- Nearest Neighbors in High-Dimensional Spaces2004
- A Global Geometric Framework for Nonlinear Dimensionality ReductionScience, 2000
- An optimal algorithm for approximate nearest neighbor searching fixed dimensionsJournal of the ACM, 1998
- AnO(n logn) algorithm for the all-nearest-neighbors ProblemDiscrete & Computational Geometry, 1989
- Multidimensional divide-and-conquerCommunications of the ACM, 1980