When you have more than a handful of strings, you will want to return only a small number (k) of completions, preferably sorted by some pre-assigned score. Depe

When you have more than a handful of strings, you will want to return only a small number (k) of completions, preferably sorted by some pre-assigned score. Depending on how you order the trie, you can only get the first k completions by lexicographic ordering, which could be very far from the "best" completions. A common approach to solve this is to store in each internal node the maximum score among all its descendants, and sort the children of each node by maximum score. This way by doing a best-first search with a heap you can efficiently retrieve the top-k completions by score. If you then have millions of strings, it becomes tricky to do this in a space-efficient and cache-efficient way. I wrote a paper a few years ago with different space-time tradeoffs: http://www.di.unipi.it/~ottavian/files/topk_completion_www13.pdf http://www.di.unipi.it/~ottavian/files/topk_completion_www13...