Breaking the Curse of Dimensionality via Locality Sensitive Hashing

This direction is merged into another direction: locality-sensitive hashing. Its last version stays readable and citable here.

Version 1 of 165 papers70 conceptsfrozen 2026-10-04

In high-dimensional spaces, traditional search methods collapse. As the number of dimensions grows, the "distance" between any two points becomes less meaningful, and the computational cost of finding a nearest neighbor scales linearly with the size of the dataset. This is the "curse of dimensionality." To find a needle in a haystack of millions of vectors, we usually have to look at every single straw.

Aristides Gionis, Piotr Indyk, and Rajeev Motwani fundamentally changed this landscape by introducing Locality-Sensitive Hashing (LSH). Their insight was simple: if we can't find the exact nearest neighbor efficiently, we should trade a small amount of accuracy for a massive gain in speed.

The Intuition of Purposeful Collisions

In standard cryptographic hashing, collisions are a failure. We want two different inputs to result in two completely different hash values. LSH flips this logic on its head. It uses a family of hash functions designed so that the probability of two points sharing the same hash "bucket" is proportional to their similarity.

If two points are close in high-dimensional space, they are likely to "collide" in the hash table. By hashing a query point and only searching the resulting bucket, we ignore the vast majority of the dataset. This transforms the search from a linear scan of $N$ items into a sub-linear lookup, as demonstrated in Similarity Search in High Dimensions via Hashing.

Optimizing the Search Space

While basic LSH is fast, it can be memory-intensive because it often requires many hash tables to ensure high recall. William Josephson and Kai Li addressed this with Multi-Probe LSH. Instead of just checking the single bucket where a query lands, their algorithm intelligently probes "nearby" buckets. By looking at buckets that are geometrically adjacent to the query's primary bucket, they achieved the same search quality with an order of magnitude less memory.

Further refinements like Falconn++, developed by Ninh Pham and Tao Liu, add a "filtering" layer. They use cheap projection values to prune candidates within a bucket before performing expensive distance calculations, making the process even leaner.

Hashing Beyond Points

The power of LSH extends beyond simple vectors. Researchers have adapted the mechanism to handle complex geometric structures:

  • Subspaces: John Wright and Xu Wang developed Grassmannian-based Locality Hashing (GLH) to find similar linear subspaces. By measuring the angles between subspaces and random lines, they enable sub-linear retrieval for tasks like face recognition.
  • Sets: Yuzhe Lu and Yan Lu introduced SLoSH, which uses Sliced-Wasserstein Embeddings to map set-structured data (like point clouds) into a space where LSH can be applied.
  • Binary Signatures: Jianmin Li and colleagues showed how to map these complex geometries into compact bitstrings, allowing for hardware-efficient bitwise comparisons that are hundreds of times faster than floating-point math.

LSH as a Computational Engine

LSH is no longer just a search tool; it has become a primitive for scaling other algorithms.

In Federated Learning, Qinbin Li and Zeyi Wen use LSH to identify similar data points across different organizations without ever exchanging raw, private data. In NLP, Sujith Ravi used hash sampling to scale machine translation decipherment to massive monolingual corpora.

Perhaps most surprisingly, LSH can act as an "informative sampler." Anshumali Shrivastava and Ryan Spring demonstrated that LSH can estimate the "partition function" in log-linear models. By treating the hashing probability as a proposal distribution, they can train large-scale models using only 1% of the typical calculations.

Why It Works

The success of LSH across these diverse fields—from metagenomics Qi Wang to star identification Hailong Zhu—stems from its ability to preserve the topology of data while discarding its density. By mapping high-dimensional continuity into discrete, searchable buckets, LSH provides a probabilistic bridge that allows us to navigate the "data deluge" without drowning in the math of exact distances.

Papers in this version

Showing 60 of 65 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_breaking_the_curse_of_dimensionality_via_84ba0ab4,
  title = {Breaking the Curse of Dimensionality via Locality Sensitive Hashing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/breaking-the-curse-of-dimensionality-via-locality-sensitive-hashing/rdr_84ba0ab42cc248f6af046e7080f4d04a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_breaking_the_curse_of_dimensionality_via_84ba0ab4_v1,
  title = {Breaking the Curse of Dimensionality via Locality Sensitive Hashing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/breaking-the-curse-of-dimensionality-via-locality-sensitive-hashing/rdr_84ba0ab42cc248f6af046e7080f4d04a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}