Part-Join:基于划分的字符串相似性连接

目前，已有许多高效的字符串相似性连接算法被提出，但是这些算法在过滤的过程中利用的往往是字符串本身的局部信息，而忽略了字符串集合的整体信息，故性能没有得到充分的提高。为此，提出了一种基于划分的算法Part—Join，它从频率向量、字母袁、频率分布三方面对数据集进行子集划分，并给出子集间的过滤策略用于排除不相似的字符串对。扩展实验表明，Part—Join比已有算法Pass—Join效率提高了10％～15％。

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

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