Accelerating t-SNE using tree-based algorithms

Laurens van der Maaten

article2014JMLR2,668 citations

Develops tree-based algorithms using Barnes-Hut and dual-tree approximations to reduce the computational complexity of t-SNE from quadratic to O(N log N), enabling practical visualization of datasets with millions of high-dimensional objects.

Listen

The article addresses the challenge of visualizing large high-dimensional datasets, where standard t-distributed stochastic neighbor embedding (t-SNE) is limited by its quadratic computational scaling that restricts it to a few thousand points. This constraint hinders visual analytics for modern data volumes in fields such as image analysis, speech processing, and metagenomics.

The work evaluates two tree-based approximations to accelerate t-SNE gradient computation to O(N log N) time while using O(N) memory. It applies vantage-point trees to sparsify input similarities and then employs either a Barnes-Hut quadtree or a dual-tree algorithm to approximate repulsive forces in the embedding.

Experiments on five datasets ranging from 48,600 to 1.1 million points demonstrate that both variants produce embeddings of comparable quality to exact t-SNE, measured by nearest-neighbor classification error, yet complete in minutes to hours rather than days. Barnes-Hut t-SNE with trade-off parameter θ equal to 0.5 consistently achieves slightly better speed-accuracy balance than the dual-tree variant with θ equal to 0.2.

These results indicate that large-scale t-SNE embeddings are now practical, enabling scatter-plot visualization and downstream tasks such as density mapping for datasets previously considered intractable. The approach preserves local structure effectively while supporting global layout through early exaggeration.

Practitioners should adopt the Barnes-Hut implementation with θ set to 0.5 for most visualization needs. Further work is warranted to develop formal error bounds that account for iterative optimization and to explore metric trees for embeddings beyond three dimensions.

Delft University of Technology adaptive algorithms dual-tree high dimensional data Barnes-Hut algorithm tree-based algorithms dimensionality reduction

lvdmaaten/bhtsne Maaten (2014).pdf

Paper: Neighbourhood Components Analysis, Jacob Goldberger et al. (2004). Introduces the probabilistic neighbor-matching framework and soft-assignment objectives that serve as the direct mathematical foundations for stochastic neighbor embedding algorithms.
Paper: Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering, Mikhail Belkin et al. (2001). Establishes non-linear manifold learning using graph Laplacians and nearest-neighbor graphs, which provides essential background for non-linear dimensionality reduction.
Paper: Locality Preserving Projections, Xiaofei He et al. (2003). Presents foundational concepts in locality preservation and graph-based dimensionality reduction that motivate modern neighborhood embedding techniques.
Paper: Dimensionality Reduction by Learning an Invariant Mapping, Raia Hadsell et al. (2006). Introduces contrastive neighborhood-preserving mappings and margin-based force modeling essential to understanding attraction-repulsion dynamics in embedding optimization.
Paper: An Efficient k-Means Clustering Algorithm: Analysis and Implementation, Tapas Kanungo et al. (2002). Demonstrates how space-partitioning kd-trees can dramatically accelerate distance-based clustering algorithms by pruning candidate interactions.
Paper: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Alexandr Andoni et al. (2008). Provides the theoretical framework and indexing mechanisms for sublinear approximate nearest-neighbor search used to accelerate input similarity computations.

Paper: UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction, Leland McInnes et al. (2018). Builds upon scalable neighbor embedding principles to create a fast, topologically motivated dimension reduction algorithm that preserves both local and global data structure.
Paper: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, Yu. A. Malkov et al. (2016). Advances large-scale approximate nearest-neighbor graph construction, which is the key computational bottleneck in high-dimensional preprocessing for accelerated embedding methods.
Paper: Unsupervised Deep Embedding for Clustering Analysis, Junyuan Xie et al. (2015). Adapts the Student's t-distribution kernel and divergence minimization from t-SNE to train deep neural networks for unsupervised clustering.
Paper: Billion-Scale Similarity Search with GPUs, Jeff Johnson et al. (2019). Develops highly parallel GPU architectures for billion-scale similarity search, extending the scalability frontier beyond tree-based CPU approximations.
Paper: LINE: Large-scale Information Network Embedding, Jian Tang et al. (2015). Extends scalable first- and second-order proximity preservation to massive network graphs using asynchronous stochastic sampling.

