Breaking 2-Cores
for Invertible Bloom Lookup Tables
by Structure Prediction

The Invertible Bloom Lookup Table (IBLT) [19] is an array of $n$ cells, each consisting of a counter and the sum of items hashed into the cell. It is equipped with $\tau$ hash functions that we assume are fully random¹¹1Using fully random hash functions is indeed impossible in practice but needed for most theoretical analyses of IBLTs, with the exception of [14]. Nevertheless, common fast hash functions, such as Tabulation or Murmur3, seem sufficient in practice. ; typically, $\tau =3$. Each element is thus hashed into $\tau$ cells. When inserting (deleting) element $x$, in each of the corresponding $\tau$ cells, we increment (decrement) the counter and increase (decrease) the sum by the element. Assuming the IBLT encodes a set (and not a multiset), the recovery process iteratively searches for pure cells, i.e., only a single element is hashed there, which are those with counter set to 1 (or -1). The recovery process succeeds with high probability if there are at least $\approx 1.22$ times more table cells than encoded items. As outlined in Section 1.1, there are multiple variants of the IBLT, and we only describe those required in our work.

The variant analyzed in [21, 3], denoted IBLT-xor, only stores the XOR of (binary representations of) all items hashed into each cell; thus, one cannot store multisets, since a repeated insertion leads to deleting the element. That is, insertions and deletions are both just toggling the element’s presence in the encoded set. While storing just the XOR of items requires just one memory word per cell, compared to two memory words of the original variant [19], it leads to more “anomalies”, such as buckets with multiple items that look “pure” (i.e., as if a single element was hashed there). Nevertheless, the same bounds on the number of cells for successful recovery apply also to IBLT-xor. As we focus on recovering sets, we will use IBLT-xor in this paper.

To reduce the effect of anomalies, and also deal with deleting items that were not inserted, one may also store the sum of checksums of items hashed into the cell [19]. Here, we assume that the checksums are computed by an additional hash function and have enough bits so that the probability that any sum of checksums of items in one cell collides with the checksum of another encoded element is negligible, i.e., no collision in checksums occurs over the whole recovery process with high probability.

A hypergraph $H$ is a pair $(V,E)$, where $V$ is a set and $E$ is a set of hyperedges, which are subsets of $V$. The hypergraph is $r$-uniform if all edges have exactly $r$ vertices. An $\mathrm{\ell }$-core in $H$ is the largest sub-hypergraph of $H$ (possibly empty) where all vertices have degree at least $\mathrm{\ell }$ (the degree of a vertex $v$ is the number of hyperedges containing $v$). The $\mathrm{\ell }$-core can be found by a process called peeling which iteratively removes vertices of degree below $\mathrm{\ell }$ together with edges containing these vertices, until no vertex remains or we get the $\mathrm{\ell }$-core. Note that an IBLT with $\tau$ hash functions corresponds to a random $\tau$-uniform hypergraph by taking cells as vertices and for each encoded element, there is a hyperedge with all cells containing the element. Then peeling this hypergraph to find a 2-core is the same process as recovering the encoded set, provided that we can find a pure cell if there is any. The IBLT recovery thus succeeds only if there is no 2-core in the hypergraph.

Since we study a beyond worst-case setting, we consider sets encoded into an IBLT that have some internal structure. Informally, we assume that the set consists of a relatively small number of “components” consisting of “related” elements, where the relation gives predictions. For example, if recovering a set of integers, we may assume that the set consists of intervals of average length at least a parameter $m>1$, while two different intervals may be completely unrelated. In the case of $k$-mers, the components are exactly the weakly-connected components of the de Bruijn graph of the $k$-mer set. In general, the notion of components needs to be specified for each application of our framework.

Although $1.23$ is a fairly small multiplicative constant, close to the information-theoretic bound of 1, our estimate for the number of lost packets can be off, and the algorithm may fail. Failing means that there exists a $2$-core in the underlying hypergraph. We would like to overcome such a situation, even though in general, the factor of $\approx 1.22$ is tight for IBLTs as the recovery process for $m$ items fails with high probability with a smaller factor. Nevertheless, considering the example and its specific assumptions, namely, whether packets $a$ and $a+1$ are missing is correlated, we attempt to make progress in the recovery process. The main idea is to use already recovered packet IDs to guess the packet IDs still encoded in the sketch.

