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

Hyundong Jin; Hyunki Hong; Yo-Sub Han

cs.DSOct 4, 2026

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

Authors: Hyundong Jin, Hyunki Hong, Yo-Sub Han

Organizations: Department of Computer Science Yonsei University, Seoul, Republic of Korea

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 .

Figures & tables

Figure 1: Overview of Algorithm 1 . It constructs the Cartesian suffix tree of a given string and iterates through the nodes to compute the occurrences.

Method	NMI (%) $\uparrow$	$h$ (%) $\uparrow$	ARI (%) $\uparrow$	Time (s) $\downarrow$	RSS (MiB) $\downarrow$
Raw	33.93	32.25	18.87	0.00	181.5
PCA	34.30	32.73	19.15	0.07	184.6
OPP	37.30	35.80	19.46	15.21	652.5
EFO	37.30	35.80	19.46	12.18	640.6
OPF	35.83	34.25	17.50	8.55	640.7
OPR	37.30	35.80	19.46	12.70	645.7

Table 1: Clustering quality and resource usage at

K=30

, averaged equally over five datasets excluding Wafer. Time includes mining and feature extraction. Bold and underline indicate the best and second-best values, respectively, excluding Raw.

Figure 2: Clustering quality versus feature budget, averaged over the five main datasets. Only the evaluated budgets are shown as ticks.

CT pattern	Constituent OP patterns	CT rank	EFO rank(s)
$(0,0,1)$	$(2,1,3)$ , $(3,1,2)$	8	18, 19
$(0,1,0,1)$	$(2,3,1,4)$ , $(2,4,1,3)$ , $(3,4,1,2)$	25	31, $>50$ , $>50$
$(0,0,1,0)$	$(3,2,4,1)$ , $(4,2,3,1)$	29	30, $>50$

Table 2: Examples of OP patterns consolidated by CT equivalence on Wafer. Ranks are based on frequency-based feature selection.

>K

indicates that the OP pattern is outside the top-

K

dictionary.

Figure 3: Occurrence counts of representative CT features on Wafer, grouped by the recorded class. Boxes show quartiles and medians, and whiskers span the observed range. The analysis is post-hoc and uses labels only for interpretation; labels are not used for feature selection or clustering.

Dataset	Algorithm	Measure	$L=8$	$L=16$	$L=32$	$L=64$	$L=128$	$L=256$
Car ( $n=577$ )	CT	Time. (s)	0.357	0.508	0.818	1.370	2.333	3.656
	CT	Mem. (MiB)	127.2	152.0	251.4	490.3	692.5	901.4
	CT-Hash	Time. (s)	0.467	0.830	1.700	3.929	10.162	25.691
	CT-Hash	Mem. (MiB)	225.0	651.3	652.7	676.7	708.8	723.4
Beef ( $n=470$ )	CT	Time. (s)	0.283	0.353	0.563	0.974	1.456	1.819
	CT	Mem. (MiB)	127.2	127.2	166.3	322.4	578.0	681.7

Table 3: Comparison with the naive CT-Hash implementation over increasing maximum pattern length

L

. We report mean feature-extraction time over five runs and peak process RSS.

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Cartesian tree for

T=(3,2,7,1,6,4,5,8)

Figure 5: Cartesian suffix tree for

T=(3,2,7,1,6,4,5,8)

Figure 6: An illustration of Theorem 7

Dataset	Sequences	Length	Classes
Car	120	577	4
Beef	60	470	5
ElectricDevices	16,637	96	7
MoteStrain	1,272	84	2
PigCVP	312	2,000	52
Wafer	7,164	152	2

Appendix

Table 4: Dataset characteristics after combining the official training and test splits.

Dataset	Method	$K=10$			$K=20$			$K=30$			$K=40$			$K=50$
Dataset	Method	NMI	$h$	ARI	NMI	$h$	ARI	NMI	$h$	ARI	NMI	$h$	ARI	NMI	$h$	ARI
Car	Raw	22.8	21.2	12.6	22.8	21.2	12.6	22.8	21.2	12.6	22.8	21.2	12.6	22.8	21.2	12.6
	PCA	23.2	21.7	13.1	22.8	21.2	12.6	22.8	21.2	12.6	22.5	20.9	12.4	22.8	21.2	12.6
	OPP	25.1	24.8	17.1	21.5	21.2	16.0	20.8	20.3	15.5	18.2	18.2	15.0	19.5	19.4	16.6
	EFO	25.1	24.8	17.1	21.5	21.2	16.0	20.8	20.3	15.5	18.2	18.2	15.0	19.5	19.4	16.6
	OPF	25.2	24.9	15.5	15.0	14.6	8.5	15.0	14.2	8.3	16.4	16.3	14.0	18.7	18.6	16.2