Cover for Accelerating t-SNE using tree-based algorithms

Abstract

The paper investigates the acceleration of t-SNE—an embedding technique that is commonly used for the visualization of high-dimensional data in scatter plots—using two tree-based algorithms. In particular, the paper develops variants of the Barnes-Hut algorithm and of the dual-tree algorithm that approximate the gradient used for learning t-SNE embeddings in $\mathcal{O}(N \log N)$ . Our experiments show that the resulting algorithms substantially accelerate t-SNE, and that they make it possible to learn embeddings of data sets with millions of objects. Somewhat counterintuitively, the Barnes-Hut variant of t-SNE appears to outperform the dual-tree variant.

Topics

adaptive algorithms dual-tree high dimensional data optimization problems visualization efficient algorithm

Keywords

Barnes-Hut algorithm tree-based algorithms dimensionality reduction vantage-point trees nearest-neighbor search fast Gauss transform large-scale embeddings fast multipole methods low-dimensional embedding

1. Introduction
2. Related Work
3. t-Distributed Stochastic Neighbor Embedding
4. Tree-Based Algorithms for t-SNE
4.1 Approximating Input Similarities
4.2 Barnes-Hut Approximation
4.3 Dual-tree Approximation
5. Experiments
5.1 Data Sets
5.2 Experimental Setup
5.3 Results
6. Conclusion
Acknowledgments
References

Knowls

Knowl 1 — Sparse Input Similarity Approximation via Vantage-Point Trees
algorithm
t-Distributed Stochastic Neighbor Embedding (t-SNE) models the similarity between $N$ high-dimensional data points $\mathcal{D} = \{x_1, x_2, \dots, x_N\}$ via normalized Gaussian kernels. To reduce the computational complexity from $\mathcal{O}(N^2)$ to $\mathcal{O}(u N \log N)$ and memory to $\mathcal{O}(u N)$ for a target perplexity $u$ , the similarity distribution $P = (p_{ij})$ is approximated by restricting conditional similarities to the $\lfloor 3u \rfloor$ nearest neighbors of each point.

The sparse distribution is constructed as follows:
1. A vantage-point tree (VP-tree) is built on $\mathcal{D}$ using metric distances $d(x_i, x_j) = \|x_i - x_j\|$ . In a VP-tree, each node stores an object and a metric ball radius set to the median distance to all descendant objects in that partition, dividing points into internal and external subsets.
2. For every point $x_i$ , an exact depth-first nearest neighbor search in the VP-tree identifies the set $\mathcal{N}_i$ of its $\lfloor 3u \rfloor$ nearest neighbors in $\mathcal{O}(u \log N)$ expected time.
3. The conditional probabilities $p_{j|i}$ are defined to be non-zero only for $j \in \mathcal{N}_i$ : $p_{j|i} = \begin{cases} \frac{\exp\left(-d(x_i, x_j)^2 / 2\sigma_i^2\right)}{\sum_{k \in \mathcal{N}_i} \exp\left(-d(x_i, x_k)^2 / 2\sigma_i^2\right)}, & \text{if } j \in \mathcal{N}_i \\ 0, & \text{otherwise} \end{cases}$ where the Gaussian bandwidth $\sigma_i$ is solved by binary search such that the Shannon perplexity $2^{-\sum_{j \in \mathcal{N}_i} p_{j|i} \log_2 p_{j|i}}$ matches $u$ .
4. Symmetrized joint probabilities $p_{ij}$ are obtained by: $p_{ij} = \frac{p_{j|i} + p_{i|j}}{2N}$ with $p_{ii} = 0$ . The resulting sparse matrix $P$ contains $\mathcal{O}(uN)$ non-zero entries.
Knowl 2 — Decomposition of the t-SNE Gradient into Attractive and Repulsive Components
equation
The low-dimensional embedding coordinates $\mathcal{E} = \{y_1, y_2, \dots, y_N\} \subset \mathbb{R}^s$ (where $s \in \{2, 3\}$ ) are learned by minimizing the Kullback-Leibler divergence between high-dimensional similarities $p_{ij}$ and Student-t embedding similarities $q_{ij}$ , defined as: $q_{ij} = \frac{(1 + \|y_i - y_j\|^2)^{-1}}{Z}, \quad q_{ii} = 0, \quad Z = \sum_{k \neq l} (1 + \|y_k - y_l\|^2)^{-1}$

