Friday, August 18, 2006

Talk on fast autocompletion

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).

4 comments:

Anonymous said...

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.

So what are your personal thoughts on this sort of work? In the past you've tended toward the Google approach, saying that users really do not want to do any extra work. They just want to type their query and go.

My ongoing counterargument has been that, by requiring users to do all the work in exploring and refining their queries themselves (for example, when a query has multiple facets), the Google approach actually makes users do more work, not less. I feel that tools help the user do less work than the supposedly "magic" one-shot, we-know-better-than-you Google approach. That's because the user ultimately ends up re-issuing multiple one-shot queries...essentially a one-sided dialogue.

So, I've spoken with Google engineers about this.. and they're still philosophically very much against this approach. What are your own thoughts?

Greg Linden said...

Hey, Jeremy. I think it come down to one issue: simplicity. If the dialogue approach can be simple, intuitive, and easy, I think it is a win.

A problem is that the bar seems very high. It is hard to beat the plain simplicity of a Google keyword search box staring back at you. That is easy and, at this point, well understood by most people.

I thought this autocompletion demo was interesting because of the simplicity of the UI. The suggestions and intermediate search results seemed to me to surface in an intuitive, unobtrusive, and helpful way.

If the dialogue approach can achieve useful simplicity, I think it could threaten or even kill the one-shot approach. And, I suspect Microsoft, with their control of the desktop, might be particularly well positioned to pursue this strategy.

What do you think, Jeremy? I know you are a fan of exploratory search. What did you think of Holger's work?

Anonymous said...

I haven't had a chance to read through the two papers you posted yet, but I think you mostly nail down the issue by focusing on simplicity. You fill in the rest of the gaps by talking about necessitating intuitiveness.

What my own internal jury is still hung about is whether intuitiveness means "instantly obvious" or "easily picked up with determination and practice"

I'll make an analogy to photography. Sure, you could just set your camera to "fully automatic". That would be the Google approach. And you'll probably get mostly decent photos.

But what about when you're taking a photo of someone at night? Or with lots of motion (sports)? Or landscape, or macro? Well, then you could set your camera to one of the still automatic, but situation-specific sub-settings, for night, sport, landscape, etc. style pictures. You'd get better results than fully automatic. That, I think, is like this Holger approach. It is simply (one turn of the dial) and intuitive to the point of immediate obviousness. It's night? Turn the dial to night. That can't be a bad thing.

What I guess I'm still struggling with is whether aperture priority, shutter priority, or even the full manual "tool" setting has any analogous place in information retrieval. I feel that these camera settings are still simple: you're basically just going up or down on the amount of light you're letting in to the camera. But while the use of these settings are not immmediately obvious, with a small amount of determination and practice, and a decent light meter, you can get really good results.. much better than any of the fully automatic modes. They are tools, I would argue, that even if not immediately obvious, are nonetheless simple. (Much simpler and more accessible to the common man than, say, than multivariate calculus.)

And while you might not need to use these priority or manual modes all the time, if you are really determined to get a good photography, you can learn the tools and do so without a prohibitive amount of effort. Once you get over that little bump, then those tools are yours for life, and you see all sorts of situations you can use them in.

I think the same is probably true for IR. Not all Google searches succeed. Some that don't could be aided by Holger-style interfaces. But the ones that even fail after that.. at this point I think people just give up. If they had "aperture priority" tools available, they might actually be motivated to start playing around with them a bit.. and learn that they could do some interesting things with them.

I am way too long-winded. I apologize. What I am trying to say is that, with the motivation that comes from the failure of existing methods, a tool that originally doesn't appear -immediately- obvious, suddenly appears much more intuitive when combined with just a little bit of effort on the user's part.

But overall, I think you are completely correct when you talk about simplicity and intuitiveness.

Anonymous said...

I think all I'm trying to say is that, in a world that is dominated by point-and-shoot, there is still a healthy market for consumer-level dSLRs. There is enough of a market for people that value being able to control the quality of their pictures, and invest in the effort it takes to learn how to do that with dSLR tools.

By the same token, I have to believe that there is also a market in the information retrieval space for those who value being able to control the quality of the information that they find, and invest in the effort it takes to do so.

That's all I'm trying to say.