AutoComplete implementation

(From an Interview Question)

Say you have a DB table with two cols: SearchPhrase(String) | Popularity(Int).

You need to initialize a DS so that you could use it to implement an autocomplete feature (like google suggest) comfortably. The requirement: Once the data from the db is processed into the data structure, when you type a letter you get the 10 most popular searchphrases from the db starti开发者_运维问答ng with that letter,then when you type the next one you get the 10 .... with these two letters and so on.

The question only concerns planning the ds and pseudocoding Insert,Search etc.

Note: YOU CANNOT USE TRIE DS.

Any ideas?

A trie would be the best fit but since you can't use it, what about a DAWG?

Have you seen similar questions on here?

autocomplete algorithms, papers, strategies, etc