# Bloom filter for predecessor queries?

Given a threshold $k$ is it possible to make a succinct data structure $S$ to answer queries of the form, given query $x$ does there exist a value $s$ in $S$ such that $s-k \leq x \leq s+k$? Like a Bloom filter it would allow rare false positives and would only report yes or no.

To clarify a little, I am looking for a data structure that uses much less space than a binary search tree would but with comparable or better performance. Also, what is theoretical minimum space for a randomized data structure for this problem with a given false positive rate?

Another related problem is (1d) emptiness queries in computational geometry but in our case the range is fixed in advance.

Here's one possible approach.

For a fixed value $b$, it's easy to build a Bloom filter that stores a set $S$ of values and lets us answer queries of the form "is there any $s \in S$ such that $s \in [x,x+2^b-1]$?", where $x$ is a parameter of the query and is constrained be a multiple of $2^b$ (in other words, the ranges are $2^b$-aligned and are of length $2^b$). (How do you do that? Store $\{\lfloor s/2^b \rfloor : s \in S\}$ in a regular Bloom filter.)

Now, for a value $x$, you can decompose the range $[x-k,x+k]$ into a union of $O(\lg k)$ ranges of the above form.

So, our succinct data structure will be composed of multiple Bloom filters: one Bloom filter for each non-negative integer $b$. We store a copy of $S$ in each of those Bloom filters. To answer the query "is there any $s \in S$ such that $s \in [x-k,x+k]$?", we decompose $[x-k,x+k]$ into $O(\lg k)$ ranges that are $2^b$-aligned, and then we make the appropriate queries to the component Bloom filters. Since we increase the number of queries by a factor of $O(\lg k)$, the false positive rate doesn't increase too much. In fact, I think you can show that you will only need to make at most 2 queries to each component Bloom filter (i.e., the constant hidden by the big-O notation is at most 2), so I expect this should work pretty well in practice.

Note that this data structure actually allows you to generalize even further: $k$ does not need to be fixed in advance; it can instead be specified as part of the query.

I would expect this data structure to be a little bit more compact than a binary search tree, but not a lot.

• A binary search tree uses $\Theta(|S| \lg \max(u,|S|))$ space, where $u$ is an upper bound on the largest value that can be stored in $S$.

• In contrast, for a fixed $k$, my data structure uses $O(|S| \lg k)$ space. This is a little bit smaller, if $k \ll u$ or $k \ll |S|$.

• Also, if $u \approx |S|$, then my data structure is more compact still: it uses $O(|S|)$ space (due to collisions, the Bloom filter for $b$ only needs to able to hold up to $u/2^b$ items and thus can be stored in $O(u/2^b)$ space; note that $u + u/2 + u/4 + \dots \le 2u$).

At this point the constants are likely to matter, so you might need to try out some implementations to see if my approach is truly better than a binary search tree in practice. You might also want to compare to storing the elements of $S$ in sorted order and answering queries using binary search over that list.

• Thank you for the update. I meant to ask if your solution with log Bloom filters is more compact than a standard binary search tree. That is the standard non compact data structure. – felix Jul 24 '13 at 18:33