- Rating
- 3(+1)
- Confidence
- 1(−2)
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies frequent time-series pattern mining under Cartesian-tree (CT) equivalence, which merges some order-preserving patterns while retaining their hierarchical minimum structure. Using an existing Cartesian suffix tree, CT-Miner obtains occurrence counts from subtree leaf counts and represents patterns through compact node references. The paper claims occurrence collection across all lengths after index construction, and introduces Catalan-based integer labels for CT structures. Experiments construct top- occurrence-count features and evaluate k-means clustering on five main UCR datasets, with Wafer analyzed separately. Comparisons include order-preserving miners, PCA, and an independent-window CT-Hash implementation. The reported results show competitive clustering quality and reduced feature-construction time, together with substantial memory costs in some longer-pattern settings.
Critical strengths
- CT-Miner finds recurring patterns faster by reusing work across overlapping subsequences. In one comparison on Car, feature-construction time falls from about 26 seconds to 4 seconds.
- The method retains useful information with a small set of features. Using 30 patterns to describe each series, it achieves clustering quality comparable to existing pattern-mining methods.
- The features have a clear meaning: each records how often a particular local structure occurs. This makes it possible to inspect which structures differ between groups of time series.
Critical weaknesses
- The endmarker check in line 12 of Algorithm 1 does not match the stated indexing conventions. The condition used in the experiments needs clarification.
- CT-Hash rebuilds every window’s representation independently. Without an incremental counting baseline, the benefit of the CST over simpler reuse strategies remains unresolved.
- The OP-baseline timing comparison does not isolate the contribution of CT’s top- early stopping to the reported speedup.
- On PigCVP at , CT uses versus for CT-Hash. The paper acknowledges this cost but does not separate index, retained-pattern, and feature-construction memory.
Questions for authors
- Please clarify the correct endmarker check in Algorithm 1 and the condition used in the experiments.
- How does CT compare with exact incremental PD counting that reuses shorter-pattern IDs?
- How much of the speedup remains when CT’s top- early stopping is disabled?
- How much peak memory comes from the index, retained patterns, and feature construction?
4 comments
Thank you for addressing some of my concerns. The ablation measures the effect of early stopping on CT-Miner, but it does not show how much of the reported 6.6x speedup over OPF remains when early stopping is disabled. I’ve updated my rating from 2 to 3.
We thank the reviewer for reconsidering our work. We would like to address the reviewer's remaining concern regarding the impact of early stopping on the reported speedup over OPF.
We agree that early stopping contributes substantially to the practical efficiency of CT-Miner. Importantly, our early stopping criterion is exact rather than heuristic. It skips unnecessary computation without changing the selected top-K patterns or their occurrence counts. We therefore use early stopping in our primary evaluation, since it does not change the mining results as confirmed by our ablation. Thus, a comparison without early stopping is less representative of CT-Miner's practical performance.
Nevertheless, to quantify its impact, we compare the existing results in Tables 6 and 16. Across the five main datasets at K=30, OPF requires 8.55 seconds on average, while CT-Miner with early stopping disabled requires 15.60 seconds. Thus, without early stopping, CT-Miner is approximately 1.83x slower than OPF on average.
Time Comparison Between CT-Miner and OPF
| Dataset | OPF (s) | CT-ON (s) | CT-OFF (s) | OPF/CT-ON | OPF/CT-OFF |
|---|---|---|---|---|---|
| Beef | 2.05 | 0.38 | 1.61 | 5.42x | 1.27x |
| Car | 15.05 | 0.54 | 4.23 | 27.72x | 3.56x |
| ElectricDevices | 4.32 | 2.62 | 8.00 | 1.65x | 0.54x |
| MoteStrain | 3.54 | 0.99 | 1.22 | 3.56x | 2.90x |
| PigCVP | 17.78 | 1.94 | 62.95 | 9.16x | 0.28x |
| Mean | 8.55 | 1.30 | 15.60 | 6.60x | 0.55x |
Thank you for your detailed response. My score is already positive.
We thank the reviewer for identifying these issues. We corrected the endmarker convention and added incremental baseline, early stopping, and memory analyses.
W1. Endmarker convention
The reviewer is correct. Under our 1-based indexing convention and half-open interval notation, the endmarker condition in Algorithm 1 should be l+idx(n)=∣T∣+3, rather than ∣T∣. We have corrected this indexing error and clarified the treatment of endmarkers in the definitions of the parent-distance representation and the associated lemmas and proofs. The experimental implementation already excludes endmarker-containing windows through valid-window bounds, so these corrections do not affect the reported results.
W2. Incremental counting baseline
We added CT-Hash-Incremental, which reuses shorter-pattern parent-distance IDs instead of reconstructing every window. We compared it with CT-Miner and CT-Hash at K=100 with identical support-bound early stopping. For each of 18 dataset-length conditions, five runs completed with matching ordered dictionaries, supports, features, and stage signatures.
CT-Miner is fastest in 15 of the 18 conditions. At L=256, it is 1.45x, 1.99x, and 1.59x faster than incremental counting on Beef, Car, and PigCVP, respectively.
W3. Effect of early stopping
Our early stopping criterion is an exact pruning strategy rather than heuristic early termination. It stops only when no unvisited pattern can enter the current top-K dictionary, thereby preserving the selected patterns and their frequencies. We further verified that early stopping produces identical results by comparing the selected pattern dictionaries and feature matrices with early stopping enabled and disabled. All 30 paired comparisons across six datasets and five repetitions produced identical results. The table reports mean wall-clock times and the maximum pattern lengths explored with early stopping enabled and disabled, allowing pattern lengths up to the full sequence length.
W4. Memory breakdown
We further analyzed the memory usage of CT-Miner by measuring the peak Java process RSS and the sizes of its major data structures. We report the results at L=256 with early stopping disabled and K=30, averaged over five runs. All values are in MiB. Tracked arrays are calculated array sizes at the sampled RSS peak. Untracked heap and non-heap residual are the remaining memory not attributed to these arrays.
On PigCVP, the prefix-ID registry arrays occupy 3,072.00 MiB, corresponding to approximately 45.0% of the peak RSS, whereas the compact index arrays occupy only 36.88 MiB. The final feature matrix requires only 0.07 MiB. The peak occurs during the feature-construction phase in all five runs.
We additionally performed garbage-collection diagnostics on all three datasets. Explicit garbage collection reclaimed 325.98 MiB on Beef, 414.72 MiB on Car, and 3,157.06 MiB on PigCVP. These results indicate that substantial heap usage comes from temporary or obsolete allocations, potentially including arrays replaced during prefix-ID registry expansion.
Overall, the high peak memory usage reflects both the retained prefix-ID registry and substantial allocations awaiting garbage collection, rather than the compact index or final feature representation.