What is a data structure for quickly finding non-empty intersections of a list of sets?

Question

I have a set of N items, which are sets of integers, let's assume it's ordered and call it I[1..N]. Given a candidate set, I need to find the subset of I which have non-empty intersections with the candidate.

So, for example, if:

I = [{1,2}, {2,3}, {4,5}]

I'm looking to define valid_items(items, candidate), such that:

valid_items(I, {1}) == {1}
valid_items(I, {2}) == {1, 2}
valid_items(I, {3,4}) == {2, 3}

I'm trying to optimize for one given set I and a variable candidate sets. Currently I am doing this by caching items_containing[n] = {the sets which contain n}. In the above example, that would be:

items_containing = [{}, {1}, {1,2}, {2}, {3}, {3}]

That is, 0 is contained in no items, 1 is contained in item 1, 2 is contained in itmes 1 and 2, 2 is contained in item 2, 3 is contained in item 2, and 4 and 5 are contained in item 3.

That way, I can define valid_items(I, candidate) = union(items_containing[n] for n in candidate).

Is there any more efficient data structure (of a reasonable size) for caching the result of this union? The obvious example of space 2^N is not acceptable, but N or N*log(N) would be.

Answer 1

One representation that might help is storing the sets I as vectors V of size n whose entries V(i) are 0 when i is not in V and positive otherwise. Then to take the intersection of two vectors you multiply the terms, and to take the union you add the terms.

Answer 2

I think your current solution is optimal big-O wise, though there are micro-optimization techniques that could improve its actual performance. Such as using bitwise operations when merging the chosen set in item_containing set with the valid items set.

i.e. you store items_containing as this:

items_containing = [0x0000, 0x0001, 0x0011, 0x0010, 0x0100, 0x0100]

and your valid_items can use bit-wise OR to merge like this:

int valid_items(Set I, Set candidate) {
    // if you need more than 32-items, use int[] for valid 
    // and int[][] for items_containing
    int valid = 0x0000;
    for (int item : candidate) {
        // bit-wise OR
        valid |= items_containing[item];
    }
    return valid;
}

but they don't really change the Big-O performance.