摘要:
相似性连接技术在数据清洗、数据集成等领域中具有重要意义, 近年来引起了学术界的广泛关注.随着数据量的不断增大、数据处理实时性的要求逐渐提高以及处理器性能提升瓶颈的出现, 传统的串行相似性连接方法已经不能满足当前大数据处理的需求.近些年, GPU作为协处理器在机器学习等领域取得了良好的加速效果, 因此基于GPU的并行算法开始成为解决各类性能问题的有效解决方案.为此, 提出了基于CPU-GPU异构体系的并行相似性连接方法.首先, 方法使用GPU构建倒排索引, 索引采用SoA(struct of arrays)结构, 从而解决了传统索引结构在并行模式下读写效率低的问题.其次, 针对串行算法的性能问题, 提出基于过滤验证框架的并行双重长度过滤算法, 其中利用前缀过滤和构建好的倒排索引提升过滤效果.方法中相似度精确计算验证过程使用CPU计算执行, 从而充分利用CPU-GPU的异构计算资源.最后, 在多个数据集上进行实验验证性能.通过与串行相似性连接算法进行对比, 实验结果表明所提出方法相对于已有方法具有更好的过滤效果和更低的索引生成代价, 并在相似性连接上具有更好的性能和良好的加速比.
Abstract:
Similarity join is an important task in data cleaning, data integration and other fields, which has attracted extensive attention in recent years. With the increasing amount of data, the improvement of real-time processing requirement and the bottleneck of CPU performance improvement, the traditional serial algorithms of similarity join have been unable to meet the requirement of current big data processing. As a co-processor, GPU has achieved good acceleration results in machine learning and other fields in recent years. It is of great practical significance to study the parallel similarity join algorithms based on GPU. This paper proposes a parallel similarity join algorithm based on CPU-GPU heterogeneous architecture. Firstly, GPU is used to construct inverted index based on SoA (struct of arrays), which solves the problem of low efficiency of traditional index structure in parallel reading and writing. Then, to address the performance problem of serial algorithms, a parallel dual-length filtering algorithm based on filter-verification framework is proposed. Inverted index and prefix filtering algorithm are used to further improve the filtering performance. And in our approach, the calculation for exact similarity verification is performed by CPU to make full use of heterogeneous computing resources of CPU-GPU. Finally, experiments are carried out on several datasets. Compared with the serial similarity join algorithms, the results show that our proposed algorithms have better filtering performance and lower index generation time than existing algorithms, and also have better processing performance and higher speedup ratio on the similarity join.
百度学术
下载:
