What strategies are used to implement type-ahead auto-completion on a large dataset?

Question

I am a .NET WinForms/ASP.NET developer with what I think of as technology agnostic questions about how to implement "type-ahead auto-completion" on a large data set. If someone could point me to a reference implementation or detailed discussion, that would be great, but here are my questions:

1. Presumably, the user starts typing and, after some interval, the client asks the server for data to do the type ahead. Is there a rule of thumb for how long that interval is? Does this rule of thumb change as the dataset to search grows? What if the user starts typing again but the previous query has not completed because of the size of the dataset?

2. What query strategies are used to pull the dataset? Obviously, the query must be asynchronous, but it is not a simply SQL "%search term%" is it? What text matching strategies are used? How rigorously is that dataset cached? What if it is too big to cache?

3. Are there any different strategies to consider when we are talking about a web client using AJAX versus a thick-client desktop app?

At some point I will look at specific .NET implementations, but I am more interested in the strategies at this stage.

Answer 1

To address your first question: There are a certain amount of performance specific considerations you will have to take into account. A system with a low latency high bandwidth connection to a fast and non-overloaded database (perhaps even a local database) can afford to poll the server more aggressively and provide a completely different auto-complete experience for the end user.

For internet applications, the general rule of thumb is that the user has to enter three characters before server-based autocomplete kicks in. This changes entirely in certain cases.

I suppose this addresses part of your third question as well.