Efficient computation of k-Nearest Neighbour Graphs for large high-dimensional data sets on GPU clusters.

Area of Science:

• Computer Science
• Data Science
• High-Performance Computing

Background:

• Exact k-Nearest Neighbor Graph (k-NNG) construction is computationally intensive, especially for ultra-large, high-dimensional datasets.
• Existing methods struggle with scalability and efficiency when dealing with massive data clouds.

Purpose of the Study:

• To implement a scalable, brute-force exact k-Nearest Neighbor Graph (k-NNG) construction method utilizing Graphics Processing Units (GPUs).
• To demonstrate the feasibility of generating k-NNG for datasets previously considered computationally prohibitive.

Main Methods:

• Leveraging multi-levels of parallelism: inter-node, inter-GPU, and intra-GPU parallelism.
• Employing Graphics Processing Units (GPUs) for accelerated computation.
• Designing a method applicable to homogeneous computing clusters with flexible node and GPU configurations.

Main Results:

• Achieved a 6-fold speedup in data processing compared to optimized CPU-based methods.
• Enabled the practical generation of k-NNG for a dataset of twenty million images with 15k dimensionality.
• Demonstrated scalability across varying cluster and GPU configurations.

Conclusions:

• The GPU-accelerated k-NNG construction method offers significant performance improvements for ultra-large, high-dimensional data.
• This approach makes previously intractable k-NNG generation tasks feasible, opening new possibilities in data analysis.
• The method's scalability and applicability to diverse hardware setups enhance its practical utility.