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)