Blog
About

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

      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 content 65,471