Hey all. Lately, I've been thinking a lot about searching autocompletion for my website. The functionality is very similar to say, something like Youtube (start typing in a song name or artist name). I've been milling over the idea of using a Trie data structure for the search. On the web, this can be problematic as there's no pointers and such that make tree-like structures easy. I would have to store a list of words somehow (in a Trie structure) and would have to fetch and parse this string every time I went to do a search (not to mention inserting and deleting from the structure wouldn't be trivial).

Currently, I just use jQuery's autocomplete that reads from an XML file (which I'm guessing just does a linear time search that has to parse the whole file anyway). It works fine I suppose, but it actually looks for matches in the entire string (not just matching prefixes) and returns them in the order they appear in the XML file (I would prefer if they ranked based on number of queries which is also stored in the XML file).

At one point I was just considering an AJAX request to a page that would just query the database for matches. I'm guessing this would be quite a hit to the server (you'd have to do the request on literally every letter typed) but it may be preferential to having users do this processing themselves (especially if they're on a mobile device).

Do any of you have some success stories on implementing your own autocomplete or can point me in the right direction?