PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey of Parallel Sequential Pattern Mining

Wensheng Gan, Jerry Chun-Wei Lin, Philippe Fournier-Viger, Han-Chieh Chao, Philip S. Yu

arXiv:1805.10515v2cs.DB

TL;DR

Large-scale sequential pattern mining strains single-node algorithms because of limited memory and computation, while prior surveys have not comprehensively covered parallel methods. This paper surveys PSPM approaches, advanced topics, software, challenges, and opportunities, concluding that pattern-growth and hybrid approaches generally outperform earlier categories.

  • Problem

    Single-node mining becomes inefficient on big data, and prior surveys did not provide a comprehensive taxonomy and development summary specific to parallel sequential pattern mining.

  • Method

    The paper provides an in-depth survey categorizing PSPM into partition-based, Apriori-based, pattern-growth, and hybrid approaches, alongside advanced topics, software, challenges, and opportunities.

  • Results

    Pattern-growth approaches usually perform better than partition-based and Apriori-based PSPM, while hybrid methods usually achieve significant performance improvements over those categories.

  • Takeaways & Limitations

    The survey identifies complex sequence types, multimodal data, privacy, and parallelization of condensed or summarizing methods as continuing PSPM challenges and opportunities.

  • Takeaways & Limitations

    Current PSPM developments address some sequence types, but various more complex sequence data, including spatio-temporal data, remains an open challenge.

Abstract

from arXiv · show

With the growing popularity of shared resources, large volumes of complex data of different types are collected automatically. Traditional data mining algorithms generally have problems and challenges including huge memory cost, low processing speed, and inadequate hard disk space. As a fundamental task of data mining, sequential pattern mining (SPM) is used in a wide variety of real-life applications. However, it is more complex and challenging than other pattern mining tasks, i.e., frequent itemset mining and association rule mining, and also suffers from the above challenges when handling the large-scale data. To solve these problems, mining sequential patterns in a parallel or distributed computing environment has emerged as an important issue with many applications. In this paper, an in-depth survey of the current status of parallel sequential pattern mining (PSPM) is investigated and provided, including detailed categorization of traditional serial SPM approaches, and state of the art parallel SPM. We review the related work of parallel sequential pattern mining in detail, including partition-based algorithms for PSPM, Apriori-based PSPM, pattern growth based PSPM, and hybrid algorithms for PSPM, and provide deep description (i.e., characteristics, advantages, disadvantages and summarization) of these parallel approaches of PSPM. Some advanced topics for PSPM, including parallel quantitative / weighted / utility sequential pattern mining, PSPM from uncertain data and stream data, hardware acceleration for PSPM, are further reviewed in details. Besides, we review and provide some well-known open-source software of PSPM. Finally, we summarize some challenges and opportunities of PSPM in the big data era.

1 INTRODUCTION

Sequential pattern mining discovers ordered, time-related subsequences but becomes difficult to scale as data volumes and application demands grow. This survey organizes parallel sequential pattern mining research, algorithms, advanced topics, software, and open challenges.

  • Scalability motivation: Single-node data-mining methods become inefficient on big data because memory, computation, bandwidth, and privacy constraints limit scalable processing.Large inputs demand parallel processing, although parallelizing the mining process is difficult.
  • Scalability motivation: Parallel data mining uses multiple processors or nodes to analyze massive databases within reasonable time and can accelerate processing of parallelizable workloads.MapReduce implementations of Apriori-like algorithms achieved certain speedup over single-node methods, although prior studies found MapReduce unsuitable for some frequent-itemset tasks.
  • Sequential pattern mining: Sequential pattern mining discovers statistically relevant subsequences from event or item sequences under criteria such as frequency, length, or profit.It differs from frequent itemset and association rule mining by accounting for sequential ordering and embedded time information.
  • Survey scope: The survey addresses the lack of a dedicated synthesis of parallel sequential pattern mining methods and develops a general taxonomy for research in parallel computing environments.Earlier big-data pattern-mining surveys were broader and presented only 12 PSPM algorithms in one section.
  • Survey scope: It reviews serial SPM categories and parallel PSPM approaches, including partition-based, Apriori-based, pattern-growth, and hybrid algorithms.The review compares representative methods and discusses their key ideas, advantages, disadvantages, and recent advances.
  • Survey scope: The paper also surveys quantitative, weighted, utility, uncertain, and stream-data PSPM, CPU/GPU acceleration, open-source software, and future challenges and opportunities.These topics extend the survey beyond core distributed algorithms toward practical resources and emerging research directions.

