如何通過R最近鄰居求解最近鄰居？

Question

援引E2LSH手冊（這並不是說是關於這個特定庫重要的是，這句話應該是一般 NN問題真）：

Ë2LSH也可以用來解決近鄰問題，其中， 在給定查詢q的情況下，數據結構是要求報告中的點P最接近於q的 。這可以通過爲R = R1，R2，...創建多個R近鄰 鄰居數據結構來完成。 。 。 Rt，其中Rt應該爲 大於從任何查詢點到其最近鄰居的最大距離 。最近的鄰居可以通過 查詢數據結構在radiae， 停止的增加順序，然後恢復時，第一點被

有人能改寫這個好嗎？我不用這個程序來找到使用R近鄰方法的最近鄰居。

Answer 1

我會提供一個例子，它應該清理一些東西。假設我們的數據集只包含一個點，p和查詢點到達，q。我們假設^*p和q的距離是3,9。

現在，通過使用E2LSH ^$，我可以創建一個解決R-近鄰問題，也就是說，它會回答是肯定的數據結構（我找了點）位於半徑爲R如果沒有這樣的內點存在，它將回答否。

比方說，我選擇建立的那種5層的數據結構，從R = 1〜5。在我們的腦海中開始，這是我們迄今所做的：所以現在

請記住，d（p，q）= 3,9，因此我們希望詢問用R = 4構建的數據結構，併爲我們找到查詢點q。現在讓我們假裝我們不知道d（p，q），所以我們從我們選取的最小半徑開始搜索，那是1.所以，我們問，是否有任何半徑（等於1）？我們的數據集？沒有！

從R = 2？沒有！ 從R = 3？沒有！ 從R = 4？是的，那是q！所以現在我們完成了。 4是你在你的問題中提到的R _t。

---

* _{這是一個很強的假設和E2LSH 遭受具有把用戶輸入該參數R，因爲通常我們不知道應該R 5具有什麼樣的價值，太大，我們會浪費空間，時間太短，我們無法找到我們的查詢！}

$ _{在Ilya Razenshteyn的主頁上，我聽說現在比E2LSH更現代。}