Evaluating search engine relevance

This is the story of some work I did for an employer over a decade ago, although I think it is still very applicable today. I always meant to try to get some of the code released, but now much of it would be considered outdated, so I’m sharing the core of the algorithm.

Suppose you have your own search engine and you want to know if it is producing good results. How can you tell?

You can get the most popular search queries, manually judge what the best result is, and measure how well those best results rank for those queries. But in a broad search engine, this will be a negligible portion of overall queries and may not be representative. Not to mention that others may not make the same judgments as you did. Similarly, if you are a giant search company like Google, you can hire a lot of people to constantly judge search results.

But if you are smaller than that, what can you do? I won’t get deep into other methods, but I will share what I did. I think it worked very well.

I did find out later on that there had been an earlier effort to compare our results to Google’s results (limited to our website), with the assumption being that Google’s results were “correct” and the better ours matched Google’s, the better the relevance, but I wasn’t a fan of that idea. Nevermind that Google doesn’t want people scraping their results.

The algorithm

Basically, this method looks at what users do with search results. It is a backwards-looking metric. In other words, you can evaluate the relevance of the live search engine on your website, but it doesn’t really* enable you to predict how a proposed change will affect relevance. What you can do is launch the change, wait a few days (well, this will vary depending on search engine use, but for us it was a few days), and then see the results. If the results are good, keep the change, and if they are bad, roll it back. After-the-fact data is a lot better than no data.

I was aware of how the old Direct Hit search engine had pioneered the practice of tracking what results users click on and putting those pages higher the next time the same query was done, but my effort was focused more on measuring than affecting.

The formula evolved a bit over time but this is what it ended up like. It used three types of data for every query:

• how many search results were clicked on
• the position of those results (1 being the first result)
• how often another search was run immediately

var irrelevance = 1;
if (resultClicksTotal > 0) {
  var differenceFromSingleClick = 1 - ( resultClicksPerSearch <= 1 ? resultClicksPerSearch : (1/resultClicksPerSearch) );
  var positionFactor = Math.min(Math.log(averagePosition), 1);
  irrelevance =
    (differenceFromSingleClick * 0.46) +
    (Math.min(refinementsPerSearch, 1) * 0.3) +
    (positionFactor * 0.24);
}Code language: JavaScript (javascript)

Going through each part,

• irrelevance will be 0 (perfect relevance) to 1 (completely irrelevant)
  • when displaying this, the number will get converted to relevance, i.e. 1 - irrelevance
• resultClicksTotal is how many times a search result was clicked on for the given query
• if no results were clicked on, that counts as completely irrelevant, so we default to a value of 1 before checking
• if any results were clicked on, then irrelevance is based on three factors: difference from a single click, how often users did another search, and what position the clicked-on results were at
  • these are the weightings I found worked well for the three factors: 0.46, 0.3, and 0.24 (which sum to 1)
• difference from a single click is used, because clicking on exactly one result can be assumed to mean the user got what they wanted on the first try (very relevant), whereas clicking on a lot of results means they struggled to find it (irrelevant), as does clicking on very few results (less than one per search)
• the position factor uses a log function, to roughy account for how users actually click on results by position; I just looked this up now and you can see some example data here for comparison
• users doing another search is assumed to mean that they didn’t find what they wanted with their initial query (refinement = new search)

To summarize: if for a given search query, nobody ever clicks on any results, then it is completely irrelevant (1), whereas for another query that everyone clicked on exactly one result, and that result was in the first position, it has perfect relevance (0 irrelevance). Anything else is somewhere in between.

All of this is for a single search query. For each query, I also calculated an irrelevance value weighted to how important the query was, by multiplying it by what percentage of searches were for that query:

irrelevanceWeighted = irrelevance * viewsPercentageCode language: JavaScript (javascript)

Lastly, overall relevance (well, irrelevance) for the whole search engine is calculated by summing all the weighted irrelevance values.

Putting this into practice,

• a cron job every day to (1) download all the analytics data from the previous day of what searches were done and what results were clicked on and (2) calculate irrelevance for each query and overall
  • this included some normalization, like trimming the queries and converting everything to lowercase
  • the analytics data also included what page the searches were being done from, as that was used for other purposes
  • irrelelevance was calculated for the day as well as for the past 7 days (rolling)
• a second cron job run monthly

Using the data

I built a pretty robust dashboard for making use of all this data. The main page showed a sparkline-like bar graph of search volume, and a table with the top 200 queries, beginning with a summary row. The column showing relevance values had its background coloured to match the number, i.e. completely red = very irrelevant and completely green = very relevant (conditional formatting in Excel-speak), making it easy to quickly see how queries were performing.

The list could be resorted ascending or descending by relevance (weighted or not) or other values, and the whole list could be filtered by regex, which would update the sparkline as well.

Clicking on each query would add in details showing what pages the query was run from and what new searches were run instead.

In practice I found this extremely useful. One could detect if relevance or search volume was changing overall or for particular sets of queries, and the tool also helped to answer the question of “why” something was changing or had poor relevance. I ended up keeping a list of regular expressions to look at various types of queries and various topics.

Once a front-end encoding bug meant that anything you searched for yielded zero search results. This tool, which showed a drastic and sudden drop in relevance was how we found out… it’s not as if our users were going to be writing in to us about it.

By sorting by weighted relevance, you could see the queries most in need of improvement and target those. One thing that people were looking for often resulted in a page that had the correct information but it wasn’t explicit in the title and the content wasn’t at the top of the page. Some reworking of the content on that one page alone resulted in a measurable improvement to overall relevance. In another case, people were looking for a topic that we had content for, but not a single high-level page that linked to the specific pages, something that was easy to rectify.

Obviously fixing individual queries and groups of queries can only take you so far, but the tool also made it easy to see overall effects of changes to the ranking algorithm.

The tool also had a second view listing pages rather than queries. With this lens, pages with lots of queries could be assumed to need more content improvement. Just like with queries, a weighting factor would enable sorting to see the pages most in need of improvement. Anyone working on specific pages could easily use the data to see what people were looking for from that page as great evidence of what needed improving.

Final thoughts

* I noted earlier that this method can’t be used for prediction, but that’s not completely true. Although I never built any such functionality, one could use it to see whether the ranking of results better matched the frequency that those results were clicked. For example, if users clicked more on result #2, and less on result #1, and an algorithm change would cause the order of those two to swap, it’s a safe assumption that it is an improvement for that particular query. There are other possibilities as well… for queries that resulted in no result clicks at all, one could determine which of those was caused by there simply being no search results… and if an algorithm update meant more no-results queries got results, one could assume that would be an improvement.

Anyhow, that’s pretty much it. If you’ve done something similar or try this algorithm out, feel free to share. I’m haven’t worked on this in some time but you’re still welcome to share any improvements you make to it or note if different weightings for the 3 factors make more sense for your own use case.