2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – felix Jul 24 '13 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.