Search Autocomplete Design

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!

Happy coding.

Advertisements

6 Responses to Search Autocomplete Design

  1. p says:

    when do you invalidate local storage? and how do you guage/limit the amount of memory you are taking up?

  2. p says:

    why dont you respond to my excellent questions browntrout?

  3. p says:

    “dont say anything” – Art, on what I should follow up my questions with.

  4. artur says:

    I think Chrome gives you about 1MB which isn’t much. The more elegant, but not yet built solution is to implement an actual cache manager on top of session/persistence offered by HTML5 browsers. I actually want to do it as the next enhancement for my Google TV project.

  5. p says:

    oooooh sneak preview into what Art is working on next. “Google TV” says you. “More blog post,” says I.

  6. p says:

    browsers suck

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: