CT-Miner: Fast and Coarse-Grained Time-Series Pattern Mining via Cartesian Trees

arXiv:2610.05330v1 Announce Type: cross Abstract: Time series often contain recurring structural patterns, and efficiently mining such patterns into compact representations is essential for scalable analysis of long sequences. Cartesian tree (CT) equivalence provides a well-established structural abstraction that preserves hierarchical order structure while discarding exact values and fine-grained ordinal variations. By grouping multiple ordinal patterns into a shared structural form, CT equivalence offers a principled way to compress recurring temporal structure. However, mining frequent CT-equivalent patterns at scale remains computationally expensive. A naive pairwise approach repeatedly constructs and counts CT representations over subsequences, requiring O(n^4) time for a sequence of length n, which severely limits its applicability to long sequences. We propose a new Cartesian pattern mining algorithm based on a Cartesian suffix tree that compactly organizes CT-equivalent subsequences and reuses shared structural information. Our method reduces exhaustive CT-pattern occurrence collection from O(n^4) to O(n^2) time, and we formally prove the correctness and complexity bounds. We further show that this computational gain translates into effective compact representations. Across diverse time-series datasets, a small set of mined CT patterns preserves meaningful clustering structure, and comparisons with finer-grained order-preserving representations show that CT equivalence reduces redundant ordinal distinctions under limited feature budgets. Our implementation is available at https://github.com/hyundong98/CT-Miner .

Related

• Anlu: Enabling In-Context Time Series Anomaly Detection in Foundation Models via Counterfactual Supervision
• Exploring Urban Land Use Patterns by Pattern Mining and Unsupervised Learning
• Longitudinal Random Forests for Sparse and Irregular Response Trajectories
• Generative Modeling of Approximately Periodic Time Series by a Posterior-Weighted Gaussian Process

Source: arXiv cs.LG | 2026-10-06