An Efficient Dual-Hierarchy t-SNE Minimization

Research output: Contribution to journalArticleScientificpeer-review

6 Citations (Scopus)
66 Downloads (Pure)

Abstract

t-distributed Stochastic Neighbour Embedding (t-SNE) has become a standard for exploratory data analysis, as it is capable of revealing clusters even in complex data while requiring minimal user input. While its run-time complexity limited it to small datasets in the past, recent efforts improved upon the expensive similarity computations and the previously quadratic minimization. Nevertheless, t-SNE still has high runtime and memory costs when operating on millions of points. We present a novel method for executing the t-SNE minimization. While our method overall retains a linear runtime complexity, we obtain a significant performance increase in the most expensive part of the minimization. We achieve a significant improvement without a noticeable decrease in accuracy even when targeting a 3D embedding. Our method constructs a pair of spatial hierarchies over the embedding, which are simultaneously traversed to approximate many N-body interactions at once. We demonstrate an efficient GPGPU implementation and evaluate its performance against state-of-the-art methods on a variety of datasets.
Original languageEnglish
Article number9552856
Pages (from-to)614-622
Number of pages9
JournalIEEE Transactions on Visualization and Computer Graphics
Volume28
Issue number1
DOIs
Publication statusPublished - 2021

Keywords

  • GPGPU
  • High dimensional data
  • dimensionality reduction
  • dual-hierarchy
  • parallel data structures

Fingerprint

Dive into the research topics of 'An Efficient Dual-Hierarchy t-SNE Minimization'. Together they form a unique fingerprint.

Cite this