Appendix

Table 5: Clustering quality across feature budgets on the five main datasets. Values are mean NMI, homogeneity, and ARI over five clustering seeds. Bold and underline denote the best and second-best values excluding Raw.

Dataset	Method	$K=10$		$K=20$		$K=30$		$K=40$		$K=50$
Dataset	Method	Time.	Mem.	Time.	Mem.	Time.	Mem.	Time.	Mem.	Time.	Mem.
Car	Raw	0.000	158.4	0.000	158.4	0.000	158.4	0.000	158.4	0.000	158.4
	PCA	0.199	163.7	0.201	159.4	0.205	163.5	0.208	161.2	0.203	159.7
	OPP	20.57	650.0	20.82	653.0	20.78	650.7	20.36	648.0	20.60	651.0
	EFO	17.07	636.7	17.01	639.2	17.09	636.0	17.27	636.5	17.22	635.1
	OPF	15.57	633.4	15.69	633.5	15.05	632.7	15.72	632.1	15.67	634.6

Appendix

Table 6: Feature-construction time and peak memory across feature budgets on the five main datasets. Time is averaged over five runs and memory is measured as peak process RSS. Bold and underline denote the lowest and second-lowest values excluding Raw.

Figure 7: Mean feature-construction time and peak process RSS as the retained input prefix increases at

K=30

. Results are averaged over the five main datasets.

Dataset	Method	20%			40%			60%			80%			100%
Dataset	Method	NMI	$h$	ARI	NMI	$h$	ARI	NMI	$h$	ARI	NMI	$h$	ARI	NMI	$h$	ARI
Car	Raw	17.7	16.3	8.4	20.8	19.6	11.1	26.5	24.5	15.1	21.6	19.9	11.1	22.8	21.2	12.6
	PCA	17.7	16.3	8.4	20.8	19.6	11.1	26.2	24.2	14.8	21.6	19.9	11.1	22.8	21.2	12.6
	OPP	17.8	16.9	9.1	14.2	14.1	11.7	13.3	13.1	6.8	14.4	14.3	9.8	20.8	20.3	15.5
	EFO	17.8	16.9	9.1	14.2	14.1	11.7	13.3	13.1	6.8	14.4	14.3	9.8	20.8	20.3	15.5
	OPF	16.4	15.8	8.7	8.8	8.7	3.5	26.0	25.6	21.5	11.9	11.8	7.6	15.0	14.2	8.3

Appendix

Table 7: Clustering quality across input prefixes at

K=30

on the five main datasets. Values are mean NMI, homogeneity, and ARI over five clustering seeds. Bold and underline denote the best and second-best values excluding Raw.

Dataset	Method	20%		40%		60%		80%		100%
Dataset	Method	Time.	Mem.	Time.	Mem.	Time.	Mem.	Time.	Mem.	Time.	Mem.
Car	Raw	0.000	157.1	0.000	157.0	0.000	157.3	0.000	158.3	0.000	158.9
	PCA	0.004	157.9	0.004	162.9	0.005	163.7	0.005	164.5	0.006	160.4
	OPP	1.99	619.9	5.25	637.7	8.70	647.6	15.58	648.3	20.86	652.7
	EFO	1.73	618.1	4.67	622.1	7.40	627.6	13.60	626.9	17.36	632.7
	OPF	1.63	620.6	4.31	621.2	7.12	630.5	12.53	640.2	15.71	634.8

Appendix

Table 8: Feature-construction time and peak memory across input prefixes at

K=30

on the five main datasets. Bold and underline denote the lowest and second-lowest values excluding Raw.

Method	$K=10$			$K=20$			$K=30$			$K=40$			$K=50$
Method	NMI	$h$	ARI	NMI	$h$	ARI	NMI	$h$	ARI	NMI	$h$	ARI	NMI	$h$	ARI
Raw	0.0	0.0	0.1	0.0	0.0	0.1	0.0	0.0	0.1	0.0	0.0	0.1	0.0	0.0	0.1
PCA	0.0	0.0	0.1	0.0	0.0	0.1	0.0	0.0	0.1	0.0	0.0	0.1	0.0	0.0	0.1
OPP	0.6	0.9	0.8	0.9	1.3	-2.0	0.2	0.2	-2.4	0.1	0.1	-1.7	100.0	100.0	100.0
EFO	0.6	0.9	0.8	0.9	1.3	-2.0	0.2	0.2	-2.4	0.1	0.1	-1.7	100.0	100.0	100.0
OPF	0.9	1.2	1.8	0.9	1.2	-2.3	0.2	0.3	-2.7	0.1	0.1	-1.8	100.0	100.0	100.0

