algorithm - 高维空间的近似最近邻 (A1NN)

Question

我读了this关于寻找 3 维点的最近邻居的问题。八叉树是这种情况的解决方案。

kd-Tree是针对小空间(通常小于 50 维)的解决方案。

对于更高维度(数百维度和数百万点的向量)，LSH 是解决 AKNN(近似 K-NN)问题的流行解决方案，如 this question 中指出的那样.

但是，LSH 在 K-NN 解决方案中很受欢迎，其中 K>>1。例如，LSH 一直是 successfully used对于基于内容的图像检索 (CBIR) 应用程序，其中每个图像都通过数百维的向量表示，数据集是数百万(或数十亿)图像。在这种情况下，K 是前 K 个最相似图像 w.r.t. 的数量。查询图片。

但是，如果我们只对高维空间中最近似的相似邻居(即 A1-NN)感兴趣怎么办？LSH 仍然是赢家，或者已经提出了临时解决方案？

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 算法大约一个数量级”。另一篇论文的表 2 P 7 似乎显示了 LSH 的加速，这对于不同的 k 值是合理一致的。

请注意，这不是 LSH vs kd-trees。这是 LSH 与各种巧妙调整的近似搜索树结构的对比，您通常只搜索树中最有希望的部分，而不是树中可能包含最近点的所有部分，并且您搜索许多不同的树为了获得找到好点的良好概率来弥补这一点，调整各种参数以获得尽可能快的性能。