14
$\begingroup$

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?
Improve this question
$\endgroup$
4
  • $\begingroup$ Could you first clarify what you mean by "internal similarity" ? $\endgroup$
    – Suresh
    Nov 6, 2012 at 19:24
  • $\begingroup$ In other words, the mean (or at least a sufficiently accurate approximation of the mean) of all Jaccard indexes in the group. $\endgroup$
    – rinogo
    Nov 6, 2012 at 20:47
  • 5
    $\begingroup$ 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. $\endgroup$
    – Suresh
    Nov 6, 2012 at 21:18
  • 6
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Nov 7, 2012 at 18:37

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Please summarize the contents of the links, and cite the paper. If links go stale, the current answer goes useless. $\endgroup$
    – vonbrand
    Dec 29, 2015 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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