Chapter 8: Sequential Pattern Mining — Temporal Discoveries

---

Abstract

Sequential pattern mining represents one of the most intellectually compelling challenges in data mining: discovering meaningful patterns hidden within the temporal dimension of data. Unlike traditional static pattern mining, sequential mining confronts the fundamental reality that time matters—the order of events, their timing, and their temporal relationships often encode the most valuable insights. This chapter explores the evolution, algorithms, applications, and research gaps in sequential pattern mining, from foundational sequence discovery algorithms to modern time-series analysis and periodic pattern detection. We trace the journey from Apriori-inspired sequence mining to sophisticated temporal discovery methods, revealing how our understanding of temporal patterns has transformed from simple ordered sets to complex temporal narratives. Keywords: Sequential pattern mining, temporal data mining, GSP, SPADE, PrefixSpan, episode mining, time-series analysis, periodic patterns, temporal association rules

---

8.1 Introduction: The Dimension of Time

In 1995, Rakesh Agrawal and Ramakrishnan Srikant published a seminal paper that would reshape how we think about patterns in data [1]. Building on their earlier work on association rule mining, they posed a deceptively simple question: What if the order of items matters? This question birthed the field of sequential pattern mining, opening a new frontier where time becomes not just a dimension, but the dimension. Consider a simple example that illustrates the profound difference between static and sequential mining. In market basket analysis, discovering that customers who buy bread also buy butter is valuable. But discovering that customers who buy a smartphone typically buy a protective case within three days, followed by accessories within two weeks, and then a replacement charger after six months tells a temporal story—a narrative of customer behavior that unfolds through time. This narrative enables not just understanding, but anticipation and intervention. Sequential pattern mining addresses a fundamental limitation of traditional association rule mining: the temporal ordering and timing of events. While association rules capture co-occurrence, sequential patterns capture succession. This distinction is not merely technical—it reflects a deeper epistemological shift in how we conceptualize patterns in data.

graph TD
    A[Pattern Mining Universe] --> B[Static Patterns]
    A --> C[Temporal Patterns]
    B --> D[Association Rules]
    B --> E[Clustering]
    C --> F[Sequential Patterns]
    C --> G[Time-Series Patterns]
    C --> H[Periodic Patterns]
    F --> I[GSP Algorithm]
    F --> J[SPADE Algorithm]
    F --> K[PrefixSpan Algorithm]
    G --> L[Episode Mining]
    G --> M[Trend Discovery]
    H --> N[Cyclic Patterns]
    H --> O[Periodic Behavior]
    
    style C fill:#f9f,stroke:#333,stroke-width:4px
    style F fill:#bbf,stroke:#333,stroke-width:2px

The mathematical formalization of sequential pattern mining begins with the concept of a sequence database. Unlike a transactional database where each transaction is a set of items, a sequence database $\mathcal{D}$ consists of sequences, where each sequence $s = \langle e_1, e_2, \ldots, e_n \rangle$ is an ordered list of events or itemsets. Each event $e_i$ may itself contain multiple items, and the temporal ordering is critical. A sequence $\alpha = \langle a_1, a_2, \ldots, a_m \rangle$ is a subsequence of another sequence $\beta = \langle b_1, b_2, \ldots, b_n \rangle$ if there exist integers $1 \leq i_1 < i_2 < \cdots < i_m \leq n$ such that $a_1 \subseteq b_{i_1}, a_2 \subseteq b_{i_2}, \ldots, a_m \subseteq b_{i_m}$. The support of a sequence $\alpha$ is the fraction of sequences in $\mathcal{D}$ that contain $\alpha$ as a subsequence. A sequence is frequent if its support exceeds a minimum support threshold $\sigma$. The sequential pattern mining problem is then: Given a sequence database $\mathcal{D}$ and minimum support threshold $\sigma$, find all frequent sequential patterns in $\mathcal{D}$. This seemingly simple problem definition masks tremendous computational complexity. The search space is exponential in the number of distinct items and sequence length, making exhaustive enumeration infeasible for even modest datasets.

8.2 The Pioneers: GSP, SPADE, and the First Generation

8.2.1 GSP: Generalized Sequential Pattern Mining

