# Set Similarity - Calculate Jaccard index without quadratic complexity

I have a group of n sets for which I need to calculate a sort of "uniqueness" or "similarity" value. I've settled on the Jaccard index as a suitable metric. Unfortunately, the Jaccard index only operates on two sets at a time. In order to calculate the similarity between all $n$ sets, it will require in the order of $n^2$ Jaccard calculations.

(If it helps, $n$ is usually between 10 and 10000, and each set contains on average 500 elements. Also, in the end, I don't care how similar any two specific sets are - rather, I only care what the internal similarity of the whole group of sets is. (In other words, the mean (or at least a sufficiently accurate approximation of the mean) of all Jaccard indexes in the group))

Two questions:

1. Is there a way to still use the Jaccard index without the $n^2$ complexity?
2. Is there a better way to calculate set similarity/uniqueness across a group of sets than the way I've suggested above?
• Could you first clarify what you mean by "internal similarity" ? Nov 6, 2012 at 19:24
• In other words, the mean (or at least a sufficiently accurate approximation of the mean) of all Jaccard indexes in the group.
– rinogo
Nov 6, 2012 at 20:47
• If you're willing to approximate the answer, then you can use min-wise hashing to estimate the Jaccard distance approximately and then use the resulting representation to compute the desired average. Nov 6, 2012 at 21:18
• I do not know what you mean by “sufficiently accurate,” but one way to estimate the average of many things is just compute several of them (the Jaccard indices of several pairs of sets in this case) at random and compute their average. Then you can use the Chernoff bound to get an upper bound on the probability that this estimate is far from the true mean. Nov 7, 2012 at 18:37