Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 36 ยท Indexing and ANN Search

Locality-Sensitive Hashing

Learn how random-hyperplane LSH hashes similar vectors into the same buckets, how bits and tables trade recall for speed, and when LSH beats or loses to HNSW.

A normal hash function scatters inputs: change one character of a string and the hash changes completely. A locality-sensitive hash does the opposite on purpose. Similar vectors get the same hash with high probability, dissimilar vectors get different hashes. Put vectors in buckets named by their hash, and a query only has to look in its own bucket.

LSH is the oldest ANN idea with theory behind it, it needs no training, and it supports cheap inserts and deletes. In practice graph and cluster indexes (HNSW, IVF) beat it for dense text embeddings, but LSH remains important for near-duplicate detection, streaming data, and for understanding binary codes.

Random hyperplanes for cosine similarity

Pick a random vector r and look at the sign of r . x: it says which side of a hyperplane through the origin the vector x lies on. Two vectors with a small angle between them are usually on the same side; vectors pointing in opposite directions are always on opposite sides. For one random hyperplane the chance that two vectors get the same bit is 1 - angle / pi.

Use b hyperplanes and you get a b-bit signature, a short binary string for each vector.

Python Collision probability follows the angle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The measured values match the formula. Close vectors agree on nearly every bit; vectors at 90 degrees agree half the time (a coin flip); opposite vectors never agree.

Buckets and tables

With b bits there are 2^b buckets. Two vectors that are close land in the same bucket only if all b bits match, which gets less likely as b grows. So:

  • More bits per table: smaller buckets, fewer false matches, faster scans, but more true neighbors get separated (lower recall).
  • To win recall back, build L independent tables with different random hyperplanes. A query collects candidates from its bucket in every table, takes the union, and ranks that small set exactly.
flowchart LR
    Q["Query"] --> H1["Table 1: hash with b random planes"]
    Q --> H2["Table 2: hash with b other planes"]
    Q --> H3["Table L: ..."]
    H1 --> U["Union of the three buckets = candidates"]
    H2 --> U
    H3 --> U
    U --> R["Exact re-rank, return top-k"]

Each table gives a chance to catch a neighbor; the union is cheap to re-rank.

Python An LSH index with tables and bits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You can see both dials. Going from 8 to 12 bits with 8 tables cuts the share scanned from 4.2% to 0.5% but drops recall from 0.62 to 0.25; tripling the tables to 24 brings recall back to 0.61 while scanning only 1.4%. Even the best row here is far below the recall that IVF reached on similar data, which is the practical weakness of plain LSH on dense embeddings. Good settings sit where recall is high while the scanned share is small, and finding them requires experiments (tuning).

Where LSH is a good choice

  • Near-duplicate detection: hashing documents (with MinHash for sets of words, or SimHash) so near-copies collide. This is used when deduplicating a corpus before indexing.
  • Streaming or constantly changing data: inserting means computing L hashes and appending ids to buckets. Deleting means removing ids. No retraining, no graph repairs.
  • Very high dimensions, huge data, tiny memory per item: signatures can be a few bytes.
  • Simple and distributed: buckets shard naturally by key across machines.

Where it falls short

  • For dense text embeddings it usually needs many tables to reach recall that HNSW gets with one structure, so it is larger and slower at equal recall.
  • Random hyperplanes ignore the data's structure; learned methods (clusters, graphs) exploit it.
  • Choosing bits and tables is data-dependent trial and error, and a bad choice silently lowers recall.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What property must a locality-sensitive hash have?

    Unlike cryptographic hashes, LSH is designed so that nearby items collide more often than distant ones.
  2. 2. For two vectors at a 90-degree angle, what is the chance a random hyperplane gives them the same bit?

    The probability is 1 minus angle over 180 degrees, which is 0.5 at 90 degrees.
  3. 3. You add more bits to each table. What happens to bucket sizes and recall?

    All bits must match, so fewer vectors share a bucket and some true neighbors are separated.
  4. 4. How do multiple hash tables help?

    The candidate set is the union of matching buckets across tables, which raises recall.
  5. 5. Which task suits LSH especially well?

    Cheap inserts and collisions for near-copies make LSH a natural fit for deduplication.

Summary

  • LSH hashes similar vectors to the same bucket; random hyperplanes realise this for cosine similarity.
  • bits sets bucket selectivity, tables restores recall; candidates are re-ranked exactly.
  • It needs no training and supports cheap updates, but dense-embedding search is usually better served by HNSW or IVF.
  • LSH shines for near-duplicate detection and streaming data.

Next: Tuning and Benchmarking Vector Indexes