The analytical gradient of the objective function $C(\mathcal{E}) = \sum_{i \neq j} p_{ij} \log \frac{p_{ij}}{q_{ij}}$ with respect to the embedding point $y_i$ decomposes into attractive and repulsive forces: $\frac{\partial C}{\partial y_i} = 4(F_{\text{attr}}(i) + F_{\text{rep}}(i)) = 4 \left( \sum_{j \neq i} p_{ij} q_{ij} Z (y_i - y_j) - \sum_{j \neq i} q_{ij}^2 Z (y_i - y_j) \right)$ where the unnormalized kernel term $q_{ij} Z = (1 + \|y_i - y_j\|^2)^{-1}$ is computed in $\mathcal{O}(1)$ time.

Using a sparse similarity distribution $P$ with $\mathcal{O}(uN)$ non-zero entries, the attractive force vector: $F_{\text{attr}}(i) = \sum_{j \in \mathcal{N}_i \cup \{k \mid i \in \mathcal{N}_k\}} p_{ij} (1 + \|y_i - y_j\|^2)^{-1} (y_i - y_j)$ requires only $\mathcal{O}(uN)$ total evaluations across all $N$ points. The repulsive force vector evaluates across all pairs as: $F_{\text{rep}}(i) = -\frac{\sum_{j \neq i} (1 + \|y_i - y_j\|^2)^{-2} (y_i - y_j)}{\sum_{k \neq l} (1 + \|y_k - y_l\|^2)^{-1}}$
Knowl 3 — Barnes-Hut Gradient Approximation for t-SNE
algorithm
The Barnes-Hut algorithm approximates the $N$ -body repulsive force interactions $F_{\text{rep}}(i)$ and the global normalization term $Z$ in $\mathcal{O}(N \log N)$ time and $\mathcal{O}(N)$ space using a quadtree ( $s=2$ ) or octtree ( $s=3$ ).
Input: Embedding points {y_1, ..., y_N} in R^s, trade-off threshold theta >= 0
Output: Approximated repulsive forces F_rep(i) for all i in {1, ..., N}
1. Construct a quadtree/octtree containing all N points in O(N log N) time.
2. For each node 'cell' in the tree, compute:
     N_cell = total number of embedding points contained in cell
     y_cell = (1 / N_cell) * sum_{y_j in cell} y_j (center of mass)
     r_cell = diagonal length (size) of the bounding cell
3. Initialize global sum Z_total = 0.
4. for each point y_i (i = 1 to N) do:
     Initialize F_repZ(i) = 0, Z_i = 0
     Traverse the tree depth-first starting at root:
       for current node 'cell' do:
         if cell is a leaf containing point y_j (with j != i) then:
           dist_sq = ||y_i - y_j||^2
           qZ = (1 + dist_sq)^(-1)
           F_repZ(i) = F_repZ(i) - (qZ^2) * (y_i - y_j)
           Z_i = Z_i + qZ
         else if cell is an internal node and (r_cell / ||y_i - y_cell||^2) < theta then:
           dist_sq = ||y_i - y_cell||^2
           qZ = (1 + dist_sq)^(-1)
           F_repZ(i) = F_repZ(i) - N_cell * (qZ^2) * (y_i - y_cell)
           Z_i = Z_i + N_cell * qZ
           Prune traversal below cell
         else:
           Continue depth-first recursion on all children of cell
     Z_total = Z_total + Z_i
5. for each point y_i (i = 1 to N) do:
     F_rep(i) = F_repZ(i) / Z_total
6. return F_rep
Knowl 4 — Dual-Tree Gradient Approximation for t-SNE
algorithm
Dual-tree t-SNE approximates the repulsive gradient forces by calculating cell-cell interactions between pairs of tree nodes rather than point-cell interactions.

