What strategies are used to auto-complete on a large dataset?

Question

I am a .NET developer of WinForms / ASP.NET, with what I consider to be technological agnostic questions on how to implement "automatic completion of input" on a large dataset. If someone can point me to a reference implementation or a detailed discussion, that would be great, but here are my questions:

• Presumably, the user begins to enter text and, after a certain period of time, the client requests data from the server to make the type in front. Is there a rule of thumb for how long this interval is? Does this rule change as the search dataset grows? What if the user types again, but the previous request did not complete due to the size of the data set?

• What query strategies are used to load the dataset? Obviously, the query must be asynchronous, but it is not just SQL "% search term%". What text matching strategies are used? How strictly is this data set stored? What if it is too big for caching?

• Are there any different strategies that should be considered when we talk about a web client using AJAX compared to a desktop application with a thick client?

At some point, I will look at specific .NET implementations, but I'm more interested in strategies at this point.

Answer 1

To ask your first question: There are certain performance considerations that you will need to consider. A low-bandwidth system with high bandwidth and fast database overload (possibly even with a local database) can allow a more aggressive polling of the server and provide a completely different autocomplete for the end user.

For Internet applications, the general rule is that the user needs to enter three characters before starting autocomplete on the server. This is completely reversed in certain cases.

I believe this also applies to your third question.