基于CPU-GPU异构体系结构的并行字符串相似性连接方法

徐坤浩 聂铁铮 申德荣 寇 月 于 戈

(东北大学计算机科学与工程学院 沈阳 110169)

(xukunhao725@163.com)

随着传统互联网的发展和移动互联网的出现，数据量迅速变大，“大数据”的概念逐渐被人们熟知.但大量的数据也对传统的数据存储和处理带来了新的挑战.为了更快地处理大数据，人们采用例如MapReduce和HDFS(Hadoop distributed file system)等分布式的策略来计算和存储大数据.传统的CPU性能提升方法已经达到瓶颈，提高主频和核心数量等方法对CPU性能的提升变得越来越困难，仅由CPU负责计算的传统相似性连接算法的处理速度已经渐渐满足不了用户的需求.近年来，GPU的处理性能和并行处理单元集成度提升迅速，更多的算术逻辑单元使得GPU的综合计算性能远超CPU.GPU能够极大地解决CPU处理能力不足的问题，因此基于CPU-GPU异构体系结构的处理模式正成为未来的发展趋势.

相似性连接处理技术是对来自不同数据集的2个对象计算相似度，并以相似度是否达到指定阈值作为对象间的连接条件.目前，相似性连接技术已经被广泛地应用在搜索引擎、数据集成以及知识库构建等领域.根据计算对象间相似度的算法不同，常见的相似性连接可以分为字符串相似性连接、集合相似性连接、向量相似性连接以及图相似性连接，其中以字符串相似性连接应用最为广泛.字符串的相似性可以通过Jaccard相似度等多种相似性度量进行计算.传统的相似性连接处理技术一般使用过滤-验证框架，包含过滤和验证2个部分：在过滤阶段设计高效的过滤算法将大量不可能符合相似度要求的数据记录对过滤剔除，大幅减少候选对的数量；……