# Barnes-Hut-SNE

arXiv: https://arxiv.org/abs/1301.3342 · HTML: https://mlsanity.com/paper/1301.3342/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2013.

## Built on by (most cited first, 14 of 14)

- [Domain Adversarial Spatial-Temporal Network: A Transferable Framework for Short-term Traffic Forecasting across Cities](https://mlsanity.com/paper/2202.03630/) (2022)
- [Cloud-Device Collaborative Adaptation to Continual Changing Environments in the Real-world](https://mlsanity.com/paper/2212.00972/) (2022)
- [SNEkhorn: Dimension Reduction with Symmetric Entropic Affinities](https://mlsanity.com/paper/2305.13797/) (2023)
- [Federated Data-Efficient Instruction Tuning for Large Language Models](https://mlsanity.com/paper/2410.10926/) (2024)
- [BEVUDA: Multi-geometric Space Alignments for Domain Adaptive BEV 3D Object Detection](https://mlsanity.com/paper/2211.17126/) (2022)
- [Exploring Dark Knowledge under Various Teacher Capacities and Addressing Capacity Mismatch](https://mlsanity.com/paper/2405.13078/) (2024)
- [ET-Agent: Incentivizing Effective Tool-Integrated Reasoning Agent via Behavior Calibration](https://mlsanity.com/paper/2601.06860/) (2026)
- [Knowledge Base Index Compression via Dimensionality and Precision Reduction](https://mlsanity.com/paper/2204.02906/) (2022)
- [MrTF: Model Refinery for Transductive Federated Learning](https://mlsanity.com/paper/2305.04201/) (2023)
- [INTENT: Trajectory Prediction Framework with Intention-Guided Contrastive Clustering](https://mlsanity.com/paper/2503.04952/) (2025)
- [BEVUDA++: Geometric-aware Unsupervised Domain Adaptation for Multi-View 3D Object Detection](https://mlsanity.com/paper/2509.14151/) (2025)
- [Visualizing Data Velocity using DSNE](https://mlsanity.com/paper/2103.08509/) (2021)
- [Index t-SNE: Tracking Dynamics of High-Dimensional Datasets with Coherent Embeddings](https://mlsanity.com/paper/2109.10538/) (2021)
- [How smoothing the affinity matrix affects neighborhood preservation in t-SNE](https://mlsanity.com/paper/2608.17190/) (2026)

## Abstract (arXiv)

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.