Order-preserving incomplete suffix trees and order-preserving indexes

Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Recently Kubica et al. (Inf. Process. Let., 2013) and Kim et al. (submitted to Theor. Comp. Sci.) 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 O (n log log n) 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 weak character oracle. However, due to its weakness, such oracle can answer queries on-line in O (log log n) 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 O (n log n/log log n) time algorithm constructing complete order-preserving suffix trees.

Original languageEnglish
Title of host publicationString Processing and Information Retrieval - 20th International Symposium, SPIRE 2013, Proceedings
PublisherSpringer Verlag
Pages84-95
Number of pages12
ISBN (Print)9783319024318
DOIs
Publication statusPublished - 1 Jan 2013
Externally publishedYes
Event20th International Symposium on String Processing and Information Retrieval, SPIRE 2013 - Jerusalem, Israel
Duration: 7 Oct 20139 Oct 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8214 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Symposium on String Processing and Information Retrieval, SPIRE 2013
Country/TerritoryIsrael
CityJerusalem
Period7/10/139/10/13

Fingerprint

Dive into the research topics of 'Order-preserving incomplete suffix trees and order-preserving indexes'. Together they form a unique fingerprint.

Cite this