Locality-Sensitive Hashing (LSH)

The defining property of an LSH family is a mathematical guarantee on collision probability. For a given distance measure D and threshold R, a hash function h is (R, cR, P1, P2)-sensitive if:

• If D(p, q) ≤ R, then Pr[h(p) = h(q)] ≥ P1
• If D(p, q) ≥ cR, then Pr[h(p) = h(q)] ≤ P2

This ensures similar items (distance ≤ R) hash to the same bucket with high probability P1, while dissimilar items (distance ≥ cR) collide with a much lower probability P2. The gap between P1 and P2 is amplified by concatenating multiple hash functions.

Raw LSH functions often have a small probability gap between P1 and P2. To make this gap arbitrarily large, we compose functions using two operations:

• AND-construction (Band): Concatenate k independent hash functions. A pair collides only if all k hashes match. This reduces both P1 and P2, drastically lowering false positives.
• OR-construction (Bucket): Use L independent bands. A pair is a candidate if it collides in any of the L bands. This boosts recall by increasing the true positive rate.

The combination of L bands of k hashes creates a tunable trade-off between precision and recall, formalized as the S-curve response.

LSH is not a single algorithm but a framework instantiated for specific distance metrics. Common families include:

• Jaccard Similarity (MinHash): The hash value is the minimum element under a random permutation. The collision probability equals the Jaccard index.
• Cosine Similarity (SimHash / Random Projection): A random hyperplane splits the space; the hash is the sign of the dot product. Collision probability relates to the angle between vectors.
• Euclidean Distance (p-stable): Uses projections onto random lines with a bucket width w. The collision probability decays with distance, suitable for high-dimensional vectors.
• Hamming Distance (Bit Sampling): Simply selects a random bit position. Collision probability is the fraction of matching bits.

The primary computational advantage of LSH is breaking the O(n) barrier of brute-force search. By hashing all n database items into buckets and only comparing the query against items in the same bucket, the search time becomes sub-linear.

For an (R, cR, P1, P2)-sensitive family, the query time is approximately O(n^ρ), where ρ = log(1/P1) / log(1/P2). Since P1 > P2, we have ρ < 1, yielding a strict asymptotic improvement over linear scan. This is the property that makes private blocking feasible for million-scale datasets.

LSH is fundamentally opposed to the goals of cryptographic hashing. A cryptographic hash like SHA-256 aims for the avalanche effect: a single-bit change in input flips ~50% of output bits, destroying all similarity information. LSH deliberately preserves it.

This distinction is critical in PPRL. Standard hashing provides privacy but destroys the ability to perform fuzzy matching. LSH provides a controlled leakage of similarity—enough to enable blocking, but not enough to reconstruct the plaintext. The security relies on the hardness of inverting the specific LSH family combined with additional hardening like salting.

In private blocking, the LSH parameters k (hashes per band) and L (number of bands) directly control linkage quality:

• High k, Low L: Very high precision. Only near-identical records collide. Risk of false negatives (missed matches) due to typographical errors.
• Low k, High L: Very high recall. Captures fuzzy matches but generates many false positive candidate pairs, increasing the downstream cryptographic comparison cost.

The optimal configuration is found by sweeping k and L against a ground-truth set to maximize the F-measure while keeping the reduction ratio (fraction of pairs pruned) above a target threshold, often >99%.