The Generalized Sequential Pattern (GSP) algorithm, introduced by Srikant and Agrawal in 1996 [2], extended their earlier AprioriAll algorithm with several critical innovations. GSP adapted the Apriori principle—if a sequence is frequent, all its subsequences must also be frequent—to the sequential domain, enabling level-wise generation of candidate sequences. The GSP algorithm operates in iterative passes. In the $k$-th pass, it generates candidate sequences of length $k$ by joining frequent sequences of length $k-1$, then scans the database to count the support of each candidate. This process continues until no new frequent sequences are found. The GSP Process: 1. Initialization: Find all frequent 1-sequences (single items) 2. Candidate Generation: Join frequent $(k-1)$-sequences to generate candidate $k$-sequences 3. Candidate Pruning: Remove candidates that contain infrequent subsequences 4. Support Counting: Scan database to count support of candidates 5. Iteration: Repeat steps 2-4 until no new frequent sequences found GSP introduced several sophisticated features beyond basic sequence mining: – Time Constraints: Minimum and maximum gap constraints between consecutive elements – Sliding Time Windows: Grouping events that occur within specified time windows – User-Defined Taxonomies: Incorporating hierarchical relationships between items However, GSP inherited a fundamental limitation from Apriori: the need for multiple database scans. For each sequence length $k$, GSP must scan the entire database to count candidate support. In domains with long frequent sequences, this results in numerous expensive database passes [3].

8.2.2 SPADE: Sequential Pattern Discovery Using Equivalence Classes

The Sequential Pattern Discovery using Equivalence classes (SPADE) algorithm, proposed by Zaki in 2001 [4], represented a paradigm shift in sequential pattern mining. Rather than generating candidates through level-wise join operations, SPADE transforms the problem into a vertical format and exploits temporal join operations on id-lists. SPADE’s key innovation lies in its vertical database representation. Instead of storing sequences as ordered lists of itemsets, SPADE maintains for each item an id-list: a list of (sequence-id, event-id) pairs indicating where the item appears. This representation enables efficient support counting through simple id-list intersections.

graph LR
    A[Horizontal Database] -->|Transform| B[Vertical Id-Lists]
    B --> C[Temporal Joins]
    C --> D[Equivalence Classes]
    D --> E[Lattice Decomposition]
    E --> F[Independent Subproblems]
    F --> G[Frequent Sequences]
    
    style B fill:#bfb,stroke:#333,stroke-width:2px
    style E fill:#bbf,stroke:#333,stroke-width:2px

The algorithm partitions the search space into equivalence classes based on common prefixes. Each equivalence class can be mined independently, enabling both depth-first and breadth-first search strategies. This decomposition has profound implications: 1. Single Database Scan: SPADE requires only three database scans—one to generate id-lists, one to find frequent 2-sequences, and one to generate equivalence classes 2. Memory Efficiency: The vertical format consumes less memory than horizontal representations for sparse datasets 3. Parallelization: Independent equivalence classes can be mined in parallel The temporal join operation is central to SPADE’s efficiency. Given two sequences $\alpha$ and $\beta$ with id-lists $L(\alpha)$ and $L(\beta)$, SPADE can compute the id-list of $\alpha \cdot \beta$ (concatenation) by joining entries from $L(\alpha)$ and $L(\beta)$ where the sequence-id matches and the event-id from $\beta$ occurs after that from $\alpha$. Empirical evaluations demonstrated that SPADE outperforms GSP by an order of magnitude on large datasets, particularly when sequences are long and support thresholds are low [4]. This performance advantage established vertical mining as a dominant paradigm in sequential pattern mining.

8.2.3 PrefixSpan: Prefix-Projected Sequential Pattern Mining

While SPADE eliminated multiple database scans, it still required substantial memory to maintain id-lists. The Prefix-Projected Sequential Pattern mining (PrefixSpan) algorithm, introduced by Pei et al. in 2001 [5], addressed this limitation through a radically different approach: projection-based divide-and-conquer. PrefixSpan’s core insight is that the search space can be recursively partitioned based on frequent prefixes, and each partition can be mined using only the relevant projected database. A projected database for prefix $\alpha$ contains only the suffixes of sequences that have $\alpha$ as a prefix. The PrefixSpan Strategy:

graph TD
    A[Original Database] --> B[Find Length-1 Frequent Items]
    B --> C{For Each Frequent Item α}
    C --> D[Construct α-Projected Database]
    D --> E[Mine Projected Database Recursively]
    E --> F[Generate Patterns with Prefix α]
    F --> C
    C --> G[Combine All Patterns]
    
    style D fill:#fbf,stroke:#333,stroke-width:2px
    style E fill:#bff,stroke:#333,stroke-width:2px

1. Find all frequent items (length-1 patterns) 2. For each frequent item $\alpha$: – Construct the $\alpha$-projected database – Mine the $\alpha$-projected database recursively – Each pattern found has $\alpha$ as prefix 3. Combine patterns from all branches The elegance of PrefixSpan lies in its simplicity and efficiency. Projected databases are progressively smaller as recursion depth increases, reducing both I/O and computation. Moreover, PrefixSpan generates no candidates—it directly mines patterns from projected databases. A critical optimization in PrefixSpan is pseudo-projection. Instead of physically creating projected databases, PrefixSpan maintains pointers into the original database, dramatically reducing memory overhead. This technique enables PrefixSpan to mine large databases that would exhaust SPADE’s memory [6]. Comparative studies have shown that PrefixSpan generally outperforms both GSP and SPADE, particularly when: – Support thresholds are low (resulting in many patterns) – Sequences are long – The alphabet (number of distinct items) is large [7] PrefixSpan’s projection-based approach has inspired numerous extensions and has become the foundation for many modern sequential mining algorithms.

