The anti-lexicographic SUS-anchor: an empirically optimal selection scheme

\[ \newcommand{\sus}{\mathsf{SUS}} \newcommand{\lcp}{\mathsf{lcp}} \newcommand{\last}{\mathsf{last}} \]

A preprint of this blog can be found here: PDF, DOI (Groot Koerkamp 2026).

Abstract Link to heading

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, Loukides, and Pissis 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 \to \infty\), while schemes such as the greedy minimizer work well for explicit small parameters roughly in the regime \(k \leq 2w\), for \(k\) and \(w\) up to \(15\) or so.

When \(k < \log_\sigma w\) is small, minimizer schemes cannot do well (Marçais, DeBlasio, and Kingsford 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, Pissis, and Sweering 2023; Ayad, Loukides, and Pissis 2025).

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 \(\sigma=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\times\) closer to the lower bound than all other tested schemes. For alphabet size \(\sigma=2\), the density is at most \(10\%\) above the lower bound, which still improves \(2\times\) to \(3\times\) 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.

1 Introduction Link to heading

Minimizers (Schleimer, Wilkerson, and Aiken 2003; Roberts et al. 2004) are a technique to subsample the \(k\)-mers of a string such that consecutive samples are at most \(w\) positions apart. Minimizer sampling has many applications in bioinformatics. In particular, a number of data structures exploit this window guarantee and use minimizers as a locality-sensitive hash: SSHash (Pibiri 2022; Pibiri and Patro 2026) and \(k\)ache-hash (Khan, Patro, and Pandey 2026) use the minimizer of a string as the key in a hash map, while the U-index (Ayad et al. 2025) is a text index that considers the minimizers of a pattern. In a similar way, the text index of Loukides et al. and Ayad et al. (Loukides, Pissis, and Sweering 2023; Ayad, Loukides, and Pissis 2025) works for patterns of length at least \(\ell\) and selects positions in the text (anchors) that are at most \(w=\ell\) apart in a locally consistent way, so that each queried pattern of length \(\geq \ell\) can be found via its anchor. Improving their bidirectional string anchors is the main goal of this work, as this directly leads to a smaller text index.

From another point of view, the minimizers of a string are a sketch or compressed (lossy) representation, allowing for faster processing. Specific applications include seeding for read-mapping as done by minimap (Li 2016), the minimizer-space De Bruijn graph (Ekim, Berger, and Chikhi 2021), sketching for Jaccard similarity in mashmap (Jain et al. 2018), host depletion in Deacon (Constantinides, Lees, and Crook 2025), and more (Zheng, Marçais, and Kingsford 2023). In this direction, there are also other schemes such as syncmers (Edgar 2021) and universal hitting sets (Orenstein et al. 2016, 2017; Marçais et al. 2017). In these schemes, each \(k\)-mer is sampled independently from its context, which may loosen the window guarantee and does not directly give a suitable key or anchor for each window.

Recent work. There is a long line of active work on minimizers. Of particular interest is the density, which is the expected fraction of sampled positions. Recently, the mod-minimizer (Groot Koerkamp and Pibiri 2024; Groot Koerkamp, Liu, and Pibiri 2025) introduced schemes with near-optimal density for \(k\to\infty\). The GreedyMini (Golan et al. 2025) is the state of the art for smaller \(w\) and \(k\) roughly up to \(15\), achieving particularly close to optimal density for \(k=w+1\), \(k=w\), and \(k\) just below \(w\). Shur et al. recently introduced spacers (Shur, Tziony, and Orenstein 2026a) that prefer sampling \(k\)-mers starting with 10 (after projecting to a binary alphabet) for which the next occurrence of 10 is as far ahead as possible. Spacers improve the density of the ABB+ scheme we introduce here, and are especially good when \(w\) is large. For particularly small parameters \((\sigma,k)=(2,\leq 6)\) and \((\sigma,k)=(4, 2)\), exactly optimal minimizer schemes are given by the search algorithm OptMini (Shur, Tziony, and Orenstein 2026b) and analysed theoretically by Shur (Shur 2025).

This raises the question: can we find near-optimal sampling schemes for small \(k\), and in particular for \(k=1\)? An ILP search suggests that the answer is yes: this is always possible when \(k\equiv 1\mod w\) (Kille et al. 2024), and thus we are motivated to search for a “clean”, constant-space scheme.

