Paper 1

Accelerating Set Similarity Joins Using GPUs

Authors: Mateus S. H. Cruz, Yusuke Kozawa, Toshiyuki Amagasa, and Hiroyuki Kitagawa

Volume 28 (2016)

Abstract

We propose a scheme for ecient set similarity joins on Graphics Processing Units (GPUs). Due to the rapid growth and diversi cation of data, there is an increasing demand for fast execution of set similarity joins in applications that vary from data integration to plagiarism detection. To tackle this problem, our solution takes advantage of the massive parallel processing oered by GPUs. Additionally, we employ MinHash to estimate the similarity between two sets in terms of Jaccard similarity. By exploiting the high parallelism of GPUs and the space eciency provided by MinHash, we can achieve high performance without sacricing accuracy. Experimental results show that our proposed method is more than two orders of magnitude faster than the serial version of CPU implementation, and 25 times faster than the parallel version of CPU implementation, while generating highly precise query results.