Specifically, suppose that we recovered $a$ but not $a+1$. We make a guess that $a+1$ is also in the sketch and remove $a+1$ from the sketch, even though there is no pure cell with $a+1$. If it was indeed in the sketch, then we decrease the degrees of three vertices in the underlying hypergraph (i.e., the number of items hashed into three cells of the IBLT). Then either some degree gets to one and we may continue with the standard IBLT recovery, or we need to make another guess as we have not broken the $2$-core yet. We continue until the sketch gets empty or we make too many guesses.

However, some of our guesses may be wrong. Suppose that we guessed $a+1$ and removed it from the sketch, although it is not in the encoded set. If the recovery process successfully continues, at some point we recover $a+1$ and find out that our guess was incorrect, allowing us to remove $a+1$ from the resulting set. However, wrong guesses do not help and, in fact, make the table more full. Thus, after a predefined number of steps, we revert the guesses by adding them back to the table and make other guesses.

The packet recovery problem serves only as an illustrative example, since this approach has wide applicability for improving space efficiency of IBLTs over structured data. Our main application is recovering $k$-mers from a symmetric difference of closely-related genomes. Specifically, our assumption is that the symmetric difference consists of paths of length at least $k$ in the de Bruijn graph, corresponding to a string of length $2k-1$. Note that if there is a mutation of a single base, two paths of length $k$ occur in the symmetric difference (assuming no $k$-mer repeats).

We provide two predictors for $k$-mers: First, the next-in-sequence predictor, which given a single recovered $k$-mer, extends it either to the left or to the right by one base and removes one base at the other end. For example, if we recovered a $4$-mer ACTG, then we predict CTGA, CTGC, CTGG, CTGT, AACT, CACT, GACT, and TACT (here, we do not consider reverse complements for simplicity), expecting that for most recovered $k$-mers, at least one predicted $k$-mer would also be encoded in the sketch. Thus, for $k$-mers, there is an additional challenge of a much higher chance of guessing wrong elements.

Second, a stronger prediction may be achieved by considering more recovered elements at once. For instance, suppose that we recovered 8-mers AAAACCCC and ACCCCTTT. Then it is likely that 8-mers AAACCCCT and AACCCCTT are also part of the symmetric difference, since we assume that the symmetric difference consists of long sequences and that one of the sequences contains AAAACCCCTTT. In other words, we use that the de Bruijn graph of the encoded set likely contains the whole path from AAACCCCT to AACCCCTT. Thus, such a path predictor takes two $k$-mers $Q_1,Q_2$ with an overlap of $k-\mathrm{\ell }$ for and predicts all $k$-mers on the shortest path from $Q_1$ to $Q_2$ in the complete de Bruijn graph (i.e., the graph containing all possible $k$-mers); when choosing the input $k$-mers $Q_1,Q_2$, the preference is given to $k$-mers with larger overlap. The path predictor makes potentially less wrong guesses (at least when the overlap is close to $k-1$), but suffers from worse time complexity to produce all predictions for recovered $k$-mers. Specifically, given a set of recovered $k$-mers, we run the following to produce predictions of $k$-mers: We list pairs of $k$-mers sorted by their overlap such that for every $k$-mer $L$, we only take a $k$-mer $R$ that has the largest overlap with $L$, and for each such pair, we use the path predictor. This can be implemented in $O(k\cdot n)$ time; see Appendix B for details.

We outline the algorithm for recovery with the next-in-sequence predictor. Given a parameter $\beta$, it runs in $\beta$ iterations of “core breaking steps”, and in each iteration, it takes all already recovered elements and applies the predictor on each of them, which yields a set of predicted elements; for efficiency reasons, we only take a subset $B$ of predicted elements and toggle the selected elements in the IBLT-xor (we assume that we use IBLT-xor). We continue with the standard recovery algorithm for at most $\gamma$ steps, for a parameter $\gamma$, and then toggle the elements in $B$ in the IBLT, reverting the guesses. Then we again run the standard recovery algorithm until the IBLT is empty or there is no pure cell. Note that bounding the number of core-breaking steps by a parameter $\beta$ prevents infinite cycles in the recovery, which may happen for IBLT-xor [21].

We describe this method for recovery with predictors in an abstract setting in more detail in Section 4.1, and prove that even a weak matching-based predictor already achieves a ratio $\rho \approx 0.785$ in Section 4.2. We also analyze it experimentally in Section 5 where we show that it achieves even better improvement in practice for $k$-mers of real-world data.

