Data Structure for Storing Prefixes

The trie data structure

Use a data structure optimized for prefix lookups. The service must match user input against a large set of strings to return query completions. For example, given the terms “UNITED”, “UNIQUE”, “UNIVERSAL”, and “UNIVERSITY”, typing “UNIV” should return “UNIVERSAL” and “UNIVERSITY” as prefix matches.

A memory-resident serving index is one way to meet the latency target, while persistent snapshots support recovery. A database with a suitable index or cache can also support prefix lookup. Compare the actual lookup and ranking work rather than assuming every database request goes to slow storage.

A trie (pronounced “try”) is commonly used for this purpose. In a simple trie, each edge represents a character and a path spells a prefix; diagrams sometimes place that character on the child node. Mark terminal nodes so one complete term can also be a prefix of another. The example words are stored in the trie as follows: