双缀过滤的大数据相似性连接处理算法

相似性连接技术是实体识别和数据集成的关键技术之一,是挖掘数据中有价值信息的重要手段。随着大数据发展,传统的集中式相似性连接已经无法满足人们对数据处理的时效性需求,并且利用分布式计算可以提高相似性连接的执行效率。因此,深入研究了基于Spark的分布式相似性连接处理算法。针对仅使用后缀位置信息过滤方法的不足,提出了利用一条记录前缀与另一条记录后缀间共同元素位置信息来进行过滤的分布式相似性连接PSJoin,提高了相似性连接的处理效率,减少了相似性连接的执行时间。同时,针对基于权重的相似度连接算法的过滤问题,结合双缀过滤原理,通过一条记录前缀共同元素之后的第一个元素的权重与另一条记录后缀中元素权重大小的关系,提出了基于双缀过滤的分布式权重相似性连接WTPSJoin。为面向大数据的相似性连接计算提供了两种可靠的解决方案。两种算法在多数据源混合数据集上进行测试实验,实验结果表明,所提算法相对于已有的过滤算法过滤效果好,执行时间少,同时具有良好的加速比。

Big Data Similarity Join Processing Based on Prefix-Suffix Filtering