Autocomplete - Classic Search System Challenge

Autocomplete is a critical feature if your service supports search functionality. It not only helps users type faster but also suggests what they should search for.

Problem Requirements

1. 1**Low latency**: relevant suggestions must appear as users type
2. 2**High availability**
3. 3**Accept eventual consistency**
4. 4**Results must be sorted by priority**
5. 5**Results must be relevant to the user's input prefix**

Simple Solution

The most naive approach is scanning through all strings:

SELECT suggestion FROM autocomplete_table 
WHERE suggestion LIKE 'iphone%' 
ORDER BY weight LIMIT 7;

This is simple but has very poor performance with millions of strings.

Trie - Optimal Data Structure

A suitable data structure for prefix string searching is **Trie**. This is a popular data structure that helps find strings with prefix length L with time complexity **O(L)**.

Advantages of Trie: - Fast search with O(L) - Memory optimization for strings with common prefixes - Easy to extend with prefix tree

Suffix Tree

• •Reduce tree complexity
• •Faster search
• •No need to visit too many intermediate nodes

Adding Weights to Suffix Tree

• •Based on search history
• •Prioritize recently searched strings
• •Keep up with user trends

Pre-computing Results

• •Pre-compute results for branches with many elements
• •Store in hash table
• •Trade memory for speed

Issues to Solve

1. 1Split large trees into smaller trees to reduce load
2. 2Ensure high availability
3. 3How to store Suffix Tree in database

Reference: System Design Vietnam Community