Pith. sign in

REVIEW 1 major objections 17 references

Parse indexing generates pseudo-MEMs with lower bounds on longest contained MEM lengths, allowing safe discard of short ones.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.3

2026-06-30 18:53 UTC pith:UAS47XOB

load-bearing objection Parse indexing adds lower bounds to KeBaB pseudo-MEMs so short ones can be discarded safely. the 1 major comments →

arxiv 2605.17574 v3 pith:UAS47XOB submitted 2026-05-17 cs.DS

Parse indexing for discarding short pseudo-MEMs safely

Travis Gagie This is my paper
classification cs.DS
keywords parse indexingpseudo-MEMsmaximal exact matchesk-mer based breakingrepetitive textstring algorithmspattern matchingdiscarding short matches
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper shows that parse indexing can produce pseudo-MEMs paired with lower bounds on the longest MEMs they are guaranteed to contain. This extends k-mer based breaking by making it possible to discard short pseudo-MEMs without the risk of also discarding long maximal exact matches. A reader would care because it reduces the total length of substrings that must be processed when searching for long MEMs in repetitive texts while preserving correctness.

Core claim

We show how we can use parse indexing to generate pseudo-MEMs together with lower bounds on the lengths of the longest MEMs they must contain, allowing us to discard short pseudo-MEMs safely.

What carries the argument

Parse indexing, which produces pseudo-MEMs along with lower bounds on the lengths of the longest MEMs contained inside them.

Load-bearing premise

The lower bounds produced by parse indexing are both correct and tight enough to let us discard short pseudo-MEMs without missing any MEM of length at least k.

What would settle it

A concrete counterexample in which a MEM of length at least k is missed after all pseudo-MEMs whose lower bound is below k are discarded.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Short pseudo-MEMs can be discarded without risking loss of any long MEMs.
  • The total length of pseudo-MEMs that must be examined is reduced compared with KeBaB alone.
  • Searches for long MEMs between a pattern and a repetitive text become more efficient.
  • The safety guarantee holds for any fixed parameter k.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The technique could be tested on genomic datasets to measure actual reduction in processed length.
  • It may combine with other string indexing methods to further speed up exact-match searches.
  • The same lower-bound idea might apply to related problems such as approximate matching.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 0 minor

Summary. The paper extends the KeBaB pre-processing step from Brown et al. (2025) for finding long maximal exact matches (MEMs) between a pattern P and an indexed repetitive text T. It shows how parse indexing can be used to generate pseudo-MEMs together with lower bounds on the lengths of the longest MEMs they must contain, allowing short pseudo-MEMs to be discarded safely while retaining all MEMs of length at least k.

Significance. If the lower bounds are correct and sufficiently tight, the technique would address a key limitation of KeBaB (risk of discarding long MEMs when pruning to the longest pseudo-MEMs) and could improve efficiency of MEM searches in repetitive texts without sacrificing completeness for long matches.

major comments (1)
  1. Abstract: the central claim is that parse indexing produces correct and sufficiently tight lower bounds permitting safe discarding, but the abstract supplies no derivation, proof sketch, equations, or experimental verification, so soundness of the result cannot be assessed from the provided text.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review of our manuscript. We respond to the single major comment below.

read point-by-point responses

  1. Referee: [—] Abstract: the central claim is that parse indexing produces correct and sufficiently tight lower bounds permitting safe discarding, but the abstract supplies no derivation, proof sketch, equations, or experimental verification, so soundness of the result cannot be assessed from the provided text.

    Authors: Abstracts are intentionally concise high-level summaries and do not contain derivations, proofs, or equations; those elements appear in the body of the manuscript. Section 3 derives the lower bounds on longest MEM lengths inside pseudo-MEMs using properties of the parse index, and Section 4 proves that the bounds are correct and tight enough to allow safe discarding of short pseudo-MEMs while retaining every MEM of length at least k. The soundness of the central claim can therefore be assessed from the full text. revision: no

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents a constructive method that augments KeBaB pseudo-MEMs with lower bounds on longest MEM lengths derived via parse indexing. No equations, fitted parameters, or self-referential definitions are visible that would reduce the claimed bounds or safe-discarding guarantee to the inputs by construction. The central claim is the derivation of these bounds as a new capability, which is self-contained and does not rely on load-bearing self-citations or imported uniqueness results. This is the normal case of an independent algorithmic construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities.

pith-pipeline@v0.9.1-grok · 5675 in / 964 out tokens · 47918 ms · 2026-06-30T18:53:03.762620+00:00 · methodology

0 comments
read the original abstract

