Tag Archives: bing search

Snippets: The unsung heroes of web search

2 Replies

Remember when Google launched into our consciousness? Below you’ll see what you probably saw back in 1999: a clean, simple results page with ten blue links.

Google search results, circa 1999

Google was a marked contrast to the other search engines of the era: AltaVista, Excite, Lycos, Looksmart, Inktomi, Yahoo!, Northern Light, and others.

What was different about Google? Most people talked about three things:

  1. PageRank, the use of the web’s link structure in search ranking. The perception was that Google found more relevant results than its competitors. Here’s the original paper
  2. Its clean page design. It wasn’t a link farm, there was plenty of white space, and an absence of advertising (banner or otherwise) for the first couple of years
  3. Its speed and its collection size. Google felt faster, reported fast search times, claimed a large index (remember when they used to say how many documents they had on the home page?), and showed large result set counts for your queries (result set estimation is a fun game – I should write a blog post about it)

What struck me most was the way Google presented result summaries on the search results page. Google’s result summaries were contextual: they were constructed of fragments of the documents that matched the query, with the query words highlighted. This was a huge step forward from what the others were doing: they were mostly just showing the first hundred or more characters of the document (which often was a mess of HTML, JavaScript, and other rubbish). With Google, you could suddenly tell if the result was relevant to you — and it made Google’s results page look incredibly relevant compared to its competitors.

And that’s what this blog post is about: contextual result summaries in search, snippets.

Snippets

Snippets are the summaries on the search results page. There’s typically ten of them per results page. Take a look at the result below from the Google search engine, it’s one of the ten snippets for the query gold base bobblehead.

A Google Snippet

The snippet is designed to help you make a decision: is this relevant or not to my information need? It helps you decide whether or not to invest a click. It’s important — it’s key to our impression of whether or not a search engine works well. The snippets are the bulk of the results page, they’re displayed below the brand of the search engine, and together they represent what the search engine found in response to your query. If they’re irrelevant, your impression of the search engine is negative; and that’s regardless of whether or not the underlying pages are relevant or not.

The snippet has three basic components:

  1. The title of the web document, usually what’s in the HTML <title> tag. In this case, “Vintage Baseball Memorabilia Bobble Heads Gold Base“
  2. A representation of the URL of the web resource, which you can click on to visit the document on the web. In this case, “keymancollectibles.com/bobbleheads/goldbasenod.htm”
  3. (Usually) a query biased summary. One, two, or three fragments extracted from the document that are contextually relevant to the query. In this case, “The Gold base series of Bobbing Heads was the last one issued in the 60’s. They were sold from 1966 through 1971. This series saw the movement of several …”
Some words in the title, URL, and query biased summary are shown in bold. They’re the query words that the user typed (in this case, the query was “gold base bobblehead“) or variants of the query words, such as plurals, synonyms, or acronym expansions or contractions. (My recent post on query rewriting introduces how variants are discovered and used.) The idea here is that highlighting the query terms helps the user identify the likely relevant pieces of the snippet, and quickly make a decision about the relevance of the web resource to their need.

I’m going to come back to discussing query biased summaries, and how the fragments of text are found and ranked. But, before I do, let’s quickly cover what’s been happening in snippets over the past few years.

What’s happening in the world of snippets

All search engines show quicklinks or deeplinks for navigational queries. Navigational queries are those that are posed by users when they want to visit a specific location on the web, such as Google, Microsoft, or eBay. Take a look at the snippet below from Bing for the query nordstrom. What you can see below the snippet are links that lead to common pages on the nordstrom.com site including “Men”, “Baby & Kids”, and so on; these are what’s known in the industry as quicklinks or deeplinks.  When I was managing the snippets engineering team at Bing, we worked on enhancing snippets for navigational queries to show phone numbers, related sites, and other relevant data. The example for the query nordstrom shows the phone number and a search box for searching only the nordstrom.com site.

Nordstrom navigational query snippet from Bing

