Holger Bast gave a fun talk at Google called "Type Less, Find More: Fast Autocompletion Search with a Succinct Index".
The demo at the beginning is a nice demonstration of the value of doing prefix matches on multiple search terms. It shows a potential direction for future search engines, away from the one-shot deal of "enter keywords, get results" and toward an interactive dialogue where the search engine constantly suggests possible results and refinements.
The talk enters a second stage around 19:00 where Holger spends most of his time on the challenging problem of how to build indexes to support prefix search efficiently. Quite interesting as well.
Holger also had two papers at the SIGIR conference on this work, one (PDF) with the same name as his Google talk but with more detail and another called "When You're Lost for Words: Faceted Search with Autocompletion" (PDF).