Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
    
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
3  
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
4  
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
add comment

migrated from cstheory.stackexchange.com Nov 7 '12 at 9:02

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

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.