在數據庫中存儲和索引二進制字符串

這裏定義的二進制字符串是固定大小的「數組」位。我稱它們爲字符串，因爲它們沒有順序（排序/索引它們，因爲數字沒有意義），每一位都獨立於其他位。每個這樣的字符串都是N位長，其中N爲數百。在數據庫中存儲和索引二進制字符串

我需要存儲這些字符串，並使用海明距離作爲距離度量給出一個新的最近鄰居的二進制字符串查詢。
針對基於度量的搜索（VP-trees，cover-trees，M-trees）有專門的數據結構（metric-trees），但我需要使用常規數據庫（在我的情況下是MongoDB）。

是否有一些索引函數可以應用於二進制字符串，在執行一對一漢明距離匹配之前可以幫助數據庫訪問記錄的一個子集？或者，如何在標準數據庫上實現這種基於漢明的搜索？

來源

2011-07-06 Adi Shavit

「我稱它們爲字符串是因爲它們沒有順序」 - 字符串有順序 - 特別是詞典。 –

當然，通常位序列被稱爲「數字」，或整數是確切的，它們確實具有自然順序。 –

漢明距離是一個度量，因此它滿足三角不等式。對於數據庫中的每個位串，可以將它的漢明距離存儲爲某個預定義的常量位串。然後，您可以使用三角不等式來過濾數據庫中的位串。

所以我們說

C <- some constant bitstring 
S <- bitstring you're trying to find the best match for 
B <- a bitstring in the database 
distS <- hamming_dist(S,C) 
distB <- hamming_dist(B,C)

所以每個B，你將存儲其相應distB。

hamming(B,S)的下限爲abs(distB-distS)。上限爲distB+distS。

您可以丟棄所有B，使得下限高於最低上限。

我不是100％確定最佳方式選擇哪個C。我想你會希望它是一個比特串，它接近比特串的度量空間的「中心」。

來源

2011-07-06 15:58:25 tskuzzy

這相當於僅存儲根節點的Bk樹。它會有所幫助，但它仍然會留下很多搜索空間來檢查。您可以將距離存儲到多個字符串（ala一個FHFQ bk-tree），但是這需要一個具有多個不等式的查詢，這無法在一維索引上高效地進行評估。 –

@tskuzzy：謝謝，就是我想要的。只是爲了澄清答覆：讓minDistB成爲數據庫中Bs的最小區域，然後丟棄所有B，例如：abs（distB-distS）> distS + minDistB。 –

@尼克約翰遜：你說得對（感謝BK-Tree的帖子鏈接）。事實上，顯而易見的擴展將是針對幾個這樣的Cs進行索引，分佈在該空間周圍並且具有數據庫索引幾個Bs，每個C.每個C.一個正確的 –

你可以使用類似levenshtein automata的方法，應用於位串：

計算第一（字典序最小）的比特串，將滿足您的漢明距離標準。
從數據庫中獲取大於或等於該值的第一個結果
如果該值匹配，則輸出它並獲取下一個結果。否則，計算下一個值大於它是是匹配，並轉到2

這相當於做了合併連接在你的數據庫，並有可能匹配的列表，無需生成每一個可能的比賽。它會減少搜索空間，但它仍然可能需要大量的查詢。

來源

2011-07-07 00:55:34

在數據庫中存儲和索引二進制字符串

回答

相關問題