相似性连接是数据挖掘分析领域的基础操作,在数据清洗、生物信息学和信息集成等众多领域有着广泛的应用意义。相似性连接处理的数据类型一般包括字符串、集合、向量和图等类型,对于不同数据类型对象之间的相似程度的衡量也有多种度量标准,如杰卡德距离、余弦距离、编辑距离。本文主要研究基于编辑距离度量的字符串相似性连接,即在被查询字符串数据集中找出所有与给定的查询字符串集合中元素满足编辑距离不小于给定阈值的字符串。目前处理字符串的相似性连接算法大多为基于单机的内存算法,他们在处理海量字符串数据时需要耗费大量时间,而分布式计算平台的兴起与广泛应用为高效解决海量字符串连接提供了条件。本文基于Spark并行计算框架良好的扩展性、容错性,将单机计算转至集群模式,研究并行字符串相似性连接问题。首先,在对传统字符串相似性连接相关技术的研究基础上,设计了字符串相似连接的并行化处理框架,在分布式计算框架Spark中进行实现,给出并分析了并行化的具体实现过程。通过字符串的频率向量信息,在数据划分的基础上,有效地过滤掉不符合相似条件的字符串,避免了大量的无效计算,通过实验证明了数据并行化与计算并行化能够有效的提高海量字符串相串相似连接的处理效率。其次,对字符串的相似连接进行优化,主要包括并行化算法的优化及平台的优化。在并行化算法方面,对字符串联合频率向量进行广播,减少连接过程中数据传输量。由于Spark基于内存计算的特性,集群环境中数据传输成为Spark计算平台的瓶颈,对此,在计算平台方面,针对任务调度策略中数据本地性进行优化,降低由于数据划分所带来的通信开销,进行有效的优化。最后,深入分析字符串相似连接解决和处理的问题,将本文提出的并行字符串相似连接算法具体应用到不同实际应用中,充分挖掘数据价值。