GPU-based swarm intelligence for Association Rule Mining in big databases

Youcef Djenouri*, Philippe Fournier-Viger, Jerry Chun Wei Lin, Djamel Djenouri, Asma Belhadi

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

Association Rule Mining (ARM) is a fundamental data mining task that is time-consuming on big datasets. Thus, developing new scalable algorithms for this problem is desirable. Recently, Bee Swarm Optimization (BSO)-based meta-heuristics were shown effective to reduce the time required for ARM. But these approaches were applied only on small or medium scale databases. To perform ARM on big databases, a promising approach is to design parallel algorithms using the massively parallel threads of a GPU processor. While some GPU-based ARM algorithms have been developed, they only benefit from GPU parallelism during the evaluation step of solutions obtained by the BSO-metaheuristics. This paper improves this approach by parallelizing the other steps of the BSO process (diversification and intensification). Based on these novel ideas, three novel algorithms are presented, i) DRGPU (Determination of Regions on GPU), ii) SAGPU (Search Area on GPU, and, iii) ALLGPU (All steps on GPU). These solutions are analyzed and empirically compared on benchmark datasets. Experimental results show that ALLGPU outperforms the three other approaches in terms of speed up. Moreover, results confirm that ALLGPU outperforms the state-of-the-art GPU-based ARM approaches on big ARM databases such as the Webdocs dataset. Furthermore, ALLGPU is extended to mine big frequent graphs and results demonstrate its superiority over the state-of-the-art D-Mine algorithm for frequent graph mining on the large Pokec social network dataset.

Original languageEnglish
JournalIntelligent Data Analysis
Volume23
Issue number1
Pages (from-to)57-76
ISSN1088-467X
DOIs
Publication statusPublished - 1. Jan 2019

    Fingerprint

Keywords

  • ARM
  • big databases
  • BSO

Cite this

Djenouri, Y., Fournier-Viger, P., Lin, J. C. W., Djenouri, D., & Belhadi, A. (2019). GPU-based swarm intelligence for Association Rule Mining in big databases. Intelligent Data Analysis, 23(1), 57-76. https://doi.org/10.3233/IDA-173785