2 PARALLEL COMPUTING FRAMEWORK

Parallel computing frameworks address the limits of single-node data mining by distributing computation, data, or both across processors and systems. The section distinguishes parallelization strategies and surveys computing platforms used for large-scale mining.

  • Parallel data mining uses multiple processors, potentially across nodes, to extract patterns from databases with high-performance architectures.Its goals include reducing the memory and computation limitations of single-node mining for large datasets.
  • Parallelism types: Task parallelism assigns portions of the search space to processors either through fixed divide-and-conquer partitions or a dynamically managed task queue.The task-queue approach assigns new work whenever a processor becomes available.
  • Parallelism types: Data parallelism distributes datasets across processors, using record-based horizontal partitioning or attribute-based division.Record-based approaches partition records or attribute lists, whereas attribute-based approaches assign attributes to processors.
  • Parallelism types: Hybrid data/task parallelism forms a pipeline whose tasks may themselves be data-parallel, with throughput constrained by the longest-latency element.Each task’s output becomes the next task’s input.
  • Design dimensions: Parallel data-mining designs vary along five dimensions: memory architecture, parallelism type, load balancing, candidate generation, and data layout.The listed contrasts are distributed versus shared memory, data versus task parallelism, static versus dynamic balancing, complete versus heuristic candidate generation, and horizontal versus vertical layout.

4 STATE-OF-THE-ART PARALLEL SEQUENTIAL PATTERN MINING

This section surveys parallel sequential pattern mining through partition-based, Apriori-based, pattern-growth, and hybrid approaches, emphasizing their characteristics, trade-offs, and scalability. It also identifies pattern-growth and hybrid methods as generally stronger than earlier approaches while documenting communication, memory, I/O, and load-balancing limitations.

  • Taxonomy: PSPM research is organized into partition-based, Apriori-based, pattern-growth, and hybrid algorithm categories.The survey also notes that many PSPM algorithms are inherently hybrid.
  • Partition-based Algorithms: Partition-based methods distribute databases or computations using replication, partitioning, or scheduling strategies such as round-robin, hash, and range assignment.SPSPM illustrates round-robin distribution of candidate sequences across three nodes.
  • Limitations: Increasing processor counts can produce good speedups, but STPF may experience load imbalance, while DPF incurs repeated local scans and added I/O overhead.DPF’s dynamic load balancing also requires more inter-processor communication and may interrupt busy processors.
  • Partition-based Algorithms: DGSP reduces communication overhead with a two-jobs MapReduce structure but performs poorly because it repeatedly scans the input data.It also partitions database fragments among Map workers and seeks workload balance.
  • Pattern-growth Algorithms: Par-CSP independently mines closed sequential-pattern tasks and uses dynamic scheduling, but distributed-memory load balancing can be too expensive for big data.PMSPX instead mines maximal frequent sequential patterns using multiple samples.
  • Pattern-growth Algorithms: Pattern-growth approaches usually perform better than earlier partition-based and Apriori-based PSPM algorithms.The survey presents this as a conclusion from its comparative analysis of the approaches.
  • Hybrid Algorithms: Hybrid PSPM methods combine technologies to reduce communication cost, memory usage, and execution time, usually improving performance over the other surveyed categories.The survey nevertheless states that hybrid methods retain their own advantages and disadvantages.

5 ADVANCED TOPICS IN PSPM

