efficient algorithm to compare similarity between sets of numbers?

Question

I have a large number of sets of numbers. Each set contains 10 numbers and I need to remove all sets that have 5 or more number (unordered) matches with any other set. For example: ``` set 1: {12,14,222,998,1,89,43,22,7654,23} set 2: {44,23,64,76,987,3,2345,443,431,88} set 3: {998,22,7654,345,112,32,89,9842,31,23} ``` Given the 3 sets of 10 numbers above sets 1 and sets 3 would be considered duplicates because they have 5 matching numbers. So, in this case I would remove set 3 (because it's considered similar to set 1). I have over 10000 sets to compare and I want to do this very efficiently. I've been turning this over and I just can't think of an efficient way to perform this comparison (it would be great to do this in a single pass). any ideas? Thanks! Mike

Accepted Answer

You should rethink your requirements because as it is, the operation does not even have a well-defined result. For example, take these sets:

```
set 1: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 
set 2: {6, 7, 8, 9, 10, 11, 12, 13, 14, 15} 
set 3: {11, 12, 13, 14, 15, 16, 17, 18, 19, 20}
```

If you first consider 1 and 2 to be "duplicates" and eliminate set 1, then 2 and 3 are also "duplicates" and you are left with only one remaining set. But if you instead eliminate set 2 first, then 1 and 3 have no matches and you are left with two sets remaining.

You can easily expand this to your full 10,000 sets so that it would be possible that depending on which sets you compare and eliminate first, you could be left with only a single set, or with 5,000 sets. I don't think that is what you want.

Mathematically speaking, your problem is that you are trying to find equivalence classes, but the relation "similarity" you use to define them is not an equivalence relation. Specifically, it is not transitive. In layman's terms, if set A is "similar" to set B and set B is "similar" to set C, then your definition does not ensure that A is also "similar" to C, and therefore you cannot meaningfully eliminate similar sets.

You need to first clarify your requirements to deal with this problem before worrying about an efficient implementation. Either find a way to define a transitive similarity, or keep all sets and work only with comparisons (or with a list of similar sets for each single set).

efficient algorithm to compare similarity between sets of numbers?

Solution

Problem