[Quora Challenges] Typeahead Search - I

This is the first post amongst a few that would follow in an attempt to solve the Quora challenge Typeahead search. This problem particularly interests me. Why? Because during my internship at Media.net (Directi), I worked on a similar problem. Having spent an entire summer working on an equivalent of Google's "instant search", I realized how complex it is. "Bigger dataset, lesser query time", this was all that was on my mind for most of my summer.

Having done a lot of research earlier, I referred back to the following to see if I can apply any ideas directly

1. A very fast approach to auto complete (or search suggestions)
2. Efficient auto-complete with a ternary search tree
3. Trie examples 
4. What is the best autocomplete/suggest algorithm,datastructure 

As is evident, most of these point towards the use of a trie to solve the problem. Considering that I developed a fascination towards Tries during the internship, I might even end up using the same structure here. However, I'm considering exploring other methods that might suit this problem better. For instance, tries are exceptionally good to reduce the time taken to search for a word, it requires a lot of space. Also, since there would be at most 40k insertions, other methods such as the 4th Approach here. I also need to check how much memory usage is allowed to solve this problem and how much pre-processing time would be acceptable.

[More discussion in follow-up posts]