# data structures – Integer set disjointness query on sketches with something like homomorphic hashing

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.