k-NN在大尺寸（〜100,000）中搜索

是否有任何關於k-NN搜索問題的文章，對於像10k-100k這樣的真正大量的維度？k-NN在大尺寸（〜100,000）中搜索

大多數測試真實世界數據的文章都以10-50個模糊進行操作，少數文章的操作數爲100-500。

在我的情況下，在〜100k特徵維中有〜10^9個點，並且沒有辦法有效地減少維數。

UPD .: 目前我們正試圖修改和實現VP樹，但是足夠清楚的是，任何有關此維度的樹結構都無法正常工作。

第二種方法是LSH，但根據數據分佈的不同，可能會有很大的準確性問題。

來源

2013-06-19 Spoilt333

我感覺到user2501091的文章創建機會。 –

爲了我們隨機遇到這個問題的好處，你能鏈接到LSH的解釋嗎？或者其他的東西？對於對這個話題一無所知的人來說，你的問題聽起來像是胡言亂語，有時候這可能是一個糟糕的問題。幸好K-nn已經是一些帶有一些信息的標籤。 –

LSH - 局部敏感散列。這是基於我們可以預測關閉點以關閉圖像的想法。 – Spoilt333

您是否使用kd-tree進行最近鄰居搜索？ kd-tree惡化到在更高維上幾乎徹底的搜索。

在更高維度中，通常建議使用近似最近鄰居搜索。這裏是鏈接到原始文件：http://cvs.cs.umd.edu/~mount/Papers/dist.pdf，如果這是一個有點太重了，試試這個：dimacs.rutgers.edu/Workshops/MiningTutorial/pindyk-slides.ppt

有是影響選擇的因素很多關於最近鄰居搜索的決定。無論您是需要在主內存中完全加載點還是可以使用輔助內存，都應控制您的決定。

來源

2013-06-19 12:58:25 metsburg

看看FLANN庫。

在this paper中，您將找到關於數據維度如何成爲對最近鄰居匹配性能產生重大影響的因素之一的論文以及FLANN中採用的解決方案。

來源

2013-06-19 13:27:57

k-NN在大尺寸（〜100,000）中搜索

回答

相關問題