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

Re:Using k-d trees to efficiently calculate nearest neighbor... by photon-torpedo on Sunday February 11, 2018 @06:05AM (#16352179)

Semi-related: Anybody know what's the current state of the art for calculating nearest neighbors in high-dimensional spaces (at least 10D, maybe 100s of D)?

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by Radim on Sunday February 11, 2018 @06:50AM (#16352303)

Various approaches based on LSH (locality sensitive hashing) and random projections.

But "the best" really depends on your data profile, as the generic problem formulation, for completely generic vectors, is too… generic. See also the curse of dimensionality [0].

In practical terms, if you're looking for an actual implementation to use, here's a benchmark of some state-of-the-art implementations for high-dimensional vector search: http://radimrehurek.com/2013/12/performance-shootout-of-near... and also the updated https://github.com/erikbern/ann-benchmarks.

In particular, for something good AND open source:

- Leonid Boytsov's NMSLIB [1]

- Erik Bernhardsson's Annoy [2]

- Facebook's FAISS [3]

For a commercial engine focused more on practical use (index management, transactions, versioning, support), see ScaleText [4] (disclaimer: our product).

[0] https://en.wikipedia.org/wiki/Curse_of_dimensionality [1] https://github.com/searchivarius/nmslib [2] https://github.com/spotify/annoy [3] https://github.com/facebookresearch/faiss [4] https://scaletext.com/

[ Parent | on HN ]

Re:Using k-d trees to efficiently calculate nearest neighbor... by photon-torpedo on Sunday February 11, 2018 @07:35AM (#16352428)

Very helpful, many thanks!

[ Parent | on HN ]