Some further recent work includes SimdMinimizers (Groot Koerkamp and Martayan 2025), a SIMD-based algorithm that computes random minimizers at around 500 Mbp/s. A precise analysis of the density of the random minimizer is given in (Golan and Shur 2025). Vigemers (Ingels, Limasset, et al. 2026) reduce the imbalance when using minimizers for partitioning, and multiminimizers (Ingels, Robidou, et al. 2026) reduce the density at the cost of more compute.

Sampling and selection schemes. Minimizer schemes hash each \(k\)-mer and sample the \(k\)-mer with the smallest hash in a window of \(w\) \(k\)-mers (or \(\ell=w+k-1\) characters). Minimizers cannot achieve a good density of \(O(1/w)\) for constant \(k\) as \(w\to\infty\) (Marçais, DeBlasio, and Kingsford 2018), but this restriction does not apply to sampling schemes, which have more freedom because they are not required to first hash all \(k\)-mers. In particular, selection schemes with \(k=1\) simply sample a single position based on a window of length \(w=\ell\). The main reason that selection schemes can achieve better density than sampling schemes is that for a fixed sized window, they can also sample the last \(k-1\) positions, and thus achieve a greater distance between consecutive samples. Bidirectional string anchors (bd-anchors) are one such selection scheme (Loukides, Pissis, and Sweering 2023). These sample the start position of the smallest rotation of a window and achieve a density of \(O(1/w)\). For large \(w\) and alphabet size \(\sigma=4\), bd-anchors have a density around \(20\%\) above the lower bound. Our goal is to reduce this to as close to \(0\%\) overhead as possible.

Contributions. In this paper, we introduce SUS-anchors, short for smallest unique substring anchors. As the name implies, given a window, these sample the start position of the smallest substring that does not occur a second time. The lexicographic SUS-anchor is equivalent (after reversing the order of the alphabet) to the the maximal suffix of each window. Our main results are as follows:

• We experimentally show that SUS-anchors with the anti-lexicographic order (see below) have density within \(1\%\) of optimal for \(\sigma=4\) and any practical value of \(w\).
• We give an \(O(n)\) time and \(O(\ell)\) space sliding-window algorithm to compute the SUS-anchors of a string of length \(n\) that is inspired by the monotone-queue approach (Groot Koerkamp and Martayan 2025).

Smaller contributions that are of possible independent interest are:

• character-based orders that generalize e.g. the lexicographic, alternating (Roberts et al. 2004), and ABB (Frith, Noé, and Kucherov 2020) order; and
• two new character-based orders: the ABB+ and anti-lexicographic order.

Parts of these results have been previously introduced in the author’s PhD thesis (Groot Koerkamp 2025).

2 Preliminaries Link to heading

2.1 Minimizer, sampling, and selection schemes Link to heading

For a more in-depth introduction to minimizers, we refer the reader to the survey by Zheng et al. (Zheng, Marçais, and Kingsford 2023), the mod-minimizer paper (Groot Koerkamp and Pibiri 2024), and the author’s thesis (Groot Koerkamp 2025). Here we briefly introduce the required notation and concepts.

Notation. For an integer \(w\), we write \([w] = \{0, 1, \dots, w-1\}\), and for a string \(W=w_0\dots w_{|W|-1}\) we use \(W[i\dots j)\) to indicate the substring \(w_i\dots w_{j-1}\). We assume an alphabet \(\Sigma\) of size \(\sigma\).

Sampling schemes. Given parameters \(w\geq 1\) and \(k\geq 1\), a window is a string over \(\Sigma\) of length \(\ell=w+k-1\) that contains exactly \(w\) \(k\)-mers. A local sampling scheme or just sampling scheme is a function \(f: \Sigma^\ell \to [w]\) that indicates that from window \(W\), the \(k\)-mer \(W[f(W)\dots f(W)+k)\) is sampled.

Given a text \(T\), we are interested in the set of all sampled positions when sliding window \(W\) over the text. Consecutive sampled positions differ by at most \(w\), and a sampling scheme is forward when the sampled position in \(T\) never decreases when sliding the window forward.

Often considered are minimizer schemes (Schleimer, Wilkerson, and Aiken 2003; Roberts et al. 2004), which are forward sampling schemes that sample (the position of) the smallest \(k\)-mer in the window according to some order as given by a hash function.

