Pith. sign in

REVIEW 4 minor 1 cited by

Online Computation of the Longest Repeating Suffix and Smallest Suffixient Sets via Incremental Run-Length BWT-based Indexes

T0 review · 0 major / 4 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Online algorithms compute longest repeating suffixes and smallest suffixient sets in compressed space with worst-case time, and any deterministic online LRS algorithm needs linear peak space.

desk verdict First compressed online SSS plus worst-case compressed LRS with matching Ω(n)-bit lower bounds; solid, careful work with one minor modelling caveat. read the letter →

arxiv 2607.05004 v1 pith:RQHK6MTE submitted 2026-07-06 cs.DS

Paola Bonizzoni , Younan Gao , Dominik Köppl , Gregory Kucherov This is my paper · ORCID
classification cs.DS MSC 68W3268P0568Q25
keywords onlinealgorithmscompresseddatastructuresrun-lengthBurrows-Wheelertransformlongestrepeatingsuffixsmallestsuffixientsetsstringrepetitiveness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

As a string is read character by character, two classical questions arise: what is the longest suffix of the current prefix that already appeared earlier, and what is a smallest set of positions that covers every super-maximal right extension of a right-maximal substring? The paper answers both questions with the first online algorithms that work in compressed working space measured by the number of runs r in the Burrows-Wheeler transform of the reverse text. Two concrete trade-offs are obtained: roughly O(r log n + n) bits and O(log^{2} n / log log n) worst-case time per character, or O(r log n + n log log n) bits and O((log n / log log n)^{2}) time. For highly repetitive strings the first bound collapses to linear bits. The same machinery also proves a matching lower bound: every deterministic online algorithm for the longest-repeating-suffix problem needs Ω(n) bits of peak memory even on a constant alphabet, and the lower bound transfers to the two natural variants of online smallest-suffixient-set maintenance.

What carries the argument

An incremental run-length BWT of the reverse text, augmented by a dynamic fusion tree that stores only the φ- and LCS-values of the run-top positions of the prefix array, together with a B-tree of Θ(L)-sized blocks that supports block enumeration, range-minimum queries and next/previous-smaller-value queries via the same samples.

What would settle it

Implement the two trade-offs (or a fully online doubling variant) and measure peak bits and worst-case update time on a family of highly repetitive strings with known r; the measured space must stay inside O(r log n + n) (respectively O(r log n + n log log n)) while every update finishes within the claimed asymptotic bound.

Watch

Extended reading notes

Core claim

There exist deterministic online algorithms that, after each character of T[1..n], compute the longest repeating suffix LRS[i] and maintain a length-annotated rightmost smallest suffixient set of the reverse prefix, using either O(r log n + n) bits and O(log^{2} n / log log n) worst-case time per character or O(r log n + n log log n) bits and O((log n / log log n)^{2}) time; any deterministic online LRS algorithm requires Ω(n) bits of peak working space even over a constant alphabet.

Load-bearing premise

The concrete trade-offs fix block size and B-tree fan-out from the first round and therefore need the final length n known in advance; without that knowledge only the more general per-round bounds hold.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper gives the first compressed-space online algorithms for constructing smallest suffixient sets and for computing the longest repeating suffix (LRS) of successive prefixes of a text T[1..n]. Using an incremental run-length BWT of the reverse text together with a B-tree over PA/LCS blocks of size L and a dynamic fusion tree over irreducible PLCS samples, it obtains two worst-case trade-offs: O(r log n + n) bits and O(log^{2} n / log log n) time per character, or O(r log n + n log log n) bits and O((log n / log log n)^{2}) time (Theorems 11, 14 and Corollaries 12, 15). It also proves an Ω(n)-bit peak-space lower bound for any deterministic online LRS algorithm over a constant alphabet (Theorem 13) and extends the bound, via short reductions, to length-annotated and rightmost smallest suffixient sets (Lemma 17, Theorem 19).

