Search Autocomplete Design
October 2, 2010 6 Comments
I’ve written half a dozen type-ahead widgets by now and definitely one of the most important aspects to type-ahead is speed. Facebook’s type-ahead is obviously really well written and might be one of the most important features on the site.
I investigated how they build their widget and one of the most interesting techniques is their use of HTML5 LocalStorage. This is one of the oldest features available in browsers, it’s only recently that it’s been standardized. There is a cool library you can use to abstract the browser quirks. Here is summation of techniques that I’ve picked up:
- Preload. First page load, grab a finite set of probably searched entities. In Facebook’s world it means grab all your friends or top X friends if you have a lot. Cache this in Local Store. You’ve now covered 80% of the cases.
- Show results right away. Chances are the user will see something they are looking for already, and if not while they are scanning the possible list of entities you can fetch the long tail list of entities they could be looking for and drop them in.
- Filter in memory. Some type-ahead widgets will filter on the DOM. Terrible idea because DOM manipulation will always be slow. Filter in memory with some regex magic.
- Optimize your Regex. Regex is an art. Rely on someone who can write you a good matcher. Or ask me!
- Memoize in memory. Chances are they will hit backspace. You want to save every mutable keypress.
- Use LocalStorage aggressively. People search for the same stuff over and over. Save the bandwidth and time. Cache the search queries. This is where LocalStorage comes in handy!