More Web Proxy on the site http://driver.im/

research-article

GPU acceleration of probabilistic frequent itemset mining from uncertain databases

Authors:

Toshiyuki Amagasa,

Hiroyuki KitagawaAuthors Info & Claims

CIKM '12: Proceedings of the 21st ACM international conference on Information and knowledge management

Pages 892 - 901

https://doi.org/10.1145/2396761.2396874

Published: 29 October 2012 Publication History

Abstract

Uncertain databases have been widely developed to deal with the vast amount of data that contain uncertainty. To extract valuable information from the uncertain databases, several methods of frequent itemset mining, one of the major data mining techniques, have been proposed. However, their performance is not satisfactory because handling uncertainty incurs high processing costs. In order to address this problem, we utilize GPGPU (General-Purpose computation on GPU). GPGPU implies using a GPU (Graphics Processing Unit), which is originally designed for processing graphics, to accelerate general purpose computation. In this paper, we propose a method of frequent itemset mining from uncertain databases using GPGPU. The main idea is to speed up probability computations by making the best use of GPU's high parallelism and low-latency memory. We also employ an algorithm to manipulate a bitstring and data-parallel primitives to improve performance in the other parts of the method. Extensive experiments show that our proposed method is up to two orders of magnitude faster than existing methods.

References

[1]

C. C. Aggarwal and P. S. Yu. A Survey of Uncertain Data Algorithms and Applications. TKDE, 21(5), 2009.

Digital Library

[2]

R. Agrawal, T. Imielinski, and A. Swami. Mining Association Rules between Sets of Items in Large Databases. SIGMOD, 1993.

Digital Library

[3]

R. Agrawal and R. Srikant. Fast Algorithms for Mining Association Rules. In VLDB, 1994.

Digital Library

[4]

R. Agrawal and J. C. Shafer. Parallel Mining of Association Rules. TKDE, 8(6), 1996.

Digital Library

[5]

N. Bell and M. Garland. Implementing Sparse Matrix-Vector Multiplication on Throughput-Oriented Processors. In SC, 2009.

Digital Library

[6]

T. Bernecker, H.-P. Kriegel, M. Renz, F. Verhein, and A. Zuefle. Probabilistic Frequent Itemset Mining in Uncertain Databases. In KDD, 2009.

Digital Library

[7]

C.-K. Chui, B. Kao, and E. Hung. Mining Frequent Itemsets from Uncertain Data. In PAKDD, 2007.

Digital Library

[8]

W. Fang, M. Lu, X. Xiao, B. He, and Q. Luo. Frequent Itemset Mining on Graphics Processors. In DaMoN, 2009.

Digital Library

[9]

N. K. Govindaraju, J. Gray, R. Kumar, and D. Manocha. GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management. In SIGMOD, 2006.

Digital Library

[10]

J. Han, J. Pei, and Y. Yin. Mining Frequent Patterns without Candidate Generation. In SIGMOD, 2000.

Digital Library

[11]

B. He, K. Yang, M. Lu, N. K. Govindaraju, Q. Luo, and P. V. Sander. Relational Joins on Graphics Processors. In SIGMOD, 2008.

Digital Library

[12]

B. He, M. Lu, K. Yang, R. Fang, N. K. Govindaraju, Q. Luo, and P. V. Sander. Relational Query Coprocessing on Graphics Processors. ACM Trans. Database Syst., 34(4), 2009.

Digital Library

[13]

Y. Kozawa, T. Amagasa, and H. Kitagawa. Fast Frequent Itemset Mining from Uncertain Databases using GPGPU. In MUD, 2011.

[14]

E. Özkural, B. Uçar, and C. Aykanat. Parallel Frequent Item Set Mining with Selective Item Replication. TPDS, 22(10), 2011.

Digital Library

[15]

H. Li, Y. Wang, D. Zhang, M. Zhang, and E. Y. Chang. PFP: Parallel FP-Growth for Query Recommendation. In RecSys, 2008.

Digital Library

[16]

L. Liu, E. Li, Y. Zhang, and Z. Tang. Optimization of Frequent Itemset Mining on Multiple-Core Processor. In VLDB, 2007.

Digital Library

[17]

J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Krüger, A. E. Lefohn, and T. J. Purcell. A Survey of General-Purpose Computation on Graphics Hardware. In Computer Graphics Forum, 2007.

[18]

S. Parthasarathy, M. J. Zaki, M. Ogihara, and W. Li. Parallel Data Mining for Association Rules on Shared-Memory Systems. Knowledge and Information Systems, 3(1), 2001.

Digital Library

[19]

L. Sun, R. Cheng, D. W. Cheung, and J. Cheng. Mining Uncertain Data with Probabilistic Guarantees. In KDD, 2010.

Digital Library

[20]

L. Wang, R. Cheng, S. D. Lee, and D. W. Cheung. Accelerating Probabilistic Frequent Itemset Mining: A Model-Based Approach. In CIKM, 2010.

Digital Library

[21]

NVIDIA. CUDA C Programming Guide. http://developer.download.nvidia.com/compute/DevZone/docs/html/C/doc/CUDA_C_Programming_Guide.pdf, 2012.

