Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?
share|cite|improve this question

migrated from Nov 7 '12 at 9:02

This question came from our site for theoretical computer scientists and researchers in related fields.

Could you first clarify what you mean by "internal similarity" ? – Suresh Nov 6 '12 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 '12 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. – Suresh Nov 6 '12 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. – Tsuyoshi Ito Nov 7 '12 at 18:37

An option would be to use the Signature Scheme of [1], size-based filtering: a scheme which uses size information to reduce the number of set pairs that need to be considered.

They also experiment with a weighted form; where weights are IDF-based.

[1] Arasu, Arvind, Venkatesh Ganti, and Raghav Kaushik. “Efficient Exact Set-similarity Joins.” In Proceedings of the 32nd International Conference on Very Large Data Bases, 918–929. VLDB ’06. VLDB Endowment, 2006

share|cite|improve this answer

Another option would be to employ local sensitivity hashing wiki link. I've seen it being used in community similarity detection by Wu and Zou (An incremental community detection method for social tagging systems using locality-sensitive hashing, Neural Networks 58:14–28; ACM DL) which is basically detecting similarity between integer or string sets.

share|cite|improve this answer
Please summarize the contents of the links, and cite the paper. If links go stale, the current answer goes useless. – vonbrand Dec 29 '15 at 9:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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