相似连接具有广泛的应用，如，合并检测，模糊的关键字匹配，数据融合，数据清理等。相似性度量方法有许多种，如Jaccard距离、Cosine距离、编辑距离。文章主要集中于字符串编辑距离相似性连接的研究，编辑距离是指两个字符串从一个转化到另一个需要的最小编辑次数（插入、删除或者修改单个字符）。本篇文章将字符串中单个字符的频率其全局的信息。在此基础上，我们提出了一种基于数据划分的算法，这种算法能够有效的将不相关的数据划分开来，因而避免了不必要的计算。与此同时，一些新的过滤方法被提出，它们拥有低的时间复杂度并且能够过滤掉现有算法不能过滤掉的字符串待选对。实验里，我们使用真数据集验证了这种方法的高效性。在磁盘算法上，我们也提出了一个基于磁盘相似连接算法的框架，而且还证明了磁盘调度问题的难度并提出了不同的启发式磁盘调度方法。此外，我们还提出了基于该外存算法框架实现字符串相似性连接增量式计算的方法。这为以后的磁盘算法奠定了基础。