字符串相似性连接就是可以在单个或多个字符串样本数据集中,找出位于数据集中的所有相似字符串对。随着互联网信息系统和人工智能系统的不断发展,字符串相似性连接在很多应用中具有广泛的使用场景,例如网页相似性检索、数据融合、生物信息学、模糊字符串匹配等,是最近几年备受关注的科研方向之一。并且,越来越多的互联网企业都把字符串相似性连接作为未来人工智能发展的基础建设。但是,大数据时代的到来,海量字符串数据日益普遍,现有的字符串相似性连接算法在处理海量数据集时并不高效,主要有如下限制:(1)现有的算法均在将海量数据存储在磁盘中,然后在计算相似性的时候导入内存。然而这些算法都会在内存中产生大量的倒转索引,大量冗余索引将大大超过单台机器节点的内存限制。(2)现有的算法使用的过滤机制并不高效,产生的候选集中仍然包含大量的不相似子集,后续的数据验证环节就需要消耗更多的时间去验证数据。(3)现有的算法都是基于单台机器节点使用,然而单机器节点的内存往往是受限的,不易扩容,已经难以应付海量的数据集。本文在传统字符串相似性连接算法的基础上提出了一种新型的基于动态索引和虚拟多重字符过滤的分布式算法——DV-Join。新的算法能够解决传统算法的历史遗留问题。本文主要在以下几个方面有了重大突破:(1)该算法引入动态索引,在计算相似性的过程中动态调整已经产生的倒转索引,能够大大减少倒转索引的内存消耗。(2)在原有的过滤机制上添加了虚拟多重字符过滤算法,能进一步过滤候选对集合中非相似子集的数量,节省候选集验证时间。(3)使用开源的集群分布式系统Spark,在集群中并行执行对海量数据的处理计算任务,大大减少计算时间。在经过了大量的实验后,能够得到以下结论:DV-Join算法在处理海量数据集时,比已有的传统字符串相似性连接算法更有效率。