HackerPapers

arXiv:1301.3342cs.LG

Barnes-Hut-SNE

Laurens van der Maaten

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

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.

arXiv comments
Journal reference
DOI
Subjects
cs.LGMachine Learning cs.CVComputer Vision and Pattern Recognition stat.MLMachine Learning (Statistics)

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Feb 2018 to Feb 2018.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Using k-d trees to efficiently calculate nearest neighbors in 3D vector space 1 comment

    • For those interested in this space, folks might like some of the work that went in to visualizing T Distributed Stochastic Neighbor Embedding and the successor to that LargeVis which use multiple forms of KNN trees each with their own trade offs: https://arxiv.org/abs/1301.3342…

      agibsoncccView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.