Exploiting GPUs for fast intersection of large sets

• Published in: Information systems (Oxford) 2022-09, Vol.108, p.101992, Article 101992
• Main Authors: Bellas, Christos, Gounaris, Anastasios
• Format: Article
• Language: English
• Subjects: Containment; CUDA; Datasets; GPU computing; Graphics processing units; Information retrieval; Information systems; Intersections; Matrix multiplication; Multiplication; Set-containment join; Set-intersection; Set-similarity join
• ISSN: 0306-4379; 1873-6076
• DOI: 10.1016/j.is.2022.101992

The main focus of this work is on large set intersection, which is a pivotal operation in information retrieval, graph analytics and database systems. We aim to experimentally detect under which conditions, using a single graphics processing unit (GPU) is beneficial over CPU techniques and which exact techniques are capable of yielding improvements. We cover and adapt techniques initially proposed for graph analytics and matrix multiplication, while we investigate new hybrids for completeness. We also explain how we can address set containment joins using the same techniques. The comprehensive evaluation highlights the main characteristics of the techniques examined when both a single pair of two large sets are processed and all pairs in a dataset are examined, while it provides strong evidence that state-of-the-art set containment stands to significantly benefit from advances in GPU-enabled set intersection. Our results reveal that there is no dominant solution but depending on the exact problem and the dataset characteristics, different techniques are the most efficient ones. •Develop hybrid GPU set intersection techniques for set sizes on the order of millions.•GPU’s fast matrix multiplication greatly improves set intersection for dense datasets.•GPU-based set intersection techniques are superior over CPU parallel alternatives.•A co-processing CPU–GPU scheme further improves performance for set containment join.