Generates autocomplete suggestions by rewriting the partial user query into more complete alternative forms when the literal-prefix candidate set fails to meet quality criteria, expanding the suggestion surface beyond strict prefix matches.
Patent Overview
- Inventor
- Nitin Gupta
- Assignee
- Google LLC
- Filed
- 2013-06-25
- Granted
- 2016-01-12
- Application Number
- US 13/927,247
The Challenge
Literal Prefix Matching Misses Real Intents
Standard autocomplete returns queries that start with the user's exact prefix. This fails when the user types an abbreviation, an unusual phrasing, or a partial term whose literal prefix has few good matches. The system needs to rewrite the partial query into alternative forms when the literal candidate set is insufficient, surfacing matches the user actually wants even when the prefix is non-canonical.
- Strict Prefix Matching Is Brittle — If the user types a prefix that no popular query starts with, the literal candidate set is empty or low-quality. The user sees bad suggestions or none at all.
- Abbreviations And Variants Need Expansion — Users type abbreviations, shortened forms, or alternative phrasings. A literal match misses the canonical form. Rewriting expands to the canonical.
- Quality Criteria Drive The Fallback — The system needs explicit quality criteria to decide when the literal candidate set is insufficient and rewriting should kick in. The criteria can include candidate count, quality scores, and predicted CTR.
- Rewrites Must Preserve Intent — A rewrite that broadens the query too far loses the user's intent. The rewriting has to be conservative enough to stay close to what the user meant while expanding enough to find good candidates.
- Latency Budget Is Tight — Autocomplete runs at every keystroke. Rewriting plus second-pass retrieval must fit within the autocomplete latency budget.
Innovation
Rewrite When The Literal Candidates Underperform
The system receives the partial query, runs the standard candidate search, and evaluates whether the candidate set meets predefined quality criteria. If the literal set fails the criteria (too few candidates, low quality), the system rewrites the partial query into alternative forms and runs a second candidate search using the rewrites. The combined candidate set drives autocomplete display.
- Receive Partial Query — User types a partial query in the search box. The partial query triggers autocomplete.
- Run Literal Candidate Search — Search the complete-query database for queries matching the literal prefix. Collect the first candidate set.
- Evaluate Against Quality Criteria — Check whether the candidate set meets predefined criteria. Criteria include candidate count, average quality score, predicted CTR, and topical coherence.
- Generate Rewrites If Criteria Fail — If the literal set fails, rewrite the partial query into alternative forms. Rewrites can expand abbreviations, correct spelling variants, or substitute synonyms.
- Run Candidate Search On Rewrites — Search the complete-query database again using the rewritten forms. Collect a second candidate set.
- Merge Candidate Sets — Combine literal and rewrite candidates into one ranked list. Preserve provenance so the user can see which candidates came from the rewrite path.
- Surface Reranked Suggestions — Display the merged ranked list to the user. The mix of literal and rewrite-derived suggestions matches the user's intent better than literal alone.
Quality-Gated Fallback To Rewrite
The patent makes rewriting a conditional fallback, not a default. Literal matching is fast and accurate when the prefix is well-formed; rewriting kicks in only when the literal path fails the quality gate. The conditional design preserves latency on common queries while still handling the edge cases.
Literal First, Rewrite On Failure
The literal-prefix search is the primary path. Rewriting is the fallback that activates when quality criteria are not met.
- Quality Criteria — Configurable thresholds for candidate count, quality score, and predicted engagement. Determine when the literal path is insufficient.
- Rewrite Strategies — Abbreviation expansion, spelling correction, synonym substitution, contextual paraphrasing. Each strategy produces alternative prefixes for the candidate search.
Technical Foundation
Two-Pass Candidate Generation
The architecture runs literal candidate search first, then rewrites and re-searches only when needed.
- Literal Candidate Set — Queries matching the literal prefix of the partial user query. Fast to retrieve from a prefix-indexed completion database.
- Quality Criteria — Predefined thresholds (count, quality score, CTR predictions) that gate whether the literal set is sufficient.
- Rewrite Rules — Transformations that convert the partial query into alternative forms. Abbreviation tables, spelling correctors, synonym mappings.
- Merged Candidate List — Combined output of literal and rewrite-derived candidates, ranked into one final autocomplete list.
The Process
End-To-End Autocomplete With Rewrite Fallback
The pipeline runs at every keystroke, with the rewrite fallback gated by literal-result quality.
- Receive Keystroke — User types a character, extending the current partial query.
- Literal Search — Retrieve queries matching the literal prefix. Cheap and fast.
- Quality Check — Apply criteria to the literal candidate set. Pass or fail.
- Conditional Rewrite — If failed, generate rewrites and run a second candidate search using the rewrites.
- Merge And Rank — Combine literal and rewrite-derived candidates into one ranked list.
- Display — Show the ranked list to the user. Update on the next keystroke.
What This Means for SEO
What This Means for SEO
Rewrite-fallback autocomplete shapes which queries get suggested when users mis-type, abbreviate, or use non-canonical phrasing. Understanding the mechanism informs how to think about prefix targeting and abbreviation handling.
- Non-Canonical Prefixes Get Rewritten — Users typing abbreviations or shortcuts ("goog" for "Google", "NYC" for "New York") trigger rewrite expansion. Optimizing for the canonical form captures traffic from abbreviated prefixes too.
- Quality Gate Means Marginal Candidates Lose — When the literal candidate set has low-quality matches, the rewrite path takes over. This advantages canonical, high-quality content that becomes the rewrite target.
- Abbreviation Awareness Matters — If your audience uses abbreviations (industry jargon, slang, shortened brand names), the canonical-form content captures rewrite-derived traffic. Both forms should be present somewhere in your content for the system to learn the abbreviation mapping.