The Jump Index

Ragnar {Groot Koerkamp}

IGGSy 2026, Ascona

curiouscoding.nl/slides/jump-index/slides github.com/RagnarGrootKoerkamp/jump-index

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

I/O-efficient pattern matching using suffix tries

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

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\)

(in M)	n	copies	r	CDAWG-n	CDAWG-e	type	\(\vert\mathsf{stpd}\vert\)	#(src)	#(src,c)	#(links)
influenza	154.81	78k	3.02	7.73	17.15	pos-	1.93	1.82	2.34	2.94
						lex-	1.82	1.58	2.09	2.98
dna.001.1	104.86	100	1.72	6.00	12.91	pos-	1.25	0.76	1.27	1.61
						lex-	1.10	0.79	1.29	1.71
einstein.de.txt	92.76	2.1k	0.10	0.08	0.23	pos-	0.06	0.04	0.09	0.10
						lex-	0.06	0.04	0.09	0.10
Escherichia_Coli	112.69	23	15.04	12.01	31.33	pos-	11.68	7.07	11.88	14.97
						lex-	9.82	6.84	11.53	14.99

Goal: match statistics on HPRCv2 in 50GB RAM