8.3 Episode Mining: Discovering Partial Orders

While GSP, SPADE, and PrefixSpan focus on totally ordered sequences, many real-world applications involve partially ordered events. Episode mining, pioneered by Mannila, Toivonen, and Verkamo in 1997 [8], addresses this scenario by discovering frequent episodes in event sequences. An episode is a collection of events with a partial ordering. Episodes can be: – Serial episodes: Totally ordered events $A \rightarrow B \rightarrow C$ – Parallel episodes: Unordered events $\{A, B, C\}$ occurring within a time window – General episodes: Arbitrary partial orders, e.g., $A \rightarrow B$ and $A \rightarrow C$, but $B$ and $C$ unordered The distinction between sequence mining and episode mining is subtle but important. In sequence mining, we have multiple sequences (e.g., customer purchase histories), and we seek patterns that occur across many sequences. In episode mining, we typically have one long sequence of timestamped events (e.g., network logs, sensor streams), and we seek patterns that occur frequently across time windows within that sequence.

graph TD
    A[Episode Mining Framework] --> B[Event Sequence]
    B --> C[Window-Based Discovery]
    B --> D[Frequency Counting]
    
    C --> E[Serial Episodes]
    C --> F[Parallel Episodes]
    C --> G[General Episodes]
    
    E --> H[Total Order Required]
    F --> I[No Order Required]
    G --> J[Partial Order]
    
    D --> K[Window-Based Frequency]
    D --> L[Minimal Occurrence Frequency]
    
    style B fill:#bfb,stroke:#333,stroke-width:2px
    style C fill:#fbb,stroke:#333,stroke-width:2px

Frequency Definitions: Episode mining employs different frequency definitions than sequence mining: 1. Window-based frequency: Count non-overlapping windows containing the episode 2. Minimal occurrence frequency: Count minimal occurrences (smallest windows containing the episode) 3. Non-overlapped frequency: Count non-overlapping occurrences Each definition has different properties and computational complexities. Minimal occurrence frequency, for instance, is more robust but computationally expensive [9]. The WINEPI and MINEPI algorithms were the first practical implementations of episode mining [8]. WINEPI uses a window-based approach with an Apriori-style level-wise search, while MINEPI focuses on minimal occurrences and can discover more refined patterns. Applications of Episode Mining: Episode mining has found applications in domains where continuous event streams need analysis: – Network Intrusion Detection: Detecting attack patterns in network logs [10] – Manufacturing Process Mining: Identifying fault sequences in production lines [11] – Medical Event Analysis: Discovering disease progression patterns from electronic health records [12] – System Log Analysis: Finding anomalous event patterns in distributed systems [13] A particularly elegant application is in alarm correlation in telecommunications networks. A single fault can trigger cascades of related alarms. Episode mining can discover the causal structure of alarm sequences, enabling root cause identification and alarm suppression [14].

8.4 Time-Series Pattern Discovery: From Discretization to Deep Learning

Time-series pattern discovery represents a specialized branch of sequential mining where values evolve continuously over time. Unlike discrete event sequences, time-series data requires different representational and algorithmic approaches.

8.4.1 Symbolic Aggregate Approximation (SAX)

A foundational challenge in time-series mining is dimensionality reduction while preserving pattern structure. Symbolic Aggregate Approximation (SAX), introduced by Lin et al. in 2003 [15], provides an elegant solution by transforming continuous time series into discrete symbolic sequences. The SAX Process: 1. Normalization: Transform time series to zero mean and unit variance 2. Piecewise Aggregate Approximation (PAA): Divide time series into segments and compute mean values 3. Discretization: Map PAA values to symbols using Gaussian breakpoints The beauty of SAX lies in its theoretical properties: – Lower Bounding: SAX distance lower-bounds Euclidean distance, enabling efficient indexing – Dimensionality Reduction: Massive compression while preserving shape information – Symbolic Mining: Enables application of sequence mining algorithms to time series SAX has become a standard preprocessing step in time-series mining, enabling pattern discovery in domains from genomics to finance [16, 17].

8.4.2 Shapelets: Primitive Pattern Discovery

While SAX discretizes entire time series, shapelets focus on discovering discriminative subsequences. Introduced by Ye and Keogh in 2009 [18], shapelets are time-series subsequences that are maximally representative of a class. A shapelet is a time-series subsequence $S$ such that the minimum distance from $S$ to instances of one class is significantly smaller than to instances of other classes. Shapelet discovery involves: 1. Enumerating candidate subsequences 2. Computing distance profiles for each candidate 3. Evaluating classification utility 4. Selecting the best shapelets The shapelet approach has proven particularly powerful in medical diagnosis, where specific waveform patterns in ECG or EEG signals indicate pathological conditions [19, 20].