Significance. The work closes a clear gap: previous online SSS constructions used O(n) words, while the best compressed LRS algorithm of Prezza–Rosone was amortized O(log^{2} n). The new bounds are worst-case, improve the amortized bound by Θ(log log n) or Θ((log log n)^{2}), and match the Ω(n)-bit lower bound (up to constants) when r = O(n / log n). The lower-bound reductions cleanly link LRS and SSS maintenance. The technical machinery—reducible PLCS values, fusion-tree samples at run tops, and B-tree RMQ/NSV/PSV—is carefully developed and appears reusable for other online string problems.

minor comments (4)
  1. Section 2 states that the concrete trade-offs assume n is known from the first round so that L and F can be fixed. A short remark on a doubling scheme (or an explicit statement that only the general O(τ_i + log r_i) bounds hold without advance knowledge of n) would make the modelling assumption fully transparent to practitioners.
  2. In the proof of Proposition 2 the telescoping argument for ϕ is correct but terse; a one-sentence reminder that reducibility also implies ϕ(p+1)=ϕ(p)+1 would help readers who have not recently consulted the PLCP literature.
  3. Table 1 lists previous LRS/SSS bounds; adding a column that distinguishes amortized versus worst-case time would make the improvement over Prezza–Rosone and over the suffix-tree algorithms immediately visible.
  4. A few typographical inconsistencies appear (e.g., “therun top”, missing spaces after commas in some complexity expressions). A light copy-edit pass would remove them.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: algorithmic upper/lower bounds derived from independent data-structure primitives and first-principles adversary arguments

full rationale

The paper is a pure algorithms paper whose central claims (Theorems 11/14 and Corollaries 12/15 for the two space-time trade-offs; Theorem 13 and the reductions of Theorem 19 for the Ω(n)-bit lower bounds) are obtained by composing standard word-RAM primitives (dynamic RL-BWT of Policriti-Prezza, fusion trees of Pătraşcu-Thorup, B-trees) with an adaptation of PLCS reducibility (Proposition 2) and new RMQ/NSV/PSV support (Lemmas 5-10). No quantity is defined in terms of a later-predicted quantity, no parameter is fitted to data, and no uniqueness theorem is imported from overlapping authors to force the result. Self-citations to the authors' earlier suffix-tree algorithms ([15,16]) supply only high-level update ideas that are re-proved and re-implemented in the compressed setting; they are not load-bearing for the space or time bounds. The sole modelling caveat (advance knowledge of n to fix L and F) is stated explicitly and does not affect the general O(τ_i + log r_i) bounds or the lower bound. The derivation chain is therefore self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claims rest only on the standard word-RAM model, the known dynamic run-length BWT of Policriti & Prezza, dynamic fusion trees, and elementary properties of the BWT/PA/LCS arrays. No free parameters are fitted; the only non-standard modelling choice is the advance knowledge of n used to fix L and F for the concrete trade-offs.

assumptions (4)
  • standard math Word-RAM model with word size w = Θ(log n)
    Stated at the opening of Section 2; all time bounds are expressed in this model.
  • domain assumption Existence of a dynamic run-length BWT supporting access/rank/select/insert/replace in O(log r_i) time and O(r_i) words (Policriti-Prezza)
    Invoked as Lemma 4; the whole online index is built on top of this black box.
  • domain assumption Dynamic fusion trees support insert/delete/predecessor/successor in O(1 + log_w r) time
    Used throughout Section 3 to store the irreducible PA samples.
  • ad hoc to paper Final length n is known from the first round so that block size L and fan-out F can be fixed
    Explicitly assumed in Section 2 to obtain the two concrete trade-offs of Corollaries 12 and 15.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Computation of the Longest Repeating Suffix and Smallest Suffixient Sets via Incremental Run-Length BWT-based Indexes." pith.science (2026). https://pith.science/paper/RQHK6MTE

