基于劃分的增量式字符串相似性連接方法
摘要：字符串相似性連接是數據質量管理的基本操作,也是數據價值發現的關鍵步驟。針對目前已有的方法不能滿足面向大數據的增量式處理需求的問題,提出一種面向流式數據的增量式字符串相似性連接方法——IncJoin,并對方法的索引技術進行了優化。該方法以Pass-Join字符串連接算法為基礎,首先,采用字符串劃分技術將字符串劃分成多個互不相交的子串;然后,建立字符串的反向索引列表并將其作為狀態;最后,新增數據只需根據狀態進行相似性計算,每次連接操作結束后都對狀態進行更新。實驗結果表明,Inc-Join方法在不影響連接準確率的同時,有效將長、短字符串重復匹配次數減少為√n（n是批處理方式的匹配次數）。實驗對3種數據集進行處理,發現使用批處理方式進行相似性連接的響應時間是Inc-Join的1至4.7倍,并呈現急劇遞增的趨勢;而且優化后Inc-Join方法的響應時間最小只占優化前的3/4,并隨處理數據的增多所占比例越來越小。同時優化后的Inc-Join不需要保存狀態,再一次減小了算法執行的時間和空間開銷。
注: 保護知識產權,如需閱讀全文請聯系計算機應用雜志社
相關推薦
更多
