[October 2026 edition]

Indexes and the Art of Searching, Part 3: Searching by Words and Ranking Results

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

Part 2 covered structures that check whether a key matches. Part 3 turns to searching by strings and words, and to ranking the documents that come back.

1. Classic Algorithms for Scanning Strings

Even when the search happens inside a single string, preprocessing and summaries can cut down the number of comparisons.

Suppose you are looking for the pattern ABABC, the input has matched up to ABAB, and the next character disagrees. The trailing AB of the matched ABAB is identical to the leading AB of the pattern, so shifting the pattern by two characters leaves that AB already matched, and the comparison can resume from the next input character without rereading anything. The Knuth–Morris–Pratt algorithm precomputes a table of how far the end of each matched prefix overlaps the start of the pattern, and on every mismatch it consults that table to shift the pattern. Textbooks describe it as a method that uses what it knows about the prefixes and suffixes of the part already matched, so that the search continues after a mismatch while the read position in the input keeps moving forward. Because no input character is ever reread, preprocessing and search together take time proportional to the lengths of the input and the pattern, which is linear time.

The Boyer–Moore algorithm compares from the end of the pattern and makes large skips based on the mismatched character and on the suffix already matched. On input such as natural-language text, every character it can skip translates directly into speed.

The Rabin–Karp algorithm slides a window the length of the pattern across the input one character at a time. By subtracting the contribution of the character leaving the window and adding that of the character entering it, it recomputes the hash of the substring in the window with little work. This is called a rolling hash update, and only positions whose hash equals the pattern’s hash get a detailed comparison. The approach makes it easy to see how multiple patterns can be handled and how it connects to the change detection discussed in Part 2.

The Aho–Corasick algorithm combines many patterns into a trie and a finite automaton, and finds all of them in a single pass over the input. It suits uses with large numbers of patterns, such as virus signatures, banned-word detection, IDS, and log classification.

All of these methods share the same shape: narrow down the candidates with a cheap summary, then check exactly only the places that need it.

Which method is fastest depends on the alphabet and the pattern length. The evaluation by Faro and Lecroq compared more than 80 matching algorithms across alphabet sizes from 2 to 256 and four classes of pattern length. The fastest algorithm changed with the conditions: SSEF won on long patterns over a binary alphabet, while FJS won on the shortest patterns over a 256-character alphabet. These results reflect the set of algorithms available in 2010, and anyone applying them has to measure again with the character set and pattern lengths of their own text.

2. Inverted Indexes: Mapping Words to Documents

An ordinary database index looks up attributes from a document ID, while an inverted index looks up document IDs from a word.

database -> [3, 18, 42, 91]
index    -> [7, 18, 55]
search   -> [1, 7, 18, 23]

A real inverted index stores more than document IDs: occurrence counts, positions within each document, fields, payloads, statistics for scoring, and compressed gaps between docIDs. It is split into a dictionary and posting lists, and for each word it retrieves the corresponding set of documents.

3. The Lineage of Scoring: From TF-IDF to BM25

Ranking by raw occurrence counts lets words that appear in every document decide the order. In 1972, Spärck Jones argued that a word’s weight should depend on how often it occurs across the document collection. Take a collection of technical documents. A word like “data,” which shows up in nearly every one, is a weak clue for telling documents apart even when it matches. A match on a word like “Bloom filter,” which appears in only a few documents, makes it far more likely that the document is the one you want. Matches on rare, specific words are worth more than matches on common ones, and IDF (inverse document frequency) expresses this by giving a word more weight the fewer documents contain it. The paper reports that this simple procedure improved performance substantially on three test collections.

BM25 came later, out of research on probabilistic relevance models. It is a weighting scheme proposed by Robertson and Walker in 1994, derived as an approximation of the 2-Poisson model. That model views a word’s occurrence counts as a mixture of two kinds of documents: those where the word is the subject, and those that mention it only in passing.

BM25 orders documents using the rarity of each word, its frequency within the document, and the document’s length, and it has been used for ranking for a long time. The first appearance of a query word in a document carries a lot of meaning, and each additional appearance adds less, so the contribution of a repeated word is designed to saturate as it approaches an upper bound. Document length is handled in the same spirit: a long document contains many words and is more likely to contain a query word by chance, so the longer the document, the more the weight of each occurrence is discounted.

