Jaccard similarity
Jaccard similarity is the size of the intersection of two sets divided by the size of their union when that union is nonempty.
The measure is symmetric and lies between zero and one. Directional containment divides the intersection by the size of one specified input instead. A small set fully contained in a larger one can therefore have low Jaccard similarity but complete containment in that direction. [1]
The item definition determines what is compared. Sets of chunk identities discard occurrence counts and recipe order; choosing shingles or occurrence-labelled tokens changes the sets. Two empty sets give 0/0, so software must declare its convention rather than infer a value from the formula. [1]
For A={a,b} and B={a,c}, Jaccard similarity is 1/3. With one occurrence of each chunk and equal sizes, half of B's bytes already occur in A. If a is nine times the size of b and c, that byte share is 9/10 without changing Jaccard similarity. Metadata, compression and replication costs remain separate. [2]
Scalar similarities cannot in general be merged. Against {a,b}, the shards {a} and {b} each score 1/2 but their union scores 1. Repeating shard {a} gives the same two input scores but a union score of 1/2. Retain compatible sketch state or the underlying identities, not only scores. [2]
Relations
Citations
- Broder. On the resemblance and containment of documents. SEQUENCES 1997, section 2.
- Hesela. MinHash and deduplication denominators: exact finite-set illustration and tests.
Sources & caveats
- Synthetic arithmetic concerns explicitly named identities and logical payload bytes, not observed capacity savings. [2]