Abstract
Data clustering is a fundamental task in modern data science, yet traditional methods like the Normalized Cut (Ncut) framework suffer from high computational complexity. This paper presents a high-performance parallel clustering algorithm that transforms the Ncut problem into a tractable isoperimetric problem on trees. By leveraging CUDA-enabled GPUs to process Minimum Spanning Trees (MST) through a novel depth-by-depth partitioning strategy, the proposed method achieves up to a 21x speedup over sequential CPU implementations while maintaining high accuracy across diverse high-dimensional datasets.
Introduction
As datasets grow in both volume and dimensionality, the need for scalable unsupervised grouping techniques becomes critical. The Normalized Cut (Ncut) framework is highly effective because it minimizes the ratio of edges cut to the volume of the resulting clusters, effectively finding natural partitions in data. However, solving Ncut is NP-complete for general graphs. While spectral clustering offers an approximation, it remains computationally intensive for large-scale applications.
This research addresses these limitations by focusing on the isoperimetric number of trees. By approximating the data's structure with a Minimum Spanning Tree (MST), the partitioning problem becomes mathematically tractable. The authors implement this approach on NVIDIA’s CUDA platform, turning a sequential backtracking problem into a structured parallel task.
Methodology
The authors propose a multi-stage parallel pipeline designed to maximize the throughput of GPU architectures. The implementation relies on a sophisticated mapping of data structures to the GPU's memory hierarchy.
1. Affinity Graph Construction and MST Generation
The process begins by treating data points as nodes in a graph. The algorithm assigns one GPU thread to each pair of data points to compute similarity weights in parallel. From this affinity matrix, a Minimum Spanning Tree is extracted using a parallelized version of Prim’s algorithm. This stage utilizes "min-reduction" primitives to find the nearest vertices across thousands of cores simultaneously.
2. Depth-by-Depth Partitioning
The core innovation lies in the tree partitioning strategy. In a rooted tree, all vertices at the same depth can be evaluated for "cutting" or "joining" independently. The algorithm traverses the tree from the lowest depth upward (BFS order), processing entire levels of the tree in parallel. To handle potential race conditions where multiple child nodes update a single parent, the authors implemented a custom ChildId array for safe conflict resolution.
3. Binary Search Optimization
To identify the optimal $k$ clusters, the algorithm performs a binary search over the isoperimetric cost. It iteratively calls the parallel partitioning routine, refining the clusters until the target criteria are met.
Experimental Results
The algorithm was benchmarked against several UCI Machine Learning Repository datasets, including Wine, Skin, Yeast, and Internet Advertisements. Key findings include:
- Significant Speedups: The GPU implementation demonstrated a 20.89x speedup on the high-dimensional "Internet Advertisements" dataset (8.4s on GPU vs. 177s on CPU).
- Scalability: In synthetic tests with 30,000 points, the GPU's execution time remained relatively flat as dimensionality increased, whereas the CPU's time grew exponentially.
- Accuracy: Speed gains did not compromise quality; the misclassification rate for the Skin dataset remained as low as 0.014.
- Small Data Penalty: For very small datasets (e.g., Wine), the CPU outperformed the GPU due to the overhead of transferring data to the graphics card, a common characteristic of GPGPU computing.
Conclusion and Future Work
By combining the structural simplicity of trees with the massive parallelism of modern GPUs, this algorithm provides a viable path for real-time clustering of high-dimensional data. The primary remaining bottleneck is GPU VRAM, as the $O(n^2)$ affinity matrix can exceed the memory limits of standard hardware. Future research will focus on sparse matrix representations and tiling techniques to extend this approach to even larger datasets.
Summary updated