AutoComplete

[militiaware]

i think GWT autocomplete use (String) array structure in the server
side, to compare the string which is coming from the client side with
the values of the array.

now, if there's over 500,000 word. What is the finest structure to be
build on the server side to make the the time cost at minimum.

and i want to know what google uses in Google Suggests Lab on the
server side!!!

[RogueCode]

A suffix tree, perhaps ?
In any case, the following link is a good start point:

http://en.wikipedia.org/wiki/String_searching_algorithm

[dukehoops]

militiaware wrote:
> i think GWT autocomplete use (String) array structure in the server
> side, to compare the string which is coming from the client side with
> the values of the array.
>
> now, if there's over 500,000 word. What is the finest structure to be
> build on the server side to make the the time cost at minimum.

A good alg for this is a trie: http://en.wikipedia.org/wiki/Trie

There are java indexing libs that likely use a Trie under the covers.
check out:
http://lucene.apache.org/java/docs/index.html