How It's Made

“Avacado” or Avocado?

Jagannath Putrevu

Jagannath Putrevu

Oct 14, 2020
A simple search query correction heuristic for the resource-constrained

At Instacart, our search engine is one of the most important tools customers rely on to quickly find their favorite grocery items in the digital aisles. But, oftentimes, some of the most common grocery goods are the trickiest to spell. We’re not all spellers or digital natives — if you mistype or forget how to spell 🥑 (it’s Avocado by the way) you’re not alone. But, that typo shouldn’t automatically mean you have a poor search experience.

Some of our most popular misspelled queries are:

  • Siracha ♨️
  • Zuchinni 🥒
  • Jalepeno 🌶
  • Cantelope 🍈
  • Parmesean 🧀

During the early days of Instacart our team was small and scrappy, and we used to manually add correction terms for commonly misspelled queries. But, this approach doesn’t scale. My first project as the first Machine Learning Engineer on Instacart’s Search & Discovery team 5 years ago, was to fix this problem. In technical terms, we wanted to improve the Recall of our search engine for misspelled queries.

The query correction problem

In general, we encounter two main query correction problems:

  • non-word query correction (spelling errors that result in non-words, for example, “avacado” for “avocado”)
  • real-word query correction (spelling errors that accidentally result in an actual word, for example “line” for “lime”)

Non-word query corrections can be solved by using a dictionary and some form of distance function to map the incorrect word with a correct word from the dictionary. Real-word query corrections are much harder problems and require more state-of-the-art techniques like building a language model. Peter Norvig wrote a great post on “How to Write a Spelling Corrector,” which walks through some of these concepts.

Given the short one-word queries we typically see with grocery searches, query correction is not an easy problem. There are thousands of papers on this topic and this is still a very active area of research. For us, the non-word query corrections were the most prevalent and accounted for most of the spelling errors that resulted in zero-result queries in the early days of Instacart.

For any given problem, there may be standard “state-of-the-art” solutions that are not always trivial to implement. In the early days, we had to solve a number of technical problems when building the Instacart marketplace, and it was impossible to prioritize each of these problems. So, we had to get scrappy vs. state-of-the-art when tackling these issues. Our commonly used approach to problem-solving in those days was — “can we use a simple approach that solves 80%-90% of the problem in a short period of time?” We often went for a quick, yet very effective, heuristic. It not only solved most of the incorrect spelling problems but also gave us the added benefit of helping with the query reformulation problem, which we’ll explain below.

The path to a successful query

After entering a search query, a customer will take one of the following actions:

  • Add an item to their cart if the query yields precise results with good recall (this event is called a conversion)
  • Search for a variation of the same query if they do not get any results or are not satisfied with the results
  • Search for a different query altogether if they decide to not convert on the given query
  • Go to the checkout page to place the order
  • Bounce off if they are not satisfied with the experience

For every query, each of these can be considered a different state the customer can move to in a Markov Chain. We are interested in helping the customer add an item to their basket (conversion state) as efficiently as possible.

Jagannath Putrevu

Jagannath Putrevu

Jagannath Putrevu is a member of the Instacart team. To read more of Jagannath Putrevu's posts, you can browse the company blog or search by keyword using the search bar at the top of the page.

Most Recent in How It's Made

How Instacart Uses Embeddings to Improve Search Relevance

How It's Made

How Instacart Uses Embeddings to Improve Search Relevance

Authors: Xiao Xiao, Taesik Na, Tejaswi Tenneti, Guanghua Shu As a fast-growing e-commerce platform and the leading grocery technology company, Instacart has an ever-expanding catalog of over 1 billion products from 900+ retailers, spanning a…...

Sep 14, 2022
Lessons Learned: The Journey to Real-Time Machine Learning at Instacart

How It's Made

Lessons Learned: The Journey to Real-Time Machine Learning at Instacart

Authors: Guanghua Shu and Sahil Khanna Figure 1: How ML models support shopping journey at Instacart Instacart incorporates machine learning extensively to improve the quality of experience for all actors in our “four-sided marketplace” — customers who place orders on…...

Sep 7, 2022
How Instacart Uses Machine Learning-Driven Autocomplete to Help People Fill Their Carts

How It's Made

How Instacart Uses Machine Learning-Driven Autocomplete to Help People Fill Their Carts

Authors: Esther Vasiete Tejaswi Tenneti For an eCommerce platform like Instacart, Search is an important tool for making shopping feel effortless by helping people find the products they want, even when they are not sure what they’re…...

Aug 30, 2022