Selection schemes. In this paper, we are particularly interested in selection schemes, which are sampling schemes with \(k=1\) (Zheng, Kingsford, and Marçais 2021). In particular, these select a position rather than \(k\)-mer in each window. Given a fixed window (context) of \(\ell\) characters, the \(w=\ell\) selection scheme has greater freedom than an \(w=\ell-k+1\) sampling scheme, and thus can achieve lower density.

Density. The particular density of a sampling scheme is the fraction of positions that are sampled. The density is the expected value of the particular density on a random string with length going to infinity. For forward schemes, the density can be computed as the probability that two consecutive windows \(W\) and \(W’\) (overlapping by \(\ell-1\) characters and together forming a context of \(\ell+1\) characters) sample a different position.

Density lower bounds. A trivial lower bound on the density of sampling schemes is \(1/w\), since at least one in every \(w\) positions is sampled. The best current lower bound for forward sampling schemes (Kille et al. 2024) simplifies (with a small loss of accuracy) to \(\frac 1{w+k} \left\lceil \frac{w+k}w\right\rceil\). For \(k=1\), this gives a lower bound for forward selection schemes of \(\frac1{w+1}\left\lceil\frac{w+1}w\right\rceil = \frac 2{w+1}\). The main insight is that the density equals the expected number of samples in a random cyclic string (cycle) of length \(w+1\), and in any such cycle, at least two different positions must be sampled.

For minimizer schemes, a lower bound is given by \(1/\sigma^k\) (Marçais, DeBlasio, and Kingsford 2018): if \(w\to\infty\), exactly all occurrences of the smallest \(k\)-mer will be sampled, and these occur every \(\sigma^k\) positions in expectation. Note, however, that this bound does not hold for general sampling schemes, and it is exactly this property that will allow us to design near-optimal sampling schemes for small \(k\).

2.2 Bidirectional string anchors Link to heading

Bidirectional string anchors (bd-anchors) are a \(k=1\) selection scheme introduced by Loukides, Pissis, and Sweering for the purpose of text indexing (Loukides, Pissis, and Sweering 2023). Given a window, they sample the (leftmost) start position of the lexicographically smallest rotation. A drawback of bd-anchors is that they are not forward: the window ZABAAC has AAC... as smallest rotation, while the shifted window ABAACA has AAB... as smallest rotation. After further shifting to BAACAY, the smallest rotation is AAC... again: the AB prefix caused the selected position to jump around. To ensure the density¹ is in \(O(1/w)\), reduced bd-anchors (Loukides, Pissis, and Sweering 2023) avoid sampling the last \(r=C\lceil \log_\sigma \ell\rceil\) positions, where \(C=4\) in theory but in practice \(C=3\) or less suffices. Given the choice of \(r>\log_\sigma \ell\), in most windows of a random string the bd-anchor is the same as the smallest lexicographic \((r+1)\)-mer. Note that reduced bd-anchors are still not forward.

In practice, bd-anchors can be computed in \(O(n\ell)\) time by using Booth’s linear-time algorithm for the lexicographically minimal rotation (Booth 1980). An \(O(n)\) time algorithm is possible using a data structure of Kociumaka (Kociumaka 2016), but this is mostly of theoretical interest only since it requires \(O(n)\) words of space for e.g. a suffix array. Theorem 3 of (Loukides, Pissis, and Sweering 2023) gives an \(O(n)\) time and \(O(\ell)\) space algorithm when the alphabet size is constant (\(\sigma = O(1)\)) by using Kociumaka’s method on overlapping chunks of size e.g. \(2\ell\). A practical linear time algorithm to compute reduced bd-anchors with \(r=\lceil 4\log_\sigma w\rceil\) is given by (Ayad, Loukides, and Pissis 2025). This works by first computing the lexicographic minimizers of size \(k=r\) and only comparing the corresponding rotations in case of ties. Additionally, the randomized reduced bd-anchor is introduced that mimics the random minimizer: it considers the smallest \(r\)-mer in a window under a pseudo-random order and breaks ties by preferring the lexicographically smallest rotation. In practice, the density of randomized reduced bd-anchors is indistinguishable from the density of random minimizers.

2.3 Maximal suffixes Link to heading

