Blocked Bloom Filters with Choices

A Bloom filter consists of an array of $m$ bits (initially all zero) and $k$ independent random hash functions from a universal family, $f_1,\mathrm{\dots },f_k:𝒰\to [m]:=\{0,\mathrm{\dots },m-1\}$, mapping the universe $𝒰$ of possible keys to bit addresses. To insert a key $x\in 𝒰$, we set all bits $f_1(x),f_2(x),\mathrm{\dots },f_k(x)$ to 1. To query the membership status of $x$, we return the logical and (product) of these bits, ${\bigwedge }_{i=1}^k{f}_i(x)$. If $x$ is a key that was never inserted, and the load factor (fraction of 1-bits) at query time is $p_1$, then the probability of a false positive equals the probability that all queried $k$ bits are 1 (set by previous insertions), which is $p_1^k$.

The size $m$ of the Bloom filter is chosen such that after inserting $n$ keys, the (expected) load is $p_1=1/2$, making the bit array incompressible and yielding an FPR of $2^{-k}$. To compute $m$, we note that $p_1=1/2$ is equivalent to $p_0:=1-p_1=1/2$ (fraction of unset bits). By the law of large numbers (with $n,m$ in the millions or billions), this (random) fraction is tightly concentrated around its expected value, which equals the probability that any fixed bit is not set. A bit is not set if it was never chosen by all $nk$ bit set operations; so the probability for this event (for large $m,n,k$) is

Solving $p_0=1/2$ for $m$ yields $m=nk/\ln (2)\approx 1.443nk$; hence the well-known space overhead factor of $C\approx 1.443$, independently of $k$.

The assumption behind the calculations above is that the $k$ hash functions behave as if they select $k$ distinct but otherwise independent random bit addresses. In practice, one can simply choose $k$ random functions from a sufficiently large family of simple hash functions. In very rare cases, two (or more) bit addresses may coincide, such that we effectively set or query less than $k$ distinct bits for a very small number of keys; this effect is so small that it has no measurable influence on the FPR when $m$ is large and $k$ is a small constant. However, this consideration can be important for Blocked Bloom filters.

A Bloom filter may be overloaded without failing completely. In that case, its FPR increases beyond the desired value. The expected fraction $p_1=1-p_0$ of set bits can be computed from Eq. (1) by replacing $n$ by $\gamma n$ with the appropriate overloading factor $\gamma >1$, yielding $p_1=1-p_0^{\gamma }=1-2^{-\gamma }$, and the resulting FPR is concentrated around

showing the smooth dependence of the FPR $\epsilon$ on the overloading factor $\gamma$. For example, for 10% overload ($\gamma =1.1$) and $k=10$, we obtain an FPR of roughly twice the desired one ($1.912\cdot 2^{-10}$ instead of $2^{-10}$). Conversely, when we query an underfull Bloom filter, the FPR is better (lower) than the desired one.

The $k$ random memory accesses (cache misses) for each insertion or query into a Bloom filter can lead to low throughput, even though modern optimizing compilers and the prefetching capabilities of current CPUs may counteract these effects to some degree. The idea behind Blocked Bloom filters [16] is to access not $k$ randomly distributed bits, but $k$ bits in close proximity, i.e., in the same block. Ideally, a block corresponds to a cache line (typically 512 bits; for simplicity of presentation, we will use this constant value throughout this article). Therefore, a Blocked Bloom filter consists of $m=512M$ bits, divided into $M$ blocks of 512 bits, a block address hash function $h_1:𝒰\to [M]$ and a number $k$ of independent bit address hash functions, randomly chosen from a universal family, $f_1,\mathrm{\dots },f_k:𝒰\to [512]$.

The obvious advantage of a Blocked Bloom filter over a standard Bloom filter is the increased speed, especially for low FPRs (high values of $k$). However, there is also a substantial disadvantage. For the same size as a Bloom filter, the overall FPR of a Blocked Bloom filter is higher due to two reasons: First, the $M$ blocks have different loads. Blocks with only few remaining unset bits have a high local FPR, while blocks with many remaining unset bits have a low local FPR. On average, because of Eq. (2) and Jensen’s inequality, the blocks with high load increase the average FPR more significantly than blocks with low load decrease it. The surplus FPR caused by inhomogeneity increases with $k$; see Section 4 (Figure 4) for concrete numbers. The effect can be compensated by using more bits (hash functions) per key and/or more blocks, thus increasing the space overhead (but maintaining the desired FPR). Second, when independent random hash functions are chosen, the probability of a bit address collision with $k$ out of 512 can be substantially high, such that in several cases, only bits are effectively queried, increasing the FPR from $p_1^{-k}$ to $p_1^{-k^{\prime }}$. This effect can be compensated by choosing the bit addresses not independently, but in a way that ensures distinct addresses (see Section 3.3), at the cost of higher insertion and lookup times.

Therefore, while offering a speed advantage over standard Bloom filters, Blocked Bloom filters either yield undesirably higher FPRs or need more space. We wondered whether it would be possible to design a variant of Bloom filters that offers close to the same speed advantage without incurring these penalties.

