Print Email Facebook Twitter An Efficient Dual-Hierarchy t-SNE Minimization Title An Efficient Dual-Hierarchy t-SNE Minimization Author van de Ruit, M. (TU Delft Computer Graphics and Visualisation) Billeter, M.J. (University of Leeds) Eisemann, E. (TU Delft Computer Graphics and Visualisation) Date 2021 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. Subject GPGPUHigh dimensional datadimensionality reductiondual-hierarchyparallel data structures To reference this document use: http://resolver.tudelft.nl/uuid:f4ee8e43-fe5e-4711-a1be-d9de4a88ef6d DOI https://doi.org/10.1109/TVCG.2021.3114817 ISSN 1941-0506 Source IEEE Transactions on Visualization and Computer Graphics, 28 (1), 614-622 Part of collection Institutional Repository Document type journal article Rights © 2021 M. van de Ruit, M.J. Billeter, E. Eisemann Files PDF An_Efficient_Dual_Hierarc ... zation.pdf 3.66 MB Close viewer /islandora/object/uuid:f4ee8e43-fe5e-4711-a1be-d9de4a88ef6d/datastream/OBJ/view