LSH Band Collision Probability

Problem

Return the probability that two MinHash LSH signatures collide at the given Jaccard similarity.

With rows rows per band and bands bands, each band collides with probability similarity ** rows and the signatures collide if any band does, giving 1 - (1 - s ** r) ** b. Non-positive rows or bands return 0.0.

Hint

Band and row counts shape the S-curve; more bands raise collisions, more rows lower them.

Test cases

case 1

in: [0.8,5,20]

expected: 0.9996439421094793

case 2

in: [0.5,4,10]

expected: 0.47553952495127305

case 3

in: [0.9,10,5]

expected: 0.8827865978466163

case 4

in: [0,3,4]

expected: 0

case 5

in: [1,3,4]

expected: 1

Starter codePython

def lsh_band_collision_probability(similarity, rows, bands):
    # Your code here
    pass

5 test cases · run your code against them in the editor