高维空间的近似最近邻（A1NN）

Question

我读到了this有关寻找三维点最近邻的问题。Octree是这种情况下的解决方案。

kd-Tree是小空间（一般少于50个维度）的解决方案。

对于更高维度（数百个维度和数百万个点的向量），LSH是解决AKNN（近似K-NN）问题的流行解决方案，正如this question所指出的。

然而，LSH在K>>1的K-NN解决方案中很受欢迎。例如，在基于内容的图像检索（CBIR）应用中，LSH已经成功地使用，其中每个图像都通过数百个维度的向量表示，数据集包含数百万（或数十亿）张图像。在这种情况下，K是相对于查询图像最相似的前K个图像的数量。

但是如果我们只对高维空间中最接近的邻居（即A1-NN）感兴趣，LSH仍然是最好的选择吗？还是已经提出了特定的解决方案？

- justHelloWorld

Answer 1

您可以查看以下两篇论文：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 算法快一个量级。” 另一篇论文第 7 页的表格 2 显然显示出相对一致的 LSH 速度优势，对于不同的 k 值。

请注意，这里并不是 LSH 对 kd 树的比较。实际上，这是 LSH 与各种精心调整的近似搜索树结构的比较，其中您通常只搜索最有希望的树部分，而不是所有可能包含最接近点的树部分，并且搜索多个不同的树以获得足够的概率来找到好的点，调整各种参数以获得最快的性能。

- mcdowella

---

这太出乎意料了。此时我有点迷茫：LSH旨在在高维数据中（如第二篇论文中描述的128维SIFT描述符）胜过KD树（及其衍生结构）。现在我发现它是低效的？那么使用LSH的意义何在？另外，你回答中引用的文章（[34]）使用的是E2LSH（与2015年发布的FALCONN相比已经过时），并通过增加R的R近邻来查找K-NN。我认为这不是一个准确的过程。当然我可能是错的，只是想听听您的意见 :) - justHelloWorld

我对各种选项的最佳实现的相对速度不是很了解。其中一篇论文 https://lear.inrialpes.fr/~douze/enseignement/2014-2015/presentation_papers/muja_flann.pdf 似乎是关于自动选择和调整特定问题的最佳选项，因此可能不存在明显的赢家。LSH 完全可以胜过 KD-trees（生成精确答案），但可能会被略有不同的树算法所取代，后者只生成近似答案。幸运的是，很少有应用程序绝对需要最快的速度。 - mcdowella