The algorithm executes as follows:
1. A quadtree (for 2D) or octtree (for 3D) is constructed on the embedding points $\{y_1, \dots, y_N\}$ . Each node stores point count $N_{\text{cell}}$ , center-of-mass $y_{\text{cell}}$ , and diameter $r_{\text{cell}}$ .
2. Two identical copies of the tree ( $T_A$ and $T_B$ ) are traversed simultaneously in a depth-first traversal. For any node pair $(\text{cell}_A, \text{cell}_B)$ , the summary condition is evaluated: $\frac{\max(r_{\text{cell}_A}, r_{\text{cell}_B})}{\|y_{\text{cell}_A} - y_{\text{cell}_B}\|^2} < \theta$ where $\theta$ is an accuracy-speed trade-off parameter.
3. When the condition holds:
  - The pairwise cell interaction $f_{AB} = -(1 + \|y_{\text{cell}_A} - y_{\text{cell}_B}\|^2)^{-2}(y_{\text{cell}_A} - y_{\text{cell}_B})$ is computed.
  - The force $N_{\text{cell}_B} f_{AB}$ is added to every constituent point in $\text{cell}_A$ , and $-N_{\text{cell}_A} f_{AB}$ is added to every constituent point in $\text{cell}_B$ .
  - All descendant node pairs of $\text{cell}_A$ and $\text{cell}_B$ are pruned from traversal.
4. When the condition is not met, the traversal recurses across all combinations of child nodes of $\text{cell}_A$ and $\text{cell}_B$ .
While reducing the number of force evaluations relative to the point-cell Barnes-Hut scheme, dual-tree t-SNE incurs bookkeeping overhead to scatter cell forces back to individual leaf points, resulting in an inferior empirical speed-accuracy trade-off for gradient computation.
Knowl 5 — Optimization Scheme and Early Exaggeration for Large-Scale t-SNE
model/method
Tree-accelerated t-SNE uses a specific optimization schedule to preserve global cluster structure when embedding large datasets:
1. Initialization: Low-dimensional coordinates $y_i \in \mathbb{R}^s$ are initialized by sampling randomly from an isotropic Gaussian distribution $\mathcal{N}(0, 10^{-4} I)$ .
2. Optimization Schedule: Gradient descent is run for 1,000 iterations. Step sizes are initialized to 200 and adapted dynamically per-coordinate using Jacobs' delta-bar-delta learning rate adaptation rule.
3. Momentum Schedule: A momentum term is weighted at $0.5$ for the first 250 iterations and increases to $0.8$ for iterations 251 through 1,000.
4. Early Exaggeration: During the first 250 iterations, all high-dimensional probabilities $p_{ij}$ are scaled by an exaggeration constant $\alpha = 12$ (increased from $\alpha = 4$ in original t-SNE). This amplifies attractive forces, forming dense, compact clusters that can easily maneuver around each other to establish global topological arrangement early in the optimization.
5. Preprocessing: High-dimensional inputs are reduced to 50 dimensions using Principal Component Analysis (PCA) prior to vantage-point tree construction and perplexity optimization (fixed to $u = 50$ ).
Knowl 6 — Empirical Performance Comparison of Barnes-Hut and Dual-Tree t-SNE
empirical result
Empirical evaluation on the full MNIST handwritten digit benchmark ( $N = 70,000$ , $D = 784$ reduced to 50 via PCA, perplexity $u = 50$ ) shows the speed and error behavior of tree-based t-SNE:
- Barnes-Hut t-SNE ( $\theta = 0.5$ ): Completes 1,000 iterations on 70,000 points in 751 seconds (12m 31s) on a 2.6 GHz dual-core CPU, achieving a 1-nearest neighbor classification error of $0.033$ , matching standard exact t-SNE.
- Dual-Tree t-SNE ( $\theta = 0.2$ ): Requires approximately 1,500 seconds to achieve a similar 1-nearest neighbor error ( $0.035$ ). Setting $\theta = 0.6$ speeds up computation but degrades 1-NN error to over $0.08$ .
- Scaling with $N$ : Evaluated on MNIST subsets from $N = 1,000$ $N = 1, 000$ to $N = 18,000$ $N = 18, 000$ :
  - Standard t-SNE exhibits quadratic runtime growth ( $\mathcal{O}(N^2)$ ), requiring over $10^4$ seconds at $N = 18,000$ .
  - Barnes-Hut t-SNE and dual-tree t-SNE exhibit $\mathcal{O}(N \log N)$ scaling, completing $N = 18,000$ in approximately $100$ seconds with negligible loss in 1-NN accuracy.