Brown et al.\ (2025) described a pre-processing step, called $k$-mer based breaking (KeBaB), that speeds up searching for long maximal exact matches (MEMs) between a pattern $P$ and an indexed repetitive text $T$. KeBaB produces a set of substrings of $P$ called pseudo-MEMs that often have total length much less than $|P|$ but are still guaranteed to contain all the MEMs of length at least a fixed parameter $k$. Brown et al.\ found that KeBaB can be particularly effective when we discard all but the longest pseudo-MEMs -- but then we risk also discarding the longest MEMs! In this paper we show how we can use parse indexing to generate pseudo-MEMs together with lower bounds on the lengths of the longest MEMs they must contain, allowing us to discard short pseudo-MEMs safely.

Figures

Figures reproduced from arXiv: 2605.17574 by Travis Gagie.

Figure 1
Figure 1. Figure 1: A summary of our approach combining KeBaB with parse indexing, guaranteed to [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗

Review history (3 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    Schloss Dagstuhl–Leibniz-Zentrum für Infor- matik (2025)

    Brown, N.K., Gagie, T., Manzini, G., Navarro, G., Sciortino, M.: Faster run-length compressedsuffixarrays.In:FromStringstoGraphs,andBackAgain:AFestschrift for Roberto Grossi’s 60th Birthday. Schloss Dagstuhl–Leibniz-Zentrum für Infor- matik (2025)

    2025

  2. [2]

    In: Proc

    Brown, N.K., et al.: KeBaB: k-mer based breaking for finding long MEMs. In: Proc. 32nd Symposium on String Processing and Information Retrieval (SPIRE) (2025) Parse indexing for discarding short pseudo-MEMs safely 7

    2025

  3. [3]

    ACM Transactions on Algorithms22(2025)

    Cobas, D., Gagie, T., Navarro, G.: Fast and small subsampled r-indexes. ACM Transactions on Algorithms22(2025)

    2025

  4. [4]

    In: Proc

    Deng, J.J., Hon, W.K., Köppl, D., Sadakane, K.: FM-indexing grammars induced by suffix sorting for long patterns. In: Proc. Data Compression Conference (DCC) (2022)

    2022

  5. [5]

    IEEE/ACM Transactions on Networking8(2000)

    Fan, L., Cao, P., Almeida, J., Broder, A.Z.: Summary cache: a scalable wide-area web cache sharing protocol. IEEE/ACM Transactions on Networking8(2000)

    2000

  6. [6]

    Journal of the ACM52 (2005)

    Ferragina, P., Manzini, G.: Indexing compressed text. Journal of the ACM52 (2005)

    2005

  7. [7]

    iScience27(2024)

    Ferro, E., Oliva, M., Gagie, T., Boucher, C.: Building a pangenome alignment index via recursive prefix-free parsing. iScience27(2024)

    2024

  8. [8]

    In: Proc

    Gagie, T.: How to find long maximal exact matches and ignore short ones. In: Proc. 28th Conference on Developments in Language Theory (DLT) (2024)

    2024

  9. [9]

    SIAM Journal on Computing35(2005)

    Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM Journal on Computing35(2005)

    2005

  10. [10]

    Algorithms for Molecular Biology19(2024)

    Hong, A., Oliva, M., Köppl, D., Bannai, H., Boucher, C., Gagie, T.: Pfp-fm: an accelerated FM-index. Algorithms for Molecular Biology19(2024)

    2024

  11. [11]

    Bioinformatics28(2012)

    Li, H.: Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly. Bioinformatics28(2012)

    2012

  12. [12]

    Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM

    Li, H.: Aligning sequence reads, clone sequences and assembly contigs with BWA- MEM. arXiv preprint 1303.3997 (2013)

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  13. [13]

    Bioinformatics40 (2024)

    Li, H.: BWT construction and search at the terabase scale. Bioinformatics40 (2024)

    2024

  14. [14]

    Journal of Computational Biology17(2010)

    Mäkinen, V., Navarro, G., Sirén, J., Välimäki, N.: Storage and retrieval of highly repetitive sequence collections. Journal of Computational Biology17(2010)

    2010

  15. [15]

    In: Companion to the Conference on Management of Data (SIGMOD) (2024)

    Pandey, P., Farach-Colton, M., Dayan, N., Zhang, H.: Beyond Bloom: A tutorial on future feature-rich filters. In: Companion to the Conference on Management of Data (SIGMOD) (2024)

    2024

  16. [16]

    Bioinformatics20(2004)

    Roberts, M., Hayes, W., Hunt, B.R., Mount, S.M., Yorke, J.A.: Reducing storage requirements for biological sequence comparison. Bioinformatics20(2004)

    2004

  17. [17]

    Tridgell, A., Mackerras, P.: The rsync algorithm. Tech. rep., Australian National University (1996)

    1996