海量數據的一種集合模糊匹配關聯算法

婁鑫坡，孔玉靜

(河南城建學院 計算機與數據科學學院，河南 平頂山 467036)

按照數據類型的不同，匹配度關聯問題可分為字符串關聯、向量關聯和集合關聯。其中，集合數據的關聯操作一般是指利用索引結構對原始數據進行分組，然后對各個分組內的數據進行匹配度關聯操作，最后對各個分組的結果進行匯總并得到最終結果。眾多學者都對面向集合數據的匹配度關聯查詢問題進行過研究，并且提出了相關的關聯算法[1-3]。其中，比較具有代表性的算法是MRSimJoin[4]，是針對集合數據源進行關聯，即自關聯。該算法從集合中隨機選K個數據作為中樞，然后利用中樞數據對集合進行劃分，形成k個分區，在k個分區內并行地進行K值匹配度關聯操作以加快算法效率。但MRSimJoin對數據的關聯是一次性的，即每次操作都是從頭開始。另外，由于實際應用中數據的差異性，在劃分分區時容易出現數據的傾斜問題，直接導致各Datanode負載不均衡。

本文提出海量數據下的一種集合模糊匹配關聯算法，針對數據增加時關聯操作效率變低的問題，該算法在Hadoop固有的分塊策略基礎之上對其分塊策略再進一步優化，即在分塊后再分階段處理。針對數據處理過程中失真問題，如同一人名或者地址在不同的集合中會出現一定的差異[5-6]，即使匹配了也不可能總是做到精確的匹配，實際上是滿足某個匹配閾值的。即給定兩個記錄文件R和S、度量函數sim和一個模糊匹配度閾值，該值隨著情況改變而動態改變，找出兩個集合中的所有記錄對S.a和R.a，且滿足sim(S.a，R.a)≥k(模糊值)[7-8]。……