Query Autocomplete and the Prefix Trie Behind It

The dropdown that appears after two or three keystrokes in a search box is a different retrieval problem from the search it feeds. It answers not “which documents match” but “which completed queries are likely given this prefix”, and it must do so with a latency budget far tighter than the result list, because the dropdown is expected to track the user’s typing in real time. The data structure at its core is a prefix tree, and its ranking is a form of popularity model.

The index is a prefix trie of past queries

The candidate set for autocomplete is drawn from previously issued queries, weighted by frequency, not from the document collection. Each distinct past query is stored with a count, and the whole set is indexed by prefix so that a partial string retrieves every completed query that starts with it. A trie encodes this naturally: a path from the root spells a query, and each node carries the aggregate frequency of the queries that pass through it.

The lookup for a prefix of length k is a single descent from the root following k edges, then a gather of the most frequent completions in the subtree. Because the descent cost is bounded by the prefix length and the gather can be bounded to the top few results, the whole lookup is a matter of tens of microseconds on an in-memory trie, which is what allows it to fire on every keystroke. Storing the top completions at each node, a form of caching, removes the need to walk the subtree at all: the answer is read off the node directly, trading memory for latency.

The structure can be stated as a small data definition. Each node holds a mapping from the next character to a child node, a frequency count, and optionally the cached list of top completions for the prefix the node represents:

node = { children: char -> node, count: int, top: list[completion] }
completion = { query: string, weight: float }

Inserting a past query walks its characters, creating nodes as needed and incrementing the count on every node along the path, so each node’s count is the number of queries that share its prefix. The cached top list is maintained by comparing the inserted query’s weight against the node’s current list, keeping the highest-weight completions. A node that caches ten completions pays forty or so bytes of memory per entry, which is why the cache is reserved for nodes at shallow depths where the fan-out is widest.

Ranking completions is not just frequency

Raw frequency is a weak ranking signal on its own. A query that is globally common but a poor match for the current user, or one that is stale, will crowd out better completions. Real systems modulate frequency with several factors. Recency discounts queries whose counts are inflated by long-past popularity. Personalization, where available, boosts completions the user has issued before or that match their context. Localization biases toward the language and region of the user, and session context biases toward completions consistent with the queries already typed in this session.

The result of this modulation is that autocomplete is a ranking function, not a data-structure read, and the trie is only its fast access path. The completion list is assembled from the candidate set the prefix descends to, then re-ranked by the full scoring model before display. A related mechanism, query suggestion without a prefix, uses the same ranked candidates to offer a full query from an empty box or after a completed search, and is covered by the same infrastructure.

The scoring model’s inputs are themselves a design surface with several distinct pressures. A completion that is frequent globally but irrelevant to the current user is a bad suggestion, so the personalization term must not be allowed to drown the frequency prior, which is why the model weights the two separately rather than multiplying them. A completion that is frequent because of a past spike must be decayed against a completion that is steadily common, which is a recency-halflife decision rather than a binary one. And a completion that merely restates what the user has already typed adds nothing, so the interface suppresses exact-prefix matches that carry no additional information. Each of these pressures is a coefficient in the ranking model, and tuning them is what separates a useful dropdown from a list of the most common strings that happen to share a prefix.

What breaks under real-time constraints

The latency budget exposes two distinct failure modes. The first is staleness: the trie of past queries must be updated as new queries arrive, and an index that is refreshed in batch will lag the moment’s most relevant completions, such as a newly trending name. The second is the cold-start problem at the start of a prefix: a single character retrieves an enormous candidate set, so the ranking must be applied over a large fan-out before the user has typed enough to disambiguate. Interfaces handle this partly by delaying the dropdown until two or three characters, which both narrows the fan-out and avoids flicker.

The staleness problem has a real architectural answer. The trie is typically maintained in memory, separate from the on-disk index that serves document retrieval, precisely so that updates can be applied incrementally and read with the microsecond-level latency the dropdown needs. New queries are inserted as they arrive, and the frequency counts decay or are aged on a schedule so that a query which spiked a month ago does not dominate forever. The trade is durability: an in-memory trie that is not checkpointed loses its counts on restart and must be rebuilt from a log of queries, which is why the query log is retained even when the trie itself lives only in memory.

The third problem is correctness under a changing query. Because the dropdown is rendered for a prefix the user has already moved past, an in-flight lookup for “ja” can return after the user has typed “java”, and the stale response must be dropped. This is a concurrency concern rather than a retrieval one: each keystroke cancels or supersedes the previous request, and the renderer must ignore any response that does not correspond to the current prefix.

Autocomplete sits on the boundary between the query-understanding pipeline that corrects and completes intent, and the result presentation that follows. Its own mechanism is compact: a prefix trie of historical queries, a descent bounded by prefix length, and a ranking layer that folds recency, personalization, and context into a frequency prior. The engineering pressure is all in the edges, in the millisecond budget and in the stale-response and cold-start cases that only appear when the structure is driven by live keystrokes.

The correction pipeline is a natural sibling rather than a competitor, because the two solve opposite halves of the same problem. Correction repairs a query the user already typed; autocomplete guesses a query the user has only started to type. They share the underlying frequency evidence, the past-query corpus, but apply it at different points: correction after a full query produces a poor result, autocomplete after a partial one produces no result at all. An interface that wires the two together can offer a corrected completion inside the dropdown itself, so the user is steered toward a well-formed query before ever submitting a misspelled one.