[October 2026 edition]

Indexes and the Art of Searching, Part 4: Similarity Search and Recommendation

Published: Oct 2, 2026
Reading time: ~16 min

Part 3 covered choosing candidates by word matches and ranking them. Part 4 covers vector search and recommendation, which find content that is close in meaning even when the words differ.

1. From Matching to Similarity: Match Criteria and Ranking Signals

The structures covered so far fall into two layers. The first layer is the match criterion that decides the candidates; the second is the signal that ranks them.

Match criterion	Question	Structures and methods	Covered in
Identity	Are the keys equal?	Hash table, B-tree, Bloom filter	Part 2
Order and range	Can it be narrowed by comparison?	Sorting, B-tree, sparse primary index	Parts 1 and 2
Form	Does a string or word occur?	String scanning, inverted index	Part 3
Distance	Is it close in the space?	Vector search	Part 4

Ranking signal	What it uses	Structures and methods	Covered in
Content	Word matches between query and document	BM25, rerankers	Part 3
Structure	Links between data	PageRank	Part 3
Behavior	User history and clicks	Learning to rank, collaborative filtering	Parts 3 and 4

With identity, order, and form, whether an item qualifies is decided exactly. With distance, closeness is a matter of degree expressed as a continuous value, and methods that return an approximate top k are the practical mainstay. Exact k-nearest neighbors can be computed too, but computing distances to every item in high dimensions is expensive.

The multistage design of candidate generation, ranking, and reranking is shared by search and recommendation. Google’s introduction to recommendation systems describes recommendation in three stages: candidate generation, scoring, and re-ranking. Recommendation can be viewed as search that treats the user’s history as an implicit query. It pulls candidates by distance from the first layer and orders them by behavioral signals from the second.

2. Similarity Search by Hash Collisions: LSH and MinHash

A hash table gathers items with equal keys into the same slot. If similar papers in a filing cabinet go into the same drawer, opening a single drawer gets you all the similar papers at once; in the same way, if you can design a hash that sends nearby items to the same slot, similarity search turns into a hash-table lookup. That is locality-sensitive hashing (LSH). In 1998, Indyk and Motwani proposed LSH as a method built on hash functions under which nearby items collide with sufficiently higher probability than distant ones. The paper guarantees preprocessing polynomial in n and d and query time truly sublinear in n. Here n is the number of items and d the number of vector dimensions, and sublinear means that as the data grows, query time grows more slowly than the data. A method that compares against every item takes twice as long when the data doubles, so the gap widens as the item count rises.

How the hash is built depends on the kind of similarity. To measure how alike two documents are, you split each document into fragments of a few consecutive words and take the share of fragments the two documents have in common, out of all the fragments in either one. That share is the Jaccard coefficient, and Broder defined resemblance as the Jaccard coefficient of documents viewed as sets of contiguous word sequences (shingles). From more than 30 million documents collected by AltaVista, over 150GB of input, Broder built 3.6 million clusters using a 50% resemblance threshold. The estimate relies on MinHash. Give every fragment a lottery number by the same rule, and pick the fragment with the smallest number in each document as that document’s representative; two documents then share a representative exactly when the smallest number among all their fragments combined falls in the shared part. So the probability that the representatives match is precisely the share of the shared part. The Min-Wise paper states this property as: under a uniformly random permutation, the probability that the minimum elements of two sets coincide equals their Jaccard coefficient. Choose representatives many times with different ways of assigning the numbers, and the fraction of matches estimates the similarity. In practice, each document stores the minimum under each of 100 independent random permutations, and resemblance is estimated from the number of matches.

For cosine similarity, Charikar presented a hash that outputs one bit according to which side of a random hyperplane a vector falls on. Cut the space in two with a randomly oriented plane, and two vectors pointing in similar directions tend to land on the same side, while the wider the angle between them, the more likely the plane passes between them. The probability that two vectors get the same bit is therefore 1 − θ/π, where θ is the angle between them. Datar et al. built a hash for Euclidean distance by projecting vectors onto a randomly oriented line, cutting that line into segments of fixed width, and putting vectors that fall in the same segment into the same bucket. Using random values with a property called p-stability for the projection makes the distance between projections reflect the original distance. The paper reports that in experiments on synthetic data this scheme was up to 40 times faster than a kd-tree.

Another way to replace vectors with short codes is product quantization. A long vector is cut into several segments, each segment has its own list of representative points, and only the index of the closest representative in each segment is recorded. It resembles writing an address as prefecture, city, and town, each given as a number from a list. Jégou et al. formalized this as decomposing the space into a Cartesian product of low-dimensional subspaces, quantizing each subspace separately, and representing a vector as a short code made of the quantization indices for each subspace. In the setting that encodes 128-dimensional SIFT descriptors in 64 bits, each of 8 subspaces has 256 centroids, and the code takes 8 bytes. Because a point is represented by a combination of per-segment indices, the number of representable points is 256 multiplied by itself 8 times, which makes fine distinctions with very little storage. A 128-dimensional float32 vector takes 512 bytes, so this shrinks it to 1/64.