8.4.3 Matrix Profile: Exact Pattern Discovery at Scale

A recent breakthrough in time-series pattern mining is the Matrix Profile, introduced by Yeh et al. in 2016 [21]. The Matrix Profile is a vector that stores, for every subsequence in a time series, the distance to its nearest neighbor. This simple data structure enables exact solutions to a remarkable array of pattern mining tasks: – Motif Discovery: Find repeated patterns – Discord Discovery: Find anomalous patterns – Semantic Segmentation: Find change points – Shapelet Discovery: Find discriminative patterns A key property of the Matrix Profile is that it can be computed in $O(n^2)$ time and updated incrementally in $O(n)$ time, making it practical for massive time series. The STOMP and STAMP algorithms provide efficient implementations [22, 23].

graph LR
    A[Time Series] --> B[Sliding Window]
    B --> C[Distance Matrix]
    C --> D[Matrix Profile]
    D --> E[Motif Discovery]
    D --> F[Discord Discovery]
    D --> G[Segmentation]
    D --> H[Shapelet Extraction]
    
    style D fill:#f9f,stroke:#333,stroke-width:3px
    style E fill:#bfb,stroke:#333,stroke-width:2px
    style F fill:#fbb,stroke:#333,stroke-width:2px

8.4.4 Deep Learning for Sequential Patterns

The deep learning revolution has profoundly impacted sequential pattern mining. Recurrent Neural Networks (RNNs), particularly Long Short-Term Memory (LSTM) networks [24], can automatically learn complex temporal dependencies without explicit pattern enumeration. Key Deep Learning Architectures: – LSTM Networks: Capture long-term dependencies through gating mechanisms [24] – Temporal Convolutional Networks (TCN): Apply dilated convolutions for long-range dependencies [25] – Transformer Models: Use attention mechanisms for sequence modeling [26] – Autoencoders: Learn compressed representations of sequences for anomaly detection [27] Deep learning approaches excel when: – Pattern complexity is high – Large training data is available – End-to-end learning is preferred over explicit pattern enumeration However, traditional sequential mining algorithms maintain advantages in interpretability and sample efficiency, particularly when patterns must be explicitly understood and communicated [28].

8.5 Periodic Pattern Mining: Discovering Cycles in Time

Many real-world phenomena exhibit periodic behavior—circadian rhythms, seasonal trends, business cycles. Periodic pattern mining addresses the discovery and characterization of such cyclic patterns.

8.5.1 Defining Periodicity

A pattern is periodic if it repeats at regular intervals. Formally, a sequence $s$ exhibits period $p$ if there exists a pattern $\alpha$ such that $\alpha$ appears in $s$ at positions $t, t+p, t+2p, \ldots$ However, perfect periodicity is rare in real data. Most periodic patterns are: – Approximate: Repetitions are similar but not identical – Partial: Only a subset of pattern elements repeat – Asynchronous: Period length varies slightly across cycles

8.5.2 Algorithms for Periodic Pattern Discovery

Autocorrelation-Based Methods: The autocorrelation function (ACF) measures correlation between a time series and its lagged version: $$ACF(k) = \frac{\sum_{t=1}^{n-k} (x_t – \bar{x})(x_{t+k} – \bar{x})}{\sum_{t=1}^{n} (x_t – \bar{x})^2}$$ Peaks in the ACF indicate potential periods. Spectral analysis via Fast Fourier Transform (FFT) provides a frequency-domain perspective, revealing dominant periodicities [29]. Pattern-Based Methods: – Partial Periodic Patterns: Yang et al.’s algorithm discovers patterns where only some elements repeat periodically [30] – Approximate Periodic Patterns: Tolerate variation in pattern elements and period length [31] – Calendar-Based Patterns: Discover patterns aligned with calendar structures (weekly, monthly, yearly) [32]

graph TD
    A[Periodic Pattern Types] --> B[Perfect Periodicity]
    A --> C[Approximate Periodicity]
    A --> D[Partial Periodicity]
    A --> E[Asynchronous Periodicity]
    
    B --> F[Rare in Practice]
    C --> G[Period Length Variance]
    C --> H[Pattern Element Variance]
    D --> I[Subset Repetition]
    E --> J[Drift in Period]
    
    K[Discovery Methods] --> L[Autocorrelation]
    K --> M[Spectral Analysis]
    K --> N[Pattern-Based Mining]
    K --> O[Calendar Alignment]
    
    style A fill:#f9f,stroke:#333,stroke-width:2px
    style K fill:#bfb,stroke:#333,stroke-width:2px

