You can use a trie that keeps track of frequencies in each node. When the user begins typing, you've selected one branch of the trie. The trick comes in selecting the branches, or leaves, with the most common occurrences. A simple way to do this would be to do a traversal of the tree based on frequency at each level of the tree. You could do this with a linear search, or you could generate a max-heap for children at each level of the tree on-the-fly.