Course contentsShow
← System Design
Lesson 1760 of 1,91942. Real-World System: Search and TypeaheadFree lesson

Top-K Suggestions Problem

Finding the K most popular or relevant suggestions for a prefix query efficiently.

Top-K Suggestions Problem

What you'll learn: How to efficiently find and return the K most popular or relevant suggestions for a given prefix in real-time typeahead systems.

The Challenge

When a user types a prefix like "sys", your system needs to instantly return the top K results (say, 10) from potentially millions of matching completions. Simply finding all matches and sorting them would be too slow. The Top-K problem asks: how do we maintain and retrieve just the most relevant suggestions efficiently?

Core Solutions

1. Pre-computed Top-K per Node

Store the top K completions directly at each trie node. When building the trie, propagate popularity scores upward so each prefix node "knows" its best children. When a query arrives for "sys", you immediately have the top 10 ready—no sorting needed.

Trade-off: More storage (K values × number of nodes), but blazingly fast queries.

2. Heap-Based Retrieval

Traverse the trie subtree for the prefix, using a min-heap of size K. As you encounter completions with their scores, maintain only the top K entries. This works when K is small and pre-computation isn't feasible.

3. Combined Score Approach

Rank suggestions by multiple signals: popularity (from TF-IDF or BM25), freshness, personalization, or click-through rates. The "top" K means highest combined score, not just raw frequency.

Real-World Pattern

Most production systems pre-compute top-K at index-build time, then cache aggressively. The trie stores references to the best completions per prefix, avoiding runtime sorting entirely. Updates happen asynchronously as new popularity data arrives.

Key Takeaway:
The Top-K Suggestions Problem is solved by pre-computing and storing the K best results per trie node, trading storage for instant query response times at typeahead scale.