Autocomplete based on popularity

Question

For a general autocomplete suggestion (lexicographically sorted keys) one could use tries or TSTs. However I would like to do autocomplete to return results based on popularity of results. So searching for "clinton" would show "bill clinton", "hillary clinton" and "chelsea clinton" in that order. I believe this can be done using ngram approach within Lucene. Are there any other ways to do it?

On a similar note, what's the backend to return a list of results for the tags autocomplete on stackoverflow? Is it lucene based?

Answer 1

Depends on

1. how big your search space is
2. If you want error correction
3. The constant-ness of your search space
4. Per-user customization needed
5. Multi-language?

For in-memory situations you can use a Trie that stores hit count at the leaf.

Another important issue to deal here is how you are going to predict incomplete multiple words. e.g. Abraham => Lincoln or Thomas (father of user). N-Grams from which corpus will be better, Google or Class VI History Book?

It depends on the context. Hit count may be hits in the current application or global. e.g. You will run into the cold-boot problem when a new word comes into vogue, but it yet to receive sustantial hits to bubble up to the top of the list

Thoughts to get the discussion started... Thanks