An Efficient Dual-Hierarchy t-SNE Minimization.

Area of Science:

• Computational statistics
• Machine learning
• Data visualization

Background:

• t-distributed Stochastic Neighbour Embedding (t-SNE) is a standard for exploratory data analysis, effective at revealing clusters in complex datasets.
• Previous optimizations addressed similarity computations and minimization, but t-SNE remains computationally expensive for datasets with millions of points.

Purpose of the Study:

• To present a novel method for accelerating the t-SNE minimization process.
• To improve the performance of t-SNE on large-scale datasets while maintaining accuracy, even for 3D embeddings.

Main Methods:

• Developed a novel approach for t-SNE minimization with overall linear runtime complexity.
• Constructed a pair of spatial hierarchies over the embedding to approximate N-body interactions efficiently.
• Implemented an efficient GPGPU (General-Purpose Graphics Processing Unit) version of the method.

Main Results:

• Achieved significant performance improvements in the most computationally intensive parts of the t-SNE minimization.
• Demonstrated comparable accuracy to state-of-the-art methods, even for 3D embeddings.
• Evaluated performance on various datasets, showcasing efficiency gains.

Conclusions:

• The proposed method offers a substantial performance boost for large-scale t-SNE applications.
• This advancement makes t-SNE more practical for analyzing massive datasets, enabling deeper insights into complex data structures.