檢索類似條目的最快（實際）存儲實現是什麼？

Question

我幾個月前閱讀了BK-trees（Burkhard-Keller-Trees），據說這是一種很好的方法來保存您想要再次讀出的東西，距離度量標準爲。因此，在每種情況下，您想通過相似性檢索某些內容。

但是，這些BK樹對我來說看起來並不是很快。當我嘗試一個實現並做了一些輸出時，只要我允許更長距離（我用levenshtein進行修改並允許多達6次編輯），它就必須在樹中四處走動。

當然，最快的實施方式（如果只是速度）將存儲距離爲的每個條目到表格中的每個條目並直接查找它們，但這是太多的開銷。

因此我在標題中添加了寫實。這是沒問題，需要更多的內存，但實現應該仍然是現實和可用的（我不太瞭解這種技術說什麼是現實的，但我想有一些邊界）。

有沒有比BK樹更快的速度還是BK真的是山頂（尚）？

方案

我沒有一個真正的用例，但情況如下：我有這樣的事情1個百萬條目，他們有彼此（由距離函數定義）的一段距離。現在，我得到一個項目，想知道可以：

• 其中5項做的最好的比賽定條目
• 哪些其它條目（一些獨立的）是低於或等於相同直到達到給定的閾值

數據庫沒關係。

我猜最後的算法會匹配兩者嗎？

Answer 1

另一種基於樹的最近鄰居度量是http://en.wikipedia.org/wiki/Cover_tree。它聲稱是實用的，http://www.cs.waikato.ac.nz/ml/weka/已經撿起來了，所以它確實如此。然而，最近的鄰居似乎很難做到與樹木或其他任何事情完全相同，因爲有一些建議是爲了近似最近的鄰居而浮動的，如果不是很難，我認爲這很愚蠢。我可以看到一個編輯距離爲http://people.csail.mit.edu/indyk/edit.ps。

近似最近鄰搜索的另一種方法是希望最近的鄰居將有一個連續的字符部分恰好出現在您的查詢字符串中。然後，對於數據庫中的所有字符串，將它們切成所有連續的k長的子字符串，然後構建一張可用於精確匹配的表格。然後，對於您的查詢字符串，請考慮所有k長連續的子字符串，對這些字符串進行精確匹配，然後計算數據庫中所有字符串的編輯距離，您可以通過對k長字符串的精確搜索找到該字符串。