The survey extends PSPM beyond conventional sequence data to quantitative, weighted, utility, uncertain, and streaming settings, and reviews hardware acceleration. These topics address application-specific data characteristics and computing constraints, although stream-data parallel mining remains limited.

  • Scope: Advanced PSPM topics include quantitative, weighted, and utility mining, uncertain and stream data, and hardware acceleration.The survey presents these methods as additional options for specific real-world problems and tasks.
  • Quantitative and Utility PSPM: PESMiner supports parallel quantitative sequential-pattern mining at scale, while Spark-based BigHUSP mines high-utility sequential patterns.BigHUSP is designed on Apache Spark and uses Spark’s distributed-processing properties.
  • Uncertain Data: Uncertain sequence data models inaccurate or imprecise timestamped data, but traditional mining algorithms are inapplicable to uncertain data.Distributed Sequential Pattern mining further targets large-scale uncertain databases with memory-efficient distributed dynamic programming.
  • Stream Data: Stream data is temporally ordered, fast changing, massive, and potentially infinite, and few parallel sequential-pattern mining algorithms currently address it.The survey identifies SPAMC and SPAMC-UDLT as proposed algorithms for stream processing.
  • Hardware Acceleration: Hardware accelerators can let a single node achieve orders-of-magnitude improvements in performance and energy efficiency.The survey discusses GPUs, many-core architectures, Automata Processor hardware, AP-SPM, and GPU-GSP.

6 OPEN-SOURCE SOFTWARE

The survey reviews open-source implementations for SPM and PSPM because limited code availability hinders reproducibility and can make performance comparisons unfair. It highlights libraries and implementations spanning classical, MapReduce-based, and Spark-based mining.

  • Motivation: Few PSPM implementations or source releases exist, forcing reimplementation and potentially undermining fair experimental comparisons.Performance may depend on the compiler and machine architecture used.
  • Additional Resources: Additional resources include Zaki’s C implementations for sequence mining and the SPAM website’s source code, documentation, examples, and presentation slides.These resources support access to classical sequential-pattern-mining algorithms.
  • General Libraries: SPMF is a Java library with 120 data-mining algorithms and the largest collection of sequential-pattern-mining implementations described by the survey.It includes implementations of AprioriAll, GSP, PrefixSpan, SPADE, and SPAM, among others.
  • General Libraries: MLlib is a scalable Apache-Spark-based library containing sequential-pattern mining alongside frequent-itemset and association-rule mining.Its algorithms are written in Java, Scala, Python, and R.
  • Distributed Implementations: MG-FSM provides a scalable MapReduce implementation for frequent sequence mining, including maximum-gap and maximum-length constraints.Its Java implementation and command-line options are available on GitHub.
  • Distributed Implementations: LASH is a scalable MapReduce distributed sequence-mining algorithm that considers item hierarchies and provides Java source code with build and execution instructions.The survey identifies it as an implementation available on GitHub.

7 CHALLENGES AND OPPORTUNITIES IN PARALLEL SEQUENTIAL PATTERN MINING

The survey identifies unresolved PSPM challenges spanning complex, multimodal, dynamic, large-scale, and privacy-sensitive data, while highlighting opportunities in computing, hardware, learning, and concise pattern output.

  • Challenges: PSPM still needs adaptable parallel frameworks for complex sequence types such as spatio-temporal data with richer semantic information.These data include time-space, location, and spatial-temporal relationships beyond traditional sequence ordering.
  • Challenges: Integrating the complementary information and diversity of multimodal data remains a major PSPM challenge.The survey frames multimodal integration as combining knowledge that cannot be obtained from any single modality alone.
  • Challenges: PSPM scalability remains difficult because parallelization for big data raises availability, accuracy, and elasticity concerns.The survey notes that existing developments still do not demonstrate the needed scalability and parallelism capacities.
  • Challenges: Privacy-preserving PSPM is underdeveloped despite the risks of data leakage and growing analysis of personal data.Many privacy-preserving data-mining methods exist, but few address parallel sequential pattern mining.
  • Opportunities: Future PSPM research can exploit cloud, MapReduce, Spark, GPUs, and deep learning to improve parallel processing and sequence analysis.The survey presents these infrastructures and technologies as opportunities for developing parallel data-mining methods.
  • Opportunities: Condensed and summarizing sequential-pattern methods could reduce redundant results, but their parallelization remains open.The survey connects long patterns or low support thresholds with potentially confusing or redundant outputs and identifies parallel condensed SPM as an unresolved issue.

8 CONCLUSION

The paper surveys parallel sequential pattern mining because single-node methods struggle with large-scale data. It organizes parallel approaches, compares computing environments, and reviews advances, challenges, and opportunities.

  • Conclusion: The survey categorizes PSPM research, reviews its key ideas and trade-offs, and summarizes developments across basic and advanced algorithms.It also discusses parallelism methods, computing platforms, distributed systems, and related PSPM work.
Loading 1805.10515v2…