The Anti-Lexicographic SUS-Anchor: An Empirically Optimal Selection Scheme

- Motivation. Selection schemes provide a way to select a subset of positions in a text in such a way that no two consecutive selected positions are more than w apart. These selected positions can be used as "anchor" points for text indices such that every sufficiently long pattern corresponds to at least one anchor [Ayad et al., 2025]. Closely related are sampling schemes, that sample a k-mer from each window of w consecutive k-mers in a text, and the more restricted minimizer schemes, that achieve this by taking the smallest k-mer according to some order. In recent years, there has been a renewed interest in the search for low density schemes that select/sample only a small fraction of positions/k-mers.
The mod-minimizer [Groot Koerkamp and Pibiri, 2024] provides a near-optimal density of 1/w as k / w → ∞, while schemes such as the greedy minimizer work well for explicit small parameters roughly in the regime k ≤ 2w, for k and w up to 15 or so.
When k < log_σ w is small, minimizer schemes cannot do well [Marçais et al., 2018]. As a first step towards low density sampling schemes in this regime, we fix k = 1 and search for a near-optimal selection scheme to improve the existing bidirectional string anchors (bd-anchors) [Loukides et al., 2023; Ayad et al., 2025].
... mehr
- Methods. Inspired by bd-anchors, we introduce the smallest unique substring or SUS-anchor: given a window, this considers all suffixes that do not occur as a substring elsewhere in the window. It then samples the start position of the smallest suffix according to the new anti-lexicographic order that minimizes the first character and maximizes the remaining characters. We give a linear-time and O(w) space streaming algorithm to compute all SUS-anchors of a string.
- Results. For alphabet size σ = 4 and k = 1, the parameter-free anti-lexicographic SUS-anchor empirically has density < 1% away from the density lower bound and is at least 4× closer to the lower bound than all other tested schemes. For alphabet size σ = 2, the density is at most 10% above the lower bound, which still improves 2× to 3× the overhead of the random minimizer and is consistently better than the greedy minimizer. Likewise, the anti-lexicographic minimizer performs better than all other schemes apart from the greedy minimizer.