Space-Efficient k-Mismatch Text Indexes

A central task in string processing is text indexing, where the goal is to preprocess a text (a string of length n) into an efficient index (a data structure) supporting queries about the text. While the most fundamental exact pattern matching queries ask to find all the occurrences of a pattern (a string of length m) as substrings of the text, many applications call for approximate pattern matching queries, where the pattern may differ slightly from the matching substrings. A breakthrough in the extensive study of approximate text indexing came from Cole, Gottlieb, and Lewenstein (STOC 2004), who proposed k-errata trees -a family of text indexes supporting several closely related flavors of approximate pattern matching queries. In particular, k-errata trees yield an elegant solution to k-mismatch queries, where the similarity is quantified using an upper bound k ≥ 1 on the Hamming distance between the pattern and its approximate occurrences. The resulting k-mismatch index uses O(n log k n) space and answers a query for a length-m pattern in O(log k n log log n + m + occ) time, where occ is the number of approximate occurrences.

In retrospect, k-errata trees appear very well optimized: even though a large body of work has adapted k-errata trees to various settings throughout the past two decades, the original time-space trade-off for k-mismatch indexing has not been improved in the general case. We present the first such improvement, a k-mismatch index with O(n log k-1 n) space and the same query time as k-errata trees.

Previously, due to a result of Chan, Lam, Sung, Tam, and Wong (Algorithmica 2010), such an O(n log k-1 n)-size index has been known only for texts over alphabets of constant size σ = O(1). In this setting, however, we obtain an even smaller k-mismatch index of size only O(n log k-2+ε+ 2 k+2-(k mod 2) n) ⊆ O(n log k-1.5+ε n) for 2 ≤ k ≤ O(1) and any constant ε > 0. Along the way, we also develop improved indexes for short patterns, offering better trade-offs in this practically relevant special case.