Blog
About

  • Record: found
  • Abstract: found
  • Article: found
Is Open Access

Order-Preserving Suffix Trees and Their Algorithmic Applications

Preprint

Read this article at

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.

      Related collections

      Most cited references 8

      • Record: found
      • Abstract: not found
      • Article: not found

      Fast Algorithms for Finding Nearest Common Ancestors

        Bookmark
        • Record: found
        • Abstract: not found
        • Article: not found

        On-line construction of suffix trees

         E Ukkonen (1995)
          Bookmark
          • Record: found
          • Abstract: not found
          • Article: not found

          Parameterized Pattern Matching: Algorithms and Applications

            Bookmark

            Author and article information

            Journal
            1303.6872

            Data structures & Algorithms

            Comments

            Comment on this article

            Similar articles 64,283