1
$\begingroup$

I hope you can help me -

Given a lot of sets containing integers, I'd like for any two sets, to quickly (i.e. O(1)) ask whether they intersect. Note that I don't need the exact intersection, rather just a yes/no answer. Also, I am fine with some false-positives. Also, the representation of the sets should be space-efficient (i.e. less than the set-size).

Ideally, I'd also like to (infrequently) update the sets.

My requirements make me think of Bloom Filters, which 1)represent sets efficiently, 2)allow O(1) containment-test and 3) have some false-positives. Unfortunately it they don't apply to two-set-intersection.

Any ideas? Thanks!

(Just FYI, the sets are subsets of ids of adjacent edges from a huge graph)

$\endgroup$
5
  • $\begingroup$ What do you mean by adjacent edges exactly? Do the sets correspond to the edges incident to each node of the graph (if not, what do they correspond to?)? If you have $k$ sets, why don't you just preprocess a $k \times k$ table with all the answers? $\endgroup$
    – Vincenzo
    Jan 10, 2019 at 12:11
  • $\begingroup$ I'd rather not expand about what the sets contain, because I'm looking for a "general" solution. And I do have $kXk$ sets. As I added, 1)I'd like to (infrequently) edit the sets and 2) this preprocessing is exactly what I'm trying to optimize :) $\endgroup$
    – selotape
    Jan 10, 2019 at 12:24
  • $\begingroup$ Why don't they apply to set intersection? You can ask whether the filters have a bit in common (whether the bitwise AND is non-zero). $\endgroup$ Jan 10, 2019 at 12:30
  • $\begingroup$ Yuval, I haven't analyzed but I feel your suggestion would lead to way too many false-positives - AFAIK in Bloom Filters a single entry flips many bits (per the size of the hash chain/functions), so several distinct items in both sets would make it almost certain that SOME bit would intersect (and I have tens/hundreds of items in each set) $\endgroup$
    – selotape
    Jan 10, 2019 at 14:41
  • $\begingroup$ How many sets ? How large ? Size of the domain ? Average number of common elements ? Probability of intersection ? $\endgroup$
    – user16034
    May 25, 2023 at 15:56

3 Answers 3

1
$\begingroup$

Use a partitioned Bloom filter for testing set intersection. It has lower FPR than unpartitioned (standard) Bloom filters.

To intersect two partitioned Bloom filters:

  1. AND the bit vectors for all the partitions.
  2. Compare the range of bits for each partition to all zeroes in turn.
  3. If ANY partition is all zero bits, the sets are likely disjoint.

If the sets ARE disjoint, on average you only have to compare half of the Bloom filter bits.

The comparison is fast, as you can rely on hardware parallelism to compare lots of bits in O(1) time. At worst it is O(log(M)) time.

However, the FPR for testing disjointedness of two sets is higher than the FPR for any given query. To match the desired FPR of a query, you must increase the size of the filter. The factor for the size increase is roughly sqrt(N) for set cardinality N.

The research on this is here:

https://www.eecg.toronto.edu/~steffan/papers/jeffrey_spaa11.pdf

"Understanding Bloom Filter Intersection for Lazy Address-Set Disambiguation" by Mark C. Jeffrey and J. Gregory Steffan

$\endgroup$
2
$\begingroup$

Build a $k \times k$ table $ans$ of answers, storing in each entry the smallest (according to some total order) element in that intersection or a sentinel value (e.g. -1) if the intersection is empty, and also maintain a mapping from each element to the set of all sets that contains it (e.g. using a hashtable of hashtables).

When you add an element $x$ to a set $i$, you can efficiently find all other sets $j$ for which $ans[i][j]$ might need to change, and the change itself is also simple: set $ans[i][j] = \min(ans[i][j], x)$. Removing an element will also be efficient, except in the rare case when you remove that minimum shared element, which requires fully recomputing (just) $ans[i][j]$.

$\endgroup$
4
  • $\begingroup$ How would you calculate the intersection of $set_i$ and $set_j$, in order to fill in $ans[i][j]$? A naive calculation would take $O(\min(|set_i|, |set_j|))$ for a single intersection, by iterating over each element in one set and checking for containment in the other. I'm trying to reduce this calculation, maybe using some compression of the sets. $\endgroup$
    – selotape
    Jan 10, 2019 at 14:48
  • $\begingroup$ It may be faster to sort all sets first, and then perform a linear list merge of each set pair -- which you can stop as soon as you find an element common to both sets (this will be the smallest such element, which is what you need for $ans$). $\endgroup$ Jan 10, 2019 at 15:00
  • $\begingroup$ Another approach would be to build a binary tree on each set, in which each internal node $v$ has a value $t_v$, with every element in the set $\le t_v$ appearing as a leaf in the left subtree, and every other element appearing as a leaf in the right subtree. $t_r$ should be set to half the maximum key value for the root $r$; in general, each child node's $t_v$ takes the midpoint of the range represented by its parent. ... $\endgroup$ Jan 10, 2019 at 15:11
  • $\begingroup$ ... Now you can more efficiently compare two such trees: Follow the leftmost path that exists in both trees. If this ends at a leaf, you have found the minimum shared element; otherwise you need to backtrack and try a "right-er" path. This is still $O(n+m)$ in the worst case, since it might be that set $i$ contains $n$ even numbers, and set $j$ contains each of those numbers with 1 added to them, meaning the entire trees will be explored to find that there is no intersection. $\endgroup$ Jan 10, 2019 at 15:15
-1
$\begingroup$

You might want to try Dynamic Partition Bloom Filters.

$\endgroup$
1
  • 2
    $\begingroup$ Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference. $\endgroup$
    – xskxzr
    Feb 11, 2019 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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