Integer set disjointness query on sketches with something like homomorphic hashing

Question

Suppose I have two sets of integers $A$ and $B$ and I have a sketch data structure described by a function $\mathsf{sketch}_n : \mathcal{P}(\mathbb{Z}) \to 2^n$ that returns a bitstring of size $n$. These sketches can be checked for disjointness with a function $\mathsf{disjoint}_n : 2^n \times 2^n \to 2$, where if $\mathsf{disjoint}_n(\mathsf{sketch}_n(A), \mathsf{sketch}_n(B)) = 1$, then $A \cap B = \emptyset$ (but $A \cap B = \emptyset$ may also be true when $\mathsf{disjoint}$ returns 0, i.e.: no false positives).

This can easily be accomplished with a bloom filter, where $\mathsf{sketch}_n$ is the result of inserting each element of the set into a bloom filter and $\mathsf{disjoint}_n(x, y) = (x \,\&\, y) \equiv \mathbf{0}$ ($\&$ being bitwise AND).

Now, suppose that I want there to exist a function $\mathsf{shift}_n : 2^n \times \mathbb{Z} \to 2^n$ such that $\mathsf{shift}_n(\mathsf{sketch}_n(X), \delta) = \mathsf{sketch}_n(\{x + \delta \mid x \in X\})$. Is there a data structure that supports this operation, perhaps using some variety of homomorphic hashing?

Alternatively, $\mathsf{shift}_n$ need not exactly return the same sketch as $\{x + \delta \mid x \in X\}$, but rather a different sketch that still has the no-false-positives property when checked for disjointness with another set.

I'm also willing to consider answers where we can't ensure no false positives, but there is a good bound on the probability of a false positive.

Also, wherever I've said $\mathbb{Z}$ here, feel free to interpret that as some finite set of integers (e.g.: 32-bit integers).

Bonus points if there is a way to compute the union of two sketches, and if there is a way to extend this to sets of tuples in $\mathbb{Z} \times 2^p$ where $\mathsf{shift}$ only affects the first element of each tuple.

Answer 1

If you use bijective hash functions, you can recover the original keys from filter structures like cuckoo filters or quotient filters. The reason is that these are essentially quotienting dictionaries, not just filters. The problem, of course, is that the values in the sketch have to come from a universe as large as your input - otherwise you must not have a bijection!

If you store $m$ items from a set of size $2^w$, the space usage is $m (w - \lg m)$ plus low-order terms, or $(1 + \Omega(1))m(w-\lg m)$ if you don't know $m$ in advance. This is less than the brute force idea in which $\mathsf{sketch}$ is just the identity function, which has size $mw$, but the $-\lg m$ term doesn't pay off much until $\lg m$ get large compared to $w$.

So the sketch is just a quotienting filter, and $\mathsf{shift}$ just reverses the hash, adds the $\delta$, then creates a new filter. The fpp is 0.

The size can be made as low as $\Theta(m)$ by hashing your universe from size $2^w$ to $2^k$, for any $\lg m < k < w$, as long as your filter supports small universes. The fpp is then the probability of collision, which is $1-(1-2^{-k})^m$.

In total, this gets to a space usage of $m(\lg (1/\varepsilon))$, as long as you know $m$ in advance. This is tight for filters, as the lower bound is also $m(\lg (1/\varepsilon))$.

Answer 2

Here is one simple idea -- not sure if it's practical.

Define $\mathsf{sketch}_n(X)$ to be a length-$n$ bitstring in which bit $i$ is set iff there exists $x \in X$ such that $x = i \mod n$. In practice, this means that inserting an element $x$ into a set involves turning on bit $x \mod n$. $\mathsf{disjoint}_n(\cdot)$ is defined as before. Then $\mathsf{shift}_n(\cdot, \delta)$ can be found by rotating the sketch right by $\delta$ bits (which can be done implicitly by storing a "rotation amount" in the data structure).

To reduce the false positive rate for membership tests (but increase the false negative rate for disjointness tests), you can store multiple bitstrings using different moduli -- e.g., if the moduli 100, 101 and 105 are used, there would be 306 bits in total. Intuition suggests relatively prime moduli would work best, but I have not tried looking into this in detail.

Answer 3

Yes. Use any linear function as your hash function. If $h(x)= \alpha x + \beta \bmod n$, where $\alpha,\beta$ are fixed constants, then

$$h(x+\delta) = h(x) + \alpha \delta \bmod n.$$

Consequently, $\mathsf{shift}$ can just rotate the bitstring right by $\alpha \delta$ positions. Note that if $n$ is prime this hash function is 2-universal, so it should be a pretty good hash.

Unfortunately, this isn't useful if you want to use a Bloom filter with multiple hash functions, because you'd need to use the same $\alpha$ for all hash functions, which means that a collision for one hash will cause a collision for all others; effectively it reduces to a Bloom filter with one hash. But, as j_random_hacker suggests, you can create a sketch with multiple bitmaps, one per hash function, and use different hash functions (e.g., with different values of $\alpha$) for each bitmap.

---

More generally, you can use any hash function that has the form

$$h(x) = f^{(x)}(1),$$

where $f^{(x)}$ denotes iterated function application (applying $f$ $x$ times), and $f:\{1,\dots,n\} \to \{1,\dots,n\}$ is any function. To make this hash function any good, you will probably want $f$ to be bijective and to be chosen so that you can efficiently iterate $h$.

A linear function is one way instantiate $h$, but there are other ways. For instance, you can use

$$h(x) = \alpha^x \bmod n,$$

where $\alpha$ is a fixed constant. I don't expect this to have any advantages over a linear hash function, but I mention it as an example of the more general framework.