我读到关于寻找三维点的最近邻居的问题。八叉树是解决这个问题的方法。
this是小空间（通常小于50维）的解决方案。
对于更高维度（几百维向量和数百万个点的向量），LSH是解决AKNN（Apxximal-K-NN）问题的一个流行的解决方案，如kd-Tree所指出的。
然而，lsh在k-nn解决方案中很流行，其中k>>1。例如，LSH已经被this question用于基于内容的图像检索（CBIR）应用，其中每个图像通过数百维的向量表示，并且数据集是数百万（或数十亿）图像在本例中，k是top-k个最相似图像的数目，w.r.t.查询图像。
但是如果我们只对高维空间中最近似的相似邻居（即A1-NN）感兴趣呢？LSH仍然是赢家，还是已经提出了特别的解决方案？
最佳答案
您可以查看http://papers.nips.cc/paper/2666-an-investigation-of-practical-approximate-nearest-neighbor-algorithms.pdf和http://research.microsoft.com/en-us/um/people/jingdw/pubs%5CTPAMI-TPTree.pdf。这两个数字和图表表明LSH的性能与基于树的方法的性能，也产生了近似的答案，不同的k值包括k＝1。微软的论文声称“已经在[34]中表明随机kd树可以
比lsh算法的性能提高了一个数量级。另一篇论文的表2第7页似乎显示了LSH的加速比，对于不同的k值是合理一致的。
注意，这不是LSH对kd树这是LSH与各种灵活调谐的近似搜索树结构，其中通常只搜索树中最有希望的部分，而不是搜索树中可能包含最接近点的所有部分，并且搜索许多不同的树，以获得良好的点来弥补这一点，调整各种参数以获得尽可能快的性能。