Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 43 ยท Projects

Project: Search-as-You-Type Autocomplete

Build fast autocomplete: edge n-grams at index time, ranking by popularity, and typo tolerance, with read-only Elasticsearch requests and a Node.js stand-in.

When a shopper types "run", the box should already suggest "running shoes". Suggestions must appear within a fraction of a second, rank popular items first, and survive a typo like "runing". In this project you design that feature for Elasticsearch and build a runnable Node.js model of the same pipeline.

The Elasticsearch requests are read-only, because the server cannot run here. The Node.js program is a teaching stand-in: it models edge n-grams, popularity ranking and fuzzy matching, but it is not how Lucene stores or scores data.

The design in four ideas

How autocomplete stays fast

Edge n-grams Index every prefix of every word.
Plain lookup Typing "run" is an exact term match.
Popularity Frequent searches rank higher.
Fuzziness Forgive a typo or two.

Work is done when indexing, so typing is cheap.

1 / 2

An edge n-gram is a prefix of a token. The word running produces r, ru, run, runn, runni, runnin, running (with a minimum and maximum length you choose). If these are stored in the index, then a user's partial input run becomes an ordinary term lookup in the inverted index, with no wildcard scanning. You pay with a bigger index to get fast queries.

Step 1: the mapping and analyzers

The important trick is to use different analyzers at index time and search time. At index time you generate prefixes. At search time you must not, because typing run should look for the single term run, not for r, ru and run (which would match everything starting with r).

HTTP
PUT /suggest-products
{
  "settings": {
    "analysis": {
      "filter": {
        "prefixes": { "type": "edge_ngram", "min_gram": 2, "max_gram": 15 }
      },
      "analyzer": {
        "autocomplete_index": {
          "type": "custom",
          "tokenizer": "standard",
          "filter": ["lowercase", "prefixes"]
        },
        "autocomplete_search": {
          "type": "custom",
          "tokenizer": "standard",
          "filter": ["lowercase"]
        }
      }
    }
  },
  "mappings": {
    "properties": {
      "title": {
        "type": "text",
        "analyzer": "autocomplete_index",
        "search_analyzer": "autocomplete_search"
      },
      "popularity": { "type": "integer" }
    }
  }
}

Choices to understand:

  • min_gram: 2 avoids one-letter prefixes, which match half of the index and are rarely helpful. max_gram: 15 caps index growth. If someone types more than 15 characters of one word, no stored prefix is that long, so such input needs a normal field or a truncation of the typed text on the search side.
  • autocomplete_search has no n-gram filter, as explained above.
  • Elasticsearch also offers a ready-made search_as_you_type field type and a completion suggester, covered in highlighting and suggesters. Custom edge n-grams give you the most control over ranking and filters, which is why we use them here.

Step 2: the query with popularity

Rank by text relevance first, then nudge by popularity with function_score, so a hugely popular item beats a rare one only when matches are comparable:

HTTP
GET /suggest-products/_search
{
  "size": 5,
  "_source": ["title"],
  "query": {
    "function_score": {
      "query": {
        "match": { "title": { "query": "runn", "operator": "and" } }
      },
      "field_value_factor": {
        "field": "popularity",
        "modifier": "log1p",
        "missing": 0
      },
      "boost_mode": "sum"
    }
  }
}
  • operator: and means every typed word must match a prefix of some word. With "red run" both a "red" prefix and a "run" prefix must match.
  • field_value_factor with log1p dampens large counts so one runaway number does not drown relevance. boost_mode: sum adds that value to the text score.

Step 3: typo tolerance

Add fuzziness for typos. Fuzziness is measured in edit distance: the number of single-character inserts, deletes, substitutions (or swaps, with transpositions on) needed to turn one word into another:

HTTP
{ "match": { "title": { "query": "runing", "fuzziness": "AUTO", "prefix_length": 1 } } }

AUTO allows 0 edits for very short terms, 1 for medium and 2 for longer ones. prefix_length: 1 means the first letter must be correct, which makes the query much cheaper and rarely hurts quality, since people seldom mistype the first letter. Fuzzy queries cost more than exact ones, so a common approach is: run the cheap exact-prefix query first, and fall back to the fuzzy query only when there are too few results.

Step 4: the stand-in

The program has three parts: an edge n-gram index (a map from prefix to titles), ranking by popularity, and a fallback that matches by edit distance when nothing is found.

Node.js Autocomplete with prefixes, popularity and typo fallback

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Read the output from top to bottom:

  • ru, run and runn all give the same top three, ranked by popularity. The limit of three hides that "ru" also matches lower-ranked titles such as "Rugby Ball"; a longer prefix shrinks the full result list, even if the top three stay the same. A real UI usually waits for two or three characters before searching.
  • red run demonstrates AND semantics across words: both typed words must be a prefix of some word in the title, and only "Red Running Cap" qualifies.
  • runing and shooes find nothing with exact prefixes, so the fuzzy fallback runs. Within one edit it finds the running products and "Running Shoes" (shooes is "shoes" plus one extra letter).
  • zzz finds nothing even with fuzziness, which is correct.

Trade-offs and tuning

  • Index size: every word of length L creates up to L โˆ’ min_gram + 1 terms. A large catalog with long titles can double the index. Limit max_gram, and do not apply edge n-grams to long free-text fields like descriptions.
  • Separate field: keep autocomplete on its own field (such as title.autocomplete, a multi-field), so the n-grammed tokens do not distort relevance scoring of the main search field.
  • Popularity source: refresh popularity from analytics in batches (a daily bulk update), not on every click. Every update creates a new document version (segments lesson).
  • Throttling: the browser should wait 100-200 ms after the last keystroke (debounce) and cancel outdated requests. Otherwise one fast typist produces a flurry of useless queries.
  • Security and cost: suggest endpoints are public, so clamp size, require a minimum length, and rate-limit (security and operations).
  • Accents and languages: add asciifolding to both analyzers so "cafe" finds "cafรฉ" (multilingual search).
  • Evaluating quality: keep a list of typed prefixes with the suggestion you expect on top, and test it after each change.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why should the search-time analyzer for an edge n-gram field not apply the n-gram filter?

    Prefixes are generated when indexing. The typed text should be looked up as it is, so run matches the stored prefix run.
  2. 2. What is the main price of using edge n-grams?

    Work moves from query time to index time. Each word stores several extra terms, so the index grows.
  3. 3. What does prefix_length: 1 do in a fuzzy match query?

    The first character is not allowed to be fuzzy, so far fewer candidate terms are examined.
  4. 4. Why is log1p used on the popularity value in the function score?

    A logarithm compresses large values, so a huge popularity gives a bonus but does not drown out how well the text matched.

Summary

  • Edge n-grams store prefixes at index time, so typing becomes a cheap exact term lookup.
  • Use an n-gram index analyzer and a plain search analyzer on the same field.
  • Combine text relevance with a dampened popularity signal using function_score.
  • Add fuzziness (with prefix_length) for typos, ideally as a fallback when exact results are few.
  • Control cost with min_gram/max_gram, a dedicated field, debouncing in the browser and rate limits.

Next: Project: Log Search and Dashboards.