Barnes-Hut-SNE
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- 80 Million Tiny Images: A Large Data Set for Nonparametric Object and Scene RecognitionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2008
- Learning distributed representations of concepts using linear relational embeddingIEEE Transactions on Knowledge and Data Engineering, 2001
- Nonlinear Dimensionality Reduction by Locally Linear EmbeddingScience, 2000
- A Global Geometric Framework for Nonlinear Dimensionality ReductionScience, 2000
- Skeletons from the Treecode ClosetJournal of Computational Physics, 1994
- Increased rates of convergence through learning rate adaptationNeural Networks, 1988
- A fast algorithm for particle simulationsJournal of Computational Physics, 1987
- A hierarchical O(N log N) force-calculation algorithmNature, 1986
- Rapid solution of integral equations of classical potential theoryJournal of Computational Physics, 1985
- Organization and maintenance of large ordered indexesActa Informatica, 1972