- Barnes-Hut t-SNE consistently achieves a superior speed-accuracy trade-off compared to dual-tree t-SNE due to the absence of node-to-point force scattering overhead.
Knowl 7 — Large-Scale Embedding Benchmarks and Density Visualization in t-SNE
empirical result
Barnes-Hut t-SNE (with $\theta = 0.5$ , perplexity $u = 50$ , and exaggeration $\alpha = 12$ ) enables nonlinear embedding of datasets containing up to over one million objects on a single CPU:
- CIFAR-10 ( $N = 70,000$ , $D = 1,024$ convolutional features): Embedding generated in 13m 20s; an 11-NN classifier on the 2D coordinates yields a test error of $0.2467$ , comparable to a logistic regressor on the 1,024-dimensional features.
- NORB ( $N = 48,600$ , $D = 9,216$ Laplacian-of-Gaussian features): Embedding generated in 6m 30s, resolving 3D elevation and azimuth rotation manifolds per object category without class label supervision.
- SVHN ( $N = 630,420$ , $D = 64$ convolutional features): Full street-view house numbers dataset embedded in 2h 57m 15s, separating digit classes while concentrating ambiguous digits at the center.
- TIMIT ( $N = 1,105,455$ speech frames, $D = 273$ MFCC features): Full acoustic dataset embedded in 3h 48m 12s across 39 phone classes.
- Density Masking Effect: When visualizing embeddings of size $N > 10^6$ , conventional scatter plots suffer from overplotting that masks local point density, falsely suggesting uniform coverage. Applying Parzen density estimation or class-conditional density mapping reveals that large-scale embeddings are composed of dense, compact clusters.
Knowl 8 — Gradient Error Bounds and Dimensionality Limitations of Tree-Based t-SNE
limitation
The tree-based approximations for t-SNE introduce two structural limitations:
1. Lack of Bounded Gradient Error in Barnes-Hut: The Barnes-Hut point-cell approximation does not guarantee bounded approximation error on the repulsive gradient, and errors can theoretically be unbounded. Dual-tree and fast multipole methods provide analytical bounds for static evaluations, but no theoretical bounds account for error propagation across iterative gradient descent steps. In practice, convergence to a local minimum is guaranteed provided the inner product between the estimated gradient and the true gradient remains positive.
2. Exponential Scaling with Embedding Dimensionality: Quadtrees and octtrees partition space into $2^s$ orthants per node, scaling exponentially with the target embedding dimension $s$ . Consequently, the Barnes-Hut and dual-tree approximations are efficient only for low-dimensional visualizations ( $s = 2$ or $s = 3$ ) and do not scale to higher target dimensions without replacing orthant trees with metric trees.

Coverage note — None was omitted; all contributed algorithmic components (VP-tree similarity sparsification, Barnes-Hut and dual-tree repulsive gradient approximations), optimization enhancements (early exaggeration scaling), empirical benchmarks on five large datasets, and stated theoretical and dimensional limitations are included.

References

