What is an efficient search algorithm to provide auto-completion?

Question

I've got a list of 10000 keywords. What is an efficient search algorithm to provide auto-completion with that list?

Answer 1

Using a Trie is an option but they are space-inefficient. They can be made more space effecient by using a modified version known as a Radix Tree, or Patricia Tree.

A ternary search tree would probably be a better option. Here is an article on the subject: "Efficient auto-complete with a ternary search tree." Another excellent article on the use of Ternary Search Tree's for spelling-correction (a similar problem to auto-complete) is, "Using Ternary DAGs for spelling correction."