One of the first things I worked on when I joined Evernote was designing and implementing Type Ahead Search for the Evernote Mac Client.
This is how it looks today:
Most of us, at some point, have faced the challenge of not knowing what exactly to search for when confronted with a search box and a blinking cursor. We introduced type ahead search to improve this experience for our users by providing suggestions for their search, as they type, that are drawn from their own note content.
In this blog post I want to touch upon some of the implementation details in bringing Type Ahead Search to life in Evernote.
What’s unique about Evernote’s brand of Type Ahead Search?
To most of us, Type Ahead Search is second nature. Stop for a second and imagine what searching on Google would be like if it did not offer you suggestions as you typed. Even though this was the norm only a short time ago, we have now come to expect a list of “smart” suggestions to follow every search box we encounter.
Yet, not all search magic is created equal. For one, Google draws its suggestions from an ever growing corpus of the public’s search queries. What this means for a user is that the suggestions you see are often things that others have searched for before and might not be familiar to you. However, this model works well for a web search engine, which attempts to search the world for information. As a contrast, search in Evernote is a very personal experience. The only search results you see in Evernote are those that you yourself have curated, and that is the same theme we apply to search suggestions as well. A corpus for our purposes is a single user’s set of notes, which sits in a silo, not being able to communicate with any other user’s data. So while many other services talk about having a ‘Big Data’ problem, Evernote has millions and millions of ‘Small Data’ problems. Every data set is every user and every user is unique in its own way.
Another distinction is the type of content from which suggestions are drawn. Many web services that support Type Ahead Search offer discrete suggestions from a finite (but large) set – for example – search queries, people, or companies. In contrast, the suggestions you see in Evernote can be drawn from any structured or unstructured content that appears in any of your notes, in any language that you can read or write. We aim to figure out which suggestions are relevant for you by analyzing the contents of the notes themselves.
Choosing an Implementation Platform
As a multi-platform company, we believe that all Evernote users should have a first-class experience on their favorite devices. Still, we had an important decision to make when it came to picking a platform for the first implementation of Type Ahead Search: should we build a server-side system that could potentially be used across clients or start with a native implementation on a single client? To start, we decided to go native on the Mac for a few reasons:
-
We wanted Type Ahead Search, like the regular search experience, to work offline.
-
We wanted to take advantage of platform-specific optimizations. The Mac OS, for one, offers a rich set of linguistic APIs that we could apply to this problem.
-
We wanted to optimize for performance and a great user experience – even if it meant taking on more work for ourselves.
The Nitty-Gritty (a.k.a. Implementation Details)
Three main components power Type Ahead Search: the Suggestion Index, Suggestion Generation, and Suggestion Retrieval.
Suggestion Index
The search suggestions are stored in an inverted index, separated from the core search index. We briefly considered whether to reuse the search index and found that, although it could be coerced to drive Type Ahead Search, it was carefully tuned for individual keyword search and produced very low quality suggestions on its own.
We structured the Suggestion Index to map a suggestion to a list of notes that contain it. In information retrieval speak, the ‘term’ is one suggestion and the ‘postings list’ is a list of notes.
Suggestion Generation
The first part of Type Ahead Search begins well before the user types characters in a search box. Every time a note is created, modified, or deleted, we generate a list of potential suggestions from the note’s title, tags, and content, which are then serialized and saved to an inverted index. Here’s how it works.
We start by detecting the individual words in the note’s text. The words are passed through a series of filters responsible for normalizing the text (e.g., lower-casing, stripping diacritical marks) and removing stop words (extremely common words). The filtered words are then further aggregated based on certain rules, which may combine them into phrases that might be relevant in the context of the larger text. Finally, the words and phrases that fall out of the filters are serialized into the suggestion index.
This component also has to ensure that special considerations are taken to accommodate the languages most widely spoken by Evernote users. For example, some languages (like Chinese and Japanese) do not use characters like spaces to delimit where one word ends and the next begins. Instead, more sophisticated software must be applied to find the word breaks in a continuous sequence of characters. To make the problem even more interesting (read: “harder”), notes can be written in a mix of different languages.
And of course, all of this processing must be done in the background based on resource availability so as not to interfere with the user’s experience.
Suggestion Retrieval
We’re ready to perform a search — now what happens? When a user begins typing in the search box, the Suggestion Retrieval system first determines the set of notes that fall within the user’s context, the combination of notebook and tags inside which the user is currently searching. It then looks up the search query prefix in the suggestion index, which yields a set of completions for that prefix. Finally, it filters out any completions that do not fall within the contextual notes.
Next, every suggestion is scored and ranked for relevance by a custom formula derived from TF-IDF. The top-K suggestions, by score, make it through to the final step, in which very similar suggestions (e.g., “ice skate” and “ice skating”) are consolidated.
In many ways, this component is the most complex, but it must also be the best performing one since users rightly expect a sub-second experience. For that reason, most of the attention we paid to performance was directed at this part of the Type Ahead Search system.
What’s Next
If you haven’t already used this feature or the Mac Client, I encourage you to give it a try and let us know what you think.
Look for this in some of our other Evernote clients in the future.
