我读了这个关于找到 3 维点的最近邻居的问题。八叉树是这种情况的解决方案。
kd-Tree是针对小空间（一般小于 50 维）的解决方案。
对于更高维度（数百维和数百万点的向量），LSH 是解决 AKNN（Aproxximate K-NN）问题的流行解决方案，如this question中所指出的。
然而，LSH 在 K-NN 解决方案中很受欢迎，其中 K>>1。例如，LSH 已成功用于基于内容的图像检索 (CBIR) 应用程序，其中每个图像都通过数百维的向量表示，数据集是数百万（或数十亿）张图像。在这种情况下，K 是与查询图像最相似的前 K 个图像的数量。
但是，如果我们只对高维空间中最近似的相似邻居（即 A1-NN）感兴趣怎么办？LSH 仍然是赢家，还是已经提出了临时解决方案？
您可以查看http://papers.nips.cc/paper/2666-an-investigation-of-practical-approximate-nearest-neighbor-algorithms.pdf和http://research.microsoft.com/en-us/嗯/people/jingdw/pubs%5CTPAMI-TPTree.pdf。两者都有图表，显示 LSH 的性能与基于树的方法的性能，对于不同的 k 值，包括 k = 1，这些方法也只产生近似答案。微软的论文声称“[34] 中表明，随机 KD 树的性能可以优于 LSH 算法大约一个数量级”。另一篇论文的表 2 P 7 似乎显示了 LSH 的加速，这对于不同的 k 值是合理一致的。
请注意，这不是 LSH 与 kd-trees。这是 LSH 与各种巧妙调整的近似搜索树结构的比较，您通常只搜索树中最有希望的部分，而不是可能包含最近点的树的所有部分，并且搜索许多不同的树为了获得一个不错的概率找到好的点来弥补这一点，调整各种参数以获得最快的性能。