Sublinear Scaling for High Dimensional Similarity Search

31 concepts30 papers1 proposal

In the era of massive datasets, the "curse of dimensionality" presents a fundamental computational bottleneck. Traditional exact search methods require a linear scan of the entire database—an $O(N)$ operation that becomes untenable when $N$ reaches billions of items. To maintain millisecond-level response times, research has shifted toward algorithms where search latency scales sublinearly with the number of items.

This direction encompasses a variety of mechanisms—hashing, graph traversal, and randomized embeddings—that trade off exhaustive precision for dramatic gains in efficiency. As Bruch et al. demonstrate, modern approximate sparse retrieval can handle a fifteen-fold increase in data with only a three-to-eight-fold increase in response time.

Hashing as a Pruning Mechanism

The most influential approach to sublinear search is Locality-Sensitive Hashing (LSH). Introduced by Gionis et al., LSH uses hash functions designed to maximize collisions for "nearby" points. By hashing items into buckets, the search space is pruned from the entire database to just a few candidate buckets, achieving sublinear query time.

The intuition behind hashing has been extended to handle increasingly complex data structures:

  • Subspaces and Hyperplanes: Rather than searching for points, Wright et al. leverage the geometry of the Grassmannian manifold to find the closest linear subspace in sublinear time. Similarly, Liu et al. use multilinear projections to identify points near a query hyperplane, which is critical for scaling active learning to millions of samples.
  • Feature Sets: Grauman et al. developed Pyramid Match Hashing to embed partial correspondences between sets of local features into an LSH-compatible space, allowing for efficient image retrieval by examining only 1–3% of the database.
  • Distance Sensitivity: While standard LSH finds the "closest" items, Pagh et al. introduced Distance-Sensitive Hashing (DSH), which allows for sublinear "annulus queries"—finding items within a specific distance range to avoid redundancy in recommendations.

The theoretical limits of this approach were refined by Andoni et al., who established an optimal bound for data-dependent hashing, reducing query complexity to a factor of the approximation quality.

While hashing partitions space, graph-based methods exploit the fact that high-dimensional data often resides on a low-dimensional manifold. By constructing a proximity graph where nodes are data points and edges connect neighbors, search becomes a greedy traversal problem.

Harwood et al. show that search costs in these structures follow a power-law relationship with dataset size, ensuring that latency remains manageable even as the database grows by orders of magnitude. This graph-based paradigm is particularly effective for complex scoring models. For instance, Babenko et al. use Relevance Proximity Graphs to achieve sublinear retrieval for non-linear models like Deep Neural Networks, where traditional matrix factorization fails.

A common misconception is that sublinear scaling requires sacrificing accuracy. However, several researchers have developed methods for exact nearest neighbor search that still beat the linear scan.

The core intuition often involves clever partitioning. Norouzi et al. introduced Multi-Index Hashing (MIH) for Hamming space. By splitting long binary codes into disjoint substrings and searching multiple hash tables, the authors guarantee exact results with a query time complexity approximately the square root of the database size. This challenges the prior assumption that exact search in high dimensions inherently requires linear time.

Other breakthroughs in exact search include:

  • Structured Hash Families: Pham et al. developed Fast CoveringLSH, which provides 100% recall (zero false negatives) while maintaining sublinear speeds.
  • Probabilistic Polynomials: Alman et al. utilized low-degree polynomial representations of Boolean functions to achieve subquadratic time for exact Batch Hamming search, breaking traditional complexity barriers.

Scaling Beyond Point Retrieval

Sublinear scaling principles are also being applied to broader data science tasks. Abboud et al. demonstrated that hierarchical clustering can be reduced from quadratic to nearly linear time by replacing exact nearest neighbor scans with approximate ones.

For set operations, Gupta et al. proposed RAMBO, a merged Bloom filter architecture that achieves $O(\sqrt{K} \log K)$ query time for multiple set membership testing. This allows researchers to search across massive genomic repositories (hundreds of terabytes) in hours rather than weeks.

As summarized by Qin et al., the maturation of these techniques—from product quantization to learned indexes—has turned sublinear retrieval from a theoretical curiosity into the backbone of modern large-scale data science.

Key Foundational Work

Similarity Search in High Dimensions via Hashing (1999) — contributed 1 concept elements to this direction.
Multiscale approximation methods (MAME) to locate embedded consecutive subsequences—its applications in statistical data mining and spatial statistics (2002) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sublinear_retrieval_scaling_ea3e4f29,
  title = {sublinear retrieval scaling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sublinear-retrieval-scaling/rdr_ea3e4f29283d4a349326efea282aa571},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_sublinear_retrieval_scaling_ea3e4f29_v1,
  title = {sublinear retrieval scaling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sublinear-retrieval-scaling/rdr_ea3e4f29283d4a349326efea282aa571/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake