Typeahead at Scale: Autocomplete, Spelling and Facets.

The week's store opens its festive sale at 21:00. Ananya, in Jaipur, wants black shoes, and types the way she speaks: in Hinglish, in Latin letters, on a 4G phone. (An illustrative scene: the people, times and numbers are made up; each failure is a classic one.)

None of these is a ranking or indexing bug. What broke is the box people type into: a separate system with its own traffic, data, privacy rules and failure modes, and one of the most asked interview questions there is: "Design typeahead."

Yesterday (Day 3) ranked results once a query is submitted. Today covers what happens around it: suggestions while the user types, "did you mean" when they get it wrong, and facets to narrow what comes back.

01Chapter 1: What Typeahead Has to Do#

1.1 The Simple Definitions#

• Typeahead (autocomplete): as the user types a prefix, show the top-k (usually 5–10) likely completions, updated on every keystroke.
• Query suggestions complete the query ("samsung s24 cover"); instant results show entities (a product, a person). Many boxes show both.
• Zero-prefix state: what shows before anything is typed: recent and trending searches.

Google states the goal well: "Autocomplete is designed to help people complete a search they were intending to do, not to suggest new types of searches to be performed" (Google, 2018). The same post says autocomplete "reduces typing by about 25 percent" on average.

1.2 The Latency Budget per Keystroke#

A suggestion that arrives after the next keystroke is useless. Facebook's 2010 description of its typeahead put the line at 100 ms: "spending more than 100 msec to retrieve a result will cause the typeahead to 'stutter,' leading to a bad user experience" (Facebook Engineering, 2010). Spend those 100 ms like this (an illustrative budget for mobile users in India):

The server gets about 15 ms: a lookup, not a query that scores millions of documents. And the cheapest request is one the CDN or browser answers.

1.3 One Search, Many Requests#

Typeahead sends one request per keystroke, not per search. That QPS amplification is the number that surprises people.

1.4 The Client's Half: Debounce, Cancel, Discard Stale#

Half of typeahead runs in the app, and it removes most of the load and the flicker:

• Debounce: send only after a short pause (100–150 ms, illustrative), so "kale j" sends one or two requests, not six. That delays every suggestion, so:
• Filter locally first: the "kal" list filtered to "kale…" is an instant placeholder (it can miss entries outside "kal"'s top-k).
• Cache per prefix in the tab: backspace and retyping are free.
• Cancel and sequence: abort the old prefix's request, and never let an older response overwrite a newer one.

let timer, controller, latest = 0;
const cache = new Map();                          // prefix -> suggestions, this tab only

input.addEventListener("input", () => {
  const prefix = normalize(input.value);          // lowercase, trim, Unicode NFKC
  clearTimeout(timer);
  controller?.abort();                            // the previous prefix no longer matters
  latest++;                                       // so no answer already in flight may render
  if (cache.has(prefix)) return render(cache.get(prefix));     // backspace or retype: free
  renderFilteredFromLastList(prefix);             // instant placeholder while we wait
  timer = setTimeout(() => load(prefix), 120);    // send only after a pause in typing
});

async function load(prefix) {
  controller = new AbortController();
  const seq = ++latest;
  try {
    const res = await fetch(`/suggest?q=${encodeURIComponent(prefix)}&loc=hi-IN`,
                            { signal: controller.signal });
    const items = await res.json();
    cache.set(prefix, items);
    if (seq === latest) render(items);            // an old answer never replaces a newer one
  } catch (e) {
    if (e.name !== "AbortError") renderFilteredFromLastList(prefix);   // fail quietly
  }
}

The sequence check alone fixes "kalonji seeds": latest moves on every keystroke, so an answer still in flight fails seq === latest. abort() saves the client's work, not the server's, so the server must be cheap anyway.

02Chapter 2: Data Structures for Prefix Lookup#

2.1 A Trie, and Why a Plain One Is Too Slow#

A trie (prefix tree) stores strings character by character; every path from the root spells a prefix. Finding the node for "sam" takes 3 steps, however many queries are stored.

The trouble is listing completions: you must visit and rank every query below that node. Below "sam" there may be thousands; below "s", millions. The short prefixes users type most have the biggest subtrees, so the work is largest where traffic is highest.

2.2 Top-k Precomputed at Every Node#

The fix: store the answer, not the means to compute it. At build time every node keeps its own top-k list, so serving is "walk the prefix, return the list": O(prefix length), no subtree walk.

%% title: A trie over six past queries, each node keeping its top 3
flowchart TD
  R(("root"))
  S["s<br/>saree · samsung s24 · shoes"]:::core
  SA["sa<br/>saree · samsung s24 · samsung tv"]
  SH["sh<br/>shoes · shirt"]
  SAR["sar<br/>saree"]
  SAM["sam<br/>samsung s24 · samsung tv"]
  SAN["san<br/>sandals"]
  SHO["sho<br/>shoes"]
  SHI["shi<br/>shirt"]
  R --> S
  S --> SA
  S --> SH
  SA --> SAR
  SA --> SAM
  SA --> SAN
  SH --> SHO
  SH --> SHI

(Illustrative scores behind it: saree 9,100, samsung s24 8,400, shoes 7,700, samsung tv 3,200, sandals 2,900, shirt 2,100.)

import heapq

K = 10

class Node:
    __slots__ = ("children", "top")
    def __init__(self):
        self.children = {}          # character -> Node
        self.top = []               # min-heap of (score, query), at most K entries

def insert(root, query, score):
    """Build time. Called once per distinct query, with its final score (Chapter 3)."""
    node = root
    for ch in query:
        node = node.children.setdefault(ch, Node())
        if len(node.top) < K:
            heapq.heappush(node.top, (score, query))
        elif score > node.top[0][0]:
            heapq.heapreplace(node.top, (score, query))    # evict this node's current K-th best

def suggest(root, prefix):
    """Serve time: O(len(prefix)) to find the node, then the list is already there."""
    node = root
    for ch in prefix:
        node = node.children.get(ch)
        if node is None:
            return []
    return [q for _, q in sorted(node.top, reverse=True)]

The costs moved to build time:

• Memory: k entries per node; store 4-byte ids into a suggestion table, not strings.
• Updates: a score change touches every node on the query's path, so suggestion indexes are rebuilt in batch and swapped (Chapter 3).
• Fixed k: a top-10 list can't answer "top 20". Pick k for the UI, plus headroom for serve-time filtering.

And a serving trick: with every list precomputed, you don't need the trie at serve time. A key-value map from prefix to list answers with one lookup, and shards like any key-value store (Chapter 4).

2.3 An FST: The Trie, Compressed#

A trie shares prefixes; a finite-state transducer (FST) also shares suffixes ("running shoes" and "walking shoes" end in the same states). Lucene builds a minimal FST in one pass over input that "must be sorted", into "a compact serialized format byte array" (Lucene FSTCompiler docs). Mike McCandless built one for the 9.8 million unique terms of a Wikipedia index in about 8 seconds: 69 MB (2010).

For suggestions, Lucene's weighted-FST suggester puts weights on the paths and "first traverses the prefix, then walks the n shortest paths to retrieve top-ranked suggestions" (Lucene WFSTCompletionLookup docs). Same idea as stored top-k, done by a best-first search. Lucene's AnalyzingSuggester indexes the analyzed form while returning the original: "ame…" suggests "Amélie" through case and accent folding (McCandless, 2012). Remember that trick for Hinglish (Chapter 4.6).

The price: an FST is immutable; you rebuild it, never edit it.

2.4 What a Search Engine Gives You#

Elasticsearch and OpenSearch offer four options; prefix matching "happens at query time", "the other three methods happen at index time" (OpenSearch docs):

1. Prefix queries (match_phrase_prefix): no special mapping, but "a fairly resource-intensive operation. A prefix of a could match hundreds of thousands of terms" (OpenSearch docs). Fine for an admin tool, wrong for a public box.
2. Edge n-grams: each word is indexed with every prefix ("nike" → n, ni, nik, nike), so a typed prefix is an exact term lookup. Search with a plain analyzer, "otherwise, the search query splits into edge n-grams" and matches everything (OpenSearch docs); and "search terms longer than the max_gram length may not match any indexed terms" (Elasticsearch docs).
3. search_as_you_type: shingle subfields (._2gram, ._3gram) plus an edge n-gram ._index_prefix, queried with bool_prefix, so words match in any order (Elasticsearch docs).
4. The completion suggester: a completion field built into an FST that "lives in memory and is optimized for fast prefix lookups" (OpenSearch docs); Elastic says its structures "are costly to build and are stored in-memory". Each input has a weight, returned as _score, with optional fuzzy matching (by default from 3 typed characters, first character exact) and up to 10 contexts such as category (Elasticsearch docs).

2.5 Choosing#

The usual production answer is two lists in one dropdown: query completions from a precomputed index, and a few instant entity results from the search engine, fetched in parallel and merged.

03Chapter 3: From Query Logs to a Suggestion Index#

Query suggestions come from what people searched: Google's "autocomplete predictions reflect real searches that have been done on Google" (Google Search Help). So the build is a batch pipeline over search logs, plus a streaming path for what's new.

%% title: Building suggestions: a nightly batch, a streaming overlay, a serve-time kill switch
flowchart TD
  LOG@{ icon: "sd:log", label: "Search events<br/>query, user, results, clicked, time" }
  LAKE@{ icon: "sd:object-storage", label: "Daily partitions<br/>last 90 days" }
  AGG@{ icon: "tech:spark", label: "Spark batch, nightly<br/>normalize · count · decay" }
  FIL["Filters<br/>PII · blocklist · min distinct users"]:::core
  BUILD["Build snapshot v1042<br/>prefix → top-k per locale"]:::core
  SNAP@{ icon: "sd:object-storage", label: "Versioned snapshots" }
  K@{ icon: "tech:kafka", label: "Kafka<br/>search events" }
  FL@{ icon: "tech:flink", label: "Flink<br/>5-minute counts vs baseline" }
  TR["Trending overlay<br/>stricter filters · short TTL"]:::hot
  SRV@{ icon: "sd:servers", label: "Typeahead replicas<br/>load · verify · swap" }
  LOG --> LAKE --> AGG --> FIL --> BUILD --> SNAP --> SRV
  LOG --> K --> FL --> TR --> SRV
  class LOG,LAKE,SNAP store
  class AGG,FL service
  class K queue
  class SRV service

3.1 Aggregation#

1. Normalize each query: Unicode NFKC, lowercase, collapse spaces, strip trailing punctuation. Keep a trailing space meaningful: "nike " means the word is finished, so it shouldn't suggest "nikon".
2. Count per query per day: searches, distinct users (so one bot can't manufacture a suggestion) and successful searches, followed by a click or add-to-cart (so useless queries aren't promoted).
3. Collapse variants ("Samsung S24", "samsung s24") into one suggestion, shown in its most common form.

3.2 Decay#

All-time counts never forget: a phone from three years ago outranks this year's model forever. Weight each day's count by its age, with a half-life:

from collections import defaultdict

HALF_LIFE_DAYS = 14     # illustrative: news-like catalogues want days, slow ones months
MIN_USERS = 20          # never suggest what fewer than 20 different people typed (illustrative)

def score_queries(daily_rows, users_90d, today, blocked):
    """daily_rows: (day, query, searches, successes) for the last 90 days.
    users_90d: query -> distinct users over the window (from a HyperLogLog sketch)."""
    score = defaultdict(float)
    for day, q, searches, successes in daily_rows:
        age = (today - day).days
        weight = 0.5 ** (age / HALF_LIFE_DAYS)             # 14 days old counts half
        score[q] += weight * (searches + 2 * successes)     # reward searches that went somewhere
    return {q: s for q, s in score.items()
            if users_90d.get(q, 0) >= MIN_USERS and not blocked(q)}

The half-life is a product decision: short is responsive and jumpy, long is stable and stale. With two weeks, seasonal queries ("diwali lights") rise each October or November from that year's searches.

3.3 Filtering: Offensive, PII and Rare Queries#

A suggestion is the system speaking: it puts words in front of a user who didn't type them. Google says autocomplete "has systems designed to prevent potentially unhelpful and policy-violating predictions from appearing" ("violent, sexually explicit, hateful, disparaging, or dangerous"), including "unconfirmed rumors after a news event" (Google Search Help); "enforcement teams" remove what automation misses, and the policies "only apply to predictions. They do not apply to search results" (Google, 2020).

A typical filter stack, in build order:

• Minimum distinct users (MIN_USERS): the key privacy filter. One person's query can hold their name or phone number; a crowd threshold keeps it out of everyone else's dropdown. The preface's number had 40 searches from one user.
• PII patterns: phone numbers, emails, 12-digit identity numbers, order and card numbers. Drop, don't mask.
• Blocklists and a classifier per language, including transliterated slurs.
• Policy lists: people's names, medical conditions, whatever legal calls sensitive.
• A serve-time blocklist, updatable in seconds: a bad suggestion found at 21:05 can't wait for the 02:00 build.

3.4 Freshness: the Trending Path#

A nightly batch can't know about the 20:00 launch. Google lists "trending interest in a query" among its signals (Google Search Help). A typical design:

• A stream job counts queries per locale in 5-minute windows against each query's baseline.
• Several times the baseline, from enough distinct users, enters a small trending overlay with a TTL of hours.
• At serve time the overlay is merged into the top-k, capped at one or two slots.
• The overlay gets stricter filters, not looser: new things are where rumours and coordinated abuse live.

3.5 Building and Shipping a Snapshot#

The batch writes a versioned, immutable snapshot per locale, shipped like Day 2's alias swap (Day 2 · Zero-Downtime Reindexing):

1. Validate: entry counts near yesterday's, a golden set ("sa" must contain "saree"), no blocked term.
2. Load beside the old one, warm, swap a pointer; keep yesterday's for rollback.
3. If the build fails, serve the last good snapshot. Stale for a day is fine; empty is an outage.

04Chapter 4: The Serving Path#

4.1 From Keystroke to Dropdown#

%% title: Typeahead serving: most keystrokes never reach the origin
flowchart TD
  U@{ icon: "sd:phone", label: "App or browser<br/>debounce · tab cache · local history" }
  CDN@{ icon: "sd:cdn", label: "CDN edge<br/>key: prefix + locale<br/>TTL ~10 min" }
  API@{ icon: "sd:api", label: "Suggest API<br/>normalize · route by locale" }
  TA["Typeahead service<br/>prefix → top-k in memory<br/>a full copy per replica"]:::core
  TR["Trending overlay<br/>merged at serve time"]:::service
  BL["Serve-time blocklist<br/>updates in seconds"]:::service
  PH@{ icon: "sd:cache", label: "Personal history<br/>per user, behind login" }
  SE@{ icon: "tech:elasticsearch", label: "Product index<br/>instant results, cached" }
  U -->|"miss"| CDN
  CDN -->|"miss"| API
  API --> TA
  TA --> TR
  TA --> BL
  U -.->|"signed in, separate call"| PH
  API -.->|"instant results, after 3 characters"| SE
  class U client
  class CDN edge
  class API edge
  class PH cache
  class SE store

The global list is the same for everyone with the same prefix and locale, so it can be cached anywhere; the personal part travels separately.

%% title: Ananya types kale, then backspaces
sequenceDiagram
  autonumber
  participant A as Ananya
  participant C as App
  participant E as CDN edge
  participant T as Typeahead service
  A->>C: k, a, l, 110 ms apart
  C->>C: debounce, nothing sent yet
  A->>C: pause after kal
  C->>E: GET suggest q=kal loc=hi-IN
  E->>T: miss, forward
  T-->>E: top 8, cacheable 10 min
  E-->>C: kale joote, kala chashma, kalonji seeds
  A->>C: types e
  C->>C: show kal list filtered to kale at once
  C->>E: GET suggest q=kale loc=hi-IN
  E-->>C: hit, answered at the edge
  A->>C: backspace to kal
  C->>C: tab cache hit, no request

4.2 Caching in the Browser and at the CDN#

In the browser. Facebook's 2010 typeahead went furthest: "As soon as the user focuses in the text box, we send off a request to retrieve all of the user's friends, pages, groups, applications, and upcoming events. We load these results into the browser's cache", and later results were cached too, "so that similar subsequent queries don't need to hit the backend again" (Facebook Engineering, 2010). For a small personal set, shipping all of it to the client turns typeahead into local filtering.

At the CDN. Global suggestions are cacheable responses: GET /suggest?q=sam&loc=en-IN with Cache-Control: public, max-age=600. Short prefixes are the most requested and the most cacheable: a locale has only about 700 one- and two-letter Latin prefixes (26 + 26²), which can live at the edge or ship to the app as a static file. Key on the normalized prefix plus locale only; a user id in the key turns a 60% hit ratio into zero. The TTL (ten minutes, illustrative) sets how fast new snapshots reach users; removals use a purge.

4.3 Sharding by Prefix and the Hot-Prefix Problem#

If one copy doesn't fit on a machine, you must split it. The obvious split, by first letter, is the classic wrong answer.

When the CDN entry for a hot prefix expires, many edges ask at once. Coalescing, one fetch per key with the rest waiting for it, is the thundering-herd fix from Week 4.

4.4 Sizing It#

4.5 Personalization Blending#

Google's suggestions consider "your past searches", and signed-in users may see "personalized predictions based on their activity on Google" (Google Search Help). LinkedIn's Cleo split typeahead into generic (the same results for everyone, "ordered according to a global ranking scheme") and network typeahead, ranked within a member's 1st- and 2nd-degree connections using "People You May Know" scores, at "~20 milliseconds on average" for more than 150 million members (LinkedIn Engineering, 2012). Cleo maps "string prefixes (or members) to documents", uses Bloom filters as "a fast means to filter documents that cannot prefix-match", and a forward index to drop their false positives.

A typical blend keeps the cacheable and personal parts apart and merges them on the client or in a thin authenticated call:

def blend(prefix, global_top, history, affinity, k=8, history_slots=2, w=0.3):
    """global_top: [(query, score, category)] for this prefix: the same for everyone, cacheable.
    history: this user's recent queries, newest first. affinity: {category: 0..1} for this user."""
    past = [q for q in history if q.startswith(prefix) and q != prefix][:history_slots]
    reranked = sorted(global_top,
                      key=lambda t: t[1] * (1 + w * affinity.get(t[2], 0.0)),  # nudge, never filter
                      reverse=True)
    return (past + [q for q, _, _ in reranked if q not in past])[:k]

Three rules: cap the personal slots; mark history and let users delete it (Google shows a clock icon on mobile and "Remove" on desktop, 2018); and never cache a blended response at a shared key.

4.6 Multi-Language and Transliteration#

Flipkart's data scientists reported that "apart from English, the major portion of the queries (around 21%)" on their platform was "code-mixed Hinglish i.e. queries where one or more Hindi words are written in Latin script", with examples like "kale jute 300 tak" and "mbile phone ki battry" (Flipkart Data Science, 2022). For full searches they translate the query into English with a transformer, distilled for "more than 4x reduction in latency" and live "serving millions of queries".

A model call per search is affordable; per keystroke it pays the 12× amplification. So a typical typeahead design moves language work into the build:

• Per-locale indexes (hi-IN, en-IN, ta-IN), with English as a fallback.
• Several keys, one suggestion. Like the AnalyzingSuggester (2.3), index "black shoes / काले जूते" under what users type: "kale joote", "kale jute", "kaale joote", "काले जूते", generated by transliteration plus phonetic normalization (collapse doubled vowels, merge common spellings).
• Mine mappings from logs: users who typed "joote", then searched "shoes" and clicked. These are one-way synonyms: "joote ⇒ shoes" widens the Hinglish query without adding Hinglish to English results.
• Show the user's script, and normalize Unicode (NFKC) on keys and prefixes, since one Devanagari word can be encoded more than one way.

05Chapter 5: "Did You Mean"#

Typos that get past typeahead reach search, where Day 3 already relaxes queries with fuzzy matching. Spelling correction is the explicit version: propose the query the user meant.

5.1 Edit Distance and Candidates#

Edit distance (Levenshtein) counts the single-character insertions, deletions and substitutions between two strings; Damerau's variant counts a swap of adjacent letters as one. Elasticsearch's fuzziness allows at most 2 edits; AUTO allows none for 1–2 characters, one for 3–5, two above 5 (Elasticsearch docs).

Comparing against every term is too slow. The old Lucene FuzzyQuery "visits every single unique term in the index"; Lucene 4.0 instead intersects a Levenshtein automaton, which accepts exactly the strings within the distance, with the sorted terms dictionary; with that and other term-seeking improvements, FuzzyQuery got about 100 times faster (McCandless, 2011).

5.2 The Noisy Channel#

Edit distance makes candidates; it doesn't choose. "adres" is one edit from "acres", two from "address". Peter Norvig's essay derives the choice with Bayes' theorem; it is the classic noisy channel model: the user meant c, the keyboard garbled it into w, so pick

argmax over candidates c of P(c) · P(w | c)

where P(c), the language model, is how common c is, and P(w | c), the error model, is how likely that typo is when someone means c (Norvig, 2007–2016). His toy version ranked every one-edit word above any two-edit word, so it turned "adres" into "acres"; it scored 75% on his development set and 68% on the test set. The fix is a real error model, learned from users correcting themselves.

def correct(word, candidates, query_freq, error_prob):
    """candidates: known queries within 2 edits. query_freq: counts from your own search logs.
    error_prob(w, c): P(typed w | meant c), learned from users' own reformulations."""
    total = sum(query_freq.values())
    return max(candidates | {word},
               key=lambda c: (query_freq.get(c, 0) / total) * error_prob(word, c))

For search, your own query logs are the language model, not a dictionary: "s24" and "boAt" are real words no dictionary has. Context matters too: the neighbouring word decides whether "strp" is "strap" or "strip".

Errors aren't only slips. Amazon's scientists described phonetic errors, like "blutut sant sistam" for "bluetooth sound system" and "nacklesh" for "necklace"; on India's e-commerce market, adding phonetics improved F1 "by 9%+" and phonetic-error recall "by 8%+", "without additional latency cost" (Amazon, 2022).

5.3 In a Search Engine#

Elasticsearch ships the pieces (Elasticsearch docs). The term suggester "suggests terms based on edit distance", one word at a time. The phrase suggester picks "entire corrected phrases" using "ngram-language models", a noisy channel over word shingles; real_word_error_likelihood (default 0.95) admits that correctly spelled words can be wrong in context, and confidence sets how much better a correction must score. collate prunes "suggestions for which no matching docs exist in the index".

5.4 Correct, or Only Suggest?#

Tune the thresholds with Day 3's metrics: zero-result rate, and clicks on the correction versus the original.

06Chapter 6: Faceted Filtering#

6.1 Facets Are Aggregations#

Facets are the counts beside the results (illustrative counts): Brand: Nike (892), Adidas (567); Price: under ₹1,000 (234). Each is an aggregation over the matching documents (terms on brand, range on price), computed in the same request as the hits, on keyword and numeric fields (Day 1's multi-field pattern). Selections go in filter context (Day 3).

6.2 Multi-Select: Facets Ignore Their Own Filter#

When Ananya ticks "Nike", results narrow to Nike, but the brand facet must still count Adidas and Puma, or she can't add a second brand; every other facet narrows to Nike. Elasticsearch: "Search requests apply post filters only to search hits, not aggregations" (Elasticsearch docs). Then wrap each facet in a filter aggregation with every selection except its own:

{
  "query": { "bool": { "must": { "match": { "name": "running shoes" } },
                       "filter": [ { "term": { "in_stock": true } } ] } },
  "post_filter": { "bool": { "filter": [ { "terms": { "brand": ["nike"] } },
                                         { "term": { "color": "black" } } ] } },
  "aggs": {
    "brand": { "filter": { "term": { "color": "black" } },
               "aggs": { "values": { "terms": { "field": "brand", "size": 20 } } } },
    "color": { "filter": { "terms": { "brand": ["nike"] } },
               "aggs": { "values": { "terms": { "field": "color", "size": 15 } } } }
  }
}

Hits get both selections; the brand facet ignores the brand selection; the color facet ignores the color selection.

6.3 Counts Are Approximate at Scale#

A terms aggregation takes each shard's top shard_size values, by default "size * 1.5 + 10", and merges them, so a value just below every shard's cut-off is undercounted: "doc_count values for a terms aggregation may be approximate" (Elasticsearch docs). For facets that's usually fine; raise shard_size where a missing value would be noticed, and put facets with thousands of values behind "show more".

6.4 Facets in the Typeahead#

Today's halves meet in the dropdown: "nike running shoes in Men's Footwear". A typical design stores with each suggestion the categories its searches ended in (from clicks) and offers one or two as scoped suggestions, which run the search with that facet selected and resolve the preview's "apple" ambiguity.

07Chapter 7: Edge Cases and Failure Modes#

Two cases the matrix below doesn't show. Very long input: cap prefixes at ~50 characters (illustrative) and answer from the last list. A user deletes their history: delete it from the personal store at once; the global list needs nothing, because a query only reaches it after enough different people typed it.

08Chapter 8: How Real Companies Do It#

09Chapter 9: Common Mistakes to Avoid#

9.1 Mistake 1: Typeahead on the Search Cluster#

9.2 Mistake 2: Raw Counts Straight From the Logs#

9.3 Mistake 3: Personal Data in Shared Caches#

9.4 Mistake 4: Sharding by First Letter#

10Chapter 10: Interview Tips and Phrases#

10.1 When to Bring It Up#

• "Design typeahead": this lesson is the outline.
• Any search design: typeahead's amplification makes it a separate system.
• Privacy or trust and safety: suggestions are the system speaking.

10.3 Questions to Ask the Interviewer#

• Are we completing queries, or showing entities like products and people, or both?
• How many locales and scripts? Is transliterated input common?
• Is personalization required, and what are the privacy rules for search history?
• How fresh must trending suggestions be: minutes, or is daily enough?

10.4 Common Follow-Up Questions#

11Chapter 11: Practice Problems#

Summary#

Further Reading#

Engineering Blogs and Papers#

• Blog

  Google — How Google autocomplete works in Search (April 2018): https://blog.google/products/search/how-google-autocomplete-works-search/

• Blog

  Google — How Google autocomplete predictions are generated (October 2020): https://blog.google/products/search/how-google-autocomplete-predictions-work/

• Blog

  LinkedIn — Cleo: the open source technology behind LinkedIn's typeahead search (March 2012): https://www.linkedin.com/blog/engineering/open-source/cleo-open-source-technology-behind-linkedins-typeahead-search

• Blog

  Facebook — The Life of a Typeahead Query (May 2010): https://engineering.fb.com/2010/05/17/web/the-life-of-a-typeahead-query/

• Blog

  Mike McCandless — Using Finite State Transducers in Lucene (December 2010): https://blog.mikemccandless.com/2010/12/using-finite-state-transducers-in.html

• Blog

  Mike McCandless — Lucene's new analyzing suggester (September 2012): https://blog.mikemccandless.com/2012/09/lucenes-new-analyzing-suggester.html

• Blog

  Mike McCandless — Lucene's FuzzyQuery is 100 times faster in 4.0 (March 2011): https://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html

• Read

  Peter Norvig — How to Write a Spelling Corrector (2007–2016): https://norvig.com/spell-correct.html

• Paper

  Flipkart Data Science — Study of Encoder-Decoder Architectures for Code-Mix Search Query Translation (2022): https://arxiv.org/abs/2208.03713

• Read

  Amazon — Spelling Correction using Phonetics in E-commerce Search (ECNLP 2022): https://aclanthology.org/2022.ecnlp-1.9/

Official Documentation#

• Read

  Google Search Help — How Google autocomplete predictions work: https://support.google.com/websearch/answer/7368877

• Docs

  Elasticsearch — Suggesters (completion, term, phrase): https://www.elastic.co/guide/en/elasticsearch/reference/current/search-suggesters.html

• Docs

  Elasticsearch — Edge n-gram tokenizer: https://www.elastic.co/guide/en/elasticsearch/reference/current/analysis-edgengram-tokenizer.html

• Docs

  Elasticsearch — Search-as-you-type field type: https://www.elastic.co/guide/en/elasticsearch/reference/current/search-as-you-type.html

• Blog

  Elasticsearch — Filter search results (post_filter): https://www.elastic.co/guide/en/elasticsearch/reference/current/filter-search-results.html

• Docs

  Elasticsearch — Terms aggregation: https://www.elastic.co/guide/en/elasticsearch/reference/current/search-aggregations-bucket-terms-aggregation.html

• Docs

  OpenSearch — Autocomplete: https://docs.opensearch.org/latest/search-plugins/searching-data/autocomplete/

• Read

  Lucene — WFSTCompletionLookup: https://lucene.apache.org/core/9_9_0/suggest/org/apache/lucene/search/suggest/fst/WFSTCompletionLookup.html