At Bing, we also invented customizing snippets for particular sites or classes of sites — for example, below is  a snippet that’s customized for a forum site. You can see that it highlights the number of posts, author, view count, and publication date separately from the query biased summary.

Custom snippet for a forum site from Bing

While Bing pioneered it, Google has certainly got in on the game — I’ve included below a few different Google examples for snippets from LinkedIn, Google Play, Google Scholar, and Fox Sports.

Custom Google snippets for LinkedIn, Google Scholar, Google Play, and Fox Sports

What’s all this innovation for? It’s to help users make better decisions about whether or not to click, and to occasionally give extra links to click on. For the Fox Sports snippet, it’s showing the top three headlines from the site — and that’s perhaps what the user wants when they query for Fox Sports (they don’t really want to go to the home page, they want to read a top story). For the Google Play and Scholar snippets, there’s information in the snippet that informs us whether the results is authoritative: has it been cited by other papers many times? Has it been voted on many times? The LinkedIn result is extracting key information and presenting it separately: the city that the person live in and who they work for, and it’s also including some data from Google+.

In my opinion, snippets are becoming too heterogeneous, the search engines are going too far. Users find it hard to switch from processing pictures to reading text, and they’re becoming too intermingled to allow users to quickly scan results pages. The snippets have too many different formats: users have to pause, understand what template they’re looking at, digest the information, and make a decision. The text justification is getting shaky. Life was simpler and faster when snippets were more consistent. I am sure the major search engines would argue that users are making better decisions (for example, I bet they’re seeing on lower mean average times from when the user types a query to when they invest their click). But I think the aesthetics are getting lost, and it’s getting a little too much for most users.

Query-Biased Summaries

Google didn’t invent query-biased summaries, Tassos Tombros and Mark Sanderson invented them in this 1998 paper.

The basic method for producing query-biased summary goes like this:

  1. Process the user’s query using the search index, and get a list of web resources that match (typically ten of them, and typically web [HTML] pages)
  2. For each document that matches:
    1. Find the location of the document in the collection
    2. Seek and read the document into memory
    3. Process the document sequentially and:
      1. Extract all fragments that contain one or more query words (or related terms — you get these from the query rewriting service)
      2. Assign a score to each fragment that approximates its likely relevance to the query
      3. Find the best few fragments based on the best few scores (one, two, or three)
    4. Neaten up the best fragments so they make sense (try and make them begin and end nicely on sentence boundaries or other sensible punctuation)
    5. Stitch the fragments together into one string of text, and save this somewhere
  3. Show the query-biased summaries to the user
I’ve spoken to engineers from the major search companies, and it’s pretty clear that producing snippets is one of the computationally most challenging problems they face. You only execute one query per user request, but you’ve got to produce ten summaries per results page. And unlike the search process, there’s no inverted index structure to help locate the terms in the documents. There are a few tricks that help:
  • Don’t process the entire document. In general, the fragments that are the best summaries are nearer the start of the documents, and so there’s diminishing returns in processing the entirety of large documents. It’s also possible to reorganize the document, by selecting fragments that are very likely to appear in snippets, and putting them together at the start of the document
  • Cache the popular results. Save the query-biased summary after it’s computed, and reuse it when the same query and document pair is requested again
  • Cache documents in memory. It’s been shown that caching just 1% of the documents in memory saves more than 75% of the disk seeks (which turn out to be a major bottleneck)
  • Compress the documents so they’re fast to retrieve from disk. Better still, compress the query words, and compare them directly to the compressed document. This is the subject of a paper I wrote with Dave Hawking, Andrew Turpin, and Yohannes Tsegay a few years ago. We showed that this makes producing snippets around twice as fast as without compression

