A New Data Layout For Set Intersection on GPUs

Rasmus Resen Amossen, Rasmus Pagh

Research output: Journal Article or Conference Article in JournalConference articleResearchpeer-review

Abstract

Set intersection is the core in a variety of problems, e.g. frequent itemset mining and sparse boolean matrix multiplication. It is well-known that large speed gains can, for some computational problems, be obtained by using a graphics processing unit (GPU) as a massively parallel computing device. However, GPUs require highly regular control flow and memory access patterns, and for this reason previous GPU methods for intersecting sets have used a simple bitmap representation. This representation requires excessive space on sparse data sets. In this paper we present a novel data layout, BATMAP, that is particularly well suited for parallel processing, and is compact even for sparse data.
Frequent itemset mining is one of the most important applications of set intersection. As a case-study on the potential of BATMAPs we focus on frequent pair mining, which is a core special case of frequent itemset mining. The main finding is that our method is able to achieve speedups over both Apriori and FP-growth when the number of distinct items is large, and the density of the problem instance is above 1%. Previous implementations of frequent itemset mining on GPU have not been able to show speedups over the best single-threaded implementations.
Original languageEnglish
JournalProceedings, International Parallel and Distributed Processing Symposium (IPDPS)
Pages (from-to)698 - 708
Number of pages10
ISSN1530-2075
Publication statusPublished - 2011
Event25th IEEE International Parallel and Distributed Processing Symposium (IPDS) 2011 - Anchorage (Alaska), United States
Duration: 16 May 201120 May 2011
Conference number: 25th
http://www.ipdps.org/ipdps2011/2011_advance_program.html

Conference

Conference25th IEEE International Parallel and Distributed Processing Symposium (IPDS) 2011
Number25th
Country/TerritoryUnited States
CityAnchorage (Alaska)
Period16/05/201120/05/2011
Internet address

Keywords

  • Set Intersection
  • Graphics Processing Unit (GPU)
  • Frequent Itemset Mining
  • Sparse Data Structures
  • Parallel Computing

Fingerprint

Dive into the research topics of 'A New Data Layout For Set Intersection on GPUs'. Together they form a unique fingerprint.

Cite this