arXiv preprint ·
CT-Miner: Fast and Coarse-Grained Time-Series Pattern Mining via Cartesian Trees
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 .
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
W[1]-Hardness of Upper Clique Transversal
Fast mixing of the SYK model at high temperatures
Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation
Near-Exact Computation of Independent Chip Model Placement Probabilities for Thousands of Players
Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.