Separate from the literature on minimizers, there is a line of work on the non-empty minimal suffix and maximal suffix of a string (Duval 1983). While these two problems appear similar, as one might simply reverse the order of the alphabet, a crucial point is that a string \(A\) is always smaller than \(B\) when \(A\) is a prefix of \(B\). Thus, the minimal suffix prefers shorter suffixes, while the maximal suffix prefers longer suffixes. Because of this, minimal suffixes are less stable as we slide a window over a text, and we do not further consider them.

Babenko et al. (Babenko, Kolesnichenko, and Starikovskaya 2013) introduce an algorithm that preprocesses a string of length \(n\) into a linear-space data structure and can then find the maximal suffix of query substrings of length \(\ell\) in \(O(\log \ell)\) time, which was improved to \(O(1)\) query time in (Babenko et al. 2016).

3 Character-based orders Link to heading

To capture some of the existing “lexicographic-like” orders, we define character-based orders that compare strings one character at a time². This is a natural requirement in our setting, because it allows comparing suffixes of a string without worrying that future characters (after shifting the window) will change the order, as long as one is not a prefix of the other.

This scheme encapsulates the lexicographic order on strings, where each \(O_i\) is simply the lexicographic order on \(\Sigma\). The main drawback of the lexicographic order is that it clusters small strings: since AAAAX is small, the next \(k\)-mer AAAXY is also small, possibly causing consecutive positions to be sampled as minimizers. Most of the following schemes instead look for a transition from a small character (A) to a large (Z) or non-small (BCD..Z) character.

The alternating order (Roberts et al. 2004) uses the lexicographic order for even \(i\), and the reverse lexicographic order for odd \(i\), so that AZAZAZ... is the smallest string. The ABB order (Blackburn 2015; Frith, Noé, and Kucherov 2020) uses the lexicographic order for \(O_0\), and for \(i>0\) it uses the order \[1=_{O_i}2=_{O_i}\dots=_{O_i}\sigma-1 <_{O_i} 0,\] so that any string like ABBBB... or AXYZDEF... is minimal. This scheme has the nice property that occurrences of small strings starting in A and not containing further A’s are disjoint (Blackburn 2015). (The concept of sets of minimally overlapping strings has been further explored in (Frith, Noé, and Kucherov 2020), but these do not form a character-based order and do not directly work with variable-length strings.) Vigemers (Ingels, Limasset, et al. 2026) are also a character-based order, where \(O_i\) is the order after xor’ing by a character \(\gamma_i\).

A drawback of the ABB order is that it throws away some information: for example, over the normal alphabet, AB and AC are considered equal. Thus, we also consider a version with tiebreaking, ABB+:

Note that this is only useful when comparing strings (\(k\)-mers) of equal length, and that the ABB+ order is not itself a character-based order.

The following scheme is more practical.

In this order, the smallest string is AZZZZ....

4 Smallest unique substring anchors Link to heading

Intuition. Consider again the bd-anchor, which samples the start position of the smallest rotation of a window \(W\). As we saw in 2.2, a drawback is that rotations “wrap around”, and that the character \(W[0]\) at the start of a string influences whether the rotation starting at the last character \(W[\ell-1]\) is small or not. This is easily fixed by considering only the smallest suffix instead. However, the smallest suffix is the empty suffix, and so we could sample the first character of the smallest non-empty suffix. Unfortunately, this results in a bad density: a random window ends in the smallest symbol \(0\) with probability \(1/\sigma\), in which case the suffix consisting of just this character is the smallest one, and the density will be around \(1/\sigma\) regardless of \(w\). To avoid this, we impose the following restriction (which, in a way, generalizes the “non-empty” condition): a suffix is only allowed to be sampled if it does not occur elsewhere in the window as a substring. Thus, we look for the smallest unique suffix \(W[i\dots)\). Let \(S=W[i\dots j)\) be the shortest prefix of \(W[i\dots)\) that is unique in \(W\). Then \(S\) is the smallest unique substring (SUS³) of \(W\) (Groot Koerkamp 2025). As an example, the string CABBAB has AB as its smallest suffix, and ABBAB as its smallest unique suffix. The smallest unique substring is ABB, and the index of the correspondingly sampled SUS-anchor is 1.

