Improving Local Search using Query Categorization based off a Web Search Engine
(This post is about our experiences at Kosmix during 2005 to 2007)
One of the key vertical search experiences has always been local search- in fact, back during early 2000s, local search was powered separately from a web search- the output of a web search engine were web pages (ten blue links) while the output of a local search was a set of local businesses relevant to a query. Users had to decide apriori if they wanted local businesses as a result and go to a local search engine (or a tab) and type their query.
The typical local search engines used to search in the local business corpus which consisted of business information and the category of the business (such as plumbers, locksmiths, etc.)- at best, in addition they used to search the web pages corresponding to the website of the business if a website was available. We started noticing the query log of local search and found that the user queries many times did not name the business category (plumbers) or the name of the business (AJ plumbing company) most of the time- local search engines were optimized for users expressing categories or names of the business. Instead, we found that many users expressed the symptoms they were experiencing such as backed up toilet, locked out of car etc.
The “aha” moment for us at that time was realizing that we actually needed to categorize the local query being issued into one of the local service categories and use that as the most important signal to retrieve the results. In fact, in many cases that was the only signal (apart from the user location of course) that we used in retrieving the results and this was a “wow” experience those days- no other search engine was providing this experience at that time.
In the rest of the post, I want to focus on how we did this query categorization those days (today we would use Deep Learning based models and I will come to that in a later post- we did do that successfully for ecommerce search much later in 2017). The state of the art in classifying text at that time was using Naive Bayes or SVMs and we did not think classifying queries with few words would work very well and provide the accuracy we needed- we felt constrained by the finite set of words or vocabulary that was going to be part of the model.
We hit upon an interesting observation- we had a good document classifier already based off the web graph structure as well as text models (a document is a much larger sequence of words and the precision of a document classifier was much more acceptable). Our observation was we could just use a web search engine (not the local search engine) and combine the score of a document D for a query with the category score of the top category (say C) for D to contribute to the query categorization score for category C. We could thus find the category that had the maximum score for the query to conclude the topmost category corresponding to the query. Thus, in effect we could use the web search engine to conclude something interesting about the query which we could then later use to improve the local search. Note, that by using a web search engine we were automatically getting the benefit of many things like proximity scoring which automatically factored in how well the order of the terms in the query matched the order of the terms in the document.
Our first implementation of the above idea was to just use the top “N” documents and then look up the category score of the top category for those top “N” documents- the default way we looked up information about a document was to do a quick key value lookup of the document store- for the 10 billion URLs we had indexed this info would be on disk and this would require N random disk accesses and to have a response time of hundreds of milliseconds N would have to be small (in the tens or hundreds). This would miss out on any long tail effects there may be and could make egregious errors.
Our next implementation was realizing that we really needed to store signals (category scores in this case) for documents in a highly compressed fashion in memory. We needed to use these signals while we were scoring and ranking documents for web search to simultaneously compute the query categorization scores. This infrastructure was fundamental to everything we built at Kosmix and this notion of storing signals in a columnar fashion (conceptually an array indexed by document id) in memory and embedding these signals deep into ranking was critical for many other applications- we will come back to this in later posts.
In summary, there were the following “aha” moments:
- We realized many local search queries would not match the inverted index for any local business e.g., backed up toilet. Using a web search engine to understand the category of the local business was a very dynamic and automatic way of adapting to changes in documents (no retraining etc.) and adapting to new queries etc. This notion can be applied in many other contexts where we are searching a limited corpus (relative to the web) — e-commerce or product search is another example.
- Implementing query categorization using a web search engine required a non-trivial infrastructure (as mentioned before Lucene did not have the required performance but more importantly at that time did not have this functionality of storing signals in memory and using it while ranking) which was the basis for many other applications.