Paper Info
Title
Order-Preserving Incomplete Suffix Trees and Order-Preserving Indexes
Abstract
Recently Kubica et al. (<em>Inf. Process. Let.</em>, 2013) and Kim et al. (<em>submitted to Theor. Comp. Sci.</em>) introduced order-preserving pattern matching: for a given text the goal is to find its factors having the same 'shape' as a given pattern. Known results include a linear-time algorithm for this problem (in case of polynomially-bounded alphabet) and a generalization to multiple patterns. We give an <em>O</em>(<em>n</em>loglog<em>n</em>) time construction of an index that enables order-preserving pattern matching queries in time proportional to pattern length. The main component is a data structure being an incomplete suffix tree in the order-preserving setting. The tree can miss single letters related to branching at internal nodes. Such incompleteness results from the weakness of our so called <em>weak character oracle</em>. However, due to its weakness, such oracle can answer queries on-line in <em>O</em>(loglog<em>n</em>) time using a sliding-window approach. For most of the applications such incomplete suffix-trees provide the same functional power as the complete ones. We also give an <InlineEquation ID=\"IEq1\" <EquationSource Format=\"TEX\"$O(\\frac{n\\log{n}}{\\log\\log{n}})$</EquationSource> </InlineEquation> time algorithm constructing complete order-preserving suffix trees.
Year
DOI
Venue
2013
10.1007/978-3-319-02432-5_13
SPIRE
Field
DocType
Volume
Data structure,Combinatorics,Suffix,Computer science,Oracle,Suffix tree,Pattern matching,Alphabet,Branching (version control)
Conference
8214
ISSN
Citations 
PageRank 
0302-9743
16
0.97
References 
Authors
15
9
Name
Order
Citations
PageRank
Maxime Crochemore12655281.75
Costas S. Iliopoulos21534167.43
Tomasz Kociumaka321738.57
Marcin Kubica462929.26
Alessio Langiu5466.52
Solon P. Pissis628157.09
Jakub Radoszewski762450.36
Wojciech Rytter82290181.52
Tomasz Waleń970639.62