0
$\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$
  • $\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 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 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$ – Yuval Filmus Jan 10 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 at 14:41
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$
  • $\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 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$ – j_random_hacker Jan 10 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$ – j_random_hacker Jan 10 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$ – j_random_hacker Jan 10 at 15:15
-1
$\begingroup$

You might want to try Dynamic Partition Bloom Filters.

$\endgroup$
  • 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 at 6:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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