@misc{pith2026260705004,
  author       = {Pith},
  title        = {Pith review of: Online Computation of the Longest Repeating Suffix and Smallest Suffixient Sets via Incremental Run-Length BWT-based Indexes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RQHK6MTE}},
  note         = {Machine review of arXiv:2607.05004}
}
abstract

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 online construction of smallest suffixient sets, and present two space-time trade-offs for both problems: $O(r\log n+n)$ bits of working space and $O(\log^2 n/\log \log n)$ worst-case time per character, and $O(r\log n+n \log \log n)$ bits of working space and $O((\log n/\log \log n)^2)$ worst-case time per character. Here, $r$ is the number of runs in the Burrows-Wheeler transform of the reverse of $T[1..n]$. In particular, for highly repetitive texts satisfying $r=O(n/\log n)$, the first trade-off uses $O(n)$ bits of working space, while the second uses $O(n\log\log n)$ bits. We also prove that any deterministic online algorithm for computing LRS requires \(\Omega(n)\) bits of peak working space in the worst case, even over a constant-size alphabet. Through reductions from online LRS computation, we extend this lower bound to deterministic online algorithms maintaining either an arbitrary smallest suffixient set augmented with the length of the supermaximal right extension represented by each selected position, or the position-only smallest suffixient set obtained by selecting the rightmost occurrence of every such extension. For constructing smallest suffixient sets, our algorithms are the first online solutions using compressed working space, improving the $O(n)$-word space required by previous online constructions. For compressed-space online LRS computation, compared with the algorithm of Prezza and Rosone~[CiE 2020], our bounds improve their $O(\log^2 n)$ amortized time per character by factors of $\Theta(\log\log n)$ and $\Theta((\log\log n)^2)$, respectively, while also providing worst-case guarantees.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Patching leaky tunnels in BWTs

    cs.DS 2026-08 conditional novelty 6.0 of 10

    A suffixient-set based index finds maximal exact matches in O(rho_P log m) time plus constant per suffix-tree edge, using O(rho_T + chi) space, when both text and pattern are run-length compressed.

Reference graph

Works this paper leans on

15 extracted references · 4 canonical work pages · cited by 1 Pith paper

  1. [1]

    Organization and maintenance of large ordered indices

    2 Rudolf Bayer and Edward McCreight. Organization and maintenance of large ordered indices. InProceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control, pages 107–141,

    1970

  2. [2]

    Constructing suffixient arrays revisited

    3 Paola Bonizzoni, Younan Gao, and Brian Riccardi. Constructing suffixient arrays revisited. In Philip Bille and Nicola Prezza, editors,37th Annual Symposium on Combinatorial Pattern Matching, CPM 2026, Copenhagen, Denmark, June 15-17, 2026, volume 369 ofLIPIcs, pages 30:1–30:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.doi:10.4230/LIPICS. ...

    doi:10.4230/lipics 2026

  3. [3]

    5 Michael Burrows and David J

    doi:10.1186/S13015-019-0148-5. 5 Michael Burrows and David J. Wheeler. A block-sorting lossless data compression algorithm

    doi:10.1186/s13015-019-0148-5

  4. [4]

    6 Davide Cenzato, Lore Depuydt, Travis Gagie, Sung-Hwan Kim, Giovanni Manzini, Francisco Olivares, and Nicola Prezza

    URL:https://api.semanticscholar.org/CorpusID:2167441. 6 Davide Cenzato, Lore Depuydt, Travis Gagie, Sung-Hwan Kim, Giovanni Manzini, Francisco Olivares, and Nicola Prezza. Suffixient arrays: a new efficient suffix array compression technique.arXiv preprint arXiv:2407.18753,

    arXiv

  5. [5]

    8 Paolo Ferragina and Giovanni Manzini

    doi: 10.1007/978-3-540-77974-2. 8 Paolo Ferragina and Giovanni Manzini. Opportunistic data structures with applications. In41st Annual Symposium on Foundations of Computer Science, FOCS 2000, Redondo 24 Online Computation of the Longest Repeating Suffix and Smallest Suffixient Sets Beach, California, USA, November 12-14, 2000, pages 390–398. IEEE Computer...

    doi:10.1007/978-3-540-77974-2

  6. [6]

    9 Michael L

    doi:10.1109/SFCS.2000.892127. 9 Michael L. Fredman and Dan E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths.J. Comput. Syst. Sci., 48(3):533–551, 1994.doi:10.1016/ S0022-0000(05)80064-9. 10 Hiroto Fujimaru, Gonzalo Navarro, Giuseppe Romana, and Cristian Urbina. Smallest suffixient sets: Effectiveness, resilience, and ...

    doi:10.1109/sfcs.2000.892127 2000

  7. [7]

    Fully functional suffix trees and optimal text searching in bwt-runs bounded space.J

    11 Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Fully functional suffix trees and optimal text searching in bwt-runs bounded space.J. ACM, 67(1):2:1–2:54, 2020.doi:10.1145/3375890. 12 Juha Kärkkäinen, Giovanni Manzini, and Simon J. Puglisi. Permuted longest-common-prefix array. In Gregory Kucherov and Esko Ukkonen, editors,Combinatorial Pattern Match...

    doi:10.1145/3375890 2020

  8. [8]

    15 Dominik Köppl and Gregory Kucherov

    doi:10.1109/SFFCS.1999.814634. 15 Dominik Köppl and Gregory Kucherov. Near-real-time solutions for online string problems. In Philip Bille and Nicola Prezza, editors,37th Annual Symposium on Combinatorial Pattern Matching, CPM 2026, Copenhagen, Denmark, June 15-17, 2026, LIPIcs, pages 2:1–2:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    doi:10.1109/sffcs.1999.814634 1999

