title: Efficient computation of k-Nearest Neighbour Graphs for large high-dimensional data sets on GPU clusters.
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 [Formula: see text]-NNG generation for a dataset of twenty million images with 15 k dimensionality into the realm of practical possibility.
authors.affiliation: Department of Mechanical Engineering, Complex Systems Simulation Lab, University of Wisconsin-Milwaukee, Milwaukee, Wisconsin, United States of America.
authors.forename: Ali
authors.initials: A
authors.lastname: Dashti
authors.forename: Ivan
authors.initials: I
authors.lastname: Komarov
authors.forename: Roshan M
authors.initials: RM
authors.lastname: D'Souza
mesh_terms: D016000:Cluster Analysis; D003196:Computer Graphics