無需 O(n) 遍歷即可跨多個屬性查找最接近的數據庫值
我有一個案例，我可以訪問一個包含許多文件（數百萬+）的大型數據庫。我想建構這樣的功能，當我想向該數據庫添加新文件時，我首先想掃描數據庫以查找潛在的重複文件。文件可能在文件類型和其他資訊方面有所不同（即一個是數字副本，而另一個是通過列印機掃描的硬拷貝），但在本質上仍然是相同的文件，所以我很遺憾不能依賴元數據或類似的.
為了確定文件是否重複，我計劃使用一些 NLP 的加權組合（通過類似spaCy的東西）來比較文件相似度，比較單詞分佈（簡單的單詞分佈和類似TF-IDF 的東西），以及其他相關指標。
為了真正找到新上傳文件的潛在重複項，我想不出任何方法來避免掃描數據庫中的每個文件，逐一比較，並使用最匹配的指標跟踪文件。
我對此進行優化的想法：
- 我知道索引通常可用於加快搜尋操作，但據我了解，這僅適用於在特定列中搜尋特定值。我認為這不太合適，因為我試圖從本質上對每個指標進行加權平均並報告最接近的指標。我想我可以索引每一列；這可能是值得的，還是不斷的重新索引會導致巨大的性能損失？
- 我一直在考慮使用分群（非監督式機器學習）模型將相似的文件分群在一起，然後嘗試使用它給我的分群來嘗試確定新文件適合哪個分群，然後在那裡搜尋，但我正在關注細節。我確信這將是一種在數據庫中查找預先存在的重複項的實用方法，但是每次將新文件添加到集合中時這樣做是否實用（即，它可以用來加快通過數據庫的實際搜尋） ? 我不太精通機器學習，所以我很感激對此的一些意見。
所以最終 - 有沒有辦法讓我建構我的數據庫，以便在這種情況下我不需要線性搜尋？
您可以在每個度量上定義一個索引，查詢每個以找到最接近的少數文件，然後建構這些不同結果的交集。這會將數據大小比較轉換為（度量的數量）x（度量中的搜尋寬度）。這可能小於合理數量的措施的行數。
根據 DBMS 以及您的 SQL-fu 有多好，您甚至可以說服查詢處理器執行這些索引讀取，然後將子結果內部連接在一起以產生交集。
與此有關的一大障礙是異常值。假設我們定義了 20 個度量。傳入文件在這 20 個文件中的 19 個中與現有文件完全匹配，但最後一個超出範圍。即使人們可能會說兩者匹配，現有文件也永遠不會進入結果。為避免這種情況，您必須在索引匹配中定義相關程度，然後再次回到數據大小操作。
進行通常的向量空間比較有什麼問題？
英特爾估計現代伺服器晶片可以做幾百 gigaflops左右。我們稱之為每秒 10^11 次浮點計算。要使用歐幾里得距離在 20 個度量上將一個文件與另一個文件進行比較，需要 80 次計算。我們稱它為 100。即每秒 10^9 次比較。因此，與 1M 現有文件進行比較將需要 10^-3 秒或 1 毫秒。讓我們再敲幾個零，因為數據必須在晶片內移動。您多久添加一次文件？您有多少台掃描器以及處理 OCR 需要多長時間？你能忍受每個文件不到一秒鐘的重複檢查嗎？
進一步採用歐幾里得方法，如果您的 DBMS 支持幾何數據類型，您可以選擇兩個或三個最具選擇性的度量並在這些度量上定義空間索引。這應該可以有效地將 100 萬多個現有文件的搜尋減少到可以進行全向量搜尋的水平。