Although recovery with (potentially wrong) predictors already achieves our main goal, it has certain drawbacks: First, as reported in Section 5, recovery with predictors can be quite time consuming due to trying many guesses that may often be wrong or due to the time complexity of the predictor itself (such as the path predictor). Note, however, that more time for recovery is only needed when the original IBLT without predictions does not succeed, as there are no overheads if full recovery is possible without the predictors.

Second, we do not fully utilize the structure. Suppose that we are recovering a de Bruijn graph of a $k$-mer set $A$ encoded in an IBLT. Thus, if the average size of a component is $m$, it seems plausible to use an IBLT of size $\mathrm{\Theta }(|A|/m)$ enhanced with an appropriate recovery procedure and small supporting data structures. However, the algorithm with predictors outlined above does not achieve such a scaling property, neither in theory (see Section 4), nor in practice (see Section 5). On the other hand, the primary advantages of Algorithm 1 are simplicity and the fact that the IBLT and its update procedures require no changes, as we only enhance the recovery.

We address the drawbacks of the previous algorithm, under the assumption that the universe size $|𝒰|$ is substantially larger than the encoded set size $|A|$, specifically that ${\log }_2|𝒰|\gg 2{\log }_2|A|$. As a primary example, we take $k$-mers with not-too-small $k$, and the assumption on $𝒰$ translates to $k\gg {\log }_2|A|$; here, we solely focus on $k$-mers for simplicity but the techniques can be used in other applications. We again suppose that the $k$-mer set consists of de Bruijn graph components of size at least $k$. The goal is to achieve scaling with $k$, namely that space per $k$-mer needed for successful recovery should not increase with increasing $k$.

The first idea is to subsample the encoded set $A$ so that at least one $k$-mer is selected from most components of the underlying de Bruijn graph. A general way to do it is using a hash function $h:𝒰\to [0,1]$, and only insert $k$-mers that hash below a specified threshold $r$; for example, for recovering symmetric differences of $k$-mers that resulted from a set of mutations, a reasonable choice is $r=\log (n)/k$ as it ensures selecting one $k$-mer from each path of length $k$ with high probability and as this choice does not affect the final asymptotic space complexity of our approach. There are better subsampling techniques for $k$-mers, such as selecting all syncmers [10] as they guarantee selecting one $k$-mer from each component and have subsampling rate approaching $2/k$ for large $k$. The subsampled set may be encoded into a common IBLT $T_S$ that does not (and cannot) use predictors as sampling destroys the structure but has size substantially smaller than the (non-subsampled) set $A$. With IBLT-xor for the subsampled elements, we need $\approx 1.22\cdot r\cdot |A|\cdot 2k$ bits for $T_S$ in expectation, which is $\approx 4.88\cdot |A|$ bits for the subsampling rate $r=2/k$ with syncmers for large $k$.

However, even if we can get one or more elements from each component of $A$ from $T_S$, it is not sufficient to recover all of the components of $A$ by using predictors as they would often provide wrong guesses for elements in $A$. We thus add a low-space approximate membership data structure, called hash filter, that will approximately represent the encoded set in smaller space, with sufficiently low false positive and false negative probabilities. To implement the hash filter, we again employ an IBLT-xor $T_H$ but, to save space, on fingerprints, computed by a universal hash function, instead of on the original elements²²2Alternatively, one may use a variant of Counting Bloom Filter (CBF) [13] in which the $b$-bit counters do not freeze when they reach the highest value but instead, we count modulo $2^b$. Note that such a variant of CBF has false negatives. We leave an analysis of this variant to future work. . These fingerprints are of size $2{\log }_2(|A|)+3$ bits so that the probability of a hash collision is small enough, namely at most $1/(8{|A|}^2)$. $T_H$ thus stores $|A|$ fingerprints but since we assume ${\log }_2|𝒰|\gg {\log }_2|A|$, these fingerprints are much smaller than the original elements. The total required size of $T_H$ is thus $\approx 1.22\cdot |A|\cdot 2{\log }_2(|A|)$ bits; note that the multiplicative constant may be improved by employing predictions for recovering fingerprints.

The nearly perfect predictor $\widehat{P}$ uses a (potentially wrong) predictor $P$ as a black box, such as the next-in-sequence. We assume that $P$ generates at most $\lambda \in O(1)$ predicted elements. Then $\widehat{P}$ works as follows: To guess the next element, $\widehat{P}$ asks $P$ for prediction of elements, given what is already recovered, which yields a set $B$, and then queries the hash filter for each element of $B$. The predicted $k$-mers whose fingerprints are in $T_H$ are added to the set of recovered elements. Let $A^{\prime }$ be the set of recovered elements using $T_S$ and $T_H$.

