非度量空間中的最近鄰居搜索

Question

我想知道在非度量空間中工作時的最近鄰搜索算法嗎？特別是，在這種設置中是否有任何變種的kd-tree算法，具有可證明的時間複雜度等？

Answer 1

NMSLIB提供了一個庫，用於在非公制空間中執行最近鄰點搜索。該Github頁面提供了十幾篇要閱讀的論文，但並非全部適用於非度量空間。

不幸的是，關於Neaest Neighbour Search的複雜性的理論結果很少，對於非度量空間並且沒有全面的經驗評估。

我可以在Effective Proximity Retrieval by Ordering Permutations上看到一些理論結果，但我不確信。不過，我建議你看看。

似乎沒有很多人使用k-d樹作爲非度量空間。他們似乎使用VP樹，也使用密度等，如Near Neighbor Search in Nonmetric Spaces中所述。

直觀而言，密度是一類裝飾樹，以類似於metric tree的方式保存數據集的點。關鍵差異 在於樹裝飾的性質;而不是有一個或幾個實際值反映了每個樹節點附加的三角不等式的一些邊界，每個密度節點都與一個特定的分類器相關聯，這裏稱爲密度估計器。

Answer 2

可能更適合您的理論興趣： PH-Tree與四叉樹相似，但是它在存儲它們之前將浮點座標轉換爲非公制系統。 PH-Tree使用非度量距離函數對非度量數據執行所有查詢（包括kNN查詢）（您可以在其上定義自己的距離函數）。

就kNN而言，PH樹與R +樹等樹相同，並且通常優於kd樹。 對於轉換和距離函數，除非可能（幾乎可忽略）執行時間，否則非度量數據存儲似乎對性能的負面影響很小，甚至可能是正數。

數據轉換的原因來自樹的固有約束：樹是一個按位樹，這意味着它只能存儲位序列（可以看作整數）。爲了在樹中存儲浮點數，我們簡單地使用浮點數的IEEE位表示並將其解釋爲一個整數（這對正數工作正常，負數稍微複雜一點）。關鍵是，這保留了排序，即。如果浮點數f1大於f2，則int（f1）位的整數表示也總是大於int（f2）。簡而言之，這種轉換允許將浮點數作爲整數存儲，而不會損失任何精度（！）。

該轉換是非度量的，因爲浮點數的前導位（在符號位之後）是指數位，後面是小數位。顯然，如果兩個數字的指數位不同，它們的距離與由分數位差異引起的距離相比，其指數增長更快（或負指數更慢）。

爲什麼我們使用按位嘗試？如果我們有d維，它允許一個簡單的轉換，以便我們可以將座標的每個d值的第n位映射爲具有d位的位串。例如，對於d = 60，我們得到一個60位的字符串。假設CPU寄存器寬度爲64位，這意味着我們可以在恆定時間內執行許多與查詢有關的操作，即許多操作只需要一次CPU操作，而不管我們是否有3維或60維。從這篇短文中可能很難理解發生了什麼，更多細節可以在here找到。