如何使用近似的查詢存儲數據？

Question

我試圖找到一種方法來存儲我的數據以快速訪問（比O（n）好）。

我的數據庫由數據（4096字節字符串）組成，它代表一些項目的一些信息。
問題是，查詢從不確切。我得到一個項目，然後需要使用函數F(a,b)找到最接近的匹配項。

只是一個例子：

1234 
3456 
6466 
F(a,b) = return % of similar digits 

GetClosest(1233,F) = 1234 

的問題是，F（A，B）是一個複雜的算法，（不是正確的度量）。

我現在只是瀏覽整個數據庫來搜索最佳匹配。
是否有一種樹型或其他類型的數據庫可以讓我更快地發現複雜性？

更多信息：

F給出回來％百分比的相似度值。 100％是完美的搭配。

Answer 1

對不起，答案是「可能不是」，除非你的問題還有一些你沒有描述的結構。有了4096字節的字符串，你正在遭受the curse of dimensionality。

如果你有更短的字符串和足夠的數據，那麼很可能是最接近的匹配在一大塊字符串上是相同的，那麼你可以用多個樹狀結構來存儲數據，這些樹狀結構索引在不同的塊上串。很有可能最近的距離足夠近，以至於只能根據這些樹中的近距離元素來證明它最近。然而，隨着字符串的大小和可以存儲在計算機中的有限數據，這是不可能的。

這就是說，你需要確切的最接近的，還是隻有一個接近一個？如果只有可能接近的一個，那麼你可以通過幾個隨機稀疏比特樣本來索引它。在您的搜索中，您只能檢查與其中一個元素完全匹配的元素。這將大大減少搜索空間，同時拒絕較少的近鄰，並可能產生合理的（即使經常出錯的）答案。

Answer 2

有什麼方法可以爲每個數據分配一個'分數'。

您可以通過您的分數對數據進行索引/排序。

當您搜索時，爲您的搜索條件分配一個分數，並查找具有最接近分數的項目。

很大程度上取決於您的數據和您的「差異」的定義是否可行。