邓诗卓，信俊昌，聂铁铮，王国仁

东北大学 计算机科学与工程学院，沈阳 110819

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

邓诗卓，信俊昌，聂铁铮，王国仁+

东北大学 计算机科学与工程学院，沈阳 110819

相似性连接；权重相似性连接；大数据；过滤；Spark

1 引言

随着信息技术的飞速发展，各行各业的数据都逐渐信息化，数据的存储形式也由传统的纸质数据发展成为电子数据。互联网技术的发展促进了网络资源的共享与传播，数据量呈现一种爆炸式增长的模式，数据数量并不代表数据质量，如何在大量数据中找到有用的数据，如同在沙漠中挖掘钻石，这给数据清洗集成和数据挖掘带来了挑战。相似性连接技术作为数据清洗集成等技术中的重要步骤[1]，同样面临着大数据的挑战。在数据清洗集成中，相似性连接技术是对不同数据源或者同源的实体记录，根据定义相似度度量函数获取记录对的相似度，将所有满足相似度阈值的记录对进行相似性连接，得到所有相似的记录对，而相似性连接搜索查询是利用相似性连接技术，对给定查询对象，查询数据集中满足相似度阈值的所有记录[2]。

随着数据量的激增，面向大数据的相似性连接技术无论是在数据大规模存储还是在数据处理速度上，实现基于相似性连接技术的应用功能都更加具有挑战性。考虑到大数据存储效率和执行效率两方面因素，基于单机计算的计算模式已经不适合处理大规模数据了，因此面向大数据的相似性连接技术由单机计算逐渐发展成为面向集群计算和分布式计算。……