Live Search or Query Suggestions?

In the proposed concepts for a new GUI we showed a keyword suggestions feature, similar to what many other applications and sites use nowadays. You type the first couple of characters and a little flyout menu starts suggesting keywords.

Until now I assumed that these keywords suggestions should be based on a mix of popularity, recency and bookmarks. I even asked you if you liked those. This is what you said:

Query suggestions based on bookmarks
Very unimportant 0.00%
Unimportant 12.50%
Neutral 37.50%
Important 37.50%
Very important 12.50%

Query suggestions based on recent searches
Very unimportant 0.00%
Unimportant 4.35%
Neutral 34.78%
Important 52.17%
Very important 8.70%

Query suggestions based on frequency / popularity
Very unimportant 0.00%
Unimportant 8.70%
Neutral 30.43%
Important 52.17%
Very important 8.70%

[Full survey result details here...]

Compared to your appreciation for other features, you weren´t that excited about it apparently. Now maybe I know why. During the World Conference Last weekend a business partner showed us a customized screen using a sort of search suggestion based on live search. So while typing it actually searches in real time. Pretty impressive. I thought this would be too slow. Perhaps with 1 million records it would be. But look at this demo of a dhtmlx-grid (Select Loading from big Datasets > 50,000 records in grid from the tree menu on the left and tick the Enable Autosearch checkbox)...and start typing away. This rocks!

Having seen this, I can´t suppress my enthusiasm for live search suggestions but we need to make sure this is what you want. Compared to search QUERY suggestions. The latter is used in consumer applications, such as iTunes or Google Suggest. Music stores use them all the time, as what the masses want, is probably what you want (typing "b" in iTunes will inevitably show Britney Spears and Beyoncé, whether you like them or not).

So what will it be, dear user? Query suggestions or Live Search? Share your thoughts on the UX Lab. Tightly related is the discussion about Endless Scrolling versus Pagination. Give us your 2 cents here as well please.

Cheers, Rob