Author: Max Shaw, VP Product
Blog Date: June 2020
One of the most common use cases for a search engine is finding something by a "location". Here are some basic examples:
These are all pretty simple queries, but getting these to work in a search engine is much more complex than you might imagine. There are three general steps to handling location intent:
Let's walk through each of these three queries, step by step, to highlight how these steps work.
The first step is identifying local intent. In this case, the query Cardiologist near Green Bay has local intent and the user is looking for the place "Green Bay". For a human (especially someone who lives in the US and speaks English) this is pretty easy, but identifying potential place names is a difficult task. You will want to use a combination of named entity recognition alongside a database of place names to accurately find "places" in the query. Named Entity Recognition is a natural language processing (NLP) problem where the goal is to identify certain entities (like people, places, and things) in a sequence of text. If we can detect the words in a search query that are locations, we can cross-reference with a location database to convert words into places on a map. Generally, this database will then be used in the resolution step which is next.
The next step is resolution, turning the string "Green Bay" into a lat/lng (Geocoding). This task is much harder than you might first think because we don't exactly know which "Green Bay" they are referring to.
On Mapbox, if you search for Green Bay, you will find 5 places that exactly match "Green Bay". So which Green Bay is the best option? Here are the different pieces you will want to factor in to this part of the algorithm:
Once you've identified the right "Green Bay", you will want to geocode that term and turn it into a lat/lng. In this scenario, the user is searching from Wisconsin, so we are confident they mean Green Bay, Wisconsin and can geocode that location: 44.5133° N, 88.0133° W.
The final step is the easiest, but there are still a few important details. You will need to store a lat/lng associated with each object in the database and then have a system that can easily and quickly filter to a set of objects based on lat/lng. There are two general approaches to Geosearch:
In this scenario, a point + radius probably makes more sense. Green Bay has an area of 50 mi2. This means the radius of Green Bay is roughly ~ 4 miles. We will double it to also include locations in the nearby region so we will use a radius of 8 miles to run a geosearch.
Using a combination of the lat/lng and a radius of 8 miles, we can turn this into a set of objects from the database. We will also filter the set of results to only show "cardiologists" and will sort the results based on their proximity to the center of Green Bay.
Notary near me is another type of search query with location intent. In this case, the user didn't explicitly specify a location (like "near Green Bay") but instead wants the search engine to find notaries near the user. Named Entity Recognition is the best way to identify "near me" intent. In theory, you could start with a hardcoded list of strings "near me", "around me", etc. but that only scales so far.
Resolution in this case looks very different from the previous search term. Instead of geocoding a place, we need to identify where the user is located. There are two ways this is generally accomplished:
Your search engine should automatically prefer device location, but if it doesn't have it, you should use IP-Geolocation as a fallback (it's better than nothing!).
With a "near me" search, only Point + Radius makes sense. In this case we don't have a place (like Green Bay) to inform the radius so you might want to use a hardcoded limit or you might want to set no radius. Either way, you will want to sort objects to show the ones nearest to the user first. This step looks pretty much the same as in the previous example.
This type of query is interesting because there is no actual local intent in the search term. However, if you search Restaurants open now in Google from the Yext Office in New York City, here are the results you get:
You'll notice that even though the user didn't signal "near me" intent, Google is treating this as a "near me"search. That's because lat/lng is so critical to Restaurants, when in doubt, you will want to filter to locations nearby. The best way to handle this is to think about the underlying data. For restaurants, physical location is critical. For something like events, physical location maybe isn't as important (e.g. online events), so you might not want to apply this filter automatically.
In this example, we'll assume "near me" intent since the user is looking for restaurants. In this case, the resolution looks pretty similar to the previous example - we should use device location or IP geolocation to determine a lat/lng.
For the geosearch, you probably don't want to do any explicit filtering since the user didn't explicitly specify "near me". In this case, we could set an infinite radius, but still rank the locations by the ones closest to the user. You could also explore other thresholding techniques in which you pick a radius based on the underlying data set, and then sort based on reviews or another indicator of relevance.
Yext Answers handles location search right out of the box. For the search algorithm, Yext Answers implements the following important steps:
For identification, Yext Answers uses a proprietary named entity recognition (NER) model based on a deep neural network called BERT. BERT (Bidirectional Encoder Representations from Transformers) was open sourced by Google in 2018. BERT combined several recent big advances in neural networks for NLP that dramatically improved performance on tasks like NER. Even better, BERT can be fine-tuned for specific applications to get the "flavor" of the vocabulary and usage of certain words in the right context. This is super important for Yext Answers, where every customer is special, and words usage can vary so much context. So, Yext Answers fine tunes a BERT model using labeled search terms makes predictions for every word in every search term. Since every set of search terms can be unique and never seen before. This means by leveraging the Yext Answers product, you get state of the art natural language understanding without any of the headache. To learn more about how Yext Answers leverages BERT, check out this deep dive.
Yext Answers uses the population of the place, distance to the user, the underlying customer's Knowledge Graph and any typo tolerance to determine the most relevant lat/lng. It then dynamically picks a radius depending on the place. To handle the geocoding of places, Yext works with Mapbox which is built on top of the Open Street Maps database.
To identify where the user is located, Yext Answers uses a combination of IP geolocation and HTML5 geolocation, depending what's available.
Every entity that gets added to the Knowledge Graph is automatically geocoded. Answers sits on top of the structured Knowledge Graph, and can find entities around a lat/lng extremely quickly.