Full-text search runs in two stages: pull candidates from the inverted index, then rank them with BM25 or a similar function. WAND and Block-Max WAND reduce the work of that second stage further. While searching for the top k, the score of the document currently in kth place acts as the bar to clear. If the maximum score for each word is recorded in advance, you can bound how high an unread document could possibly score, however well it matches, and any document whose bound falls below the bar can be skipped before its score is computed. In the paper’s terms, postings whose upper score bound is below the current top-k threshold are pruned early. Lucene splits posting lists into blocks and gives each block its own score bound. Optimizations that let MAXSCORE and WAND-style scorers skip whole blocks are still being refined.

As a result, the running time of a full-text search depends less on the total number of matching postings than on what fraction of them the top-k threshold lets you skip.

4. Ranking by Link Structure: PageRank and Link Analysis

Word matching looks only at a document’s content, but the links between documents are a ranking signal too.

PageRank, introduced in Brin and Page’s 1998 paper, defines a page’s importance as the probability that a user who keeps following links (the random surfer) lands on it. This user does nothing but follow links forward, and every so often gets bored and starts again from some other random page. When pages T1 through Tn link to page A, PR(A) = (1−d) + d × (PR(T1)/C(T1) + … + PR(Tn)/C(Tn)). C(T) is the number of outgoing links from T, and d is a damping factor that the paper says is usually set to 0.85. The second half of the formula splits each linking page Ti’s value evenly over its outgoing links and gives A the share carried by the one link pointing to it, so A’s value grows the more pages link to it, and the more valuable those pages are. Read as a formula, the surfer follows a link with probability d and, with the remaining probability 1−d, moves to another page unrelated to the links. Start by giving every page the same value and apply the formula repeatedly; the values eventually stop moving, and those settled values are the PageRank. In linear-algebra terms, PageRank corresponds to the principal eigenvector of the normalized link matrix, and this simple iteration computes it. The paper states that PageRank for 26 million pages can be computed in a few hours on a medium-size workstation.

A variant that restricts the jump targets to a particular set of pages lets the ranking differ per user. This Personalized PageRank is now used in graph search as well. HippoRAG uses an LLM to build a knowledge graph from documents, then runs Personalized PageRank from the concepts in a question to find documents.

PageRank remains in use in web search. In its guide to ranking systems, Google lists PageRank among the core ranking systems it has used since its first launch, and explains that while the mechanism has evolved considerably since then, it is still part of the core ranking systems. A mechanism where links lift rankings also gave rise to link spam. One countermeasure, TrustRank, starts from a seed set of fewer than 200 manually evaluated sites and propagates trust along links. The authors report that in experiments it filtered out a significant share of the spam on the web.

5. Combining Signals: Learning to Rank and Rerankers

Learning to Rank learns the weight of each signal when signals such as the BM25 score, PageRank, and click-through rate are merged into a single ranking. According to Burges’s overview, RankNet takes pairs of documents for the same query, checks whether the more relevant one is placed higher, and learns to reduce the number of pairs in the wrong order. In the overview’s words, it optimizes a smooth approximation of the number of pairwise errors. That objective diverges from metrics like NDCG that emphasize the top of the list. Nudging a document’s score changes the ranking only at the instant two documents swap places, in a step, so metrics that involve sorting are non-differentiable, and it is hard to read off the direction of improvement that training needs directly from the metric. LambdaRank therefore skips writing down a cost function and instead specifies, for each document, the desired gradient (λ): which way it should move and by how much. Its magnitude is matched to how much NDCG would change if two documents swapped, so ordering errors near the top get corrected more forcefully. LambdaMART implements this with gradient-boosted trees, and an ensemble of LambdaMART models won Track 1 of the 2010 Yahoo! Learning To Rank Challenge.

When the task is combining tabular numerical features, tree-based methods are strong. The ICLR 2021 paper by Qin et al. showed that many neural ranking models of the time fell well short of the best publicly available tree-based implementations, and proposed a framework to close the gap. That conclusion holds only in settings that use hand-crafted features.

