5 papers
Online Computation of the Longest Repeating Suffix and Smallest Suffixient Sets via Incremental Run-Length BWT-based Indexes
Paola Bonizzoni, Younan Gao, Dominik Köppl +1
We revisit the online construction of \emph{smallest suffixient sets} and the online computation of the \emph{longest repeating suffix} (LRS). We give the first compressed-space on…
Smallest suffixient set maintenance in near-real-time
Dominik Köppl, Gregory Kucherov
The size of the \textit{smallest suffixient set} of positions of a string recently emerged as a new measure of string \textit{repetitiveness} -- a measure reflecting how much of re…
Near-real-time Solutions for Online String Problems
Dominik Köppl, Gregory Kucherov
Based on the Breslauer-Italiano online suffix tree construction algorithm (2013) with double logarithmic worst-case guarantees on the update time per letter, we develop near-real-t…
Online computation of normalized substring complexity
Gregory Kucherov, Yakov Nekrich
The normalized substring complexity of a string is defined as , where is the number of \textit{distinct} substrings of length . This simply defined…
Better space-time-robustness trade-offs for set reconciliation
Djamal Belazzougui, Gregory Kucherov, Stefan Walzer
We consider the problem of reconstructing the symmetric difference between similar sets from their representations (sketches) of size linear in the number of differences. Exact sol…