Locality-Sensitive Hashing: Finding Similar Items in Massive Datasets

Why Ordinary Hashing Fails at Similarity Search

A standard hash function, the kind used in hash tables and hash maps, is judged by how well it avoids collisions. If two different keys hash to the same value, that is treated as an unfortunate coincidence, handled with chaining or probing, and ideally made as rare as possible through good avalanche behavior, where a tiny change to the input scrambles the output completely and unpredictably. That property is exactly what you want for building a dictionary or a cache, but it is the opposite of what you want for similarity search. Imagine you have ten million image embeddings, each a vector of a few hundred numbers, and you want to find the handful that are visually similar to a new photo. Comparing the query against all ten million vectors one at a time, an approach called brute-force or linear scan, requires a full pass over the entire dataset for every single query. As the dataset grows to billions of items, this becomes far too slow for any interactive application, whether it is a reverse image search, a plagiarism checker, or a product recommendation engine. Tree-based structures such as kd-trees solve a related problem, exact nearest-neighbor search, but they work well only in low dimensions. Once the number of dimensions climbs into the dozens or hundreds, which is typical for embeddings from modern machine learning models, tree structures suffer from the curse of dimensionality: nearly every branch of the tree ends up needing to be explored, and the search degrades toward the same cost as comparing against everything. LSH sidesteps both problems at once. It gives up the guarantee of finding the exact nearest neighbor and instead finds an approximate one with high probability, and it scales gracefully to high-dimensional, high-volume data by using specially designed hash functions instead of a branching tree.

Random Hyperplane Hashing for Cosine Similarity

One of the clearest ways to build a locality-sensitive hash function is random hyperplane hashing, designed for data compared using cosine similarity, which measures the angle between two vectors rather than their raw distance. The idea starts with picking a random hyperplane through the origin of the vector space, defined by a random vector. For any data point, you check which side of the hyperplane it falls on, producing a single bit, say zero or one. Intuitively, if two vectors point in nearly the same direction, a randomly chosen hyperplane is very unlikely to slice between them, so they almost always land on the same side and get the same bit. If two vectors point in very different directions, a random hyperplane is much more likely to separate them, so they often get different bits. This single-bit hash is a weak signal on its own, but it has the essential locality-sensitive property: the probability that two vectors get the same bit is directly related to the angle between them, and therefore to their cosine similarity. To turn this weak signal into a usable hash bucket, you generate several random hyperplanes at once, say sixteen or thirty-two of them, and concatenate the resulting bits into a single binary code. Two items that share that exact binary code land in the same bucket. Because each individual bit only weakly favors similar items, using many bits together makes the combined signature much more discriminating, sharply reducing the chance that dissimilar vectors accidentally share a bucket while still keeping very similar vectors together most of the time. This technique underlies many practical nearest-neighbor systems for embeddings produced by neural networks, where cosine similarity is the natural notion of closeness.

MinHash and Jaccard Similarity for Sets

A different flavor of LSH, called MinHash, is built for data represented as sets rather than vectors, and for similarity measured by the Jaccard similarity, defined as the size of the intersection of two sets divided by the size of their union. This is the natural notion of closeness for tasks like near-duplicate document detection, where each document is represented as the set of overlapping word sequences, or shingles, that appear in it, or for comparing the sets of items two users have purchased in a recommendation system. The MinHash trick works like this: take a random permutation of the entire universe of possible elements, apply it to a set, and record the minimum element that appears in that set after permutation. It is a remarkable fact that the probability two sets share the same minimum element under a random permutation is exactly equal to their Jaccard similarity. In other words, this single random statistic is, in expectation, a perfect estimator of set overlap. In practice, computing a true random permutation over a huge universe is expensive, so implementations use a family of independent hash functions and take, for each one, the minimum hashed value across the set's elements, building a compact signature made of many such minimums. Two documents with a high Jaccard similarity will agree on many of these minimum values, while two very different documents will rarely agree on any of them. Just as with random hyperplane hashing, this weak per-hash signal becomes a strong discriminator once many independent MinHash values are combined into a signature, letting near-duplicate detection systems, such as those used to find plagiarized text or mirrored web pages, compare compact fixed-size signatures instead of the full original documents.

The AND-OR Construction: Banding for Precision and Recall

A single hash signature, whether built from random hyperplanes or MinHash values, gives you a knob but not yet a well-tuned system. Real LSH implementations combine many hash functions using a two-layer structure often called the AND-OR construction or banding. Within one hash table, you concatenate several hash values together, say a band of five, and require all five to match for two items to be considered a candidate pair in that table. This is the AND part: agreeing on all five hash values is a strict requirement, which makes false collisions between dissimilar items rare, but it also makes it easier for two genuinely similar items to just barely miss on one of the five and be lost. To recover that lost recall, you build several independent hash tables this way, each with its own randomly chosen band of hash functions, and you declare two items a candidate pair if they collide in at least one of these tables. This is the OR part: needing to match in only one table out of many makes it far more likely that a truly similar pair will be caught by at least one table, even if they miss in most of the others. The two knobs work against each other in a predictable and mathematically well-understood way. Increasing the band width, the number of hash functions ANDed together within a table, increases precision by filtering out more false positives, but decreases recall because genuine matches are more likely to fail to match on all of them. Increasing the number of independent tables, the OR part, increases recall by giving similar items more chances to collide somewhere, but increases both memory use and query cost since every table must be checked. Practitioners tune these two numbers based on the similarity threshold they care about and how much they are willing to trade accuracy for speed and memory.

Why This Beats Brute-Force Search at Scale

The entire payoff of LSH comes down to what happens at query time. Without LSH, finding the nearest neighbors of a query point among a dataset of size n requires comparing the query against all n items, an approach whose cost grows linearly with the size of the dataset; double the data, double the query time, which becomes unworkable once n reaches the billions. With LSH, the expensive comparisons only happen among the small set of candidates that land in the same bucket, or buckets, as the query, after the hash tables have already done the heavy lifting of narrowing the search space. Because the hash functions were specifically designed so that similar items are likely to collide, that small bucket is disproportionately likely to contain the true near neighbors, even though it represents a tiny fraction of the overall dataset. Hashing the query itself takes time that depends only on the number of hash functions used, not on the size of the dataset, and looking up the corresponding buckets in a hash table is a fast, roughly constant-time operation. The result is a query cost that stays close to constant, or at worst grows very slowly, as the dataset grows, instead of scaling with every item in it. This is precisely why LSH became foundational infrastructure for systems that must operate at internet scale: reverse image search engines that index billions of photos, recommendation systems comparing millions of user profiles, and near-duplicate detection pipelines that scan huge web crawls for copied or mirrored content. The tradeoff is that LSH is approximate; it can occasionally miss a true near neighbor or admit a false one, unlike an exact method. But by tuning the banding structure, that error rate can be pushed as low as an application requires, while keeping the enormous speed advantage that makes searching truly massive, high-dimensional datasets practical in the first place.

Frequently asked questions

Try it live

Everything above runs in your browser — open Locality-Sensitive Hashing: Finding Similar Items in Massive Datasets and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.