Exploiting GPUs for fast intersection of large sets. Issue 108 (September 2022)

• Record Type: Journal Article
• Authors: Bellas, Christos; Gounaris, Anastasios
• Is Part Of: Information systems. Issue 108(2022)
• Publication Date: 2022-09
• Subjects: Set-intersection -- Set-similarity join -- Set-containment join -- Matrix multiplication -- GPU computing -- CUDA; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2022.101992
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: 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. Highlights: 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.