Appendix

Table 9: Clustering quality across feature budgets on Wafer. Values are mean NMI, homogeneity, and ARI over five clustering seeds. Bold and underline denote the best and second-best values excluding Raw.

Method	$K=10$		$K=20$		$K=30$		$K=40$		$K=50$
Method	Time.	Mem.	Time.	Mem.	Time.	Mem.	Time.	Mem.	Time.	Mem.
Raw	0.000	214.8	0.000	214.8	0.000	214.8	0.000	214.8	0.000	214.8
PCA	0.045	215.3	0.045	215.2	0.049	215.6	0.061	215.5	0.070	215.7
OPP	31.06	669.0	31.12	661.1	31.33	672.3	31.15	661.8	31.09	678.3
EFO	29.67	650.4	29.89	654.9	29.82	648.8	30.43	645.9	30.06	645.9
OPF	28.18	660.5	28.67	662.1	28.94	657.2	29.06	660.4	28.66	660.8

Appendix

Table 10: Feature-construction time and peak memory across feature budgets on Wafer. Time is averaged over five runs and memory is measured as peak process RSS. Bold and underline denote the lowest and second-lowest values excluding Raw.

Method	20%			40%			60%			80%			100%
Method	NMI	$h$	ARI	NMI	$h$	ARI	NMI	$h$	ARI	NMI	$h$	ARI	NMI	$h$	ARI
Raw	0.6	0.9	2.5	2.0	2.8	4.5	0.0	0.0	0.1	0.0	0.1	0.6	0.0	0.0	0.1
PCA	0.6	0.9	2.5	2.0	2.8	4.5	0.0	0.0	0.1	0.0	0.1	0.6	0.0	0.0	0.1
OPP	97.8	97.4	99.3	3.8	5.2	-4.8	1.8	1.8	-7.0	4.5	6.0	-6.0	0.2	0.2	-2.4
EFO	97.8	97.4	99.3	3.8	5.2	-4.8	1.8	1.8	-7.0	4.5	6.0	-6.0	0.2	0.2	-2.4
OPF	94.1	93.0	97.6	5.1	7.0	-4.7	1.9	1.9	-7.1	2.8	3.8	-5.2	0.2	0.3	-2.7

Appendix

Table 11: Clustering quality across input prefixes on Wafer at

K=30

. Values are mean NMI, homogeneity, and ARI over five clustering seeds. Bold and underline denote the best and second-best values excluding Raw.

Method	20%		40%		60%		80%		100%
Method	Time.	Mem.	Time.	Mem.	Time.	Mem.	Time.	Mem.	Time.	Mem.
Raw	0.000	174.7	0.000	185.7	0.000	194.3	0.000	204.0	0.000	215.4
PCA	0.018	174.0	0.029	185.6	0.037	194.2	0.044	204.7	0.053	215.0
OPP	1.65	627.7	3.68	661.5	8.27	650.8	10.64	651.3	30.74	671.8
EFO	1.40	631.6	2.94	632.8	7.26	635.9	10.45	642.9	30.14	651.7
OPF	1.49	559.7	2.86	648.6	6.86	645.7	9.58	650.4	28.41	658.5

Appendix

Table 12: Feature-construction time and peak memory across input prefixes on Wafer at

K=30

. Time is averaged over five runs and memory is measured as peak process RSS. Bold and underline denote the lowest and second-lowest values excluding Raw.

Rank	CT code	Total support	Mean $-1$	Range $-1$	Mean $+1$	Range $+1$
8	$(0,0,1)$	57,857	50.71	[28, 64]	3.00	[0, 17]
25	$(0,1,0,1)$	16,507	20.00	[7, 32]	0.20	[0, 4]
29	$(0,0,1,0)$	15,482	18.05	[8, 30]	0.27	[0, 6]
30	$(0,0,1,2)$	15,227	18.12	[7, 29]	0.22	[0, 6]

Appendix

Table 13: Detailed statistics for representative Wafer CT features from the saved

K=30

dictionary. Class means and ranges use unstandardized occurrence counts.

