← All questions
Data, Privacy & LegalVery Hard· LSH· Probability

How do you choose b and r to hit a specific threshold w...

To achieve a sharp transition at a target similarity threshold, first set K = b × r based on your memory budget. The threshold is approximately (1/b)^(1/r). Increasing ‘r’ steepens the transition curve but reduces the number of bands. After selecting ‘b’ and ‘r’, evaluate the collision probability P at θ - 0.05 and θ + 0.05 to ensure false positive and false negative rates are acceptable. If the transition is too shallow, increase K to allow for a larger ‘r’ while keeping ‘b’ constant.

Code playground (Python)