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

Re:Using k-d trees to efficiently calculate nearest neighbor... by agibsonccc on Saturday February 10, 2018 @07:12PM (#16350392)

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 (Barnes Hut)

https://arxiv.org/abs/1602.00370 (LargeVis)

One uses Vantage Point Trees which sudivides the space in to quadrants, and the other uses Random Projection Trees.

Both are interesting exercises in using KNN like techniques to visualize high dimensional spaces.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by joshvm on Sunday February 11, 2018 @12:36AM (#16351362)

There's also FLANN which is an approximate nearest neighbour algorithm which is routinely used for things like feature/keypoint matching (e.g. SIFT keypoints are 128 dimensional).

https://www.cs.ubc.ca/research/flann/

Barnes Hut is a fun one to implement for N-body simulations.

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by _wmd on Sunday February 11, 2018 @02:24AM (#16351626)

I was toying with compqring similarity of texts just last night, is there anything that could handle 10k+ sized sparse vectors? Obviously there are tools like lucene, but I wanted to mess around in the interactive interpreter

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by agibsonccc on Sunday February 11, 2018 @03:08AM (#16351729)

Check out LargeVis then. The original github repo by the authors has a sparse mode: https://github.com/lferry007/LargeVis/

TSNE didn't scale well no matter what you did to it (hence the newer technique) - in general though you can't beat cosine similarity of TFIDF vectors as a baseline.

[ Parent | on HN ]