Note that $\widehat{P}$ may still give incorrect predictions due to false positives and false negatives of the hash filter, and we analyze their probabilities. First, a false positive may occur if there is a hash collision in the fingerprints between a $k$-mer from $A$ and a predicted $k$-mer; due to the setup of fingerprints, such a collision happens with probability $1/(8{|A|}^2)$ and thus, over all steps, only $O(1)$ false positives occur with high probability. Second, a false negative may occur if the recovery of $T_H$ fails or if there is a hash collision in the fingerprints among an even number of $k$-mers from $A$, which then cancel out in IBLT-xor; overall, there are again $O(1)$ false negatives with high probability. Furthermore, the subsampling step may, in general, miss some components, unless we use syncmers for $k$-mers or a similar method that guarantees a sample from each component.

Thus, $A^{\prime }$ may not contain all $k$-mers of $A$ and may have some additional elements not in $A$. We thus use IBLT-xor $T_E$ of a small size, sublinear in $A$, to correct such errors, given that the analysis above shows that the number of additional or missing $k$-mers, that is, $k$-mers in the symmetric difference $A\mathrm{\Delta }{A}^{\prime }$, is $O(1)$ with high probability. Despite that this IBLT is small, it encodes all elements of $A$ but we toggle $A^{\prime }$ after running the recovery of $T_S$ and nearly-perfect predictor $\widehat{P}$. Then only $k$-mers in $A\mathrm{\Delta }{A}^{\prime }$ remain in $T_E$. Thus, even with $T_E$ of constant size, we can recover $A\mathrm{\Delta }{A}^{\prime }$ and get $A$.

Concluding the discussion above, our second proposed algorithm for recovery with predictors contains three IBLT tables:

$T_S=$

IBLT-xor containing subsampled elements from the set $A$ that we aim to recover.

$T_H=$

IBLT-xor containing fingerprints of all elements in $A$, where the fingerprints may be given by a universal hash function.

$T_E=$

IBLT-xor for correcting errors.

Then, given a predictor $P$ and the three tables, the recovery process goes as follows:

1. 1.

   Recover the subsampled set $S$ from $T_S$.

2. 2.

   Recover the set of fingerprints $F$ from $T_H$.

3. 3.

   Expand $S$ by using the nearly-perfect predictor that gets elements from $P$ but only adding those with their fingerprint in $F$.

4. 4.

   Correct errors as follows: Let $A^{\prime }$ be the set obtained from the first three steps. Toggle $A^{\prime }$ in $T_E$ (i.e., toggle the presence/absence of each element from $A^{\prime }$). Then call the recovery on $T_E$, which, if it succeeds, provides exactly the elements in $A\mathrm{\Delta }{A}^{\prime }$.

The recovery of any of the three tables may fail, but we set up the parameters so that all recovery steps succeed with high probability. Overall, the memory consumption of this approach, up to asymptotically smaller terms, is $\approx 1.22\cdot (4+2{\log }_2(|A|))\cdot |A|$ bits, compared to $\approx 1.22\cdot 2k\cdot |A|$ bits with IBLT-xor using no predictors.

We have implemented IBLTs and the recovery procedures in several C# libraries, which are available at GitHub (links provided on the title page). The experiments with Algorithm 1 were conducted using Yak, a console wrapper for the main library SymmetricDifferenceFinder that provides the IBLT-xor (denoted HPW there) and IBLT with checksum data structures and implements Algorithm 1 for recovery with predictors. The method of three tables is provided in Halina. We implemented several common hash function families (tabulation, linear congruence, polynomial, multiply-shift) in library FlashHash; the experiments below use $\tau =3$ tabulation hash functions. Finally, processing $k$-mer sets is done via their masked superstrings [34] in library KMerUtils.

Our implementation requires .NET version 9.0 or higher. We used advanced $C\mathrm{\#}$ features to gain performance, most notably runtime compilation using expression trees to recompile the code for the parameters given, such as the randomly selected parameters of hash functions. To achieve a certain level of type safety with expression trees and to make coding with them less error-prone, we provide a wrapper around expression trees called LittleSharp. These features allowed us to encode 31-mers of the human genome in less than 100 s with an IBLT of size 134M. The experiments were run on Intel Xeon E5-1620 (4 cores, 3.8 GHz) and 62 GB RAM.