Model

LSH banding: the S-curve

Pairs above the threshold are found; pairs below it are almost never compared.

P (candidate) = 1 - (1 - J^{r})^{b}, threshold \approx (\frac{1}{b})^{1/ r}

$J$: Similarity; Jaccard similarity of the pair
$b$: Bands; bands
$r$: Rows per band; rows (hashes) per band

How it behaves

One input on the horizontal axis, the others held fixed.

b = 16, r = 8 (threshold ≈ 0.71)b = 32, r = 4 (threshold ≈ 0.42)

Data table

Chance a pair becomes a candidate, by similarity
Jaccard similarity J	series	P(candidate)
0	b = 16, r = 8 (threshold ≈ 0.71)	0
0.013	b = 16, r = 8 (threshold ≈ 0.71)	0
0.025	b = 16, r = 8 (threshold ≈ 0.71)	0
0.038	b = 16, r = 8 (threshold ≈ 0.71)	0
0.05	b = 16, r = 8 (threshold ≈ 0.71)	0
0.063	b = 16, r = 8 (threshold ≈ 0.71)	0
0.075	b = 16, r = 8 (threshold ≈ 0.71)	0
0.088	b = 16, r = 8 (threshold ≈ 0.71)	0
0.1	b = 16, r = 8 (threshold ≈ 0.71)	0
0.113	b = 16, r = 8 (threshold ≈ 0.71)	0
0.125	b = 16, r = 8 (threshold ≈ 0.71)	0
0.138	b = 16, r = 8 (threshold ≈ 0.71)	0
0.15	b = 16, r = 8 (threshold ≈ 0.71)	0
0.163	b = 16, r = 8 (threshold ≈ 0.71)	0
0.175	b = 16, r = 8 (threshold ≈ 0.71)	0
0.188	b = 16, r = 8 (threshold ≈ 0.71)	0
0.2	b = 16, r = 8 (threshold ≈ 0.71)	0
0.212	b = 16, r = 8 (threshold ≈ 0.71)	0
0.225	b = 16, r = 8 (threshold ≈ 0.71)	0
0.237	b = 16, r = 8 (threshold ≈ 0.71)	0
0.25	b = 16, r = 8 (threshold ≈ 0.71)	0
0.263	b = 16, r = 8 (threshold ≈ 0.71)	0
0.275	b = 16, r = 8 (threshold ≈ 0.71)	0.001
0.287	b = 16, r = 8 (threshold ≈ 0.71)	0.001
0.3	b = 16, r = 8 (threshold ≈ 0.71)	0.001
0.313	b = 16, r = 8 (threshold ≈ 0.71)	0.001
0.325	b = 16, r = 8 (threshold ≈ 0.71)	0.002
0.338	b = 16, r = 8 (threshold ≈ 0.71)	0.003
0.35	b = 16, r = 8 (threshold ≈ 0.71)	0.004
0.362	b = 16, r = 8 (threshold ≈ 0.71)	0.005
0.375	b = 16, r = 8 (threshold ≈ 0.71)	0.006
0.388	b = 16, r = 8 (threshold ≈ 0.71)	0.008
0.4	b = 16, r = 8 (threshold ≈ 0.71)	0.01
0.412	b = 16, r = 8 (threshold ≈ 0.71)	0.013
0.425	b = 16, r = 8 (threshold ≈ 0.71)	0.017
0.438	b = 16, r = 8 (threshold ≈ 0.71)	0.021
0.45	b = 16, r = 8 (threshold ≈ 0.71)	0.027
0.463	b = 16, r = 8 (threshold ≈ 0.71)	0.033
0.475	b = 16, r = 8 (threshold ≈ 0.71)	0.041
0.487	b = 16, r = 8 (threshold ≈ 0.71)	0.05
0.5	b = 16, r = 8 (threshold ≈ 0.71)	0.061
0.512	b = 16, r = 8 (threshold ≈ 0.71)	0.074
0.525	b = 16, r = 8 (threshold ≈ 0.71)	0.088
0.537	b = 16, r = 8 (threshold ≈ 0.71)	0.106
0.55	b = 16, r = 8 (threshold ≈ 0.71)	0.126
0.563	b = 16, r = 8 (threshold ≈ 0.71)	0.149
0.575	b = 16, r = 8 (threshold ≈ 0.71)	0.175
0.588	b = 16, r = 8 (threshold ≈ 0.71)	0.204
0.6	b = 16, r = 8 (threshold ≈ 0.71)	0.237
0.613	b = 16, r = 8 (threshold ≈ 0.71)	0.274
0.625	b = 16, r = 8 (threshold ≈ 0.71)	0.314
0.637	b = 16, r = 8 (threshold ≈ 0.71)	0.358
0.65	b = 16, r = 8 (threshold ≈ 0.71)	0.404
0.662	b = 16, r = 8 (threshold ≈ 0.71)	0.454
0.675	b = 16, r = 8 (threshold ≈ 0.71)	0.506
0.688	b = 16, r = 8 (threshold ≈ 0.71)	0.559
0.7	b = 16, r = 8 (threshold ≈ 0.71)	0.613
0.713	b = 16, r = 8 (threshold ≈ 0.71)	0.667
0.725	b = 16, r = 8 (threshold ≈ 0.71)	0.719
0.738	b = 16, r = 8 (threshold ≈ 0.71)	0.769
0.75	b = 16, r = 8 (threshold ≈ 0.71)	0.815
0.762	b = 16, r = 8 (threshold ≈ 0.71)	0.857
0.775	b = 16, r = 8 (threshold ≈ 0.71)	0.893
0.787	b = 16, r = 8 (threshold ≈ 0.71)	0.923
0.8	b = 16, r = 8 (threshold ≈ 0.71)	0.947
0.813	b = 16, r = 8 (threshold ≈ 0.71)	0.966
0.825	b = 16, r = 8 (threshold ≈ 0.71)	0.979
0.838	b = 16, r = 8 (threshold ≈ 0.71)	0.988
0.85	b = 16, r = 8 (threshold ≈ 0.71)	0.994
0.863	b = 16, r = 8 (threshold ≈ 0.71)	0.997
0.875	b = 16, r = 8 (threshold ≈ 0.71)	0.999
0.887	b = 16, r = 8 (threshold ≈ 0.71)	1
0.9	b = 16, r = 8 (threshold ≈ 0.71)	1
0.912	b = 16, r = 8 (threshold ≈ 0.71)	1
0.925	b = 16, r = 8 (threshold ≈ 0.71)	1
0.938	b = 16, r = 8 (threshold ≈ 0.71)	1
0.95	b = 16, r = 8 (threshold ≈ 0.71)	1
0.963	b = 16, r = 8 (threshold ≈ 0.71)	1
0.975	b = 16, r = 8 (threshold ≈ 0.71)	1
0.988	b = 16, r = 8 (threshold ≈ 0.71)	1
1	b = 16, r = 8 (threshold ≈ 0.71)	1
0	b = 32, r = 4 (threshold ≈ 0.42)	0
0.013	b = 32, r = 4 (threshold ≈ 0.42)	0
0.025	b = 32, r = 4 (threshold ≈ 0.42)	0
0.038	b = 32, r = 4 (threshold ≈ 0.42)	0
0.05	b = 32, r = 4 (threshold ≈ 0.42)	0
0.063	b = 32, r = 4 (threshold ≈ 0.42)	0
0.075	b = 32, r = 4 (threshold ≈ 0.42)	0.001
0.088	b = 32, r = 4 (threshold ≈ 0.42)	0.002
0.1	b = 32, r = 4 (threshold ≈ 0.42)	0.003
0.113	b = 32, r = 4 (threshold ≈ 0.42)	0.005
0.125	b = 32, r = 4 (threshold ≈ 0.42)	0.008
0.138	b = 32, r = 4 (threshold ≈ 0.42)	0.011
0.15	b = 32, r = 4 (threshold ≈ 0.42)	0.016
0.163	b = 32, r = 4 (threshold ≈ 0.42)	0.022
0.175	b = 32, r = 4 (threshold ≈ 0.42)	0.03
0.188	b = 32, r = 4 (threshold ≈ 0.42)	0.039
0.2	b = 32, r = 4 (threshold ≈ 0.42)	0.05
0.212	b = 32, r = 4 (threshold ≈ 0.42)	0.063
0.225	b = 32, r = 4 (threshold ≈ 0.42)	0.079
0.237	b = 32, r = 4 (threshold ≈ 0.42)	0.097
0.25	b = 32, r = 4 (threshold ≈ 0.42)	0.118
0.263	b = 32, r = 4 (threshold ≈ 0.42)	0.141
0.275	b = 32, r = 4 (threshold ≈ 0.42)	0.168
0.287	b = 32, r = 4 (threshold ≈ 0.42)	0.197
0.3	b = 32, r = 4 (threshold ≈ 0.42)	0.229
0.313	b = 32, r = 4 (threshold ≈ 0.42)	0.264
0.325	b = 32, r = 4 (threshold ≈ 0.42)	0.302
0.338	b = 32, r = 4 (threshold ≈ 0.42)	0.342
0.35	b = 32, r = 4 (threshold ≈ 0.42)	0.384
0.362	b = 32, r = 4 (threshold ≈ 0.42)	0.427
0.375	b = 32, r = 4 (threshold ≈ 0.42)	0.472
0.388	b = 32, r = 4 (threshold ≈ 0.42)	0.518
0.4	b = 32, r = 4 (threshold ≈ 0.42)	0.564
0.412	b = 32, r = 4 (threshold ≈ 0.42)	0.609
0.425	b = 32, r = 4 (threshold ≈ 0.42)	0.654
0.438	b = 32, r = 4 (threshold ≈ 0.42)	0.697
0.45	b = 32, r = 4 (threshold ≈ 0.42)	0.738
0.463	b = 32, r = 4 (threshold ≈ 0.42)	0.777
0.475	b = 32, r = 4 (threshold ≈ 0.42)	0.812
0.487	b = 32, r = 4 (threshold ≈ 0.42)	0.844
0.5	b = 32, r = 4 (threshold ≈ 0.42)	0.873
0.512	b = 32, r = 4 (threshold ≈ 0.42)	0.898
0.525	b = 32, r = 4 (threshold ≈ 0.42)	0.92
0.537	b = 32, r = 4 (threshold ≈ 0.42)	0.939
0.55	b = 32, r = 4 (threshold ≈ 0.42)	0.954
0.563	b = 32, r = 4 (threshold ≈ 0.42)	0.966
0.575	b = 32, r = 4 (threshold ≈ 0.42)	0.975
0.588	b = 32, r = 4 (threshold ≈ 0.42)	0.983
0.6	b = 32, r = 4 (threshold ≈ 0.42)	0.988
0.613	b = 32, r = 4 (threshold ≈ 0.42)	0.992
0.625	b = 32, r = 4 (threshold ≈ 0.42)	0.995
0.637	b = 32, r = 4 (threshold ≈ 0.42)	0.997
0.65	b = 32, r = 4 (threshold ≈ 0.42)	0.998
0.662	b = 32, r = 4 (threshold ≈ 0.42)	0.999
0.675	b = 32, r = 4 (threshold ≈ 0.42)	0.999
0.688	b = 32, r = 4 (threshold ≈ 0.42)	1
0.7	b = 32, r = 4 (threshold ≈ 0.42)	1
0.713	b = 32, r = 4 (threshold ≈ 0.42)	1
0.725	b = 32, r = 4 (threshold ≈ 0.42)	1
0.738	b = 32, r = 4 (threshold ≈ 0.42)	1
0.75	b = 32, r = 4 (threshold ≈ 0.42)	1
0.762	b = 32, r = 4 (threshold ≈ 0.42)	1
0.775	b = 32, r = 4 (threshold ≈ 0.42)	1
0.787	b = 32, r = 4 (threshold ≈ 0.42)	1
0.8	b = 32, r = 4 (threshold ≈ 0.42)	1
0.813	b = 32, r = 4 (threshold ≈ 0.42)	1
0.825	b = 32, r = 4 (threshold ≈ 0.42)	1
0.838	b = 32, r = 4 (threshold ≈ 0.42)	1
0.85	b = 32, r = 4 (threshold ≈ 0.42)	1
0.863	b = 32, r = 4 (threshold ≈ 0.42)	1
0.875	b = 32, r = 4 (threshold ≈ 0.42)	1
0.887	b = 32, r = 4 (threshold ≈ 0.42)	1
0.9	b = 32, r = 4 (threshold ≈ 0.42)	1
0.912	b = 32, r = 4 (threshold ≈ 0.42)	1
0.925	b = 32, r = 4 (threshold ≈ 0.42)	1
0.938	b = 32, r = 4 (threshold ≈ 0.42)	1
0.95	b = 32, r = 4 (threshold ≈ 0.42)	1
0.963	b = 32, r = 4 (threshold ≈ 0.42)	1
0.975	b = 32, r = 4 (threshold ≈ 0.42)	1
0.988	b = 32, r = 4 (threshold ≈ 0.42)	1
1	b = 32, r = 4 (threshold ≈ 0.42)	1

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Core Data Structures
How do we choose a data structure when the real cost is set by the hardware, not by Big-O?
$P (candidate) = 1 - (1 - J^{r})^{b}$
Read it in place →