For large-scale vector search, methods that exploit the distribution of the vectors have the upper hand over LSH. In the same paper, Jégou et al. write that on real data LSH falls behind such methods. ANN-Benchmarks also reports that graph-based methods are best on many datasets and that HNSW is often the fastest. The strength of LSH is that it handles similarity search with the same equality-test tooling as a hash table. That makes it useful where the similarity is something other than vector distance, such as detecting duplicate sets.

3. Vector Search: Speed in Exchange for Approximation

Where traditional search relies on ordering, equality, and word matches, vector search turns documents, images, and audio into high-dimensional vectors and looks for objects whose distance or inner product is close. Computing the distance to every vector in a high-dimensional space is expensive, so most systems use approximate nearest neighbor (ANN) search.

Method	Core idea
Flat	Compute the distance to every item
IVF	Partition the space into clusters and examine only nearby clusters
PQ	Split vectors into subspaces and quantize them
HNSW	Traverse a hierarchical neighbor graph
DiskANN	Search a neighbor graph on SSD efficiently

HNSW, proposed in 2016, is a graph index that starts searching from a sparse upper-layer graph and descends into denser lower layers as it looks for neighbors. It works like a trip to a distant destination: take the highway to get close, then drop down to ordinary roads and finally to narrow streets. The upper layers cross a few points in long strides, and the lower layers search the neighborhood in fine detail. DiskANN was designed for billion-scale nearest-neighbor search by placing a huge vector collection across SSD and memory. The NeurIPS 2019 paper handles a billion points on a single workstation with 64GB of RAM and an inexpensive SSD.

pgvector offers HNSW and IVFFlat. HNSW has the better speed-recall tradeoff, but it builds slowly and uses more memory. IVFFlat, for its part, needs a training step and clustering up front.

Being approximate, these methods can miss some of the true neighbors. The evaluation metrics change accordingly: besides accuracy metrics such as Recall@k, Precision@k, nDCG, and MRR, you look at index build time, update latency, and p95 and p99 query latency. In ANN, Recall@k is the fraction of the true k nearest neighbors, found by checking every item, that appear among the k results the approximate search returned, so it expresses how little is missed. p95 and p99 are the 95th and 99th latencies when 100 queries are sorted from fastest to slowest, and they capture the waiting time of slow queries that an average would bury. Memory per vector, freshness, and recall under filtered search all matter at the same time.

Looking only at averages hides failures. A 2026 study pointed out that two systems with the same average Recall@k can behave very differently on individual queries. One delivers moderate recall on every query, while the other is near perfect on most queries but finds almost no neighbors for a few, and the average shows the same value for both. Because the long tail of hard queries disappears into the average, the paper proposed setting a passing bar for per-query recall and counting what fraction of all queries clear it. This is Robustness-δ@K, defined as the fraction of queries exceeding a threshold δ. If you treat ANN results as ground truth, you miss the fact that they change as soon as you alter the index build settings or search parameters.

4. Vector Indexes That Keep Changing

Many recent proposals take an adaptive design that keeps adjusting an index after it is built, following updates and shifts in access. The issues include in-place updates, tombstone handling, partial rebuilds, and streaming inserts, and the same discussion takes in distribution drift over time, adaptation to skewed access, and tiering across memory and disk.

FreshDiskANN handles thousands of concurrent inserts, deletes, and searches per second on a billion-point graph index while keeping 5-recall@5, the fraction of the true 5 nearest neighbors that appear among the 5 returned, at 95% or higher. It reports that the cost of maintaining freshness dropped to between 1/5 and 1/10 of that of existing methods. Quake, presented at OSDI 2025, adjusts multilevel partitions according to updates and access patterns. It has a cost model that predicts latency from partition size and access frequency, and it also sets search parameters dynamically. LSM-VEC splits an HNSW-style neighbor graph, keeps the upper layers in memory and the bottom layer in an LSM-tree, and processes updates without rewriting data in place. Here the classic LSM-tree meets modern vector search once again.

Quantization and reduced precision are advancing too. Converting vectors from float32 to int8, binary, or product-quantized codes cuts memory and cache usage and the cost of distance computation all at once. A widely used design generates candidates with low-precision vectors and reranks only a small number of them with the original vectors.

5. Queries Distributed Differently from the Indexed Data

The performance of a vector index depends on how the distribution of the indexed data relates to the distribution of queries. The OOD-DiskANN paper pointed out that data-dependent indexes such as HNSW, FAISS-IVF, and DiskANN lose their advantage when queries come from a different distribution than the index. In an example that sends text queries to an image index, latency for out-of-distribution queries at a fixed target recall is more than an order of magnitude worse than for in-distribution queries.

In the NeurIPS 2021 big-ann-benchmarks competition, the same baseline achieved very different recall depending on the dataset. At 10000 QPS, BIGANN reached 0.6345 and Text-to-Image 0.0693. The paper explains that in Text-to-Image the query and base distributions are entirely different (text embeddings versus image embeddings), which makes it especially hard for methods that rely on quantization or compression.

