基于多核的并行相似连接

发布时间：2018-05-06 20:22

本文选题：多核 + 多线程　；参考：《天津工业大学》2017年硕士论文

【摘要】：相似连接(similarityjoin)是指在给定的数据集中,根据给定的相似度度量函数来衡量数据之间的相似度,并找出所有相似度不小于给定阈值的数据对的操作。相似连接有着广泛的应用领域,如,模糊的关键字匹配,文档聚类,系统推荐,协同过滤,数据集成与清洗等。随着网络和移动应用等信息技术的不断发展,数据呈现爆炸式增长,海量数据的分析需要强大的计算能力,相似连接成为大数据处理领域的热点方式之一。度量相似性的方法有很多种,如,Jaccard similarity,Cosine similarity,Overlap similarity,Hamming distance,Edit distance。本篇文章主要采用 Jaccard similarity的方法去量化数据对相似值。传统的单核计算机平台的处理能力已经很难满足海量数据处理的计算要求。为了提高计算效率和计算性能,利用基于多核平台的多线程并行编程发挥多核体系结构的优势,已经成为实现个人低成本并行计算和多核技术发展的趋势。为海量数据下的相似连接带来了曙光。实验中,本文基于提出的数据分解和任务分解策略实现了四种不同相似连接算法,以此来验证本文提出的基于多核的并行相似连接方法的性能和可扩展性。四种算法为:数据量均衡划分与共享索引的方法,等长数据划分与共享索引的方法,数据量均衡划分与独立索引的方法,等长数据划分与独立索引的方法。通过实验证明,本文提出的方法可以充分利用多核处理器架构的并行处理能力,可以显著的提高相似连接的效率。
[Abstract]:Similarity join is an operation that measures the similarity between data according to the given similarity measure function in a given data set and finds out all the data pairs whose similarity is not less than a given threshold. Similar join has a wide range of applications, such as fuzzy keyword matching, document clustering, system recommendation, collaborative filtering, data integration and cleaning. With the development of information technology, such as network and mobile application, the data is increasing explosively. The analysis of massive data needs powerful computing power. Similarity connection has become one of the hot methods in big data's processing field. There are many methods to measure similarity, such as Jaccard similarity and Cosine similarity / overlap similarity / hamming distance.Edit distance. This article mainly uses Jaccard similarity method to quantify the data pair similarity value. The processing ability of the traditional single-core computer platform has been difficult to meet the computing requirements of mass data processing. In order to improve computing efficiency and computing performance, it has become a trend to realize personal low-cost parallel computing and multi-core technology development by using multi-core multi-thread parallel programming based on multi-core platform to give play to the advantages of multi-core architecture. It brings the dawn to the similar connection under the massive data. In the experiment, four different similarity join algorithms are implemented based on the proposed data decomposition and task decomposition strategies to verify the performance and scalability of the proposed parallel similar join method based on multiple cores. The four algorithms are: the method of data equalization and sharing index, the method of equal-length data partition and shared index, the method of data balance partition and independent index, the method of equal-length data partition and independent index. The experiments show that the proposed method can make full use of the parallel processing ability of the multi-core processor architecture and can significantly improve the efficiency of similar connections.
【学位授予单位】：天津工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP332;TP311.13

【相似文献】