Walter Underwood of Netflix posts about the minimal text that people use to search for movie titles. Examples include frank g[ehry], baron mu[nchausen], and apoc[alypto]. Adding auto-complete to the search field improved usability considerably.
Creating autocomplete suggestions based on query logs, click-through patterns and reformulation, and clustering them with an appropriate label. The result is compared to web search logs, but not tested with users or click-through analysis.
An academic approach to efficiency in generating autocompletion suggestions, and evaluating the results using only query logs as input. I think that more traditional relevance testing with user assessments and click-tracking is much more likely to be meaningful.
(PDF is available at the authors' publications pages)
