Fast k-NNG construction with GPU-based quick multi-select.

Area of Science:

• Computer Science
• Data Science
• Machine Learning

Background:

• k-Nearest Neighbor Graph (k-NNG) construction is crucial for machine learning, bioinformatics, and clustering.
• Existing algorithms are efficient for low-dimensional data but struggle with high-dimensional datasets.
• Brute force search remains the optimal strategy for high-dimensional k-NNG construction.

Purpose of the Study:

• To present a novel brute force algorithm for building the k-Nearest Neighbor Graph (k-NNG).
• To optimize the k-NN search process for high-dimensional data using GPU acceleration.
• To improve the efficiency and performance of k-NNG construction.

Main Methods:

• The algorithm involves two main stages: calculating inter-vector distances (matrix multiplication) and selecting k-Nearest Neighbors (k-NNs).
• A novel GPU-based multi-select algorithm, leveraging quick sort, is introduced for efficient k-NN selection.
• Optimization techniques utilize GPU warp voting functions and user-controlled cache for enhanced performance.

Main Results:

• The proposed GPU-based algorithm demonstrates significant performance improvements over existing state-of-the-art implementations.
• Benchmarks confirm the effectiveness of the novel multi-select algorithm on GPUs.
• The matrix multiplication formulation for distance calculation is efficient for high-dimensional data.

Conclusions:

• The new brute force algorithm offers a superior solution for k-NNG construction in high-dimensional spaces.
• GPU acceleration, particularly with the novel multi-select method, drastically speeds up k-NN search.
• This work advances the efficiency of k-NNG applications in data-intensive fields.