随着社会网络、移动应用以及传感器技术的发展和普及，数据收集的效率、规模和种类得到了很大的提高，催生了对非结构化数据的管理。由于开放环境下的非结构化数据具有海量、异构、多源和分散等新特征，使得收集的数据中存在大量的重复数据，给数据处理带来了新的问题和挑战。随着web2.0以及电子商务的发展，传统的关系数据库在应付超大规模和高并发的动态网站时已经显得力不从心。NoSQL数据库由于具有高可扩展性、高可用性，以及数据存储的灵活性优势，成为大数据处理的利器，越来越多的数据存储到NoSQL数据库中。在进行数据分析和信息集成的过程中往往需要对描述同一个实体的数据进行关联。由于在开放以及无模式存储环境下，同一个实体在不同的数据源中存在不同的描述信息，我们无法使用关系数据库中的基于逻辑关系的连接运算来实现关联，因此人们提出了相似连接操作。相似连接是要在给定的数据集中按照指定的相似度计算方法找出所有相似度不小于给定阈值的记录对。相似连接作为一种基本的操作在很多领域得到广泛的应用，在社会网络的推荐系统中，根据用户的属性信息、日志等计算不同用户之间的相似度，进而做好友推荐、广告投放等;在数据集成的过程中，将来自不同数据源的数据进行数据之间的关联，可以提高数据的质量，对数据分析有非常重要的意义;在信息检索中可以提高服务的质量和查询结果的多样性;还可以应用于文档聚类、剽窃检测和协同过滤等。　　现实世界的同一个实体在不同的数据源中存在不同的描述信息由许多的原因造成。总结起来有以下两类:一是数据源内部原因，另一个是数据源之间的原因。数据源内部原因主要是由于系统缺乏统一的约束机制，导致错误的数据进入系统:拼写错误，输入错误。数据源之间的原因有:(1)不同的数据源对数据的要求不一致，比如数据的单位、格式、精度等;(2)同一个实体的一些属性会随着时间的变化而发生改变，相应的数据在进入到数据库的时候与其他数据源中之前的数据版本不一致:(3)不同的数据源中数据的模式不一致，虽然是对同一个实体的描述但是模式不一致。　　在数据集成的过程中，往往需要对不同数据源中描述同一实体的数据进行数据之间的关联。传统关系数据库中的连接操作是基于逻辑判断关系的，由于数据源的异构性和多样性使得数据库中的连接方法不能适用，因此人们提出了相似连接方法。所谓的相似连接是要在给定的数据集中按照指定的相似度计算方法找出所有相似度不小于给定阈值的记录对。相似连接的研究内容主要包含两个方面:(1)相似度衡量方法，用来衡量对象之间的相似度;(2)数据处理方法，相似连接作为其基本的操作，选择合适的数据划分方法和过滤机制是提高相似连接效率的措施。　　由于数据的类型复杂多样、产生的效率高、规模大，为了更好的利用这些数据从中发现有用的价值以更好的为经济社会服务，对数据处理的规模、实时性提出了更高的要求。相似连接作为一个基本操作，它的执行效率是影响数据处理性能的关键。本文主要针对文本型数据上的相似连接方法进行研究，在分析已有工作的基础上提出新的相似连接算法。具体来讲，本文的贡献包含以下几个方面:　　(1)对相似连接涉及的主要技术进行了系统的总结和分析，其中包括相似度计算方法、相似度计算方法的约束转换、过滤机制、相似连接方法等，并对它们的优缺点进行了分析。　　(2)提出了基于不同排序规则的多重前缀过滤的相似连接方法。已有的前缀过滤方法一般利用词频的升序规则来对字符串集合进行规范化，然后取其中的前缀部分建立倒排索引，通过扫描索引确定候选集合，并进一步验证得到最终的结果。根据前缀过滤的性质，如果数据集中的字符串都按照同样的排序规则排序，那么相似的字符串至少存在一个前缀token。因此，不论采用何种排序规则相似的记录肯定会出现在同一个倒排列表中。但是，按照不同的排序规则来对字符串进行规范化，token的顺序是不同的，那么出现在前缀中的token是不同的。只有那些始终共同出现在同一个倒排列表上的记录才可能是最终的结果。我们可以利用多种排序方式对字符串进行规范化并求得候选集合，候选集合的交集进行验证。简单的利用多种排序规则的方法是对每一种排序规则建立索引并扫描。为了提高执行的效率，提出了以Pipeline的方式来执行多重前缀过滤方法来提高相似连接的效率。文中给出了排序规则的选择方法，并对排序规则的性质进行了详尽的分析，最后通过实验证明了在不同的数据集上均可取得明显的效果。　　(3)提出了基于划分的集合相似连接方法。根据集合相似的必要条件，提出了相似集合之间的差异度。利用差异度和鸽巢原理，提出了一种新颖的基于数据划分的集合相似连接计算方法，该方法对集合进行自适应的均衡划分，并利用基于划分块的过滤方法来提高过滤的效率。为了进一步提高过滤的效果和相似连接的效率，利用划分块的位置信息提出了增强的过滤方法。针对提出的方法，在不同的环境下进行了试验，实验结果表明该方法与已有的方法相比可以有效的提高相似连接的效率。　　(4)重复数据检测是相似连接的一个重要应用，本文第四部分提出了基于公共前缀的相似连接方法来进行重复数据检测。此方法针对数据集重复数据比较多、记录的长度比较长的情况，利用公共前缀作为字符串的签名，来减少重复的比较和通信的开销。该方法利用MapReduce平台来建立分析基于前缀的倒排索引，在生成签名的过程中在MapReduce的两个阶段分别采用不同的过滤方法，将确定不是最终结果的候选过滤掉，以节省数据传输和后续处理步骤的开销。　　(5)利用云计算平台将本文第三章提出的方法进行扩展来处理大规模的数据。由于MapReduce是share-nothing的编程模式，与传统的集中式环境不同。这样的模式下，全局共享变量不容易实现，数据在节点之间的传输开销大。将MGJoin扩展到MapReduce模式下，减少了对全局变量的依赖和数据传输的开销。为了进一步提高数据处理的性能，结合MapReduce执行框架的特点，利用了三种优化措施。