4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Such a sketch will enable you to get a good glimpse of $A$ by fixing $B$ and considering all possible shifts of $A$. Hence it would need to be quite long. To say more, you will have to define all your concepts more formally (a sketch with no true negative is easy to implement, for example, but probably won't be interesting for you). $\endgroup$ – Yuval Filmus Jan 12 at 8:05
  • $\begingroup$ Appreciate you marking my answer accepted, but you might want to leave it a few more days to see if others answer? BTW, what is the application? $\endgroup$ – j_random_hacker Jan 13 at 1:44
  • $\begingroup$ @j_random_hacker I was interested in scheduling nonconvex sets of pairs of (Time, Resource), so I thought representing those as some kind of precomputed sketch might be an efficient way to do scheduling. In hindsight, Map<Time, BloomFilter<Resource>> would probably work well enough, and it turns out that disjointness checking of bloom filters is less efficient than I thought, so I've abandoned the whole idea as impractical. Homomorphic sketches are an interesting topic, though! $\endgroup$ – taktoa Jan 14 at 2:04
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @D.W.: I'm describing a different data structure, not a bloom filter (though somewhat related I guess). There is a separate bitstring for each different modulus -- so, e.g., if the moduli 100, 101 and 105 were used, there would be 306 bits in total. I added this example to my answer, is it clearer? $\endgroup$ – j_random_hacker Jan 14 at 0:38
  • $\begingroup$ Good, makes sense now! Thank you! $\endgroup$ – D.W. Jan 14 at 7:58
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is the intention to use a set of such hash functions with a bloom filter? Because in that case, and w.r.t. linear hash functions, I think the hash functions in the set must all use the same $\alpha$, since otherwise different bits in the bitvector need to be rotated different amounts for $\mathsf{shift}$ (depending on which hash function they "came from"), and we don't have that information. But using multiple linear hash functions with the same $\alpha$ but different $\beta$s is wasteful, since if $h_1(x)=h_1(y)$ then $h_2(x)=h_2(y)$. $\endgroup$ – j_random_hacker Jan 13 at 9:49
  • $\begingroup$ @j_random_hacker, you're right, this answer isn't useful for Bloom filters. I missed that. Thank you! Unfortunately it looks like your answer has a related problem; I'll comment there. $\endgroup$ – D.W. Jan 13 at 18:31

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.