Dataset	Algorithm	Measure	$L=8$	$L=16$	$L=32$	$L=64$	$L=128$	$L=256$
Car ( $n=577$ )	CT	Time. (s)	0.357	0.508	0.818	1.370	2.333	3.656
	CT	Mem. (MiB)	127.2	152.0	251.4	490.3	692.5	901.4
	CT-Hash	Time. (s)	0.467	0.830	1.700	3.929	10.162	25.691
	CT-Hash	Mem. (MiB)	225.0	651.3	652.7	676.7	708.8	723.4
Beef ( $n=470$ )	CT	Time. (s)	0.283	0.353	0.563	0.974	1.456	1.819
	CT	Mem. (MiB)	127.2	127.2	166.3	322.4	578.0	681.7

Appendix

Table 14: Comparison with the naive CT-Hash implementation as the maximum pattern length

L

increases. We report five-run mean feature-construction time and single-run peak process RSS.

Dataset	Method	minsup = 5					minsup = 10					minsup = 25
Dataset	Method	Dim	NMI	$h$	ARI	Time.	Dim	NMI	$h$	ARI	Time.	Dim	NMI	$h$	ARI	Time.
Car	Raw	577	22.8	21.2	12.6	0.00	577	22.8	21.2	12.6	0.00	577	22.8	21.2	12.6	0.00
	PCA	30	22.8	21.2	12.6	0.01	30	22.8	21.2	12.6	0.01	30	22.8	21.2	12.6	0.01
	OPP	596	27.1	25.6	20.1	15.99	293	28.4	26.3	22.7	15.14	219	25.5	23.7	19.9	11.59
	EFO	596	27.1	25.6	20.1	14.78	293	28.4	26.3	22.7	14.03	219	25.5	23.7	19.9	10.88
	OPF	334	23.5	21.4	17.5	14.74	253	23.9	21.8	18.2	13.46	208	23.0	21.9	17.6	9.82

Appendix

Table 15: Threshold-based feature selection on the five main datasets. All qualifying features are retained at each minimum support. Dim denotes the resulting feature count and Time denotes mean feature-construction time. OPR and SOPP use the best mean-NMI setting from their parameter grids. Bold and underline denote the best and second-best quality among pattern-mining methods.

Explore similar work

Discovering Frequent Closed Embedded Sub-DAGs in Spatio-Temporal Event Data
Jul 7, 2026Piotr S. MaciągData Mining Spatiotemporal
Institute of Computer Science, Warsaw University of Technology, Nowowiejska 15/19, 00-661, Warsaw
MINT: Tensor Decomposition on Stacked Recurrence Matrices for Time Series Data Mining
Aug 4, 2026Kaamil Kaka, Audrey Der, Evangelos E. Papalexakis +2Tensor Decomposition Time Series
University of California, Riverside, Department of Computer Science · Neuralix AI
CLUES-WEASEL: No additional clues required to choose your time series clustering algorithm
Sep 7, 2026Johann FaouziTime-Series Classification Clustering
Univ Rennes, Ensai, CNRS, CREST - UMR 9194, F-35000 Rennes, France.

Jul 7, 2026, cs.DBJ/K move · Enter open · S save

Discovering Frequent Closed Embedded Sub-DAGs in Spatio-Temporal Event Data

Piotr S. Maciąg

Institute of Computer Science, Warsaw University of Technology, Nowowiejska 15/19, 00-661, Warsaw

Data Mining Spatiotemporal Subgraphs Closure

Open paper AskPDF arXiv

We propose a novel approach to mine patterns in spatio-temporal event data based on discovering frequent closed embedded sub-Directed Acyclic Graphs (DAGs). In our method, event instances are represented as nodes labelled by event types, while edges capture spatio-temporal following relationships. We formally define the considered class of patterns and provide the rationale for focusing on closed sub-DAGs as compact and non-redundant representations of recurring interaction patterns. We implement the DigDag algorithm for mining such patterns and experimentally compare its efficiency with two related approaches: propagation pattern mining using the SLEUTH algorithm and Cascading Spatio-Temporal Pattern mining using the CSTPM algorithm. The experimental results demonstrate that our approach is substantially more efficient while operating under comparable parameter settings. Finally, we present a qualitative analysis of selected discovered patterns.

Abstract

Explore similar work

Discovering Frequent Closed Embedded Sub-DAGs in Spatio-Temporal Event Data

MINT: Tensor Decomposition on Stacked Recurrence Matrices for Time Series Data Mining

CLUES-WEASEL: No additional clues required to choose your time series clustering algorithm