UUtah Data Mining | Fall 2026 | L7 - LSH & Distribution Dist

Overview

The lecture develops locality-sensitive hashing (LSH) from MinHash’s unbiased Jaccard estimator to banding, which combines hash functions into an S-shaped candidate-retrieval probability curve. It then presents LSH for angular and Euclidean similarity, explains how to sample random directions correctly, and compares probability-vector distances such as KL divergence and Hellinger distance with Wasserstein earth mover’s distance for spatial distributions.

Key takeaways

A MinHash signature estimates Jaccard similarity without bias: across T independent hashes, the fraction of matching coordinates has expectation equal to the true similarity.
With B hashes per band and R bands, MinHash LSH retrieves a pair with probability 1 − (1 − s^B)^R, where s is its Jaccard similarity; B controls selectivity and R controls the number of collision opportunities.
For angular similarity, hashing a unit vector by sign(u · a) with random direction u gives collision probability 1 − arccos(a · b)/π.
To sample a uniform random direction in high dimensions, normalize a vector of independent standard normal coordinates; normalizing a vector sampled uniformly from a box introduces directional bias.
For Euclidean LSH, random projection followed by offset binning of width σ gives one-dimensional collision probability 1 − |a − b|/σ for pairs less than σ apart.
Discrete distribution distances encode different assumptions: KL divergence is directional, Hellinger uses square-root geometry, and Wasserstein distance accounts for spatial transport through an expensive optimal matching.

Chapters

0:00 Project Deadlines and the Lecture’s Similarity-and-Distance Scope

Project proposals are due by the end of the day and should be 100–200 words; each group member submits the same proposal while groups are being formed.
The posted homework is due September 22 and is intended to use material from this lecture.
The lecture covers locality-sensitive hashing (LSH) and distances for distributions, both relevant to data-mining projects.

4:00 MinHash Collision Probability Estimates Jaccard Similarity

For sets S and S′, a randomly selected MinHash function collides with probability equal to their Jaccard similarity.
Although a chosen hash function is deterministic, randomness in selecting it makes the collision event a random variable.
An indicator for whether two sets hash equally has expectation equal to their Jaccard similarity.

8:30 A MinHash Sketch Averages Independent Hash Functions

Using T independent hash functions, estimate Jaccard similarity by the fraction of hashes that match.
The estimator is unbiased, and increasing T improves its accuracy; the lecture suggests roughly 100–1,000 hashes as a practical scale.
Concentration bounds such as a Chernoff bound can quantify the probability that the estimate deviates from the true similarity.

13:30 LSH Turns Similarity Estimates into Fast Candidate Retrieval

A MinHash signature can estimate similarity through the Hamming agreement rate across its coordinates, but that alone does not explain how to retrieve neighbors efficiently.
The target is a collision-probability curve that is high above a chosen similarity threshold and low below it.
LSH accepts an uncertain transition region rather than requiring a perfect threshold, supporting approximate-nearest-neighbor search.

19:30 OR and AND Combinations Trade False Negatives for False Positives

The aggressive strategy takes the union of matches across hash functions: a single collision makes an item a candidate, reducing false negatives but admitting false positives.
The conservative strategy concatenates hash outputs and requires agreement in every coordinate, reducing false positives but potentially missing similar items.
Combining many hash outputs into a single key can create an enormous, sparse hash space, motivating a compromise between the two strategies.

26:00 Banding Combines Strict Hash Keys with Multiple Chances to Match

Split T = B × R hash functions into R bands, each containing B hashes.
Concatenate the B hashes within each band, then return a candidate if it matches in any of the R bands.
Each band is selective like an AND operation, while the union across bands behaves like an OR operation.

31:00 Banding Produces the LSH S-Curve

If two sets have Jaccard similarity s, their probability of matching within one B-hash band is s^B.
Across R independent bands, the probability of becoming a candidate is 1 − (1 − s^B)^R.
The resulting S-curve approximates a similarity threshold while retaining a probabilistic transition zone.

