The Jump Index

FM-index et al.: LF cache-miss per character :( Link to heading

I/O-efficient pattern matching using suffix tries Link to heading

• Suffix trees are in text space and I/O efficient!
• Suffix trees of repetitive texts are repetitive!

• “run-length suffix trees” embedded in the text:

  • Suffixient Sets: Depuydt et al. (2023)
  • Suffixient Array: Cenzato et al. (2024)
  • Suffix Tree Path Decomposition: Becker et al. (2026)

• Greedily match pattern against text.

  • “Reposition” on mismatch by searching sparse prefix array.

Jump Index:

• For every possible mismatch (switch between paths):
  • store link/pointer (source_pos, char, depth) ↦ target
  • Eg: (3, $, 2) ↦ 11:
    • Prefix AA of pattern AA$ matches at pos 2.
    • Mismatch as pos 3: got C, want $.
    • We find the $ at pos 11.

Jump Index Link to heading

• Full example:

  • (source, char, depth) ↦ target
  • (1, $, 0) ↦ 11
  • (1, C, 0) ↦ 3
  • (1, G, 0) ↦ 4
  • (2, $, 1) ↦ 11
  • (2, C, 1) ↦ 3
  • (3, $, 2) ↦ 11
  • (5, A, 1) ↦ 9
  • (5, A, 2) ↦ 9
  • (7, A, 3) ↦ 9
  • (7, A, 4) ↦ 9

• Store using Elias-Fano or HashMap.
• With similar pointers for suffix links, we get match statistics!
• Incremental/online construction similar to Ukkonen’s algorithm.

• Locates only the leftmost occurrence of each substring
  • Does not support locate-all!

Pizza & Chili results: #links \(\approx r\) Link to heading

Goal: match statistics on HPRCv2 in 50GB RAM Link to heading