java - How to design the server side data structure of autocomplete function? -

java - How to design the server side data structure of autocomplete function? -

i have millions of search engine queries looks this:

stack overflow java video tutorials cars c++ vs java

now want implement auto-complete function fit these demands:

1. type in 'so', prompt ['stack overflow','...','...'] 2. type in 'overflow', prompt ['stack overflow','...'] 3. type in 'jvt', prompt ['java video tutorials','...'] ...

here solution:

1). extract query's abbreviation, e.g. stack overflow -> so;

2). split query suffix words, e.g. stack overflow -> 'overflow' + 'stack overflow';

3). 3 sequences 'stack overflow':

'so','overflow','stack overflow'

4). in last, index these 3 sequences trietree, , in lastly node of every sequence denote orignal query(or query id):

'o' --> 'stack overflow' 'w' --> 'stack overflow' 'w' --> 'stack overflow'

but think much complexity, there has improve solution ? much !

java algorithm data-structures string-matching trie