一種基于數(shù)據(jù)劃分的字符串相似連接外存算法

曹海 駱吉洲 陳懿誠

摘要： 字符串相似連接操作具有廣泛應(yīng)用，因而將著重研究基于編輯距離的字符串相似連接。而現(xiàn)有的字符串相似連接算法大多為內(nèi)存算法。實(shí)際應(yīng)用中的數(shù)據(jù)集越來越大，有必要針對超大規(guī)模數(shù)據(jù)集研制字符串相似性連接外存算法。利用組合頻率向量劃分?jǐn)?shù)據(jù)集，并提出了基于編輯距離的字符串相似性連接外存算法框架，證明了磁盤調(diào)度問題的難度并提出了不同的啟發(fā)式磁盤調(diào)度方法。此外，還提出了基于該外存算法框架實(shí)現(xiàn)字符串相似性連接增量式計算的方法。實(shí)驗(yàn)結(jié)果表明，數(shù)據(jù)劃分方法可以有效地過濾不相關(guān)的數(shù)據(jù)子集；磁盤調(diào)度算法能夠有效減少磁盤IO次數(shù)；外存算法是高效的；增量式計算方法能夠高效地處理數(shù)據(jù)更新。

關(guān)鍵詞：

中圖分類號：TP391.41文獻(xiàn)標(biāo)識碼：A文章編號：2095-2163（2012）05-0031-05