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

我读了this关于找到三维点的最近邻居的问题。八叉树是这种情况下的解决方案。高维空间的近似最近邻居（A1NN）

kd-Tree是小空间（通常小于50尺寸）的解决方案。

对于高维（向量为几百个维和几百万个点）LSH是解决AKNN（Aproxximate K-NN）问题的流行解决方案，如this question中指出的那样。

然而，LSH对K-NN解决方案很流行，其中K >> 1。例如，对于基于内容的图像检索（CBIR）应用，LSH已经是successfully used，其中每个图像通过数百维度的矢量来表示，并且数据集是数百万（或数十亿）图像。在这种情况下，K是顶部K最相似图像的数量w.r.t.查询图像。

但是如果我们感兴趣的是只是在高维空间中最接近的相似邻居（即A1-NN）呢？ LSH仍然是赢家，还是提出了临时解决方案？

来源

2016-09-26 justHelloWorld

您可能会看到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 = 1的k的不同值。微软的论文宣称“在[34]中已经表明，随机化的KD树可以比LSH算法优越大约一个数量级”。表2另一篇论文的P7似乎显示LSH的加速对于不同的k值是合理一致的。

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

来源

2016-09-27 04:27:48 mcdowella

这是意想不到的。在这一点上，我感觉有点失落：LSH被设计为在高维数据（如第二篇论文中描述的128维SIFT描述符）中胜过KD树（和派生结构）。现在我发现它效率低下？那么使用LSH有什么意义？此外，引用的论文（[34]在您的答案中）使用E2LSH（与2015年发布的FALCONN相比已经过时），并且通过R近邻发现K-NN增加R.我认为这不是一个准确的处理。当然，我可能错了，我只是要求一个意见:) – justHelloWorld

我不是最新的各种选项的最佳实施的相对速度。一篇论文https://lear.inrialpes.fr/~douze/enseignement/2014-2015/presentation_papers/muja_flann.pdf似乎是关于自动挑选和调整特定问题的最佳选项，所以大概没有明确的赢家。 LSH完全符合KD树（它能产生确切的答案），仅仅通过一个略有不同的树算法，只能产生近似的答案而超越自身。幸运的是，非常少的应用程序绝对必须具有最快的速度。 – mcdowella

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

回答

相关问题