Auto-suggestion Service

2 minute read

This section covers proposed solutions for problems when designing auto-suggestion service where service will suggest words or phrases when user searchs for any prefix

  1. What are service requirements?
    • Highly available: the service will have more read requests than write. We can affort for data to be inconsistent for a short while.
    • Low latency: this is very important in this service as it is pointless if the suggestion is slower than users typing speed
  2. What is the logical workflow workflow of retrieving suggestions?

  3. How do we store our words that can quickly be queried with prefix?
    • Trie can be used to achieve this. A trie is a tree-like data structure used to store words where each node stores a character (or many characters if that node has only 1 branch) of the word. A node where the word ends will also have store a variable that signal end of the word.
    • Trie can be stored in filesystem. With each node, we can store what character it contains and how many children it has, i.e A2B1C2…(node A has 2 children). Besides, we can also store the frequency of search word at the final node.
    • If we need to store trie data over multiple servers, then the results could scatter over different places, we should have a centralized server to aggregate the results.
  4. How do we return suggestions?
    • Since we need to minimize the latency, we should only return for small number of suggestions, i.e. 10
    • Top suggestions can be retrived based on number of search. In order to keep track of number of search per words, we can store number of search at the last node of each word. When performing traversal, we can go to each sub-tree and find top 10 words.
    • Another suggestion is to simply store 10 suggestions words right at each node, so that the time to return will be minimized.
  5. How do we update The trie?
    • We should update new word and the frequency offline to avoid load by both read and write requests
  6. What are ranking criteria for suggestions?
    • We can simply rank based on the frequency of search term, or we can consider other factors, i.e. freshness, user location, language, demographics, personal history etc.
  7. How to lower latency?
    • As soon as client open the search engine website, the client immidiately establish connection with the server.
    • Client should also cache some of the data from server adn only send request to server only if user has not typed any character for, say 50ms

Leave a comment