A Two-Level Indexing Scheme for Extracting Frequent Patterns with GPUs from Symbolic Sequence Data
摘要
Symbolic sequence data is generated from applications such as human activity recognition, financial modeling, intrusion detection systems, and drug discovery tasks. Extracting frequent patterns from symbolic data is an important research problem. In the literature, several CPU-based approaches have been proposed for pattern extraction from symbolic sequence data. However, due to their sequential execution, CPU-based approaches suffer from performance issues in extracting patterns from large sequence data. In modern computing infrastructures, GPUs are playing a central role in carrying out high-performance computing tasks due to their parallel design. Consequently, researchers are investigating GPU-based data mining techniques for tasks such as pattern mining, clustering, and classification. In this paper, we propose a two-level indexing scheme that utilizes extra auxiliary memory to facilitate the efficient extraction of frequent patterns from symbolic data by exploiting the parallel processing capabilities of GPUs. Experimental results on three real-world datasets demonstrate that the proposed approach achieves substantial runtime improvements—approximately 4 \(\times \) speedup over traditional CPU-based algorithms for smaller support values (e.g., 5), and more than 20 \(\times \) speedup for support thresholds greater than 10—when applied to large symbolic sequence data, outperforming both CPU-based and naïve GPU-based methods.