We note that for the purposes of the definition, it would be sufficient to only consider the starting position of smallest unique suffix. Nevertheless, we prefer to consider the smallest unique substring since it has properties that are similar to the \(k\)-mers sampled by minimizer schemes. For example, both optimal-density minimizer schemes and optimal-density SUS-anchors would always sample non-overlapping \(k\)-mers and SUS-anchors respectively.

Variants. Alongside the lexicographic variant, the SUS-anchor allows variants based on character-based orders. Specifically, we consider SUS-anchors with the anti-lexicographic order. These variants work just like the lexicographic version: simply consider the set of suffixes that do not occur as a substring elsewhere, and then take the smallest of these using the chosen character-based order.

MS-anchor. It turns out that the concept of lexicographic smallest unique suffix is exactly equivalent to that of the maximal suffix (Duval 1983; Babenko et al. 2016) after reversing the order of the alphabet: in both cases, we look for the extremal suffix where longer suffixes should be preferred over shorter ones. More generally, for any character-based order \(O\), the SUS-anchor under \(O\) starts at the same position as the maximal suffix when suffixes are compared by the reverse of \(O\). Whereas the SUS-anchor explicitly requires considering a unique suffix, this is handled implicitly by the maximal suffix: when one suffix is a prefix of a longer suffix, the longer suffix is automatically the larger one (regardless of the chosen character-based order \(O\)).

4.1 Properties Link to heading

We now state some observations and then prove some properties of SUS-anchors.

4.2 Computing SUS-anchors Link to heading

Via the equivalence to maximal suffixes, we can compute all lexicographic SUS-anchors using the theoretical algorithm of (Babenko et al. 2016) that requires \(O(n)\) space, \(O(n)\) preprocessing, and supports \(O(1)\) queries for substring suffix-maximum. When the alphabet has constant size, we can use the same trick as for bd-anchors to reduce the space usage: Run the construction algorithm on chunks of size \(2\ell\) that overlap by \(\ell-1\), so that the total space usage is \(O(\ell)\) and the total time remains \(O(n)\).

Below, we first adapt the method of (Babenko et al. 2016) for computing the maximal suffix of each window to our streaming setting. Then, we adapt it to compute SUS-anchors for any character-based order.

A streaming algorithm for the maximal suffix. We first adapt the algorithm of (Babenko et al. 2016) to our streaming setting. Suppose that we have so far processed \(T[0\dots t)\). The algorithm maintains a doubly linked list \(A=(a_0, a_1, a_2, \dots)\) of active text positions \(a_i\) such that \(T[a_i\dots t) > T[j\dots t)\) for all \(a_i < j < t\). This list is decreasing in the sense that \(T[a_0\dots t) > T[a_1\dots t) > T[a_2\dots t) > \dots\), and it plays a similar role to the monotone queue in the classic minimizer algorithm (Groot Koerkamp and Martayan 2025). Unlike that original case, here we also store a list of events for every text position that can modify the middle of the list.

As we shift the window and increment \(t\) to \(t’=t+1\), we remove \(a_0\) when \(a_0 < t’-\ell\). After appending \(T[t]\), we get a new suffix \(T[t\dots t’)\). We update \(A\) before pushing the new element \(t\).

• Repeatedly pop \(A\). We remove the last element \(\last(A)=A_{|A|-1}\) from \(A\) as long as \(T[\last(A)\dots t’) < T[t\dots t’)\).
• Add event. Then, if \(A\) is not empty and \(T[\last(A)\dots) < T[t\dots)\) (taking into account upcoming characters), compute \(\lambda=\lcp(T[t\dots), T[\last(A)\dots))\) and add the event “check if we should drop the element preceding \(t\) from \(A\)” to the event queue for position \(t+\lambda+1\).
• Push \(t\). Then, push \(t\) to \(A\) and increment \(t\) to \(t’ = t+1\).
• Handle event. As soon as \(t’’\) reaches position \(t+\lambda+1\), we check if \(t\) is still in \(A\), and if so, if it has now become larger than its preceding element. Then repeatedly remove the preceding element as long as \(T[t\dots t’’)\) is larger, and end when either there is no preceding element, or when \(T[a_i\dots t’’) > T[t\dots t’’)\). In that case, again check if the order will flip in the future, and if so, add a new event to the event queue.

