A small team in Germany has written a cool front-end to the search engines on Google, Wikipedia, and YouTube. Keyboardr executes and displays searches as you type. It's a better interface than the type-wait-retype cycle of most search engines.
Keyboardr also lets you navigate your results with the keyboard, which adds to its speed for users.
I'm not sure if this technology could scale to support a mass of users (or even if using Google this way is legal). Certainly, a typical Google search is more compute-efficient than searching on every letter typed. But the Keyboardr method is more efficient for users, since it lets you watch and refine your search as you go.
Worth a look.
See also: SearchMe. And the .