Upper and lower bounds for dynamic data structures on strings

DOI10.4230/LIPICS.STACS.2018.22MaRDI QIDQ3304117zbMATH OpenOpenAlexFDO

Authors Raphaël Clifford, Allan Grønlund, Kasper Green Larsen, Tatiana Starikovskaya

Publication date 5 August 2020

Full work available at URL https://arxiv.org/abs/1802.06545

zbMATH Keywords

conditional lower boundsexact pattern matching with wildcardsHamming distanceinner product

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Abstract: We consider a range of simply stated dynamic data structure problems on strings. An update changes one symbol in the input and a query asks us to compute some function of the pattern of length $m$ and a substring of a longer text. We give both conditional and unconditional lower bounds for variants of exact matching with wildcards, inner product, and Hamming distance computation via a sequence of reductions. As an example, we show that there does not exist an $O(m^{1/2-varepsilon})$ time algorithm for a large range of these problems unless the online Boolean matrix-vector multiplication conjecture is false. We also provide nearly matching upper bounds for most of the problems we consider.

Recommendations

• scientific article; zbMATH DE number 6850408
• New amortized cell-probe lower bounds for dynamic problems
• scientific article; zbMATH DE number 1445383
• scientific article; zbMATH DE number 1476488
• Cell-probe bounds for online edit distance and other pattern matching problems

Cites work

• A black box for online approximate pattern matching
• Approximate string matching using compressed suffix arrays
• Consequences of Faster Alignment of Sequences
• Dictionary matching and indexing with errors and don't cares
• Dictionary matching with a few gaps
• Dynamic text and static pattern matching
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Fast algorithms for approximately counting mismatches
• Faster Online Matrix-Vector Multiplication
• Generalized String Matching
• scientific article; zbMATH DE number 1445383 (Why is no real title available?)
• Indexing methods for approximate dictionary searching, comparative analysis
• Simple deterministic wildcard matching
• Sparser Johnson-Lindenstrauss transforms
• Text Indexing and Dictionary Matching with One Error
• The cell probe complexity of dynamic range counting
• Tight bounds for the partial-sums problem
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
• Verifying candidate matches in sparse and wildcard matching

Cited in

(14)

• Dynamic and internal longest common substring
• scientific article; zbMATH DE number 6850408 (Why is no real title available?)
• Construction of Fundamental Data Structures for Strings
• Longest common substring made fully dynamic
• Asymptotic Optimality of Antidictionary Codes
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• scientific article; zbMATH DE number 7765406 (Why is no real title available?)
• Range updates and range sum queries on multidimensional points with monoid weights
• Internal masked prefix sums and its connection to fully internal measurement queries
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• A textbook solution for dynamic strings
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Dynamic membership for regular languages
• Longest common extensions with wildcards: trade-off and applications

This page was built for publication: Upper and lower bounds for dynamic data structures on strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304117)