Reading a document’s text directly to rank it is the role of neural models. On MS MARCO passage retrieval, monoBERT beat the previous best MRR@10 by 27% in relative terms. Because the query and the document pass through BERT together, however, reranking is computationally heavy. ColBERT encodes queries and documents separately and matches them with a light similarity computation called late interaction. The document side can be encoded when the index is built, so only the query goes through the heavy model at search time; then, for each query term, it finds the closest term in the document and sums those similarities into a score. In a setting that reranks the top 1,000 BM25 results, its MRR@10 of 34.9 matched BERT-base’s 34.7, with a latency of 61 ms against BERT-base’s 10,700 ms, roughly 1/175 of the time. BM25 alone scores an MRR@10 of 16.7.

Another approach has an LLM generate the ranking directly. RankGPT reranks BM25 candidates and raised the average nDCG@10 on BEIR from BM25’s 43.42 to 53.68 with GPT-4. On BEIR, it kept costs down by having GPT-4 rerank only the top 30 results already reranked by GPT-3.5. On TREC it used about 19,890 tokens per query, which cost about $0.6 at the API prices of the time. Reranking can only surface documents that are in the first-stage candidates, so the recall of the first stage sets the ceiling on performance.

6. Metrics and Evaluation Data for Rankings

As ranking metrics, MS MARCO uses MRR@10, and BEIR uses nDCG@10 and Recall@100. MRR@10 takes, for each query, the reciprocal of the rank where the first correct answer appears in the top 10, then averages over queries: a correct answer in first place earns full marks, in second place half, and outside the top 10 zero. It measures how soon a user reading from the top meets the first hit. nDCG@10 sums the relevance of each of the top 10 results, discounted more heavily the lower the rank, and expresses the total as a fraction of the value an ideal ordering would achieve. Graded judgments such as “highly relevant” and “somewhat relevant” can be used directly as points. Recall@100 is the fraction of the relevant documents that land in the top 100, which makes it a good way to see how well the candidates passed to a later reranking stage capture the right answers. In Burges’s summary, MRR and MAP suit binary relevant/not-relevant judgments, while NDCG handles graded relevance and rank-based discounting.

The evaluation data has biases of its own. TREC evaluation data is built by pooling: the outputs of participating systems are collected and judged for relevance. Voorhees’s study showed that even when assessors disagree on relevance judgments, the rankings of systems remain very highly correlated. That claim holds only within the set of systems that contributed to the pool. When a new method returns documents outside the pool, those documents are unjudged and treated as non-relevant, which puts the new method at a disadvantage.

BEIR compared 10 systems zero-shot on 18 datasets. On TREC-COVID, the share of unjudged documents in the top 10 was 6.4% for BM25, 14.4% for ANCE, and 31.8% for TAS-B. After the 980 unjudged pairs were judged by hand and nDCG@10 was recomputed, BM25 rose only slightly, from 0.656 to 0.668, while ANCE climbed from 0.654 to 0.735 and overtook BM25. The way the evaluation data had been built was working in BM25’s favor.

In BEIR’s results tables, the winner changes from dataset to dataset. On Touché-2020, BM25’s 0.367 beats DPR, ANCE, TAS-B, GenQ, and ColBERT, which range from 0.131 to 0.240. On Quora, ANCE’s 0.852 and TAS-B’s 0.835 beat BM25’s 0.789. The paper concludes that BM25 is a robust baseline and that performance on the training data is no guide to performance on other data.

MS MARCO is built with sparse labels, with roughly one known relevant document per query. In the study by Arabzadeh et al., assessors often preferred the top results of modern neural models over the judged answers, and preferred them even over an ideal ranking that would earn a perfect MRR. The evaluation data had fallen behind the progress of the methods.

The problem of method rankings flipping with the data comes back in Part 8, from the angle of choosing a method.

Part 4 moves on to finding content that is close in meaning even when the words differ, covering vector search, which finds documents and images by proximity, and recommendation, which suggests items from a user’s history.