This article is about what I call “live search boxes”. They’re the text boxes that perform some sort of search while you type.  Google Suggest and iTunes both have them. But I have a problem with how they work, and I’ve got a solution too.


the problem

These things start searching before I’m done typing, which is distracting and inefficient. They’re distracting, because the first part of my search may not yield results that are relevant once the whole thing is in. For example, see the screenshots below of me searching for “free running” with Google Suggest. The results after typing “free” don’t overlap at all with the results after the full query “free running” is entered.

google suggest free google suggest free running

These live search boxes are also inefficient, because if they run a search while I’m typing, another search will be necessary when I’m done; but as long as I’m typing I can’t click on the intermediate results, so they’re wasted. In the iTunes screenshot below I’m searching for “bon jovi” but it does a premature search for “bon”. That does bring up the right results, but it brings up some wrong results along with them, and if it had been patient enough to wait the milliseconds for me to finish typing ” jovi” I would have gotten the exact results I wanted.

itunes bon search

I admit that when my computer is running smoothly these intermediate results just flash by until I’ve finished typing and my final results are shown. But when my computer isn’t at full processing capacity, the intermediate searches can be slow enough that they cause iTunes to freeze temporarily, and interfere with me typing out my full query. That’s what really gets me about live search boxes with this behavior: they can make it harder to do the search I want to do.

Maybe an analogy is useful. In the gym at my school the men’s locker room has toilets with those infrared sensors that lets them detect when they’re occupied, and flush when appropriate. When functioning correctly, this system works exactly how I want the live search to work: the device accepts input from the user, and when it has detected that the user is finished inputting, it processes the input appropriately. Unfortunately, the sensor systems don’t work properly, and they frequently process input while it’s still coming in. As with the search boxes above, this operation is inefficient (here in terms of water usage) and believe me it’s distracting. But the correct functioning of these toilet systems gives the perfect analog of my solution to the live search box problem.

sidenote: I feel justified using toilet humor to describe this problem because Jef Raskin did it too; “A search is either incremental or excremental.” (footnote on p.126 of Jef Raskin, The Humane Interface, 2000).

my solution

The problem was that these search boxes start searching before I’m done typing, so the solution should be apparent. It’s to make the damn boxes wait for me (and you and everyone else) to finish typing! A simple way to accomplish this would be to wait half a second or so after the user types each character, and if another character hasn’t been typed in that half-second, assume the user is done typing and run the query. The problem with this approach is that users can have different typing speeds, and a one-size-fits-all delay of 0.5 seconds (or 0.3 or 1.2 or whatever) before searching may not be appropriate to all of them. If 0.5 seconds is too long, there will be an annoying lag before the search is run, and if it’s too short, then the search box will be at least as bad as the ones I just finished griping about.

Because individual variation is the issue, we need a solution that varies with the user. This can be accomplished with some really basic artificial intelligence. At a high level, my method is to watch how fast the user types by counting the milliseconds between keystrokes, fit a simple probabilistic model (specifically, a Gaussian) to that data to describe the user’s typing speed, and then use that model to determine the amount of time beyond which it’s very unlikely for the user to type another character. Once that (probabilistic) upper limit has passed without any typing activity, I run the search.

Now for the details. That talk about probability probably made this sound more complicated than it is. Basically, I keep a running average of the amount of time between keystrokes, and that gives the best estimate of how much time there will be between this keystroke and the next. But this is an average, and it may be that some keystrokes are a bit slower and some are a bit faster than the average; to account for that I also track the running standard deviation of keystroke times, which is a measure of how much they vary. By the empirical rule (and the assumption that the Gaussian is an appropriate model for these keystroke times), we know that just about all keystrokes are going to be shorter than the average plus 3 standard deviations (sigmas). So my probabilistic upper limit is set at the average plus 3 sigma, plus a little fudge factor that (hopefully) doesn’t add an uncomfortable delay, but prevents short hesitations from triggering a search.

the result