37:00 Adjusting Band Size and Count Moves the Similarity Threshold

Increasing R gives a pair more chances to collide, raising candidate probability even at lower similarities.
Increasing B makes a band stricter, shifting the curve toward higher similarity and making retrieval more selective.
Examples with B = 3 and R = 5 use 15 hashes; larger configurations such as B = 8 and R = 100 use 800 hashes for a sharper transition.

42:00 Random-Projection Hashes for Angular Similarity

For unit vectors a and b, choose a random unit vector u and define hᵤ(a) = sign(u · a), producing one of two hash values: −1 or +1.
The random hyperplane divides the space into two half-spaces; the probability that a and b receive the same sign is 1 − arccos(a · b)/π.
Repeated hashes estimate angular similarity, and the same banding method can turn those hashes into an LSH candidate index.

47:00 Uniform Directions Require Gaussian Sampling, Not a Normalized Box Sample

Sampling each coordinate uniformly from [−1, 1] and normalizing does not produce a uniform direction; it over-samples directions associated with corners of the box.
Instead, draw each coordinate of a vector G independently from a standard normal distribution and normalize: u = G/‖G‖.
The multivariate Gaussian is rotationally symmetric, so normalizing it yields a uniformly distributed direction; the Box–Muller transform is one way to generate normal samples.

52:00 Randomly Shifted Bins Create One-Dimensional Euclidean LSH

For points on the real line and a distance scale σ, choose an offset β uniformly from [0, σ] and divide the line into bins of width σ.
Hash a point by its bin index, computed from its shifted coordinate and a floor operation.
For points less than σ apart, collision probability decreases linearly with distance: 1 − |a − b|/σ; it is zero at distances of at least σ.

58:00 Projection Extends Shifted-Bin LSH to Euclidean Space

In higher dimensions, project a point onto a random direction u, apply a random offset β, and quantize the result into bins of width σ.
A standard form is h(a) = ⌊(u · a + β)/σ⌋; projection reduces the Euclidean comparison to the one-dimensional binning construction.
This combines geometry, linear algebra, and randomness; the lecture notes that graph-based methods such as HNSW often search more efficiently but lack the same probabilistic guarantees.

1:01:00 County Counts Become Probability Vectors on a Simplex

Represent observations across Utah’s 29 counties as counts C₁ through C₂₉, then normalize each count by the total n to obtain xᵢ = Cᵢ/n.
The resulting vector has nonnegative coordinates summing to one, so it lies on the 28-dimensional probability simplex rather than in unrestricted Euclidean space.
This representation compares distributions across counties while preserving the constraint that all county probabilities total one.

1:07:00 KL Divergence and Hellinger Distance Compare Discrete Distributions

Kullback–Leibler divergence is Dₖₗ(A‖B) = Σᵢ aᵢ log(aᵢ/bᵢ); it is information-theoretically motivated and is not symmetric.
Hellinger distance compares square-root-transformed probabilities, commonly written as √(Σᵢ(√aᵢ − √bᵢ)²), connecting probability vectors to Euclidean geometry.
The choice between these measures changes how differences between county-level or other discrete distributions are modeled.

1:12:00 Wasserstein Distance Preserves Geometry Between Point Distributions

When observations are locations in ℝᵈ, county aggregation can discard useful geometry, such as the fact that Utah County and Salt Lake County are adjacent.
The Wasserstein-1 distance, also called earth mover’s distance, finds a minimum-cost matching or mass transport between two point distributions.
Computing the optimal matching requires solving an optimization problem, making Wasserstein distance informative about spatial movement but relatively expensive.

1:16:00 Distance Choice Is a Modeling Decision for Clustering

Wasserstein-2 and other Lᵖ variants offer additional ways to quantify transport between distributions.
Methods for fast retrieval and LSH exist for several distribution distances, but their suitability depends on the chosen representation and metric.
The next course topic is clustering with a given dataset and distance, while keeping the modeling tradeoffs behind that distance in view.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, UofU Data Science.