8.5.3 Applications of Periodic Mining

– Smart Grid Analysis: Discovering daily and seasonal electricity consumption patterns [33] – Environmental Monitoring: Identifying cyclic patterns in climate and pollution data [34] – Social Media Analysis: Detecting periodic trends in user behavior and content posting [35] – Manufacturing: Predictive maintenance through discovery of periodic equipment degradation patterns [36]

8.6 Contemporary Challenges and Advanced Topics

8.6.1 Streaming Sequential Pattern Mining

The shift from batch to streaming data has necessitated new algorithmic paradigms. Streaming sequential pattern mining must discover patterns incrementally as data arrives, under strict time and memory constraints. Key Challenges: – Memory Constraints: Cannot store entire history – Concept Drift: Pattern distributions change over time – Real-Time Requirements: Must update patterns faster than data arrival rate Algorithms like IncSpan [37] and PLWAP [38] maintain summary structures that enable incremental pattern updates. However, handling concept drift—the evolution of pattern distributions—remains challenging [39].

8.6.2 High-Utility Sequential Pattern Mining

Traditional sequential mining treats all patterns equally. High-Utility Sequential Pattern Mining (HUSPM) considers both frequency and utility (e.g., profit, weight, importance). The utility of a sequence is the sum of utilities of all its occurrences. HUSPM seeks sequences whose utility exceeds a threshold. This problem is more complex than traditional sequential mining because the utility measure is neither monotonic nor anti-monotonic [40]. Recent algorithms like HUS-Span [41] and HUSP-SP [42] employ tight upper bounds and pruning strategies to make HUSPM tractable.

8.6.3 Privacy-Preserving Sequential Mining

Sequential data often contains sensitive information about individuals’ behaviors and trajectories. Privacy-preserving sequential mining applies techniques from differential privacy and secure multi-party computation to enable pattern discovery while protecting individual privacy. Techniques: – Differential Privacy: Add calibrated noise to pattern counts to provide formal privacy guarantees [43] – Secure Multi-Party Computation: Enable collaborative mining across multiple parties without revealing individual data [44] – k-Anonymity for Sequences: Ensure each sequence is indistinguishable from at least k-1 others [45] The challenge lies in balancing privacy protection with pattern utility—too much privacy often destroys informative patterns.

8.7 Research Gaps and Future Directions

Despite decades of progress, sequential pattern mining faces several critical research gaps:

Gap S8.1: Causal Discovery from Sequential Patterns (Critical) ⭐

Current sequential mining discovers correlation (co-occurrence in time) but not causation. Distinguishing causal patterns from spurious temporal correlations remains an open challenge [46, 47]. The Problem: A sequence $(A \rightarrow B \rightarrow C)$ might reflect: – $A$ causes $B$ which causes $C$ (causal chain) – $A$ and $B$ are both effects of a hidden cause $X$ – Pure coincidence Research Directions: – Integration of causal inference frameworks (e.g., do-calculus [48]) with sequential mining – Counterfactual reasoning over discovered patterns – Experimental validation protocols for putative causal patterns Potential Impact: Transformative for domains requiring actionable insights—healthcare intervention design, economic policy, system debugging.

Gap S8.2: Interpretability of Deep Sequential Models (Critical) ⭐

Deep learning models for sequences (LSTMs, Transformers) achieve remarkable predictive performance but offer minimal interpretability. Unlike explicit pattern mining, their learned representations are opaque [49, 50]. The Problem: – Cannot explain why a prediction was made – Cannot extract explicit patterns for human understanding – Difficult to debug failures or biases Research Directions: – Attention visualization and interpretation methods – Hybrid symbolic-neural architectures – Post-hoc pattern extraction from trained models Potential Impact: Critical for high-stakes domains (medicine, finance, law) where decisions must be explainable.

Gap S8.3: Sequential Pattern Mining at Extreme Scale (High)

While algorithms have improved, truly massive sequence databases (billions of sequences, millions of distinct items) remain challenging. The combinatorial explosion of candidates and the I/O bottleneck persist [51, 52]. Research Directions: – Sampling-based approximate pattern mining with quality guarantees – Distributed and GPU-accelerated implementations – Sketching and streaming algorithms for billion-scale sequences

Gap S8.4: Multivariate Complex Event Patterns (High)

Most sequential mining assumes univariate discrete events. Real-world applications increasingly involve multivariate continuous event attributes (e.g., sensor networks, financial tick data) [53]. Research Directions: – Unified frameworks for discrete and continuous sequential patterns – Tensor-based representations for multivariate sequences – Deep generative models for complex event patterns

Gap S8.5: Temporal Pattern Transfer Learning (Medium)