Most search folks don’t think about the ranking techniques that are used in the snippet generator. The big ranking teams at major search companies focus on matching queries to documents. But the snippet generator does do interesting ranking: its task is to figure out the best fragments in the document that should be shown to the user, from all of the matching fragments in the document. Tombros and Sanderson discuss this briefly: they scored sentences using the square of the number of query words in the sentence divided by the number of query words in the query. Net, the more query words in the fragment, the better. I’d recommend adding a factor that gives more weight to fragments that are closer to the beginning of the document. There are also other things to consider: does the fragment make sense (is it a complete sentence)? Which of the query words are most important, and are those in the fragment? Do the set of fragments we’re showing cover the set of query terms? You could even consider how the set of query-biased summaries give an overall summary of the topic. I’m sure there’s lots of interesting ideas to try here.

Snippets have always fascinated me, and I believe their role in search is critical to users, unsung, and important to building a great search engine.

Hope you enjoyed this post — if you did, please share it with your friends through your favorite social network. There’ll be a new post next Monday…

Ideas and Invention (and the story of Bing’s Image Search)

23 Replies

I was recently told that I am an ideas guy. Probably the best compliment I’ve received. It got me thinking, and I thought I’d share a story.

With two remarkable people, Nick Craswell and Julie Farago, I invented infinite scroll in MSN Search’s image search in 2005. Use Bing’s image search, you’ll see that there’s only one page of results – you can scroll and more images are loaded, unlike web search where you have to click on a pagination control to get to page two. Google released infinite scroll a couple of years ago in their image search, and Facebook, Twitter, and others use a similar infinite approach. Image search at Bing was the first to do this.

MSN Search's original image search with infinite scroll

How’d this idea come about? Most good ideas are small, obvious increments based on studying data, not lightning-bolt moments that are abstracted from the current reality. In this case, we began by studying data from image search engines, back when all image search engines had a pagination control and roughly twenty images per page.

Over a pizza lunch, Nick, Julie, and I spent time digging in user sessions from users who’d used web and image search. We learnt a couple of things in a few hours. At least, I recall a couple of things – somewhere along the way we invented a thumbnail slider, a cool hover-over feature, and a few other things. But I don’t think that was over pizza.

Back to the story. The first thing we learnt was that users paginate in image search.  A lot. In web search, you’ll typically see that for around 75% of queries, users stay on page one of the results; they don’t like pagination. In image search, it’s the opposite: 43% of queries stay on page 1 and it takes until page 8 to hit the 75% threshold.

Second, we learnt that users inspect large numbers of images before they click on a result. Nick remembers finding a session where a user went to page twenty-something before clicking on an image of a chocolate cake. That was a pretty wow moment – you don’t see that patience in web search (though, as it turns out, we do see it at eBay).

If you were there, having pizza with us, perhaps you would have invented infinite scroll. It’s an obvious step forward when you know that users are suffering through clicking on pagination for the bulk of their queries, and that they want to consume many images before they click. Well, perhaps the simplest invention would have been more than 20 images per page (say, 100 images per page) – but it’s a logical small leap from there to “infinity”. (While we called it “infinite scroll”, the limit was 1,000 images before you hit the bottom.) It was later publicly known as “smart scroll”.

To get from the inspiration to the implementation, we went through many incarnations of scroll bars, and ways to help users understand where they were in the results set (that’s the problem with infinite scroll – infinity is hard to navigate). In the end, the scroll bar was rather unremarkable looking – but watch what it does as you aggressively scroll down. It’s intuitive but it isn’t obvious that’s how the scroll bar should have worked based on the original idea.

This idea is an incremental one. Like many others, it was created through understanding the customer through data, figuring out what problem the customers are trying to solve, and having a simple idea that helps. It’s also about being able to let go of ideas that don’t work or clutter the experience – my advice is don’t hang onto a boat anchor for too long. (We had an idea of a kind of scratchpad where users could save their images. It was later dropped from the product.)

The Live Search scratchpad. No longer in Bing's Image Search

I’m still an ideas guy. That’s what fires me up. By the way, Nick’s still at Microsoft. Julie’s at Google. And I am at eBay.

(Here’s the patent document, and here’s a presentation I made about image search during my time at Microsoft. All of the details in this blog post are taken from the presentation or patent document.)