Order-preserving pattern mining and comparison via indexing

Frequent Pattern Mining (FPM) from a time series has received much attention. The problem has been studied under various matching relations, including, more recently, the order-preserving (OP) matching relation, in which two time series match if their elements share the same relative order (i.e., the same ranks). Thus, a frequent OP pattern captures a trend shared by sufficiently many parts of the input time series. Here, we propose exact, highly scalable algorithms for FPM in the OP setting. Our algorithms employ an OP suffix tree (OPST) as an index to store and query time series efficiently. Unfortunately, there are no practical algorithms for OPST construction. Thus, we first propose a novel and practical $\mathcal{O}(n\sigma log \sigma)$-time and $\mathcal{O}(n)$-space algorithm for constructing the OPST of a length-$n$ time series over an alphabet of size $\sigma$. We also propose an alternative faster OPST construction algorithm running in $\mathcal{O}(n log \sigma)$ time using $\mathcal{O}(n)$ space; this algorithm is mainly of theoretical interest. Then, we propose an exact $\mathcal{O}(n)$-time and $\mathcal{O}(n)$-space algorithm for mining all maximal frequent OP patterns, given an OPST. This significantly improves on the state of the art, which takes $\Omega(n^3)$ time in the worst case. We also formalize the notion of closed frequent OP patterns and propose an exact $\mathcal{O}(n)$-time and $\mathcal{O}(n)$-space algorithm for mining all closed frequent OP patterns, given an OPST. In addition, we show how to utilize the OP matching relation to efficiently compare two time series based on their trends. We evaluated our algorithms extensively through experiments and case studies on real-world, multi-million-letter time series, demonstrating both their efficiency and effectiveness.

• View at Publisher
• View at Scopus