1.J. Barnes and P. Hut. A hierarchical O(N log N) force-calculation algorithm. Nature, 324 (4):446–449, 1986.
2.B.J.C. Baxter and G. Roussos. A new error estimate of the fast Gauss transform. SIAM Journal on Scientific Computation, 24(1):257–259, 2002.
3.R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1(3):173–189, 1972.
4.A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. In Proceedings of the International Conference on Machine Learning, pages 97–104, 2006.
5.S. Brin. Near neighbor search in large metric spaces. In Proceedings of the International Conference on Very Large Data Bases, pages 574–584, 1995.
6.C.J.C. Burges. Dimension reduction: A guided tour. Foundations and Trends in Machine Learning, 2(4):1–95, 2010.
7.M.Á. Carreira-Perpiñán. The elastic embedding algorithm for dimensionality reduction. In Proceedings of the International Conference on Machine Learning, pages 167–174, 2010.
8.M. Chalmers. A linear iteration time layout algorithm for visualising high-dimensional data. In Proceedings of IEEE Visualization, pages 127–132, 1996.
9.K. Cho, B. van Merriënboer, C. Gulcehre, F. Bougares, H. Schwenk, and Y. Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. In arXiv 1406.1078, 2014.
10.D.J. Croton, V. Springel, S.D.M. White, G. De Lucia, C.S. Frenk, L. Gao, A. Jenkins, G. Kauffmann, J.F. Navarro, and N. Yoshida. The many lives of active galactic nuclei: cooling flows, black holes and the luminosities and colours of galaxies. Monthly Notices of the Royal Astronomical Society, 365(1):11–28, 2006.
11.N. de Freitas, Y. Wang, M. Mahdaviani, and D. Lang. Fast Krylov methods for N-body learning. In Advances in Neural Information Processing Systems, volume 18, pages 251–258, 2006.
12.J.H. Freidman, J.L. Bentley, and R.A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software, 3:209–226, 1977.
13.T.M.J. Fruchterman and E.M. Reingold. Graph drawing by force-directed placement. Software: Practice and Experience, 21(11):1129–1164, 1991.
14.K. Fukunaga and P.M. Narendra. A branch and bound algorithm for computing k-nearest neighbors. IEEE Transactions on Computers, 24:750–753, 1975.
15.A.G. Gray. Fast kernel matrix-vector multiplication with application to gaussian process learning. Technical Report CMU-CS-04-110, Carnegie Mellon University, 2004.
16.A.G. Gray and A.W. Moore. N-body problems in statistical learning. In Advances in Neural Information Processing Systems, pages 521–527, 2001.
17.A.G. Gray and A.W. Moore. Rapid evaluation of multiple density models. In Proceedings of the International Conference on Artificial Intelligence and Statistics, 2003.
18.L. Greengard and V. Rokhlin. A fast algorithm for particle simulations. Journal of Computational Physics, 73:325–348, 1987.
19.J. Heer, M. Bostock, and V. Ogievetsky. A tour through the visualization zoo. Communications of the ACM, 53:59–67, 2010.
20.G.E. Hinton and S.T. Roweis. Stochastic Neighbor Embedding. In Advances in Neural Information Processing Systems, volume 15, pages 833–840, 2003.
21.G.E Hinton, N. Srivastava, A. Krizhevsky, I. Sutskever, and R.R. Salakhutdinov. Improving neural networks by preventing co-adaptation of feature detectors. In arXiv 1207.0580, 2012.
22.Y. Hu. Efficient and high-quality force-directed graph drawing. The Mathematica Journal, 10(1):37–71, 2005.
23.P. Indyk and R. Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of 30th Symposium on Theory of Computing, 1998.
24.R.A. Jacobs. Increased rates of convergence through learning rate adaptation. Neural Networks, 1:295–307, 1988.
25.S. Ji. Computational genetic neuroanatomy of the developing mouse brain: dimensionality reduction, visualization, and clustering. BMC Bioinformatics, 14(222):1–14, 2013.
26.Y. Jia. Caffe: An open source convolutional architecture for fast feature embedding. http://caffe.berkeleyvision.org/, 2013.
27.D. Keim, J. Kohlhammer, G. Ellis, and F. Mansmann. Mastering the Information Age: Solving Problems with Visual Analytics. Eurographics Association, Germany, 2010.
28.A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
29.C.C. Laczny, N. Pinel, N. Vlassis, and P. Wilmes. Alignment-free visualization of metagenomic data by nonlinear dimension reduction. Scientific Reports, 4:1–12, 2014.
30.D. Lang, M. Klaas, and N. de Freitas. Empirical testing of fast kernel density estimation algorithms. Technical Report TR-2005-03, University of British Columbia, 2005.
31.N.D. Lawrence. Spectral dimensionality reduction via maximum entropy. Proceedings of the International Conference on Artificial Intelligence and Statistics, JMLR W&CP, 15:51–59, 2011.
32.Y. LeCun, F.J. Huang, and L. Bottou. Learning methods for generic object recognition with invariance to pose and lighting. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 97–104, 2004.
33.T. Liu, A.W. Moore, A. Gray, and K. Yang. An investigation of practical approximate nearest neighbor algorithms. In Advances in Neural Information Processing Systems, volume 17, pages 825–832, 2004.
34.M. Mahdaviani, N. de Freitas, B. Fraser, and F. Hamze. Fast computational methods for visually guided robots. In Proceedings of the IEEE International Conference on Robotics and Automation, pages 138–143, 2005.
35.M. Muja and D.G. Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. In Proceedings of the International Conference on Computer Vision Theory and Applications, 2009.
36.Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A.Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
37.D. Nister and H. Stewenius. Scalable recognition with a vocabulary tree. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2161–2168, 2006.
38.A. Quigley and P. Eades. FADE: Graph drawing, clustering, and visual abstraction. In Proceedings of the International Symposium on Graph Drawing, pages 197–210, 2000.
39.V.C. Raykar and R. Duraiswami. Fast optimal bandwidth selection for kernel density estimation. In Proceedings of the 2006 SIAM International Conference on Data Mining, pages 524–528, 2006.
40.V. Rokhlin. Rapid solution of integral equations of classic potential theory. Journal of Computational Physics, 60:187–207, 1985.
41.S.T. Roweis and L.K. Saul. Nonlinear dimensionality reduction by Locally Linear Embedding. Science, 290(5500):2323–2326, 2000.
42.R.R. Salakhutdinov and G.E. Hinton. Semantic hashing. In Proceedings of the SIGIR Workshop on Information Retrieval and Applications of Graphical Models, pages 52–63, 2007.
43.J.K. Salmon and M.S. Warren. Skeletons from the treecode closet. Journal of Computational Physics, 111(1):136–155, 1994.
44.L.K. Saul, K.Q. Weinberger, J.H. Ham, F. Sha, and D.D. Lee. Spectral methods for dimensionality reduction. In Semisupervised Learning. The MIT Press, 2006.
45.P. Sermanet, S. Chintala, and Y. LeCun. Convolutional neural networks applied to house numbers digit classification. In Proceedings of the International Conference on Pattern Recognition, pages 3288–3291, 2012.
46.F. Sha and L.K. Saul. Large margin Gaussian mixture modeling for phonetic classification and recognition. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, pages 265–268, 2006.
47.C. Silpa-Anan and R. Hartley. Optimised kd-trees for fast image descriptor matching. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2008.
48.V. Springel, N. Yoshidaa, and S.D.M. White. GADGET: A code for collisionless and gasdynamical cosmological simulations. New Astronomy, 6(2):79–117, 2001.
49.J.B. Tenenbaum, V. de Silva, and J.C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319–2323, 2000.
50.P. Tiño and I.T. Nabney. Hierarchical GTM: Constructing localized nonlinear projection manifolds in a principled way. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(5):639–656, 2002.
51.A. Torralba, R. Fergus, and W.T. Freeman. 80 million tiny images: A large dataset for non-parametric object and scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30(11):1958–1970, 2008.
52.L.J.P. van der Maaten. Learning a parametric embedding by preserving local structure. In Proceedings of the International Conference on Artificial Intelligence and Statistics, JMLR W&CP, volume 5, pages 384–391, 2009.
53.L.J.P. van der Maaten. Barnes-Hut-SNE. In Proceedings of the International Conference on Learning Representations, 2013.
54.L.J.P. van der Maaten and G.E. Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9(Nov):2431–2456, 2008.
55.L.J.P. van der Maaten, E.O. Postma, and H.J. van den Herik. Dimensionality reduction: A comparative review. Technical Report TiCC-TR 2009-005, Tilburg University, 2009.
56.N.J. van Eck and L. Waltman. Software survey: Vosviewer, a computer program for bibliometric mapping. Scientometrics, 84:523–538, 2010.
57.J. Venna, J. Peltonen, K. Nybo, H. Aidos, and S. Kaski. Information retrieval perspective to nonlinear dimensionality reduction for data visualization. Journal of Machine Learning Research, 11(Feb):451–490, 2010.
58.M. Vladymyrov and M.Á. Carreira-Perpiñán. Partial-Hessian strategies for fast learning of nonlinear embeddings. In Proceedings of the International Conference on Machine Learning, pages 345–352, 2012.
59.M. Vladymyrov and M.Á. Carreira-Perpiñán. Entropic affinities: Properties and efficient numerical computation. Proceedings of the International Conference on Machine Learning, JMLR W&CP, 28(3):477–485, 2013.
60.M. Vladymyrov and M.A. Carreira-Perpiñán. Linear-time training of nonlinear low-dimensional embeddings. In Proceedings of the International Conference on Artificial Intelligence and Statistics. JMLR: W&CP, volume 33, pages 968–977, 2014.
61.X. Wan and G.E. Karniadakis. A sharp error estimate for the fast gauss transform. Journal of Computational Physics, 219(1):7–12, 2006.
62.M.S. Warren and J.K. Salmon. A parallel hashed octtree N-body algorithm. In Proceedings of the ACM/IEEE Conference on Supercomputing, pages 12–21, 1993.
63.Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In Advances in Neural Information Processing Systems, pages 1753–1760, 2008.
64.C. Yang, R. Duraiswami, N.A. Gumerov, and L. Davis. Improved fast Gauss transform and efficient kernel density estimation. In Proceedings of the IEEE International Conference on Computer Vision, pages 664–671, 2003.
65.Z. Yang, J. Peltonen, and S. Kaski. Scalable optimization of neighbor embedding for visualization. In Proc. of the Int. Conf. on Machine Learning, 2013.
66.P.N. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 311–321, 1993.
67.G. Zoutendijk. Methods of Feasible Directions. Elsevier Publishing Company, Amsterdam, The Netherlands, 1960.