Practical considerations. To make this practical, all \(\lcp\) computations can be bounded to \(\ell\), and the event queues can be stored in a ring buffer with just \(\ell+1\) slots for the current and next \(\ell\) positions. Originally, the \(\lcp\) computations are done in constant time using the suffix array. Instead, we simply do a word-by-word scan on the bit-representation of the text, which takes expected constant time on random strings since LCPs of, say, over \(64\) bits are unlikely in random strings.

A more direct algorithm for SUS-anchors. We now make some modifications to use the algorithm above for SUS-anchors. Most importantly, \(A\) will now be an increasing list of suffixes, with the smallest at the start, with the caveat that unlike usually a string is considered smaller than all its prefixes. A final modification drops the event queues and allows us to replace the doubly linked list \(A\) by a simple double-ended queue, as shown in \cref{alg}. For each \(a\in A\), we now additionally store the text position \(x_a\) where \(a\) becomes “hot”, i.e., we store that \(a\) becomes the first element of \(A\) (and thus the start of the maximal suffix of the window) when the character \(T[x_a]\) enters the sliding window. When comparing \(t\) to \(\last(A)\), there are three cases.

1. \(A\) is empty, in which case we push \(t\) and set \(x_t = t\).
2. \(T[\last(A)\dots \last(A)+\ell) \leq_O T[t\dots t+\ell)\), in which case we push \(t\) and note that it becomes hot (the smallest suffix) when \(\last(A)\) falls out of the window, i.e., \(x_t = \last(A)+\ell\).
3. \(T[\last(A)\dots \last(A)+\ell) > T[t\dots t+\ell)\): \(t\) “takes over” \(\last(A)\) when character \(t+\lambda\) enters the window, where \(\lambda = \lcp(T[t\dots), T[\last(A)\dots))\).
   • If \(\last(A)\) is already hot by that time (\(x_{\last(A)} < t+\lambda\)), push \(t\) with \(x_t = \min(t + \lambda, a+\ell)\).
   • If not, \(\last(A)\) will never be hot. We pop it and (repeatedly) compare \(t\) to \(\last(A)\).

Once this process finishes, the first element of \(A\) indicates the maximum suffix of the current window. We then increment \(t\) to the next text position and check whether we reached the position \(x_{a_1}\) where the next element of \(A\) becomes hot (either because \(a_0\) falls out of the window or \(a_1\) introduces a new maximal suffix). In that case, we pop \(a_0\).

5 Results Link to heading

In Figure 1, we compare the density of SUS-anchors against the bd-anchors selection scheme as well as minimizer schemes. For the minimizer schemes, we choose the \(k\) that minimizes the density, and we adjust \(w\) to \(w’=w+1-k\) accordingly to preserve the overall window length \(\ell = w’+k-1\). The true density is approximated by computing the particular density on a uniform random string of \(10^7\) characters over alphabets of size \(2\), \(4\), and \(32\). A new independent random string is used for each data point.

Lexicographic minimizers are roughly on-par with bd-anchors, and lexicographic SUS-anchors are slightly better but still far from optimal. Double decycling (Pellow et al. 2023) and the random minimizer appear to converge to density factor \(2\) as \(w\to\infty\) and have similar density. The greedy minimizer (Golan et al. 2025) only performs well for small \(w\) and \(\sigma\), as it requires precomputed orders that are not always available. (We did not implement the logic to extrapolate from smaller orders.) The greedy minimizer is the only scheme that improves over anti-lexicographic minimizers for \(\sigma=2\) and \(\sigma=4\) (excluding very small \(w\leq 6\)).

The anti-lexicographic minimizer consistently improves over the random minimizer and double decycling. The anti-lexicographic SUS-anchors consistently have the best density of all, while also being parameter-free. They get surprisingly close to the lower bound: they are away from the lower bound by less than \(10\%\) for \(\sigma=2\) and less than \(1\%\) for \(\sigma=4\) and \(\sigma=32\). For \(\sigma=32\), the anti-lexicographic sus-anchor is indistinguishable from optimal for all \(w\leq 64\), and improves over the random minimizer that is \(>1\%\) away from optimal here.

Density and throughput on chromosome 19. In Table 1, we compare the density on a random string with the particular density on chromosome 19 of CHM13 (Rhie et al. 2023), which has length \(61.7\) Mbp. Most schemes have slightly worse density on chromosome 19 than on real data. The greedy minimizer has worse than expected performance in both cases, which is likely due to the fact that our parameters are large and require extrapolating from smaller cases. The anti-lexicographic SUS-anchor has the best performance on random data, but on chromosome 19, it is outperformed by the random minimizer and double decyling (Pellow et al. 2023) for \(w=63\).

