Deterministic indexing for packed strings

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2017

Documents

DOI

View graph of relations

Given a string S of length n, the classic string indexing problem is to preprocess S into a compact data structure that supports efficient subsequent pattern queries. In the deterministic variant the goal is to solve the string indexing problem without any randomization (at preprocessing time or query time). In the packed variant the strings are stored with several character in a single word, giving us the opportunity to read multiple characters simultaneously. Our main result is a new string index in the deterministic and packed setting. Given a packed string S of length n over an alphabet σ, we show how to preprocess S in O(n) (deterministic) time and space O(n) such that given a packed pattern string of length m we can support queries in (deterministic) time O (m/α + log m + log log σ), where α = w/log σ is the number of characters packed in a word of size w = θ(log n). Our query time is always at least as good as the previous best known bounds and whenever several characters are packed in a word, i.e., log σ
Original languageEnglish
Title of host publicationProceedings of 28th Annual Symposium on Combinatorial Pattern Matching
Number of pages6
Volume78
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date2017
ISBN (print)9783959770392
DOIs
StatePublished - 2017
Event28th Annual Symposium on Combinatorial Pattern Matching - Warsaw, Poland

Conference

Conference28th Annual Symposium on Combinatorial Pattern Matching
LocationUniversity of Warsaw Library
CountryPoland
CityWarsaw
Period04/07/201706/07/2017
SeriesLeibniz International Proceedings in Informatics
ISSN1868-8969
CitationsWeb of Science® Times Cited: No match on DOI

    Keywords

  • Information Sources and Analysis, Combinatorial Mathematics, Includes Graph Theory, Set Theory, Deterministic algorithm, Suffix array, Suffix tree, Word packing, Pattern matching, Trees (mathematics), Compact data structure, Deterministic algorithms, Pattern query, Pattern strings, Preprocessing time, Single words, Suffix arrays, Suffix-trees
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

Download statistics

No data available

ID: 134946204