Citation

MLA

Maaten, L. van . der . “Accelerating t-SNE Using Tree-Based Algorithms”. Journal of Machine Learning Research, vol. 15, no. 93, 2014, pp. 3221–45, https://www.jmlr.org/papers/v15/vandermaaten14a.html.

APA

Maaten, L. van . der . (2014). Accelerating t-SNE using Tree-Based Algorithms. Journal of Machine Learning Research, 15(93), 3221–3245. https://www.jmlr.org/papers/v15/vandermaaten14a.html

Chicago

Maaten, L. van . der . 2014. “Accelerating t-SNE Using Tree-Based Algorithms”. Journal of Machine Learning Research 15 (93): 3221–45. https://www.jmlr.org/papers/v15/vandermaaten14a.html.

Harvard

Maaten, L. van . der . (2014) “Accelerating t-SNE using Tree-Based Algorithms”, Journal of Machine Learning Research, 15(93), pp. 3221–3245. Available at: https://www.jmlr.org/papers/v15/vandermaaten14a.html.

Vancouver

1. Maaten L van der (2014) Accelerating t-SNE using Tree-Based Algorithms. Journal of Machine Learning Research 15:3221–3245

BibTeX

@article{JMLR:v15:vandermaaten14a,
  author  = {Laurens van der Maaten},
  title   = {Accelerating t-SNE using Tree-Based Algorithms},
  journal = {Journal of Machine Learning Research},
  year    = {2014},
  volume  = {15},
  number  = {93},
  pages   = {3221--3245},
  url     = {http://jmlr.org/papers/v15/vandermaaten14a.html}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Accelerating t-SNE using tree-based algorithms

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Sparse Input Similarity Approximation via Vantage-Point Trees

Knowl 2 — Decomposition of the t-SNE Gradient into Attractive and Repulsive Components

Knowl 3 — Barnes-Hut Gradient Approximation for t-SNE

Knowl 4 — Dual-Tree Gradient Approximation for t-SNE

Knowl 5 — Optimization Scheme and Early Exaggeration for Large-Scale t-SNE

Knowl 6 — Empirical Performance Comparison of Barnes-Hut and Dual-Tree t-SNE

Knowl 7 — Large-Scale Embedding Benchmarks and Density Visualization in t-SNE

Knowl 8 — Gradient Error Bounds and Dimensionality Limitations of Tree-Based t-SNE

References

Citation

BibTeX

Source Code

Access the Paper