10
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

# Order-Preserving Suffix Trees and Their Algorithmic Applications

Preprint

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### Abstract

Recently Kubica et al. (Inf. Process. Let., 2013) and Kim et al. (submitted to Theor. Comp. Sci.) introduced order-preserving pattern matching. In this problem we are looking for consecutive substrings of the text that have the same "shape" as a given pattern. These results include a linear-time order-preserving pattern matching algorithm for polynomially-bounded alphabet and an extension of this result to pattern matching with multiple patterns. We make one step forward in the analysis and give an $$O(\frac{n\log{n}}{\log\log{n}})$$ time randomized algorithm constructing suffix trees in the order-preserving setting. We show a number of applications of order-preserving suffix trees to identify patterns and repetitions in time series.

### Most cited references8

• Record: found

### Fast Algorithms for Finding Nearest Common Ancestors

(1984)
Bookmark
• Record: found

### On-line construction of suffix trees

(1995)
Bookmark
• Record: found

### Parameterized Pattern Matching: Algorithms and Applications

(1996)
Bookmark

### Author and article information

###### Journal
1303.6872

Data structures & Algorithms