王晓霞，孙德才

（渤海大学信息科学与技术学院，锦州 121013）

0 引言

随着互联网的飞速发展，各行各业数据量也急速增长，传统的数据处理方式已不能满足要求，大数据以其在存储、处理、管理和分析等方面的优势渐渐成为解决海量数据处理的有效工具［1-2］。而基于MapReduce 框架的相似连接技术在海量大数据分析中取得了重大进展，已成为主流的大数据分析技术［3］。近年来，大量的重复数据导致MapReduce 的混淆消耗过大［4］，同时也导致网络传输的拥堵。为提高基于编辑距离的相似连接算法速度，本文提出了一种基于MapReduce 的双集合全局相似连接算法Q-sample，力图通过减少MapReduce 框架的混淆消耗和网络传输来提高连接效率。通过真实数据集的实验，结果显示本算法获得了较高的连接效率。

1 基于Q-sample和统计特征的相似连接算法

Q-sample 算法的定义是：给定二个字符串集R,S和一个编辑距离阈值τ，相似连接算法的主要目的是在集合R和集合S间找出所有满足相似要求的字符串对。为实现相似连接，设计了四个MapReduce 阶段，即统计阶段、过滤阶段、验证阶段1和验证阶段2。

1.1 统计阶段

统计阶段是统计集合中各个q-gram 的频率和对q-gram 进行m集合分类，输入是一个样例集合和q-gram 过滤器参数Q和统计向量长度限值m。统计阶段包含map、shuffle和reduce三个过程。

Map 过程的任务是输入一个key-value 对，key 是片段的编号sn，value 是片段的内容。首先将value 拆分出字符串的内容s，再把s从0到 |s|-Q拆分成固定长度为Q的连续且重叠Q-1 的q-gram，并输出一个key-value对。

在shuffle 过程中，把map 过程中产生的所有具有相同key 的key-value 对传输到同一个reduce结点上。……