Efficient algorithm to count number of intersections of n sets

Question

I've come across this problem when working on a personal project of mine. I need an efficient algorithm of counting the number of overlaps between all pair combinations of n sets.

Example:

Set a = [adam, ben, charlie, ...]

Set b = [adam, john, kenny, ...]

Set c = [adam, john, eve, ...]

...

Set n

The algorithm will then get all pair combinations of sets, and count the number of intersections within those pairs.

e.g.

Set a & b = 1 (adam is in both sets)

Set a & c = 1 (adam is in both sets)

Set b & c = 2 (adam and john is in both sets)

...

The naïve algorithm I have come up with is:

1. Generate all 2-combinations of the sets and put them in a list.
2. For each pair in the list, find the intersection of the pair, add the count to the result list
3. Repeat for all pairs

Each set can have over 10k elements (strings), and there are over 1k sets. Obviously the performance is horrible since the runtime is exponential.

Are there any methods to improve the runtime? Is there a different algorithm that would improve the calculation? The results doesn't have to be exact, i.e. it can be an estimation.

Edit:

The task is to find overlapping users from different communities. For example we have different communities 1, 2, 3, etc. each community has their users (usernames in the list). I am trying to find the number of overlapping users from each community. e.g. community 1 shares 200 users with community 2, shares 400 users with community 3, so on and so forth.

Answer 1

Assuming you really need the number for all pairs of sets and hearing that we are thinking of users in communities you could use the following algorithm which relies on the idea that the the average number of sets/communities a user is part of $k$ is much smaller that the number of total sets $k << n$. Let $m$ refer to the total number of unique users.

Now:

// build a reverse index as described in the comments 
// this takes  $O(n + km)$ because every user is in $\approx k$ sets
reverse_index := new HashMap() 

for i = 0, ..., sets.length-1:
    S := sets[i]
    for key in S:
        if key not in reverse_index:
            reverse_index[key] = new List()
        reverse_index[key].append(i)

// create a n x n array for out final results $O(n^2)$
results := int[n][n] 
for i = 0,...,n-1:
    for j = 0,...,n-1:
        results[i][j] = 0

// go through every user and connect all the sets they are in $O(mk^2)$ 
for key in reverse_index:
    L := reverse_index[key]
    k := L.length
    for i = 0,...,k-1:
        for j = i+1,...,k-1:
            // each user is in $k$ sets
            // so we need to add $k^2$ "connections" 
            results[L[i]][L[j]] += 1
            results[L[j]][L[i]] += 1

The total runtime is $O(n^2+mk^2)$. The worst case occurs if $k \approx n$ - as mentioned all ready all of this is based on a heuristic. Also make sure that you use an integer user id to identify users and not strings, as computing the hashes of string is additional overhead.