[22]

NVIDIA. CUFFT Library User Guide. http://developer.download.nvidia.com/compute/DevZone/docs/html/CUDALibraries/doc/CUFFT_Library.pdf, 2012.

[23]

M. Harris. Optimizing Parallel Reduction in CUDA. http://developer.download.nvidia.com/compute/cuda/2_2/sdk/website/projects/reduction/doc/reduction.pdf, 2007.

[24]

M. Harris. Parallel Prefix Sum (Scan) with CUDA. http://developer.download.nvidia.com/compute/cuda/2_2/sdk/website/projects/scan/doc/scan.pdf, 2009.

Cited By

McCoy HHofmeyr SYelick KPandey PDehnavi MKulkarni MKrishnamoorthy S(2023)High-Performance Filters for GPUsProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577507(160-173)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577507
Bustio-Martínez LCumplido RLetras MHernández-León RFeregrino-Uribe CHernández-Palancar J(2021)FPGA/GPU-based Acceleration for Frequent Itemsets Mining: A Comprehensive ReviewACM Computing Surveys10.1145/347228954:9(1-35)Online publication date: 8-Oct-2021
https://dl.acm.org/doi/10.1145/3472289
Weiler MSchmid KMamoulis NRenz MMouratidis KRenz MEmrich TZüfle AJanowicz K(2015)Geo-Social Co-location MiningSecond International ACM Workshop on Managing and Mining Enriched Geo-Spatial Data10.1145/2786006.2786010(19-24)Online publication date: 31-May-2015
https://dl.acm.org/doi/10.1145/2786006.2786010
Show More Cited By

Index Terms

GPU acceleration of probabilistic frequent itemset mining from uncertain databases
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Frequent itemset mining on graphics processors
DaMoN '09: Proceedings of the Fifth International Workshop on Data Management on New Hardware

We present two efficient Apriori implementations of Frequent Itemset Mining (FIM) that utilize new-generation graphics processing units (GPUs). Our implementations take advantage of the GPU's massively multi-threaded SIMD (Single Instruction, Multiple ...
Probabilistic frequent itemset mining in uncertain databases
KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining

Probabilistic frequent itemset mining in uncertain transaction databases semantically and computationally differs from traditional techniques applied to standard "certain" transaction databases. The consideration of existential uncertainty of item(sets),...
Weighted frequent itemset mining over uncertain databases

Frequent itemset mining (FIM) is a fundamental research topic, which consists of discovering useful and meaningful relationships between items in transaction databases. However, FIM suffers from two important limitations. First, it assumes that all ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '12: Proceedings of the 21st ACM international conference on Information and knowledge management

October 2012

2840 pages

ISBN:9781450311564

DOI:10.1145/2396761

General Chair:
Xuewen Chen
Wayne State University, USA
,
Program Chairs:
Guy Lebanon
Georgia Institute of Technology
,
Haixun Wang
Microsoft Research Asia
,
Mohammed J. Zaki
Rensselaer Polytechnic Institute

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 October 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM'12

Sponsor:

CIKM'12: 21st ACM International Conference on Information and Knowledge Management

October 29 - November 2, 2012

Hawaii, Maui, USA

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
348
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

McCoy HHofmeyr SYelick KPandey PDehnavi MKulkarni MKrishnamoorthy S(2023)High-Performance Filters for GPUsProceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3572848.3577507(160-173)Online publication date: 25-Feb-2023
https://dl.acm.org/doi/10.1145/3572848.3577507
Bustio-Martínez LCumplido RLetras MHernández-León RFeregrino-Uribe CHernández-Palancar J(2021)FPGA/GPU-based Acceleration for Frequent Itemsets Mining: A Comprehensive ReviewACM Computing Surveys10.1145/347228954:9(1-35)Online publication date: 8-Oct-2021
https://dl.acm.org/doi/10.1145/3472289
Weiler MSchmid KMamoulis NRenz MMouratidis KRenz MEmrich TZüfle AJanowicz K(2015)Geo-Social Co-location MiningSecond International ACM Workshop on Managing and Mining Enriched Geo-Spatial Data10.1145/2786006.2786010(19-24)Online publication date: 31-May-2015
https://dl.acm.org/doi/10.1145/2786006.2786010
KOZAWA YAMAGASA TKITAGAWA H(2014)Probabilistic Frequent Itemset Mining on a GPU ClusterIEICE Transactions on Information and Systems10.1587/transinf.E97.D.779E97.D:4(779-789)Online publication date: 2014
https://doi.org/10.1587/transinf.E97.D.779
Cuzzocrea ALeung CMacKinnon R(2014)Mining constrained frequent itemsets from distributed uncertain dataFuture Generation Computer Systems10.1016/j.future.2013.10.02637:C(117-126)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.1016/j.future.2013.10.026
Kozawa YAmagasa TKitagawa H(2013)Parallel and Distributed Mining of Probabilistic Frequent Itemsets Using Multiple GPUsProceedings of the 24th International Conference on Database and Expert Systems Applications - Volume 805510.1007/978-3-642-40285-2_14(145-152)Online publication date: 26-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40285-2_14

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents