What autocomplete does
As a user types, autocomplete offers completed queries. It must respond within a few tens of milliseconds, so the data structure matters.
Fast prefix lookup
- A prefix tree, or trie, stores known queries so any prefix maps quickly to its completions.
- Each completion carries a score, usually based on past popularity.
Ranking suggestions
The candidates for a prefix are ordered by:
- Popularity of the full query in logs.
- Recency, boosting queries trending right now.
- Personalization, favoring what this user searched before.
To stay fast, the top completions per prefix are often precomputed and stored with the trie node.
Quality guards
Suggestions must avoid offensive or unsafe completions, so a filter sits between candidate generation and display.
Diagram
Key idea
Autocomplete uses a prefix tree for instant lookup, then ranks completions by popularity, recency, and personalization before a safety filter.