Projekter pr. år
Abstract
Set intersection is the core in a variety of problems, e.g. frequent itemset mining and sparse boolean matrix multiplication. It is wellknown 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 casestudy 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 FPgrowth 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 singlethreaded implementations.
Frequent itemset mining is one of the most important applications of set intersection. As a casestudy 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 FPgrowth 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 singlethreaded implementations.
Originalsprog  Engelsk 

Tidsskrift  Proceedings, International Parallel and Distributed Processing Symposium (IPDPS) 
Sider (fratil)  698  708 
Antal sider  10 
ISSN  15302075 
Status  Udgivet  2011 
Begivenhed  25th IEEE International Parallel and Distributed Processing Symposium (IPDS) 2011  Anchorage (Alaska), USA Varighed: 16 maj 2011 → 20 maj 2011 Konferencens nummer: 25th http://www.ipdps.org/ipdps2011/2011_advance_program.html 
Konference
Konference  25th IEEE International Parallel and Distributed Processing Symposium (IPDS) 2011 

Nummer  25th 
Land/Område  USA 
By  Anchorage (Alaska) 
Periode  16/05/2011 → 20/05/2011 
Internetadresse 
Emneord
 Set Intersection
 Graphics Processing Unit (GPU)
 Frequent Itemset Mining
 Sparse Data Structures
 Parallel Computing
Fingeraftryk
Dyk ned i forskningsemnerne om 'A New Data Layout For Set Intersection on GPUs'. Sammen danner de et unikt fingeraftryk.Projekter
 1 Afsluttet

SQERD: Scalable Query Evaluation in Relational Databases
Pagh, R. (PI) & Amossen, R. R. (CoI)
01/06/2007 → 31/08/2010
Projekter: Projekt › Forskning