The idea behind the BlowChoc filter is that it works like a Blocked Bloom filter, but there are two (or more) independent choices for the block. The bits for a key may be set in either block. When querying the key, both blocks are examined, and the answer True is returned if all queried bits are set in at least one of the blocks. In contrast to Cuckoo and Quotient filters, data of inserted keys is never moved after insertion.

At first sight, the idea of BlowChoc filters seems to be disadvantageous: By querying two locations, the FPR approximately doubles from $\epsilon$ to $\epsilon +\epsilon -{\epsilon }^2\approx 2\epsilon$, and accordingly almost triples for three choices. On the other hand, having a choice between two or more blocks allows us to choose the block where the insertion requires setting fewer new bits, reducing the load factor overall, and balancing the load better between the blocks. Together, these possibilities can reduce the FPR overall or the required space overhead for the same FPR. The question is whether in the possible design space there is an insertion strategy that results in an overall advantage.

The main idea and the differences in comparison to a Blocked Bloom filter without choices are illustrated in Figure 2. As for a Blocked Bloom filter, there are $M$ blocks and $m=512M$ bits in total. There are two block address hash functions $h_1,h_2:𝒰\to [M]$ and $k$ bit address hash functions $f_1,\mathrm{\dots },f_k:𝒰\to [512]$. From the existing bit pattern in blocks $h_1(x),h_2(x)$ and the bit addresses to be used for key $x$, given by the set

the costs $C_1,C_2$ of setting the bits indexed by $F(x)$ in either block are computed, and the insertion into the block with lower cost is performed. A cost function to compute $C_1$ and $C_2$ is described in Section 3.2. Note that is possible if some of the bit addresses collide (see Section 3.3).

This basic idea can be generalized from two choices to $c\ge 2$ choices, with the disadvantages of increasing cost evaluation time during insertion and increasing query time, especially for unsuccessful lookups, where all choices have to be examined.

Whether more choices lead to a higher or lower overall FPR depends on whether the multiplied FPR can be compensated for by better load balancing and an overall lower load. Assuming idealized conditions (distinct bit addresses, homogeneous load in every block), we may ask for the maximally allowed load (number of set bits out of 512) in every block to achieve the desired FPR of $2^{-k}$ if the filter size is the same as for a standard Bloom filter. Figure 3A shows this maximum allowed load for different choices $c$ (colors) and different $k\ge 3$ (x-axis). Especially for small $k$ (a large FPR of $2^{-k}$), the allowed load in each block is considerably smaller for several choices than for Blocked Bloom filters without choices (i.e., one choice). We therefore need to carefully design a cost function that allows us to achieve both lower loads on average and more balanced loads (ideally constant load per bucket). It also seems reasonable to expect that the design works better for larger values of $k$.

When selecting a block, we have two simultaneous goals, which may contradict each other: On the one hand, we desire a small local FPR (equivalently, a small fraction of set bits within the block). On the other hand, we desire to set as few additional bits as possible (equivalently, to re-use as many already set bits as possible), keeping the overall load and FPR small. Therefore, we experimented with different cost functions for selecting the best block for insertion among the choices $h_i(x)$, $i=1,\mathrm{\dots },c$ for a given key $x$.

First and foremost, if one of the possible blocks already has all bits of index set $F(x)$ from Eq. (3) set to 1, we do not need to change anything, as a query for $x$ already returns True; so the following considerations do not apply.

All reasonable cost functions we invented are based on the following properties of a block:

• $\mathrm{■}$

  $j$, the total number of bits that would be set in the block after insertion,

• $\mathrm{■}$

  $a$, the number of bits that would have to be newly set in the block.

In other words, if $F(x)$ is the set of bit addresses for a key $x$, and $F^{\prime }$ is the set of already used bits in the block under evaluation, then $j=|F^{\prime }\cup F(x)|$ and $a=|F(x)\setminus F^{\prime }|=j-|F^{\prime }|$.

When comparing two blocks whose load increases beyond $1/4$ (128 of 512 bits set), we penalize more and more steeply the number $j$ of total set bits in comparison to $a$. In an almost empty block, however, parameter $a$ should be decisive. After experimentation with different cost function forms (with mixed success; see Appendix A), we decided to use the following exponential form with a base parameter $\beta >0$:

We evaluate different values of $\beta$ systematically in Appendix C, together with other cost function types and with different bit selection strategies, which we describe next.

We describe alternatives for selecting the set of bit addresses $F$ given by Eq. (3). The two strategies that we consider are called random and distinct and described here.

We have implemented BlowChoc filters with two and more choices and re-implemented Blocked Bloom filters (equivalent to BlowChoc filters with one choice without cost evaluation) and standard Bloom filters. Our implementation is available via GitLab (see abstract). We now discuss several details and optimizations, including parallelization.

