Barnes-Hut-SNE

By L. V. D. van der Maaten. 2013

224 citations recorded by the source corpus.

The paper presents an O(N log N)-implementation of t-SNE -- an embedding technique that is commonly used for the visualization of high-dimensional data in scatter plots and that normally runs in O(N^2). The new implementation uses vantage-point trees to compute sparse pairwise similarities between the input data objects, and it uses a variant of the Barnes-Hut algorithm - an algorithm used by astronomers to perform N-body simulations - to approximate the forces between the corresponding points in the embedding. Our experiments show that the new algorithm, called Barnes-Hut-SNE, leads to substantial computational advantages over standard t-SNE, and that it makes it possible to learn embeddings of data sets with millions of objects.

Subfields: Astronomy and Astrophysics, Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Representation & Self-Supervised Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Astronomy and Astrophysics

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

In Representation & Self-Supervised Learning

Citations in the corpus

Learning Phrase Representations using RNN Encoder–Decoder for Statistical Machine Translation (2014, methodology): “The projection was done by the recently proposed Barnes-Hut-SNE (van der Maaten, 2013).”
Domain-Adversarial Training of Neural Networks (2015, methodology): “We use t-SNE (van der Maaten, 2013) projection to visualize feature distributions at different points of the network, while color-coding the domains (Figure 5).”
The Variational Fair Autoencoder (2015, methodology): “In order to further assess the nature of our new representations, we visualized two dimensional Barnes-Hut SNE (van der Maaten, 2013) embeddings of the z1 representations, obtained from the model trained on the Adult dataset, in Figure 4.”
Achieving Open Vocabulary Neural Machine Translation with Hybrid Word-Character Models (2016, methodology): “Figure 4 shows the two-dimensional representations of words computed by the Barnes-Hut-SNE algo-7 rithm (van der Maaten, 2013).”
Approximated and User Steerable tSNE for Progressive Visual Analytics (2015, methodology): “Throughout the experiments we used a parameter setup similar to the one used to benchmark the BHSNE [4], [6].”
Deep Domain Generalization via Conditional Invariant Adversarial Networks (2018, methodology): “To better understand the generalization ability of different methods, we also visualize the learned feature distribution using t-SNE [32] projection in Figure 3.”
The GALAH survey: observational overview and Gaia DR1 companion (2016, methodology): “The latter is checked by morphological classification of spectra which is based on a t-distributed stochastic neighbor embedding algorithm (Traven et al. 2016, in preparation; for description of the algorithm see van der Maaten 2013 and references therein).”
Perplexity-free t-SNE and twice Student tt-SNE (2018, background): “Variants with alternative divergences as cost functions [7, 8, 9] and lower-complexity tree-based approximations [10, 11] have been developed.”
PPF-FoldNet: Unsupervised Learning of Rotation Invariant 3D Local Descriptors (2018, methodology): “We then run the Barnes Hut T-SNE algorithm [24,42] on the extracted codewords and form a two-dimensional embedding space, as shown in Fig.”