Space-Efficient Text Indexing with Mismatches using Function Inversion

A classic data structure problem is to preprocess a string T of length n so that, given a query q, we can quickly find all substrings of T with Hamming distance at most k from the query string. Variants of this problem have seen significant research both in theory and in practice. For a wide parameter range, the best worst-case bounds are achieved by the "CGL tree" (Cole, Gottlieb, Lewenstein 2004), which achieves query time roughly O(|q| + log k n + #occ), where #occ is the size of the output, and space O(n log k n). The CGL Tree space was recently improved to O(n log k-1 n) (Kociumaka, Radoszewski 2026).

A natural question that arises is whether a high space bound is necessary. How efficient can we make queries when the data structure is constrained to O(n) space? While this question has seen extensive research, all known results have query time with unfavorable dependence on the alphabet size, n and k. The state of the art query time from (Chan, Lam, Sung, Tam, Wong 2011) is roughly O(|q| + |Σ| k log k 2 +k n + #occ) for alphabet Σ.

We give an O(n)-space data structure with query time roughly O(|q| + log 4k n + log 2k n • #occ), with no dependence on the size of the alphabet. Even for a constant-sized alphabet, this is the best known query time for linear space if k ≥ 3 unless #occ is large. Our results give a smooth tradeoff between time and space. Interestingly, our results are the first to extend to the sublinear space regime: we give a succinct data structure using only o(n) space in addition to the text itself, with only a modest increase in query time.

The main technical idea behind this result is to apply Fiat-Naor function inversion (Fiat, Naor 2000) to the CGL tree. Combining these techniques is not immediate; in fact, we revisit the exposition of both the Fiat-Naor data structure and the CGL tree to obtain our bounds. Along the way, we obtain improved performance for both data structures, which may be of independent interest.