Another approach is something similar to Google Suggests http://www.google.com/webhp?complete=1&hl=en, it gives the user immediate feedback, but I'm not sure how fast your server has to be.