시계열에서는 반복적으로 나타나는 subsequence를 pattern으로 추출하여 representation으로 활용할 수 있습니다. 기존의 Order-Preserving(OP) pattern은 실제 값 대신 subsequence 내부의 상대적 순서를 이용합니다. 하지만 OP pattern은 모든 원소 사이의 상대 순서를 보존하기 때문에, 전체적인 구조가 비슷하더라도 일부 ordinal relation이 다르면 서로 다른 pattern으로 분리됩니다. 그 결과 유사한 temporal structure가 여러 feature로 fragment될 수 있습니다. CT-Miner는 이를 해결하기 위해 더 coarse-grained한 Cartesian Tree(CT) equivalence를 사용합니다.
Cartesian tree는 sequence의 최소값을 root로 두고, 그 왼쪽과 오른쪽 subsequence에 대해 같은 과정을 재귀적으로 반복하여 만든 binary tree입니다. 두 sequence의 실제 값이나 complete relative order가 달라도 Cartesian tree의 구조가 동일하면 CT-equivalent하다고 봅니다. 즉, 여러 OP Pattern들이 CT-equivalence 아래에서는 하나의 structural pattern으로 묶일 수 있으며 더 coarse한 규칙을 mining할 수 있습니다. CT-Miner는 Cartesian tree 자체 대신 Parent-Distance(PD) representation을 사용합니다. 두 sequence의 PD representation이 같다는 것은 두 sequence의 Cartesian tree가 같다는 것과 동치이므로, CT matching을 문자열 matching과 유사하게 처리할 수 있습니다.
목표는 주어진 sequence에서 등장하는 모든 CT pattern의 occurrence를 계산하는 것입니다. 가장 단순한 방법은 모든 substring을 열거하고, 각각의 Cartesian tree를 만든 뒤 서로 비교하는 것입니다. 그러나 가능한 모든 pattern length에 대해 이를 반복하면 전체 시간 복잡도가 O(n⁴)까지 증가합니다. Hash를 사용하면 practical하게 개선할 수 있지만, 여전히 overlapping window마다 Cartesian-tree representation을 독립적으로 생성해야 하므로 많은 중복 계산이 발생합니다.
CT-Miner는 **Cartesian Suffix Tree(CST)**를 이용해 overlapping subsequence가 공유하는 Cartesian structure를 재사용합니다. 각 suffix의 PD representation을 compacted trie 형태로 저장하면, 동일한 CT prefix를 공유하는 suffix들이 같은 subtree 아래 모이게 됩니다. 따라서 어떤 node가 나타내는 CT pattern의 occurrence 수는 그 node 아래의 leaf 개수만으로 바로 얻을 수 있습니다. 기존 방식처럼 각 pattern을 다시 전체 sequence에서 검색할 필요가 없습니다. Cartesian suffix tree는 O(n log n) 시간에 구축할 수 있으며, 모든 CT pattern의 occurrence를 수집하는 전체 시간 복잡도는 **O(n²)**입니다. 즉, O(n⁴) → O(n²)으로 exhaustive CT pattern mining의 복잡도를 줄입니다.
CT equivalence는 여러 OP pattern의 occurrence를 하나의 feature로 합칩니다. 예를 들어 Wafer 데이터에서 CT pattern (0, 0, 1)은 서로 다른 OP pattern (2, 1, 3)과 (3, 1, 2)를 하나로 통합합니다. OP representation에서는 두 pattern의 support가 따로 계산되지만, CT에서는 두 occurrence가 합쳐져 하나의 stronger structural feature가 됩니다. 따라서 feature budget이 제한되어 있을 때 여러 ordinal variant에 각각 feature를 사용하는 대신, 하나의 shared structural pattern에 representation capacity를 집중할 수 있습니다. 중요한 점은 CT가 항상 pattern의 개수 자체를 줄이는 것은 아니라는 것입니다. 여러 low-support OP pattern이 하나의 CT pattern으로 합쳐지면서 support threshold를 넘을 수도 있기 때문입니다. CT의 핵심 장점은 단순한 pattern 수 감소가 아니라 분산된 ordinal variation을 하나의 structural feature로 consolidate하는 것입니다.
주요 실험에는 다음 다섯 개의 time-series dataset을 사용합니다.