Additionally, Table 1 shows the obtained throughput of evaluating each scheme on an Intel i7-10750H CPU running at 2.6 GHz. but we note that the implementations have not been optimized for speed. In particular, for bd-anchor we use a very naive \(O(nw^2)\) implementation. Most other methods are \(O(n)\) in practice, as can be seen from the fact that they do not slow down from \(w=31\) to \(w=63\). SIMD-minimizers (Groot Koerkamp and Martayan 2025), an optimized library for computing random minimizers, has a throughput over \(500\) MB/s, which is more than \(10\times\) faster than all of the methods shown here.

Intuition on SUS-anchor density. Low-density schemes sample positions that are as far apart as possible. When sampling \(k\)-mers, this means that ideally each \(k\)-mer does not overlap with the preceding or succeeding sampled \(k\)-mer, or else as little as possible.⁴ Thus, shorter SUS-anchors are beneficial since they are both less likely to overlap and can be the anchor for more consecutive \(k\)-mers.

Taken together, this means that short unique substrings should work well. In particular, the anti-lexicographic order is better than the lexicographic order since it avoids sampling overlapping substrings: in the lexicographic order, consecutive substrings like AAAB and AAB are both small, causing overlapping samples when a window starts with such a string. The anti-lexicographic order prevents this by explicitly preferring a large suffix after removing the first character. A weakness of the ABB scheme is that it needs to sample a relatively long substring before it becomes unique: in a window like ABDDCBA, 6 of the 7 characters (ABDDCB) are part of the ABB-SUS, so that this sample can only cover a few windows. The anti-lexicographic SUS is simply AB instead.

This also explains the effect of the alphabet size: for \(\sigma=2\), on average a substring needs to have length \(\log_2 w\) before it becomes unique. Thus, the SUS-anchors are longer and more likely to overlap. An example of a case where anti-lexicographic SUS-anchors still overlap is given by the consecutive windows ABABABB and BABABBB, with anti-lexicographic SUS-anchors ABABA and ABA. For alphabet size \(\sigma=2\), such cases are somewhat common. For \(\sigma=32\) on the other hand, most characters in the window are unique (for \(w\leq 32\)) and most anchors will consist of only one or two characters (e.g. just A or AZ) and thus rarely overlap.

6 Conclusion Link to heading

We introduced anti-lexicographic SUS-anchors, gave a linear-time algorithm to compute them, and showed that they empirically get to within \(1\%\) of the density lower bound for \(\sigma=4\). They are consistently the lowest density selection scheme of all tested variants, while also being parameter-free. As a second best, anti-lexicographic minimizers also perform better than all other schemes apart from the greedy minimizer.

Future work. More work is needed to prove that, for example, anti-lexicographic SUS anchors have a close-to-optimal density of \(2/(w+1) + o(1/w)\). Given how close to optimal these schemes already are, the fact that exactly optimal schemes are known to exist for small \(w\) (Kille et al. 2024), including manually constructed for \(\sigma=2\) and \(w\leq 12\), the question remains whether “clean”, constant space schemes can be developed for generic \(w\). The spacers of (Shur, Tziony, and Orenstein 2026a) are similar to our own ongoing work, and provide a first step in this direction.

On a practical level, further work is needed to improve the current monotone-queue-based algorithm to a rescan-like approach (Groot Koerkamp and Martayan 2025) or even a branchless variant that could be implemented in parallel using SIMD.

It would also be interesting to use SUS-anchors in combination with the mod-minimizer (Groot Koerkamp and Pibiri 2024). In particular, the mod-minimizer requires a lower bound \(r = \Theta(\log_\sigma w)\) on the length of the chosen minimizers (typically around \(4\) in practice), and it would be interesting to see if “mod-SUS-anchors” can work without such a restriction. More generally, SUS-anchors can be extended to \(k>1\) by simply excluding the last \(k-1\) suffixes, and preliminary results show that this gives good density up to \(k \approx \log_\sigma w\).

Lastly, the SUS-anchor is a forward scheme. It is known that non-forward schemes can be (at least) slightly better at times and break the forward lower bound, but this is not well understood.

References Link to heading