On the Accuracy and Parallelism of GPGPU-Powered Incremental Clustering Algorithms

Area of Science:

• Computer Science
• Data Mining
• High-Performance Computing

Background:

• Incremental clustering is crucial for massive and real-time data analysis, demanding significant computational resources.
• General Purpose Graphics Processing Units (GPGPUs) offer parallel computing capabilities but present challenges for incremental clustering algorithms.
• A fundamental dilemma exists between maintaining clustering accuracy and achieving high parallelism when using GPGPUs.

Purpose of the Study:

• To formally analyze the cause of the accuracy-parallelism dilemma in incremental clustering on GPGPUs.
• To establish theoretical bounds and relationships between key concepts like evolving granularity, clustering accuracy, and parallelism.
• To provide a foundation for developing optimized incremental clustering algorithms for parallel hardware.

Main Methods:

• Formalization of core incremental clustering concepts, including evolving granularity.
• Mathematical proof of two theorems: one relating clustering accuracy to evolving granularity (via mis-affiliation bounds), and another linking parallelism to evolving granularity (via work-depth).
• Validation of theoretical findings through a demonstration algorithm and experimental analysis.

Main Results:

• Clustering accuracy is negatively correlated with evolving granularity; higher granularity leads to lower accuracy.
• Parallelism is positively correlated with evolving granularity; higher granularity enables superior parallelism (smaller work-depth).
• The inherent contradiction between these relationships explains the observed accuracy-parallelism dilemma.

Conclusions:

• The study formally elucidates the trade-off between accuracy and parallelism in GPGPU-based incremental clustering.
• Evolving granularity is identified as the critical factor driving this dilemma.
• Theoretical insights pave the way for designing incremental clustering algorithms that better balance accuracy and performance on parallel architectures.