We created datasets of $2\cdot {10}^9$ random 64-bit integers. To compute the empirical FPR, we query $N=2\cdot {10}^9$ keys that were not inserted into the filter and count how often the filter erroneously returns True ($W$ times). The estimated FPR is then $W/N$. The selected number $N$ allows reasonably accurate empirical evaluations up to $k=20$. While the FPR could also be computed theoretically from the load histogram of the blocks, the empirical approach has the advantage that it also captures potential problems with the hash functions or with randomization.

To benchmark insertion and query throughput, we created different datasets, each containing random 64-bit integers. We configured all filters to have a size of 2 GB ($m=16$ Gbits) and inserted $n=\lfloor m\cdot \ln (2)/k\rfloor$ keys to build a filter with a target FPR of $2^{-k}$. We measured insertion times, successful lookup times (for previously inserted keys) and unsuccessful lookup times for Bloom, Blocked Bloom and BlowChoc filters with 2 and 3 choices and both bit selection strategies.

Figure 5 shows the throughput in million keys per second (wall time) for different numbers of inserter threads and different values of $k$ using the mean of three runs. As expected, the throughput of all filters increases in principle with the number of threads. Note that, for insertions, the number of threads shown corresponds to the number of subfilters, but we use one additional thread for file reading, and one for distributing the keys to the inserter threads; hence 15 inserter threads actually means 17 running threads, one more than cores on the CPU, explaining the slight decrease in throughput above 14 inserter threads.

As also expected, insertions (column A in Figure 5) are generally slower than queries (columns B and C): If the key is not already contained, one of the blocks (cache lines) has to be re-written. In addition, BlowChoc filters must evaluate the cost function for all blocks during insertion.

The distinct bit selection strategy is comparably fast to the random strategy for smaller $k$ but considerably slower for large enough $k$ (bottom row of Figure 5). This difference is caused by the additional computational overhead of ensuring distinct bits, which includes an implicit sorting step. Since the cost for the sorting step increases with $k$, the gap widens notably for increasing $k$. Given the small FPR differences between the random and distinct bit selection strategies (Figure 4), the random strategy seems to be of higher practical relevance.

Given the characteristics of standard and Blocked Bloom filters and BlowChoc filters, the following picture emerges: For small $k\le 3$ (FPR $\ge 1/8$), standard Bloom filters can be used. If speed is paramount and $3\le k\le 7$, or if memory usage is of no concern in case of larger $k$, Blocked Bloom filters are the method of choice. For larger $k>7$, if available memory is limited, Blow2Choc filters offer a good compromise, requiring memory comparable to standard Bloom filters, but offering higher throughput.

Considering in addition the other filter types permitting online insertions (Cuckoo, Quotient, Vector Quotient filters; not evaluated here), one may ask whether there are realistic real application cases for BlowChoc filters. We see such a scenario in genomics, where we represent either a reference genome (DNA sequence, a string over alphabet ACGT) or an individual sequenced sample as billions of distinct short fragments of DNA, each being $q$ nucleotides long, often $21\le q\le 31$. These so-called $q$-grams can be encoded as 64-bit integers and stored as an approximate set using a probabilistic filter. Clearly, the space consumption (for a given desired FPR) matters. The Bloom filter family is useful because the space overhead factor is predictable (near 1.44, higher for the Blocked Bloom filter). The non-Bloom filter types may have both lower and higher overhead factors (cf. Figure 1), depending on circumstances, making them more uncertain candidates in automated workflows.

As an example, we store several species’ reference genomes as 31-gram sets in Bloom-type filters: the fruit fly Drosophila melanogaster (122 million keys), the human Homo sapiens (2.5 billion keys) and the axolotl Ambystoma mexicanum (17.7 billion keys). Table 1 shows wall-clock build times and required space when using $k=14$ for an FPR of $2^{-14}$ with 9 inserter threads. While the Blocked Bloom filter is always fastest and the Blow3Choc filter always requires the least memory, the Blow2Choc filter is a good compromise: For the large genomes, the build time is roughly 1.5 times that of the Blocked Bloom filter, but only half of that of the standard Bloom filter, while using memory comparable to standard Bloom and Blow3Choc filters. This can make a difference if one has, say, a system with 48 GB of RAM and wants to work on the axolotl genome.

As another example, recent work on xenograft sorting [20], concretely separating DNA reads from a mixture of mouse tissue and human tumor cells (engrafted in mouse tissue) may benefit from Blow2Choc filters by replacing the exact human/mouse $q$-gram representations with approximate ones with an FPR of $2^{-16}\approx 1/\mathrm{65\hspace{0.17em}000}$. The size would reduce for $q=27$ from the reported 17.3 GB to 13.3 GB, enabling the use of the application on a 16 GB multi-core laptop. Detailed trade-offs would have to be evaluated in future work.

Furthermore, in genomics applications, the exact number of $q$-grams to be stored is usually not known in advance, although rough estimates can be given, e.g., we know that the human and comparable mammalian genomes have approximately $2.5$ billion $q$-grams for $q$ in a reasonable range around 31. In such a situation, the Bloom filter family has advantages over the other filter types in Figure 1, which would fail if dimensioned too small, whereas the Bloom-type filters can be slightly overloaded at the cost of slightly increasing FPRs.