Bwjoin: A Blockwise GPU-based Algorithm for Set Similarity Joins

Set similarity joins play a pivotal role in diverse fields, ranging from modern database management systems to near-duplicate detection and even galaxy cluster analysis in cosmology. However, due to their quadratic nature, these operations have been associated with substantial computational costs. To tackle this challenge, parallel solutions have been developed in recent years, spanning algorithms for distributed and shared memory architectures, as well as massively parallel systems like GPU accelerators. In this paper, we propose a new GPU-based algorithm, using the prefix-filtering technique, that harnesses the power of blockwise parallelism, achieving better performance than its competitors, especially for high threshold similarity joins in big datasets.