Patterns discovered in one domain or dataset are rarely transferable to others. Meta-learning approaches that enable pattern transfer across domains remain underdeveloped [54, 55]. Research Directions: – Domain adaptation for sequential patterns – Few-shot learning for rare pattern discovery – Transfer learning from simulation to real-world sequences

8.8 Conclusion: Time as the Ultimate Dimension

Sequential pattern mining has evolved from a simple extension of association rules to a rich field encompassing diverse algorithms, representations, and applications. The journey from GSP’s level-wise candidate generation to deep learning’s end-to-end temporal modeling reflects both algorithmic innovation and changing data landscapes. Yet fundamental challenges persist. The tension between efficiency and expressiveness, between interpretability and performance, between privacy and utility—these tradeoffs define the field’s frontier. As we progress deeper into the age of ubiquitous temporal data—from IoT sensors to financial tick streams to social media—the importance of principled sequential pattern discovery will only grow. The next chapter turns from the temporal dimension to the spatial dimension, exploring clustering and segmentation—the art of discovering natural groupings in data.

---

References

[1] Agrawal, R., & Srikant, R. (1995). Mining sequential patterns. Proceedings of the 11th International Conference on Data Engineering, 3-14. DOI: 10.1109/ICDE.1995.380415 [2] Srikant, R., & Agrawal, R. (1996). Mining sequential patterns: Generalizations and performance improvements. Proceedings of the 5th International Conference on Extending Database Technology, 1057, 3-17. DOI: 10.1007/BFb0014140 [3] Han, J., Pei, J., Mortazavi-Asl, B., Chen, Q., Dayal, U., & Hsu, M. C. (2000). FreeSpan: frequent pattern-projected sequential pattern mining. Proceedings of the 6th ACM SIGKDD, 355-359. DOI: 10.1145/347090.347167 [4] Zaki, M. J. (2001). SPADE: An efficient algorithm for mining frequent sequences. Machine Learning, 42(1-2), 31-60. DOI: 10.1023/A:1007652502315 [5] Pei, J., Han, J., Mortazavi-Asl, B., Wang, J., Pinto, H., Chen, Q., … & Hsu, M. C. (2004). Mining sequential patterns by pattern-growth: The PrefixSpan approach. IEEE Transactions on Knowledge and Data Engineering, 16(11), 1424-1440. DOI: 10.1109/TKDE.2004.77 [6] Ayres, J., Flannick, J., Gehrke, J., & Yiu, T. (2002). Sequential pattern mining using a bitmap representation. Proceedings of the 8th ACM SIGKDD, 429-435. DOI: 10.1145/775047.775109 [7] Fournier-Viger, P., Lin, J. C. W., Gomariz, A., Gueniche, T., Soltani, A., Deng, Z., & Lam, H. T. (2016). The SPMF open-source data mining library version 2. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 36-40. DOI: 10.1007/978-3-319-46131-1_8 [8] Mannila, H., Toivonen, H., & Verkamo, A. I. (1997). Discovery of frequent episodes in event sequences. Data Mining and Knowledge Discovery, 1(3), 259-289. DOI: 10.1023/A:1009748302351 [9] Laxman, S., Sastry, P. S., & Unnikrishnan, K. P. (2007). A fast algorithm for finding frequent episodes in event streams. Proceedings of the 13th ACM SIGKDD, 410-419. DOI: 10.1145/1281192.1281238 [10] Qin, X., & Lee, W. (2004). Attack plan recognition and prediction using causal networks. Proceedings of the 20th Annual Computer Security Applications Conference, 370-379. DOI: 10.1109/CSAC.2004.4 [11] Tatti, N., & Cule, B. (2012). Mining closed strict episodes. Data Mining and Knowledge Discovery, 25(1), 34-66. DOI: 10.1007/s10618-011-0232-z [12] Batal, I., Valizadegan, H., Cooper, G. F., & Hauskrecht, M. (2013). A temporal pattern mining approach for classifying electronic health record data. ACM Transactions on Intelligent Systems and Technology, 4(4), 1-22. DOI: 10.1145/2508037.2508044 [13] Lou, J. G., Fu, Q., Yang, S., Xu, Y., & Li, J. (2010). Mining invariants from console logs for system problem detection. USENIX Annual Technical Conference, 1-14. [14] Hatonen, K., Klemettinen, M., Mannila, H., Ronkainen, P., & Toivonen, H. (1996). Knowledge discovery from telecommunication network alarm databases. Proceedings of the 12th International Conference on Data Engineering, 115-122. DOI: 10.1109/ICDE.1996.492116 [15] Lin, J., Keogh, E., Wei, L., & Lonardi, S. (2007). Experiencing SAX: a novel symbolic representation of time series. Data Mining and Knowledge Discovery, 15(107), 107-144. DOI: 10.1007/s10618-007-0064-z [16] Esmael, B., Arnaout, A., Fruhwirth, R. K., & Thonhauser, G. (2012). Multivariate time series classification by combining trend-based and value-based approximations. Computational Statistics, 27(3), 485-505. DOI: 10.1007/s00180-011-0273-9 [17] Alaee, S., Kamgar, K., Keogh, E., & Zimmerman, Z. (2020). Matrix profile XVII: Merlin: Parameter-free discovery of arbitrary length anomalies in massive time series archives. 2020 IEEE International Conference on Data Mining (ICDM), 972-977. DOI: 10.1109/ICDM50108.2020.00111 [18] Ye, L., & Keogh, E. (2009). Time series shapelets: a new primitive for data mining. Proceedings of the 15th ACM SIGKDD, 947-956. DOI: 10.1145/1557019.1557122 [19] Lines, J., & Bagnall, A. (2015). Time series classification with ensembles of elastic distance measures. Data Mining and Knowledge Discovery, 29(3), 565-592. DOI: 10.1007/s10618-014-0361-2 [20] Grabocka, J., Schilling, N., Wistuba, M., & Schmidt-Thieme, L. (2014). Learning time-series shapelets. Proceedings of the 14th ACM SIGKDD, 392-401. DOI: 10.1145/2623330.2623613 [21] Yeh, C. C. M., Zhu, Y., Ulanova, L., Begum, N., Ding, Y., Dau, H. A., … & Keogh, E. (2016). Matrix profile I: all pairs similarity joins for time series: a unifying view that includes motifs, discords and shapelets. 2016 IEEE 16th International Conference on Data Mining (ICDM), 1317-1322. DOI: 10.1109/ICDM.2016.0179 [22] Zhu, Y., Zimmerman, Z., Senobari, N. S., Yeh, C. C. M., Funning, G., Mueen, A., … & Keogh, E. (2016). Matrix profile II: Exploiting a novel algorithm and GPUs to break the one hundred million barrier for time series motifs and joins. 2016 IEEE 16th International Conference on Data Mining (ICDM), 739-748. DOI: 10.1109/ICDM.2016.0085 [23] Yeh, C. C. M., Van Herle, H., & Keogh, E. (2016). Matrix profile III: The matrix profile allows visualization of salient subsequences in massive time series. 2016 IEEE 16th International Conference on Data Mining (ICDM), 579-588. DOI: 10.1109/ICDM.2016.0069 [24] Hochreiter, S., & Schmidhuber, J. (1997). Long short-term memory. Neural Computation, 9(8), 1735-1780. DOI: 10.1162/neco.1997.9.8.1735 [25] Bai, S., Kolter, J. Z., & Koltun, V. (2018). An empirical evaluation of generic convolutional and recurrent networks for sequence modeling. arXiv preprint arXiv:1803.01271. DOI: 10.48550/arXiv.1803.01271 [26] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., … & Polosukhin, I. (2017). Attention is all you need. Advances in Neural Information Processing Systems, 30, 5998-6008. [27] Malhotra, P., Ramakrishnan, A., Anand, G., Vig, L., Agarwal, P., & Shroff, G. (2016). LSTM-based encoder-decoder for multi-sensor anomaly detection. arXiv preprint arXiv:1607.00148. DOI: 10.48550/arXiv.1607.00148 [28] Rudin, C. (2019). Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5), 206-215. DOI: 10.1038/s42256-019-0048-x [29] Vlachos, M., Yu, P., & Castelli, V. (2005). On periodicity detection and structural periodic similarity. Proceedings of the 2005 SIAM International Conference on Data Mining, 449-460. DOI: 10.1137/1.9781611972757.40 [30] Yang, J., Wang, W., & Yu, P. S. (2003). Mining asynchronous periodic patterns in time series data. IEEE Transactions on Knowledge and Data Engineering, 15(3), 613-628. DOI: 10.1109/TKDE.2003.1198394 [31] Cao, H., Cheung, D. W., & Mamoulis, N. (2004). Discovering partial periodic patterns in discrete data sequences. Advances in Knowledge Discovery and Data Mining, 653-658. DOI: 10.1007/978-3-540-24775-3_77 [32] Mahanta, A. K., Mazarbhuiya, F. A., & Baruah, H. K. (2008). Finding calendar-based periodic patterns. Pattern Recognition Letters, 29(9), 1274-1284. DOI: 10.1016/j.patrec.2008.01.022 [33] Fanaee-T, H., & Gama, J. (2016). Tensor-based anomaly detection: An interdisciplinary survey. Knowledge-Based Systems, 98, 130-147. DOI: 10.1016/j.knosys.2016.01.027 [34] Chandra, R., Goyal, P., & Gupta, A. (2021). Evaluation of deep learning models for multi-step ahead time series prediction. IEEE Access, 9, 83105-83123. DOI: 10.1109/ACCESS.2021.3085085 [35] Yang, J., & Leskovec, J. (2011). Patterns of temporal variation in online media. Proceedings of the 4th ACM International Conference on Web Search and Data Mining, 177-186. DOI: 10.1145/1935826.1935863 [36] Susto, G. A., Schirru, A., Pampuri, S., McLoone, S., & Beghi, A. (2015). Machine learning for predictive maintenance: A multiple classifier approach. IEEE Transactions on Industrial Informatics, 11(3), 812-820. DOI: 10.1109/TII.2014.2349359 [37] Cheng, H., Yan, X., & Han, J. (2004). IncSpan: incremental mining of sequential patterns in large database. Proceedings of the 10th ACM SIGKDD, 527-532. DOI: 10.1145/1014052.1014114 [38] Ezeife, C. I., & Lu, Y. (2005). Mining web log sequential patterns with position coded pre-order linked WAP-tree. Data Mining and Knowledge Discovery, 10(1), 5-38. DOI: 10.1007/s10618-005-0248-3 [39] Gama, J., Žliobaitė, I., Bifet, A., Pechenizkiy, M., & Bouchachia, A. (2014). A survey on concept drift adaptation. ACM Computing Surveys, 46(4), 1-37. DOI: 10.1145/2523813 [40] Gan, W., Lin, J. C. W., Fournier-Viger, P., Chao, H. C., & Philip, S. Y. (2019). A survey of parallel sequential pattern mining. ACM Transactions on Knowledge Discovery from Data, 13(3), 1-34. DOI: 10.1145/3314107 [41] Alkan, O. K., & Karagoz, P. (2015). CRoM and HuspExt: Improving efficiency of high utility sequential pattern extraction. IEEE Transactions on Knowledge and Data Engineering, 27(10), 2645-2657. DOI: 10.1109/TKDE.2015.2420557 [42] Yin, J., Zheng, Z., & Cao, L. (2012). USpan: an efficient algorithm for mining high utility sequential patterns. Proceedings of the 18th ACM SIGKDD, 660-668. DOI: 10.1145/2339530.2339636 [43] Chen, R., Acs, G., & Castelluccia, C. (2012). Differentially private sequential data publication via variable-length n-grams. Proceedings of the 2012 ACM Conference on Computer and Communications Security, 638-649. DOI: 10.1145/2382196.2382263 [44] Kantarcioglu, M., & Clifton, C. (2004). Privacy-preserving distributed mining of association rules on horizontally partitioned data. IEEE Transactions on Knowledge and Data Engineering, 16(9), 1026-1037. DOI: 10.1109/TKDE.2004.45 [45] Terrovitis, M., Mamoulis, N., & Kalnis, P. (2008). Privacy-preserving anonymization of set-valued data. Proceedings of the VLDB Endowment, 1(1), 115-125. DOI: 10.14778/1453856.1453874 [46] Pearl, J. (2009). Causality: Models, reasoning, and inference (2nd ed.). Cambridge University Press. DOI: 10.1017/CBO9780511803161 [47] Spirtes, P., Glymour, C. N., & Scheines, R. (2000). Causation, prediction, and search (2nd ed.). MIT Press. [48] Pearl, J. (2012). The do-calculus revisited. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, 3-11. DOI: 10.48550/arXiv.1210.4852 [49] Lipton, Z. C. (2018). The mythos of model interpretability. Communications of the ACM, 61(10), 36-43. DOI: 10.1145/3233231 [50] Molnar, C. (2020). Interpretable machine learning: A guide for making black box models explainable. Lulu.com. [51] Dean, J., & Ghemawat, S. (2008). MapReduce: simplified data processing on large clusters. Communications of the ACM, 51(1), 107-113. DOI: 10.1145/1327452.1327492 [52] Zaharia, M., Chowdhury, M., Franklin, M. J., Shenker, S., & Stoica, I. (2010). Spark: Cluster computing with working sets. HotCloud, 10(10-10), 95. [53] Ceci, M., Appice, A., Loglisci, C., Caruso, C., Fumarola, F., & Malerba, D. (2015). Novelty detection from multivariate time series data streams: An efficient approach based on support vector machines. ACM Transactions on Intelligent Systems and Technology, 6(4), 1-26. DOI: 10.1145/2700469 [54] Pan, S. J., & Yang, Q. (2010). A survey on transfer learning. IEEE Transactions on Knowledge and Data Engineering, 22(10), 1345-1359. DOI: 10.1109/TKDE.2009.191 [55] Hospedales, T., Antoniou, A., Micaelli, P., & Storkey, A. (2021). Meta-learning in neural networks: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9), 5149-5169. DOI: 10.1109/TPAMI.2021.3079209

---

Chapter Progress: 8/20 (40% complete)