高维空间的近似近邻(A1NN)
我读过这关于为三维点寻找最接近的邻居的问题.八叉树是这种情况的解决方案。
kd-Tree是一个小空间(一般小于50维)的解决方案。
对于高维(数百个维数和数百个点的向量)，LSH是解决AKNN (Aproxximate )问题的热门方法，正如这个问题中所指出的那样。
例如，基于内容的图像检索( K>>1 )应用一直是基于内容的图像检索(CBIR)应用程序，其中每幅图像通过一个数百维的向量表示，数据集是数百万(或数十亿)个图像。在这种情况下，K是最相似的图片w.r.t的数量。查询图像。
但是，如果我们对高维空间中最近似的相似邻域(即A1-NN)感兴趣呢？ LSH仍然是赢家，或者已经提出了特别的解决方案？
回答 1
Stack Overflow用户
发布于 2016-09-27 04:27:48
你可以看看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，P，7似乎显示了LSH上的加速，对于不同的k值，这是合理一致的。
请注意，这不是。这是LSH和各种聪明的调优近似搜索树结构，通常只搜索树中最有希望的部分，而不是树中可能包含最接近点的所有部分，然后搜索多个不同的树，以获得一个很好的概率来找到好的点来弥补这一点，调整各种参数以获得最快的性能。
https://stackoverflow.com/questions/39712680
复制相似问题
腾讯云开发者
