MinHash Bands for Threshold

Problem

Find the smallest number of bands whose collision probability reaches target at the given similarity.

Solve 1 - (1 - s ** rows) ** bands >= target for bands, returning ceil(ln(1 - target) / ln(1 - s ** rows)) clamped to at least 1. Return 0 when similarity or target lies outside (0, 1) or rows is non-positive.

Hint

Both logs in the ratio are negative, so the quotient is positive and rounds up.

Test cases

case 1

in: [0.8,5,0.5]

expected: 2

case 2

in: [0.5,4,0.9]

expected: 36

case 3

in: [0.9,10,0.5]

expected: 2

case 4

in: [0.5,1,0.5]

expected: 1

case 5

in: [0.5,4,1]

expected: 0

Starter codePython

import math


def minhash_bands_for_threshold(similarity, rows, target):
    # Your code here
    pass

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