Difficulty also varies from query to query. The study by Aumüller and Ceccarello showed that recall drops as a query’s local intrinsic dimensionality (LID) rises. Even when vectors have hundreds of dimensions, the data around a given query may actually spread out in only a few directions. Local intrinsic dimensionality estimates the number of dimensions of that local spread from how sharply the number of neighbors grows when the distance from the query is widened a little. Around a query with a high value, the difference in distance between near points and slightly farther points shrinks, and picking out the close ones becomes hard. No implementation adapts to query difficulty, so keeping average recall high requires parameters tuned for the hard queries, which makes the easy queries correspondingly much slower.

Whether to choose a method specialized for out-of-distribution queries also depends on the data. VIBE compared 22 implementations on 11 in-distribution and 8 out-of-distribution datasets. On out-of-distribution data from text retrieval and text-to-image, the best general-purpose methods outperformed the out-of-distribution specialists. On the other hand, the inner-product search data used to compute approximate attention had the largest gap between query and document distributions, and Glass and hnswlib failed to reach 50% average recall in every configuration evaluated. RoarGraph, an out-of-distribution specialist, beat Glass on one dataset and lost to it on another. In the end, the only way to decide which method is better is to measure with your own queries.

6. Recommendation: Search with History as an Implicit Query

Recommendation, which suggests items a user is likely to want based on their history, also has the structure of pulling candidates and then ordering them. YouTube’s 2016 paper builds recommendation in two stages: candidate generation, which narrows a vast pool of videos down to candidates, and a separate ranking model that orders them.

At the core of candidate generation is turning users and items into vectors in the same space and pulling the nearby ones. Matrix factorization learns, for each user, a list of numbers describing their tastes and, for each item, a list of numbers describing its characteristics, and represents preference as the inner product of the two. A user whose vector leans toward action movies and a film whose vector has a strong action component produce a large inner product, and the film gets recommended. Because closeness is measured by inner product, candidate retrieval becomes maximum inner product search (MIPS). With a distance, if A is close to B and B is close to C, then A and C are also reasonably close (the triangle inequality), and most nearest-neighbor methods rely on this to narrow the search region. With inner products, long vectors tend to score high against queries in any direction, and that guide breaks down. Shrivastava and Li showed that because the inner product does not satisfy the triangle inequality, the existing LSH framework used for distance-based nearest-neighbor search is insufficient for MIPS, and they extended it to asymmetric hashing. Their evaluation uses item recommendation on Netflix and MovieLens.

Which recommendation method comes out ahead also depends on the data and the evaluation protocol. The reproducibility study by Ferrari Dacrema et al. reported that of 18 neural recommendation methods published at top-level conferences, only 7 could be reproduced with reasonable effort, and 6 of those 7 were often beaten by comparatively simple methods based on nearest neighbors or graphs. In the re-evaluation by Rendle et al., a plain inner product, with properly chosen hyperparameters, substantially outperformed a learned similarity (MLP). An inner product also lets you use efficient methods on the retrieval side.

7. Pipelines That Combine Lexical and Vector Search

Vector search can handle semantic similarity, but lexical search is still stronger for proper nouns, product numbers, error codes, dates, and exact quotations. Leave queries that call for identifiers, negation, or exact matches to semantic search alone, and things that are close but different rise to the top.

Measurements show clearly where lexical search is strong. LIMIT builds on a theory that the number of top-k subsets a single-vector embedding can return is bounded by the embedding dimension, and constructs a synthetic dataset of simple queries. On this data, state-of-the-art embeddings fail while BM25 scores nearly perfectly. On a paraphrased version, however, BM25’s score drops by about 90% and falls below many single-vector models. The paper itself notes that lexical models have weaknesses too. BRIGHT is a retrieval benchmark of questions that require reasoning; a model with an nDCG@10 of 59.0 on MTEB retrieval tasks drops to 18.3 on BRIGHT. BM25’s average over 12 datasets is 14.5.

Practical search therefore uses a multistage design. Filters restrict the target set, BM25 generates lexical candidates, and vector ANN generates semantic candidates. The two rankings are fused, reranked with a cross-encoder or an LLM, and finally subjected to permissions, freshness, and business rules. Elastic describes hybrid search as fusing lexical search such as BM25 and semantic vector search into a single ranking.

Rank fusion uses weighted score sums, score normalization, and Reciprocal Rank Fusion, and some designs insert a learned ranking model or reranker. Lexical and vector search produce scores with different distributions and ranges, so a normalization step or rank-based fusion keeps one side’s scores from dominating the order. Reciprocal Rank Fusion is the representative rank-based method: it scores each document by the reciprocal of its rank in each search plus a constant, sums those scores, and re-sorts. Because it discards score values and looks only at ranks, it can blend two result lists measured on different scales with equal weight, and documents that rank high in both searches stay at the top of the final list.

How many stages of candidate generators and judges to chain, how many results to keep at each stage, and whether to fuse by score or by rank: these are the central items in designing a search system.

Part 5 takes up search in problems where you cannot see the whole set of candidates, such as car-navigation routing or choosing the next move in shogi (Japanese chess).