skip to content

For server-side typeahead, how does a trie with precomputed top-k per node compare with an edge-ngram index and an FST?

level: middleimportance: must knowfreq 55%

answer

  1. where does ranking happen
  2. lists stored on every node
  3. every prefix becomes a token
  4. suffix sharing shrinks memory
  5. rebuild and swap, not edit

basics

~20 s

A top-k trie gives lookups proportional to prefix length but costs memory; an edge-ngram index reuses search infrastructure and ranks at query time, costing index size and latency; an FST is compact and fast but immutable, rebuilt offline.

solid answer

~50 s

A **trie with a top-k list at every node** answers by walking one node per prefix character and returning the stored list, so latency is tiny and predictable, but every node carries its list, which makes it memory-hungry, and an update must fix the lists along the whole path. An **edge-ngram index** stores each term under all of its leading prefixes inside an ordinary search index, so a prefix becomes a normal term lookup; it brings filters, multi-field matching and query-time scoring for free, at the price of a much larger index and more work per request. An **FST** (finite state transducer) shares both prefixes and suffixes, so it is far more compact than a trie and fast to traverse, and it can carry weights to find the best completions; but it is built offline from sorted input and cannot be edited in place, so updates mean rebuild and swap.

code

pseudocode · 7 lines
pseudocode
function suggest(prefix):
  node = root
  for ch in prefix:
    node = node.child(ch)
    if node is null:
      return []
  return node.topK

go deeper

for a junior

Recall the three names and one line each: trie stores ranked lists per prefix, edge-ngram indexes every prefix as a term, FST is a compact automaton built offline.

for a middle

Explain where ranking happens in each design and why that decides request cost, and give the memory arithmetic for per-node top-k lists with stated assumptions.

for a senior

Show judgment on update models: batch rebuild and swap for tries and FSTs, live index writes for edge-ngrams, and when caching in front of an index is enough.

for a principal

Argue a hybrid: a compact precomputed path for the hot majority and an index-backed fallback for filtered or rare prefixes, and who owns keeping both consistent.

## The job all three structures do A server-side **typeahead** service receives a prefix such as `lapt` and must return the best few completions, such as `laptop` and `laptop stand`, within a tight latency budget. Three structures are commonly proposed. They differ in where the ranking work happens, how much memory they use, and how they handle change. ## Trie with precomputed top-k per node A **trie** is a tree where each edge is a character and each path from the root spells a prefix. For typeahead, each node additionally stores a **top-k list**: the k highest-scoring completions anywhere below it, computed by an offline build. ```pseudocode function suggest(prefix): node = root for ch in prefix: node = node.child(ch) if node is null: return [] // no stored completion starts with this prefix return node.topK // already ranked at build time ``` Properties: - **Lookup cost** is proportional to the prefix length plus reading k items. It does not depend on how many completions exist under the prefix. - **Memory** is the weak point. Illustratively, with **50 million nodes** each holding **10 suggestion IDs of 4 bytes**, the lists alone take 50,000,000 x 40 bytes = **2 GB**, before counting the nodes and the suggestion strings. - **Updates** are awkward: a score change for one completion can alter the top-k list of every ancestor node, so most systems rebuild in batch and swap. ## Edge-ngram index An **edge n-gram** of a word is one of its leading prefixes: `lap` yields `l`, `la`, `lap`. An edge-ngram approach indexes every candidate term under each of its leading prefixes inside a regular **inverted index**. A typed prefix is then an ordinary exact term lookup, followed by the normal scoring machinery. - **Flexibility** is the strength: the same query can filter by category, match the prefix against any word of a multi-word title, and blend signals at query time. - **Index size** grows because a term of length n contributes up to n prefix tokens instead of one. - **Request cost** is higher: the engine gathers matching documents and scores them per request, so a very short prefix with a huge posting set is the expensive case. ## FST A **finite state transducer** is a minimized automaton over the sorted set of keys. Like a trie it shares common prefixes; unlike a trie it also shares common **suffixes**, so words such as `testing` and `running` can reuse the states for `ing`. Outputs, such as weights, can be attached to arcs. - **Compactness** is the strength: the same key set usually needs far less memory than a pointer-based trie. - **Top-k** can be found with a best-first search that uses the weights, so a request stays cheap. - **Immutability** is the cost: an FST is built in one pass from sorted keys and is not edited in place. Changes arrive by rebuilding and atomically swapping the new structure, sometimes with a small mutable side structure for recent additions. ## Side by side | Dimension | Top-k trie | Edge-ngram index | FST | |---|---|---|---| | Work per request | walk + read stored list | term lookup + scoring | automaton walk + weighted top-k search | | Where ranking happens | offline build | query time | mostly offline, via stored weights | | Memory / size | high | high (prefix tokens) | low | | In-place updates | possible but costly | yes, as a normal index write | no, rebuild and swap | | Filters and blended scoring | limited | strong | limited | ## Choosing between them 1. If the product is **query suggestions** from logs, served at huge rates with a strict budget, a precomputed structure (top-k trie or FST) fits, and the FST wins when memory is the constraint. 2. If suggestions must respect **live filters** or match inside multi-field records such as product titles, an edge-ngram index on an existing search engine is often the pragmatic choice, with caching in front of it. 3. Many systems combine them: a precomputed structure for the fast common path, and a search-index fallback for rare or filtered cases. How the trie or automaton is implemented node by node is a data-structures topic; the system-design question is where the ranking cost lands and what the update model is.

  • Why does updating one completion's score in a top-k trie touch many nodes?
    Each node stores the best k completions anywhere beneath it. When one completion's score changes, every ancestor from its end node up to the root may need its list re-evaluated, which is one node per character of that completion. Doing this for many changes is costly, so most systems batch updates into a periodic rebuild and swap.
  • When would you put an edge-ngram index behind a cache rather than replace it with a precomputed structure?
    When suggestions depend on filters or on fields that change often, such as in-stock products per category, and the team already runs a search engine. Caching the popular short prefixes removes most of the per-request scoring cost, while the index keeps filters and fresh writes that a precomputed structure would lose.

saying these in an interview costs you the question

  • A top-k trie scores all completions under a node on each request.
  • An edge-ngram index costs no more space than indexing whole terms.
  • An FST can be updated in place like a hash map.
  • A trie and an FST use the same memory because both share prefixes.
  • Lookup time in a top-k trie grows with the number of stored queries.