Sublinear Retrieval for Large Scale Search

This direction is split into other directions: linear search complexity. Its last version stays readable and citable here.

Version 1 of 190 papers91 conceptsfrozen 2026-10-04

In the early days of information retrieval, searching a database was a straightforward task: you compared your query to every single item in the collection. This "linear search" approach works perfectly for a few thousand records. However, as modern datasets scale to millions or billions of entries—whether they are faces, images, or "thoughts" in a Large Language Model (LLM)—this $O(N)$ complexity becomes a brick wall.

The research direction across these papers focuses on sublinear retrieval: the art of decoupling search time from the total volume of stored information. The goal is to achieve retrieval times that scale logarithmically ($O(\log N)$) or even independently ($O(1)$) of the database size.

The Linear Search Wall

The fundamental problem, as noted by Rada M. Granovskaya as early as 1971, is that identification time should not grow in lockstep with memory volume. In modern contexts, Lei Liu and colleagues point out in Think-in-Memory that exhaustive pairwise similarity searches create a latency bottleneck that prevents real-time interaction in long-term memory systems. Whether it is a robot trying to recognize a face in a city-scale environment Beyond SIFT using Binary features for Loop Closure Detection or a business identifying users for a new product SAH: Shifting-aware Asymmetric Hashing for Reverse k-Maximum Inner Product Search, the "store-and-compare" strategy eventually fails.

Geometric and Hierarchical Partitioning

The most intuitive way to break the linear bottleneck is to organize data so that large swaths of the search space can be discarded instantly.

Richard H. Stottler pioneered this using recursive spatial partitioning, which treats data as points in a multi-dimensional space and carves that space into smaller and smaller regions. Similarly, Kevin R. Farrell and Richard J. Mammone introduced Neural Tree Networks, which use the hierarchical efficiency of decision trees to achieve logarithmic retrieval times for speaker recognition.

In the era of LLMs, this concept has evolved into From Isolated Conversations to Hierarchical Schemas: Dynamic Tree Memory Representation for LLMs. By organizing interactions into a dynamic tree structure rather than a flat vector database, models can navigate from high-level summaries to granular details without scanning every past conversation.

Binary Fingerprinting and Hashing

If partitioning is about where the data lives, hashing is about what the data is. By compressing complex objects into short binary "fingerprints," researchers can perform near-instantaneous comparisons.

Alex Krizhevsky and Geoffrey E. Hinton demonstrated in Using very deep autoencoders for content-based image retrieval that deep learning could map images into compact binary codes. This allows for "semantic" searching where the distance between binary strings reflects the visual similarity of the images.

To further optimize this, Jian Cheng proposed Fast and Accurate Image Matching with Cascade Hashing for 3D Reconstruction, which uses a multi-layered approach to filter candidates from coarse to fine. Similarly, Rong-Cheng Tu introduced the HEI framework, which uses binary hashing as a "plug-and-play" pre-filter to narrow down billions of entries to a tiny pool that expensive attention models can then process.

From Search-and-Match to Memorize-and-Generate

A radical shift in this field is the move toward Generative Retrieval. Instead of maintaining an external database and searching through it, the model internalizes the data within its own parameters.

The Generative Cross-Modal Retrieval (GRACE) framework by Yongqi Li and colleagues treats retrieval as a "recall" task. By associating images with unique text identifiers, the model can "generate" the identifier of a matching image directly. This approach, also seen in Unified Text-to-Image Generation and Retrieval, bypasses the need for dense vector similarity searches entirely, offering a path toward constant-time retrieval.

Hardware and Parallelism

Finally, when software algorithms reach their limits, researchers turn to specialized architectures. Ian N. Robinson proposed the Chameleon board, a hardware co-processor that integrates logic directly into "smart memory" chips to enable index-free searching. On the software-parallel side, Matthew P. Evett developed PARKA, which uses a "parallel activation wave" to search millions of knowledge frames in time proportional only to the depth of the network, not its size.

Summary of Intuition

The transition from linear to sublinear retrieval is essentially the transition from scanning to indexing and memorizing:

  1. Trees/Partitioning: Don't look at the whole library; look at the signposts for the right section.
  2. Hashing: Don't compare the whole book; compare the ISBN.
  3. Generative Retrieval: Don't go to the library at all; memorize the book's location.

By combining these mechanisms, researchers are enabling AI systems to maintain real-time performance even as the world's digital knowledge continues to grow exponentially.

Papers in this version

Showing 60 of 90 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sublinear_retrieval_for_large_scale_sear_7432b401,
  title = {Sublinear Retrieval for Large Scale Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sublinear-retrieval-for-large-scale-search/rdr_7432b40124b2425eb933df8bef8d3794},
  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_for_large_scale_sear_7432b401_v1,
  title = {Sublinear Retrieval for Large Scale Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sublinear-retrieval-for-large-scale-search/rdr_7432b40124b2425eb933df8bef8d3794/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}