2
$\begingroup$

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.

$\endgroup$
9
  • 3
    $\begingroup$ What data structure do you use for the sets? What algorithm do you currently use to calculate the intersection between two sets? It does not sound like your runtime is exponential. If you have $n$ sets and with each $m$ elements, it seems you describe something like $O(n^2m)$ (if you use hash maps). $\endgroup$
    – plshelp
    Jun 28 at 3:08
  • 2
    $\begingroup$ Just as a suggestion, you may like to experiment with pre-computing, for each element, a list of which sets that element appears in. This data structure is called an inverted index. In your case, there is only on the order of 10 million (element,set id) pairs, so simply sorting those pairs may be sufficient. $\endgroup$
    – Pseudonym
    Jun 28 at 3:32
  • $\begingroup$ What is the initial task/problem, what do you use (an estimate of) the cardinality of all pairs set intersection for? What is the cardinality of the union of all sets, the total number of different strings? $\endgroup$
    – greybeard
    Jun 28 at 4:00
  • $\begingroup$ @plshelp the data structure used are hash maps. the algorithm used to calculate the intersection is whatever built-in function that was implemented (e.g. x.intersection(y)). the complexity might not be as bad as I thought, but the real world performance is still not that great. $\endgroup$
    –  snow
    Jun 28 at 6:21
  • 1
    $\begingroup$ @greybeard 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. $\endgroup$
    –  snow
    Jun 28 at 6:27

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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