Show all 15 references
  1. [9]

    16 Dominik Köppl and Gregory Kucherov

    URL:https://doi.org/10.4230/ LIPIcs.CPM.2026.2,doi:10.4230/LIPICS.CPM.2026.2. 16 Dominik Köppl and Gregory Kucherov. Smallest suffixient set maintenance in near-real-time. InProceedings of the 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2...

    2026 doi

  2. [10]

    17 Abraham Lempel and Jacob Ziv

    To appear. 17 Abraham Lempel and Jacob Ziv. On the complexity of finite sequences.IEEE Trans. Inf. Theory, 22(1):75–81, 1976.doi:10.1109/TIT.1976.1055501. 18 Edward M. McCreight. A space-economical suffix tree construction algorithm.J. ACM, 23(2):262–272, 1976.doi:10.1145/3219...

    1976 doi

  3. [11]

    Springer, 2008.doi:10.1007/978-3-540-87744-8\_58

    Proceedings, Lecture Notes in Computer Science, pages 696–707. Springer, 2008.doi:10.1007/978-3-540-87744-8\_58. 20 Mihai Pătraşcu and Mikkel Thorup. Dynamic integer sets with optimal rank, select, and predecessor search. In55th IEEE Annual Symposium on Foundations of Computer...

    2008 doi

  4. [12]

    22 Nicola Prezza and Giovanna Rosone

    URL:https://doi.org/10.1007/s00453-017-0327-z, doi:10.1007/S00453-017-0327-Z. 22 Nicola Prezza and Giovanna Rosone. Faster online computation of the succinct longest previous factor array. InConference on Computability in Europe, pages 339–352. Springer,

    doi

  5. [13]

    Rlbwt-based lcp computation in compressed space for terabase-scale pangenome analysis.bioRxiv, pages 2026–01,

    23 Ahsan Sanaullah, Nathaniel K Brown, Pramesh Shakya, Arun Deegutla, Ardalan Naseri, Ben Langmead, Degui Zhi, and Shaojie Zhang. Rlbwt-based lcp computation in compressed space for terabase-scale pangenome analysis.bioRxiv, pages 2026–01,

    2026

  6. [14]

    Faster and simpler online/slid- ing rightmost lempel-ziv factorizations

    24 Wataru Sumiyoshi, Takuya Mieno, and Shunsuke Inenaga. Faster and simpler online/slid- ing rightmost lempel-ziv factorizations. InString Processing and Information Retrieval: P. Bonizzoni, Y. Gao, D. Köppl, and G. Kucherov 25 31st International Symposium, SPIRE 2024, Puerto ...

    2024

  7. [15]

    26 PeterWeiner

    doi:10.1007/BF01206331. 26 PeterWeiner. Linearpatternmatchingalgorithms. In14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973, pages 1–11. IEEE Computer Society, 1973.doi:10.1109/SWAT.1973.13. 27 Jacob Ziv and Abraham Lempel. A un...

    1973 doi

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.