一种基于数据划分的字符串相似连接外存算法

曹海 骆吉洲 陈懿诚

摘要： 字符串相似连接操作具有广泛应用，因而将着重研究基于编辑距离的字符串相似连接。而现有的字符串相似连接算法大多为内存算法。实际应用中的数据集越来越大，有必要针对超大规模数据集研制字符串相似性连接外存算法。利用组合频率向量划分数据集，并提出了基于编辑距离的字符串相似性连接外存算法框架，证明了磁盘调度问题的难度并提出了不同的启发式磁盘调度方法。此外，还提出了基于该外存算法框架实现字符串相似性连接增量式计算的方法。实验结果表明，数据划分方法可以有效地过滤不相关的数据子集；磁盘调度算法能够有效减少磁盘IO次数；外存算法是高效的；增量式计算方法能够高效地处理数据更新。

关键词：

中图分类号：TP391.41文献标识码：A文章编号：2095-2163（2012）05-0031-05