高維空間的近似最近鄰居（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）

回答

相關問題