Dynamic suffix array with polylogarithmic queries and updates

DOI10.1145/3519935.3520061MaRDI QIDQ6083620zbMATH OpenFDO

Authors Dominik Kempa, Tomasz Kociumaka

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

dynamic data structurespattern matchingstring synchronizing setssuffix arraytext indexing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: The suffix array $SA[\mathrm{1..}n]$ of a text $T$ of length $n$ is a permutation of $1,ldots,n$ describing the lexicographical ordering of suffixes of $T$, and it is considered to be among of the most important data structures in string algorithms, with dozens of applications in data compression, bioinformatics, and information retrieval. One of the biggest drawbacks of the suffix array is that it is very difficult to maintain under text updates: even a single character substitution can completely change the contents of the suffix array. Thus, the suffix array of a dynamic text is modelled using suffix array queries, which return the value $SA[i]$ given any $iin[\mathrm{1..}n]$. Prior to this work, the fastest dynamic suffix array implementations were by Amir and Boneh. At ISAAC 2020, they showed how to answer suffix array queries in $ildeO(k)$ time, where $kin[\mathrm{1..}n]$ is a trade-off parameter, with $ildeO(fracnk)$-time text updates. In a very recent preprint [2021], they also provided a solution with $O(lo{g}^{5}n)$-time queries and $ildeO(n^{2/3})$-time updates. We propose the first data structure that supports both suffix array queries and text updates in $O(mpolylog,n)$ time (achieving $O(lo{g}^{4}n)$ and $O(lo{g}^{3+o(1)}n)$ time, respectively). Our data structure is deterministic and the running times for all operations are worst-case. In addition to the standard single-character edits (character insertions, deletions, and substitutions), we support (also in $O(lo{g}^{3+o(1)}n)$ time) the "cut-paste" operation that moves any (arbitrarily long) substring of $T$ to any place in $T$. We complement our structure by a hardness result: unless the Online Matrix-Vector Multiplication (OMv) Conjecture fails, no data structure with $O(mpolylog,n)$-time suffix array queries can support the "copy-paste" operation in $O(n^{1-epsilon})$ time for any $epsilon>0$.

Cited in

(17)

• On the number of elements to reorder when updating a suffix array
• Internal pattern matching queries in a text and applications
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• A textbook solution for dynamic strings
• Minimizing tardy processing time on a single machine in near-linear time
• Double-ended palindromic trees in linear time
• Internal pattern matching in small space and applications
• Maintaining the size of LZ77 on semi-dynamic strings
• Approximate circular pattern matching under edit distance
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Minimizing tardy processing time on a single machine in near-linear time
• Locally consistent parsing for text indexing in small space
• Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
• Computing string covers in sublinear time
• Logarithmic-time internal pattern matching queries in compressed and dynamic texts
• Bounded weighted edit distance: dynamic algorithms and matching lower bounds
• Dynamic extended suffix arrays

This page was built for publication: Dynamic suffix array with polylogarithmic queries and updates

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