Stochastic proximity embedding on graphics processing units: taking multidimensional scaling to a new scale.

Area of Science:

• Computational statistics
• Machine learning
• Data visualization

Background:

• High-dimensional data analysis presents computational challenges.
• Traditional dimensionality reduction methods like Multidimensional Scaling (MDS) have quadratic time complexity (O(n²)).
• Stochastic Proximity Embedding (SPE) offers a linear time complexity (O(n)) alternative for efficient embedding.

Purpose of the Study:

• To accelerate the Stochastic Proximity Embedding (SPE) algorithm.
• To enable the analysis of extremely large datasets previously intractable for SPE.
• To leverage the parallel processing capabilities of Graphics Processing Units (GPUs) for dimensionality reduction.

Main Methods:

• Developed a multithreaded implementation of Stochastic Proximity Embedding (SPE).
• Utilized Graphics Processing Units (GPUs) to parallelize distance calculations and updates.
• Applied the GPU-accelerated SPE to high-dimensional datasets of varying sizes.

Main Results:

• The GPU-accelerated SPE achieves significant speedups compared to the CPU-based version.
• Embeddings generated by the GPU-SPE are of comparable quality to classical MDS.
• The method successfully embeds datasets with millions of data points within interactive time scales.

Conclusions:

• GPU-accelerated SPE provides a scalable and efficient solution for dimensionality reduction.
• This approach makes advanced data embedding techniques accessible for massive datasets.
• The findings open new possibilities for interactive analysis of large-scale, high-dimensional data.