<p>Here's one possible approach.</p>

<p>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.)</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

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

<ul>
<li><p>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$.</p></li>
<li><p>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|$.</p></li>
<li><p>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$).</p></li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2013-07-24T18:33:23.263Z
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.
Simd
CC BY-SA 3.0
2013-07-24T18:15:02.240Z
2013-07-24T18:59:07.330Z
2013-07-24T18:59:07.330Z
D.W.
<p>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.</p>

<p>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?</p>

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

<ds.data-structures><cg.comp-geom>
Bloom filter for predecessor queries?
Simd
# Bloom filter for predecessor queries?

(Asked by: username_0 on 2013-07-24)

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.

**Tags:** ds.data-structures, cg.comp-geom


---

## 1 answers

### Answer by username_1 on 2013-07-24. Score: 1

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.

> **Comments:**
> **username_0**: 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.  

---

