Highly Parallel Sequential Pattern Mining on a Heterogeneous Platform

Yu Heng Hsieh, Chun Chieh Chen, Hong-Han Shuai, Ming Syan Chen

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    2 Scopus citations

    Abstract

    Sequential pattern mining can be applied to various fields such as disease prediction and stock analysis. Many algorithms have been proposed for sequential pattern mining, together with acceleration methods. In this paper, we show that a heterogeneous platform with CPU and GPU is more suitable for sequential pattern mining than traditional CPU-based approaches since the support counting process is inherently succinct and repetitive. Therefore, we propose the PArallel SequenTial pAttern mining algorithm, referred to as PASTA, to accelerate sequential pattern mining by combining the merits of CPU and GPU computing. Explicitly, PASTA adopts the vertical bitmap representation of database to exploits the GPU parallelism. In addition, a pipeline strategy is proposed to ensure that both CPU and GPU on the heterogeneous platform operate concurrently to fully utilize the computing power of the platform. Furthermore, we develop a swapping scheme to mitigate the limited memory problem of the GPU hardware without decreasing the performance. Finally, comprehensive experiments are conducted to analyze PASTA with different baselines. The experiments show that PASTA outperforms the state-of-the-art algorithms by orders of magnitude on both real and synthetic datasets.

    Original languageEnglish
    Title of host publication2018 IEEE International Conference on Data Mining, ICDM 2018
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages1037-1042
    Number of pages6
    ISBN (Electronic)9781538691588
    DOIs
    StatePublished - 27 Dec 2018
    Event18th IEEE International Conference on Data Mining, ICDM 2018 - Singapore, Singapore
    Duration: 17 Nov 201820 Nov 2018

    Publication series

    NameProceedings - IEEE International Conference on Data Mining, ICDM
    Volume2018-November
    ISSN (Print)1550-4786

    Conference

    Conference18th IEEE International Conference on Data Mining, ICDM 2018
    Country/TerritorySingapore
    CitySingapore
    Period17/11/1820/11/18

    Keywords

    • Data mining
    • Frequent sequential pattern
    • GPGPU
    • Heterogeneous platform
    • Parallel computing

    Fingerprint

    Dive into the research topics of 'Highly Parallel Sequential Pattern Mining on a Heterogeneous Platform'. Together they form a unique fingerprint.

    Cite this