Danny Sullivan on Microsoft search

Danny Sullivan has a couple great posts ([1] [2]) on Microsoft renaming its search engine to Bing, the new features and improvements in relevance coming along with the launch, and what it might mean for Google and Yahoo.

Danny is wise in the ways of search. His words are well worth reading.

Update: To be clear, just because I think Danny's posts are well worth reading doesn't mean I agree with him on everything. In fact, quite the opposite, I usually find the most interesting articles to be the ones that make a convincing argument on something with which I disagree.

One particular point of disagreement I have with Danny is on whether Microsoft's Bing needs to be different or better than Google to succeed. Many, including Danny, have said that being good enough isn't enough because of the power of Google's brand. I'm not sure that's true.

Until now, we haven't been able to tell who is right since Microsoft's search has been noticeably weaker than Google's. But, as Rafe Needleman noted, as did Danny, the name change to Bing comes with substantial improvements to relevance.

So, I think we're about to get the first real test of whether being about as good as Google is enough to see people using Microsoft's search engine.

Update: A week later, Danny Sullivan has a Q&A with Nick Eaton. Interesting how low Danny sets the bar for success for Microsoft's Bing, saying, "They're roughly at 10 percent [market share], I think that they could count themselves really successful if they got themselves to 15 or 20."

Update: Three weeks later, an article in the NY Post claims, "Co-founder Sergey Brin is so rattled by the launch of Microsoft's rival search engine that he has assembled a team of top engineers to work on urgent upgrades to his Web service." Frankly, I find that a little hard to believe, at least as phrased. Seeing as Microsoft is getting closer, I would expect Googlers are redoubling their efforts to stay ahead in core search, but I doubt that Sergey, Larry, or Eric are deeply rattled by some new competition.

Google Suggest and the right ad

In "Google Kills a Sacred Cow", Anders Bylund at the Motley Fool has an interesting take on Google's decision to show advertising in their search suggestion feature.

An excerpt:

You know how you get suggestions on ... the query you're typing into a Googlish search box? That suggestion list just became context-sensitive, more personalized, and more likely to send you to your destination without ever seeing a page of search results.

Oh, and you'll see advertising in that box, too. If you never see a results page, you might still send revenue Big G's way.

Yahoo recently promised to kill the typical "10 blue links" results in favor of more dynamic presentations. Google immediately took that idea one step further and did away with results altogether for many searches.

While Yahoo, Microsoft's MSN/Live/Kumo/whatever, Time Warner's AOL, and IAC/InterActiveCorp's Ask.com depend on exposing users to as many ads as possible by keeping them on their sites, Google is going the other way. All it takes is one ad -- the right ad in the right place -- and Google's cash flow is secure.

All it takes is one ad, the right ad in the right place.

Long ago, when I was at Amazon working on personalization, we used to joke that the ideal Amazon site would not show a search box, navigation links, or lists of things you could buy. Instead, it would just display a giant picture of one book, the next book you want to buy.

When you overwhelm people with choices, the important becomes lost in the mediocrity. Showing as many ads as possible just encourages ad fatigue. The focus of web advertising should be on getting the right ad in the right place. The focus should be on relevance.

The datacenter is the new mainframe

For a while, I have been planning on writing a post comparing large scale clusters with the mainframes of yore, a piece that would be full of colorful references to timesharing, scheduling and renting compute resources, and other tales that would date me as the fossil that I am.

Fortunately, Googlers Luiz Andre Barroso and Urs Holzle recently wrote a fantastic long paper, "The Datacenter as a Computer" (PDF), that not only spares me from this task, but covers it with much more data and insight than I ever could.

Some excerpts:

New large datacenters ... cannot be viewed simply as a collection of co-located servers. Large portions of the hardware and software resources in [our] facilities must work in concert to efficiently deliver good levels of Internet service performance, something that can only be achieved by a holistic approach to their design and deployment.

In other words, we must treat the datacenter itself as one massive warehouse-scale computer (WSC).

Much like an operating system layer is needed to manage resources and provide basic services in a single computer, a system composed of thousands of computers, networking, and storage also requires a layer of software that provides an analogous functionality at this larger scale.

[For example] resource management ... controls the mapping of user tasks to hardware resources, enforces priorities and quotas, and provides basic task management services. Nearly every large-scale distributed application needs ... reliable distributed storage, message passing, and cluster-level synchronization.

The paper goes on to describe the challenges of making an entire datacenter behave like it is one large compute resource to applications and programmers, including discussing the existing application frameworks and need for further tools.

Do not miss Figure 1.3 that shows latency, bandwidth, and capacity to resources in the data center. It includes an insightful look at latency to local and remote memory and the equivalent latencies but drastically different capacities of local and remote disk for programs running in the cluster. As the authors say, a key challenge is to expose these differences when they matter and hide them when they don't.

There are also thought-provoking tidbits on minimizing interference between jobs on the cluster and maximizing utilization, two goals that often are at odds with each other.

Much of the rest of the paper covers the cost and efficiency issues of data centers more generally, nicely and concisely summarizing much of the recent publicly known work on power, cooling, and infrastructure.

One small thing it does not mention is the ability to rent resources (e.g. EC2) on a WSC, much like buying time on the old mainframes, and the impact that could have on utilization, especially once we allow variable pricing and priorities.

[Google paper found via James Hamilton]

Update: A couple weeks later, security guru Bruce Schneier writes, "Cloud computing is nothing new. It's the modern version of the timesharing model from the 1960s."

Update: Seven months later, Amazon launches variable pricing for low priority jobs on EC2.

The potential of behavioral targeted advertising

An important WWW 2009 paper out of MSR Asia, "How much can Behavioral Targeting Help Online Advertising?" (PDF), looks at how much value we can get from targeting ads to past behavior. It is a must read for anyone interested in personalized advertising.

Some excerpts:

To our best knowledge, this work is the first systematic study for [behavioral targeting] (BT) on real world ad click-through [logs].

[We] empirically answer ... whether BT truly as the ability to help online advertising ... how much BT can help ... [and] which BT strategy can work better than others.

We observe that the users who clicked the same ad can be over 90 times more similar than the users who clicked different ads .... [which verifies] the basic assumption of BT.

We observe that .... the ads CTR can be improved as high as 670% by the simple user segmentation strategies used for behavioral targeted advertising .... [More] advanced user representation and user segmentation algorithms [yielded improvements of] more than 1,000%.

Through comparing different user representation strategies for BT, we draw the conclusion that user search behavior, i.e. user search queries, can perform several times better than user browsing behavior, i.e. user clicked pages. Moreover, only tracking the short term user behaviors are more effective than tracking the long term user behaviors.

One issue with the study is that it looks only at coarse-grained user segments, at most 160 segments, not fine-grained, one-to-one, personalized advertising. I would suspect there would be added benefit from fine-grained, personalized targeting to past behavior rather than clustering users into large groups. In fact, as Figure 5 in the paper shows, they do not appear to have hit the point of diminishing returns even on splitting into more segments.

Another issue is that they explicitly did not look at using demographic data or locality. It is possible that many of the BT user segments might be grouped roughly by locality, having derived it from search or browsing behavior. If that is true, then much of the gains they saw from BT could be reaped much more easily by targeting the ads to implicit local information. And, if we target to locality, then the additional gains we could expect from behavior targeting then might be much smaller.

But, limitations aside, it is a great paper. The authors clearly and cleanly state their key question -- what is the value of behavioral targeting for advertising? -- and then analyzes a massive historical log to convincingly derive the likely value. It also provides much guidance for those who might seek to build these or similar systems.

The paper has an interesting conclusion that recent search queries are the most useful indicators of people's interests when targeting ads. Yahoo's Andrei Broder said something similar recently when thinking about targeting advertising. It is also worth noting that others who were looking at the value of personalized search came to similar conclusions ([1] [2]).

For more on fine-grained personalized advertising, please see my earlier posts, "What to advertise when there is no commercial intent?" and "A brief history of Findory".

Exploiting spammers to make computers smarter

Googlers Rich Gossweiler, Maryam Kamvar, and Shumeet Baluja had a fun paper at WWW 2009, "What's Up CAPTCHA? A CAPTCHA Based On Image Orientation" (PDF), that asks people to rotate images correctly to prove they are human rather than the norm of deciphering distorted text.

Some brief excerpts from their paper:

We present a novel CAPTCHA which requires users to adjust randomly rotated images to their upright orientation ... Rotating images to their upright orientation is a difficult task for computers .... [Our] system ... results in a 84% human success rate and .009% bot success rate.

The main advantages of our CAPTCHA technique over traditional text recognition techniques are that it is language-independent, does not require text-entry (e.g. for mobile devices), and employs another domain for CAPTCHA generation beyond character obfuscation.

The paper goes on to say that "no algorithm has yet been developed to successfully rotate the set of images used in our CAPTCHA system." The key word there is "yet." As soon as there is a strong incentive for people to develop better algorithms for this problem, better algorithms will be developed.

But, as Luis von Ahn insightfully pointed out in a recent interview in New Scientist, it is a perfectly fine outcome if spammers find a way to break this new image-based CAPTCHA technique. By doing so, they are helping us make computers smarter.

From the New Scientist article:

"If [the spammers] are really able to write a programme to read distorted text, great – they have solved an AI problem," says von Ahn. The criminal underworld has created a kind of X prize for OCR.

Security groups ... [then] can ... switch for an alternative CAPTCHA system -- based on images, for example -- presenting the eager spamming community with a new AI problem to crack ... Image orientation is difficult for computers. But if [image-based] CAPTCHA becomes common, it won't be long before spammers turn their attention to cracking the problem, with potential fringe benefits to cameras and image editing software.

Speech recognition CAPTCHAs are already being used, and image labelling ones could follow, says von Ahn. AI researchers are already working in both these areas, but they could soon be joined by spammers also helping advance the technology.

Perhaps it is time to start designing CAPTCHAs in a different way -- pick problems that need solving and make them into targets to be solved by resourceful criminals.

More Microsoft layoffs

It is being widely reported ([1] [2] [3] [4] [5]) that Microsoft did another large round of layoffs today.

Microsoft never has done layoffs on this scale. It is a difficult thing to do well. For more on that, please see my earlier post, "Layoffs and tech layoffs".

Leaving Microsoft

With the dissolution of much of Live Labs, I have decided to resign from Microsoft. I will be leaving at the end of April.

Working at Microsoft on search and advertising turned out to be a lot of fun. High impact, useful, and interesting problems are everywhere.

For example, during my time there, I had a chance to work a bit on advertising relevance (for work with similar motivation, see [1] in Section 6.2 and [2]), search relevance (closest public example of something vaguely similar might be [1]), improving the quality of human judgments (vaguely similar to the ideas published in [1] and [2]), looking at new evaluation methods for search (motivated by [1]), ubiquitous online experimentation (same goals as ExP), personalized web search (like Findory and motivated by [1] and [2]), personalized advertising (see [1]), and large scale data analyses (see [1]).

And, as fun as the problems were the people. I had a chance to talk with so many at Microsoft, from celebrated researchers to the hard-working talent pounding on the code. It was very enjoyable to work on such a breadth of problems and with so many different people. I did much, learned much, and I will miss it.

As for next steps, I will be taking some time before settling into anything new. I still hold the same passion for taming information overload, for personalizing the data streams of the Web to make them relevant, helpful, and useful. Whoever manages to change the nature of content display on the Web from a search problem to a recommender problem will reap tremendous rewards. I hope to play my part in that shift.

Google server and data center details

At the Efficient Data Center Summit, Google and others were discussing techniques to reduce energy consumption from massive clusters. In the process, the Googlers offered some very fun peeks into how they designed some of their servers and data centers.

For example, Chris Malone and Ben Jai offered a talk, "Insights Into Google's PUE", that, starting on slide 8, describes how Google uses single volt power and on-board uninterruptible power supply to raise efficiency at the motherboard from the norm of 65-85% to 99.99%. There is a picture of the board on slide 17.

Amazon's James Hamilton attended the conference and elaborated on this:

The server design Google showed was clearly a previous generation ... a 2005 board ... [but] was a very nice design.

The board is a 12volt only design ... 12V only supplies are simpler, distributing on-board the single voltage is simpler and more efficient, and distribution losses are lower.

The most innovative aspect of the board design is the use of a distributed UPS. Each board has a 12V VRLA battery that can keep the server running for 2 to 3 minutes during power failures. This is plenty of time to ride through the vast majority of power failures ... [and] it avoids the expensive [and less efficient] central UPS system.

The server was designed to be rapidly serviced with the power supply, disk drives, and battery all being Velcro attached and easy to change quickly.

Also fun is a video tour of one of Google's data centers. The video is short and worth watching for a look at how cooling and wiring is done these days as well as checking out how they used servers in shipping containers.

For more details, Amazon's James Hamilton has additional notes ([1] [2] [3]) and CNet's Stephen Shankland links to all the videos (including video of the talks at the summit).

Serendipity, diversity, and personalized search

Aside from the amusing double entendre in its title, a recent paper out of Microsoft Research, "From X-Rays to Silly Putty via Uranus: Serendipity and its Role in Web Search" (PDF), is notable for its take on two topics that seems to be attracting increasing attention lately, personalized search and improving the diversity of search results.

Some excerpts:

Partially-relevant search results, identified as "containing multiple concepts, [or] on target but too narrow," play an important role in a user's information seeking process and problem definition.

By studying Web search query logs and the results people judge relevant and interesting, we find many of the queries people perform return interesting (potentially serendipitous) results that are not directly relevant .... More than a fifth of all search results were judged interesting but not highly relevant to the search task.

Serendipity was more likely to occur in diverse result sets .... Personalization scores correlate with both relevance and also with interestingness, suggesting that information about personal interests and behaviour may be used to support serendipity.

So, the paper suggests that there may be multiple benefits to personalized search. Not only do we get the benefits of improved understanding of query intent and increased relevance, but also we can improve diversity and discovery.

For a discussion of yet another benefit, reducing the payoff to web spammers, please see also my July 2006 post, "Combating web spam with personalization".

MapReduce using Amazon's cluster and differential pricing

Amazon recently launched Elastic MapReduce, a web service that lets people run MapReduce jobs on Amazon's cluster.

Elastic MapReduce appears to handle almost all the details for you. You upload data to S3, then run a MapReduce job. All the work of firing up EC2 instances, getting Hadoop on them, getting the data out of S3, and putting the results back in S3 appears to be done for you. Pretty cool.

Even so, I have a big problem with this new service, the pricing. MapReduce jobs are batch jobs that could run at idle times on the cluster, but there appears to be no effort to run these during idle times nor is there any discount on the pricing. In fact, you actually pay a premium for MapReduce jobs above the cost of the EC2 instances used during the job.

It is a huge missed opportunity. Smoothing out peaks and troughs in cluster load improves efficiency. Using the idle time of machines in Amazon's EC2 cluster should be essentially free. The hardware and infrastructure costs are all sunk. In a non-peak time, only the marginal cost of the additional electricity used by a busy box over an idle box is a true cost.

What Amazon should be doing is offer a steep discount on EC2 pricing for interruptible batch jobs like MapReduce jobs, then only run those jobs in the idle capacity of non-peak times. This would allow Amazon to smooth the load on their cluster and improve utilization while passing on the savings to others.

For more on this topic, please see also my Jan 2007 post, "I want differential pricing for Amazon EC2".

Please see also Amazon VP James Hamilton's recent post, "Resource Consumption Shaping", which also talks about smoothing load on a cluster. Note that James argues that the marginal cost of making an idle box busy is near zero because of the way power and network use is billed (at the 95th percentile).

For some history on past efforts to run Hadoop on EC2, please see my Nov 2006 post, "Hadoop on Amazon EC2".

Update: Eight months later, Amazon launches differential pricing for EC2.

Semantic interpretation and the effectiveness of big data

Googlers Alon Halevy, Peter Norvig, and Fernando Pereira have an article, "The Unreasonable Effectiveness of Data" (PDF), in the April 2009 IEEE Intelligent Systems on semantic interpretation using big data.

Some excerpts:

The number of grammatical English sentences is theoretically infinite ... However, in practice we humans care to make only a finite number of distinctions. For many tasks, once we have a billion or so examples, we essentially have a closed set that represents (or at least approximates) what we need.

We're left with ... interpreting the content, which is mainly that of learning as much as possible about the context of the content to correctly disambiguate it .... What we need are methods to infer relationships between ... entities in the world. These inferences may be incorrect at times, but if they're done well enough we can connect disparate data collections and thereby substantially enhance our interaction with Web data.

Unlabeled data ... is so much more plentiful than labeled data ... With very large data sources, the data holds a lot of detail. For natural language applications, trust that human language has already evolved words for the important concepts. See how far you can go by tying together the words that are already there.

The article talks in more detail about work at Google and elsewhere on extracting relationships from massive crawls of text, tables, and the deep web.

On a related note, Google announced some new features a couple days ago, improved query suggestions and snippets, that Googler Ori Allon apparently described as scanning pages "in real-time ... after a query is entered" and identifying "conceptually and contextually related sites/pages" using "an 'understanding' of content and context." Many news articles are referring to this as a step toward semantic search.

Please see also my April 2008 post, "GoogleBot starts on the deep web", which discusses related work by Alon Halevy on mining data in tables and the deep web.

Please see also my post on the WSDM 2008 keynote by Oren Etzioni on semantic interpretation. His work is mentioned a few times by Halevy et al.

[IEEE article found via the Google Research Blog]

Startups and being relentlessly resourceful

Paul Graham wrote an insightful article, "Be Relentlessly Resourceful", that captures what I think is the most important characteristic for the founders of a startup. Some excerpts:

A couple days ago I finally got being a good startup founder down to two words: relentlessly resourceful.

Not merely relentless. That's not enough to make things go your way except in a few mostly uninteresting domains.

In any interesting domain, the difficulties will be novel. Which means you can't simply plow through them, because you don't know initially how hard they are; you don't know whether you're about to plow through a block of foam or granite. So you have to be resourceful. You have to have keep trying new things.

Be relentlessly resourceful.

Flickr is a great example of this. The company started as a massively multiplayer online game, failed at that, and morphed, in what appears to be pure grit and determination to succeed, into a photo sharing service.

More than any other characteristic, I think this is what to look for in the founding team of a startup, determination, flexibility, and willingness to do what it takes to succeed. As Paul says, be relentlessly resourceful.

Please see also Paul Graham's recent post, "Startups in 13 Sentences", that offers some other excellent advice for startups.

For a darker view on being relentlessly resourceful, please see my Nov 2006 post, "Ruthless enough for a startup?"

What is a good recommendation algorithm?

I have an article on the new Communications of the ACM blog, blog@CACM, titled "What is a good recommendation algorithm?"

The post picks on the root mean squared error (RMSE) measure used for evaluating recommender systems in the Netflix Prize, talks about precision and why making recommendations is like search, and discusses some factors that impact people's perception of the usefulness and quality of the recommendations that are not captured by RMSE.

If you have thoughts on evaluating recommender systems, please go to the article and comment there. I left many questions unanswered in that post and was hoping to get a bit of a discussion going over on that new CACM blog.

The blog@CACM is just getting started, but the list of contributors is quite impressive and includes Peter Norvig, Daniel Reed, Michael Stonebraker, and many others. If you like, you can get the feed here.

By the way, if you are an ACM member or just remember it fondly from school, you might also go check out the new CACM website. It's been recently redesigned to emphasize news articles on the front page and in its many new feeds.

[Full disclosure: I'm on the CACM web board.]

Google launches personalized advertising

Miguel Helft at the New York Times writes in "Google to Offer Ads Based on Interests" that "Google will begin showing ads on Wednesday to people based on their previous online activities in a form of advertising known as behavioral targeting."

Google will assign those users to categories based on the content of the pages they visit. For example, a user may be pegged as a potential car buyer, sports enthusiast or expectant mother.

Google will then use that information to show people ads that are relevant to their interests, regardless of what sites they are visiting. An expectant mother may see an ad about baby products not only on a parenting site but also, for example, on a sports or fashion site that uses AdSense or on YouTube, which is owned by Google.

Google said the approach could help advertisers reach their audiences more easily and publishers to earn more from their sites. Users will also see ads that are more relevant to their interests, the company said.

Google said that it planned to segment users along 20 categories and nearly 600 subcategories.

Barry Schwartz over at Search Engine Land, in an excellent and detailed review of the new product, writes:

I asked Google how detailed can these ads get? I asked, can an advertiser pass along a specific ad to a specific user? For example, can I show an ad for the Sony HDR-XR200V if this user added the Sony HDR-XR200V to their shopping cart on my site but did not check out?

[Brad] Bender [Google’s Product Manager] said yes, but ultimately it is up to the advertiser how specific they want to get with those ads.

The post on the Official Google Blog about this new product, "Making ads more interesting", is rather bland, but it does give a good description of the goal of personalized advertising:

By making ads more relevant ... we can create more value for everyone. Users get more useful ads, and these more relevant ads generate higher returns for advertisers and publishers.

Please see also my Oct 2008 post, "Google describes perfect advertising", which quotes an article by Googler Susan Wojcicki and gives more context to what Google is trying to do with personalized advertising.

Please see also my May 2004 post, "Bringing sense to web advertising", and my July 2007 post, "What to advertise when there is no commercial intent?"

Update: Philipp Lenssen posts the full list of category interests used by Google.

Jeff Dean keynote at WSDM 2009

Google Fellow Jeff Dean gave an excellent keynote talk at the recent WSDM 2009 conference that had tidbits on Google I had not heard before. Particularly impressive is Google's attention to detail on performance and their agility in deployment over the last decade.

Jeff gave several examples of how Google has grown from 1999 to 2009. They have x1000 the number of queries now. They have x1000 the processing power (# machines * speed of the machines). They went from query latency normally under 1000ms to normally under 200ms. And, they dropped the update latency by a factor of x10000, going from months to detect a changed web page and update their search results to just minutes.

The last of those is very impressive. Google now detects many web page changes nearly immediately, computes an approximation of the static rank of that page, and rolls out an index update. For many pages, search results now change within minutes of the page changing. There are several hard problems there -- frequency and importance of recrawling, fast approximations to PageRank, and an architecture that allows rapid updates to the index -- that they appear to have solved.

Their performance gains are also impressive, now serving pages in under 200ms. Jeff credited the vast majority of that to their switch to holding indexes completely in memory a few years back. While that now means that a thousand machines need to handle each query rather than just a couple dozen, Jeff said it is worth it to make searchers see search results nearly instantaneously.

The attention to detail at Google is remarkable. Jeff gleefully described the various index compression techniques they created and used over the years. He talked about how they finally settling on a format that grouped four delta of positions together in order to minimize the number of shift operations needed during decompression. Jeff said they paid attention to where their data was laid out on disk, keeping the data they needed to stream over quickly always on the faster outer edge of the disk, leaving the inside for cold data or short reads. They wrote their own recovery for errors with non-parity memory. They wrote their own disk scheduler. They repeatedly modified the Linux kernel to meet their needs. They designed their own servers with no cases, then switched to more standard off-the-rack servers, and now are back to custom servers with no cases again.

Google's agility is impressive. Jeff said they rolled out seven major rearchitecture efforts in ten years. These changes often would involve completely different index formats or totally new storage systems such as GFS and BigTable. In all of these rollouts, Google always could and sometimes did immediately rollback if something went wrong. In some of these rollouts, they went as far as to have a new datacenter running the new code, an old datacenter running the old, and switch traffic between datacenters. Day to day, searchers constantly were experiencing much smaller changes in experiments and testing of new code. Google does all of this quickly and quietly, without searchers noticing anything has changed.

The raw computational power is staggering already -- thousands of machines for a single request -- but what is to come seems nearly unbelievable. Jeff said that Google's machine translation models use a million lookups in a multi-terabyte model just to translate one sentence. Jeff followed by saying that Google's goal is to make all information in all languages accessible regardless of which language you choose to speak. The amount of processing required is difficult to fathom, yet it seems the kind of computational mountain that might cause others to falter calls out to Googlers.

In all, a great talk and a great start to the WSDM 2009 conference. If you want to catch Jeff's talk yourself, and I highly recommend you do, the good people at videolectures.net were filming it. With any luck, the video should be available on their site in a few weeks.

In addition to this post, you might enjoy Michael Bendersky's notes on Jeff Dean's talk. It appears Michael took about as detailed notes as I did.

Update: Jeff now has made his slides (PDF) from his talk available.

Update: Jeff Dean's talk is now available on videolectures.net along with many of the other talks from WSDM 2009.

Book review: Introduction to Information Retrieval

My old favorite book on search, "Managing Gigabytes", is getting quite dated at this point. I've been looking for one I liked as much for the last few years, but just hadn't come across anything as practical or useful as that old text.

Now, I think I may have found a new favorite. Three search gurus, Chris Manning, Prabhakar Raghavan (head of Yahoo Research), and Hinrich Schutze, just published a wonderful new book, "Introduction to Information Retrieval".

If you work in search or if you are just the kind of person that reads textbooks for fun, this one is a great one. It not only describes how to build a search engine (including crawling, indexing, ranking, classification, and clustering), but also offers the kind of opinionated wisdom you can only get from people who have had substantial experience using these techniques at large scale.

Let me try to pick out some excerpts to show at least a few examples of why I found this book so valuable. First, on the difference between perceived relevance and measured relevance:

The key utility measure is user happiness. Speed of response and the size of the index are factors in user happiness. It seems reasonable to assume that relevance of the results is the most important factor: blindingly fast, useless answers do not make a user happy. However, user perceptions do not always coincide with system designers' notions of quality. For example, user happiness commonly depends very strongly on user interface design issues, including the layout, clarity, and responsiveness of the user interface, which are independent of the quality of the results returned.

This is a point that is often missed in information retrieval. It is extremely common to measure the quality of search results by having judges sit down and mark how relevant they think they are. That ignores speed, layout, the quality of nearby results, and the many other factors that go into perceived quality and impact user satisfaction.

On compression:

One benefit of compression is immediately clear. We need less disk space.

There are two more subtle benefits of compression. The first is increased use of caching ... With compression, we can fit a lot more information into main memory. [For example,] instead of having to expend a disk seek when processing a query with t, we instead access its postings list in memory and decompress it ... Increased speed owing to caching -- rather than decreased space requirements -- is often the prime motivator for compression.

The second more subtle advantage of compression is faster transfer data from disk to memory ... We can reduce input/output (IO) time by loading a much smaller compressed posting list, even when you add on the cost of decompression. So, in most cases, the retrieval system runs faster on compressed postings lists than on uncompressed postings lists.

The authors go on to say that simple compression techniques might be better for some applications than more complicated algorithms because small additional reductions in data size may not be worth any substantial increase in decompression time.

On supporting phrase searches:

If users commonly query on particular phrases, such as Michael Jackson, it is quite inefficient to keep merging positional posting lists. A combination strategy uses a phrase index, or just a biword index, for certain queries, and uses a positional index for other phrase queries. Good queries to include in the phrase index are ones known to be common based on recent querying behavior. But this is not the only criterion: the most expensive phrase queries to evaluate are ones where the individual words are common but the desired phrase is comparatively rare.

Adding Britney Spears as a phrase index may only give a speedup factor to that query of about three, because most documents that mention either word are valid results, whereas adding The Who as a phrase index entry may speed up that query by a factor of 1,000. Hence, having the latter is more desirable, even if it is a relatively less common query.

Another factor that might be important to consider when picking phrases to put in the phrase index is the caching layer. If [Britney Spears] is almost always cached when queried, it will be satisfied without hitting the posting lists. You probably want to use the frequency of the query hitting the posting lists, not the frequency of the query in the logs, when looking at what to put in a phrase index.

On compression, skip lists, and other attempts to speed up access to the index:

Choosing the optimal encoding for an inverted index is an ever-changing game for the system builder, because it is strongly dependent on underlying computer technologies and their relative speeds and sizes. Traditionally, CPUs were slow, and so highly compressed techniques were not optimal. Now CPUs are fast and disk is slow, so reducing disk postings list size dominates. However, if you're running a search engine with everything in memory, the equation changes again.

A nice, long excerpt on Naive Bayes as a classifier and why it works so well:

Naive Bayes is so called because the independence assumptions ... are indeed very naive for a model of natural language.

The conditional independence assumption states that features are independent of each other given the class. This is hardly ever true for terms in documents. In many cases, the opposite is true. The pairs hong and kong or london and english ... are examples of highly dependent terms.

In addition, the multinomial model makes an assumption of positional independence [and] the Bernoulli model ignores positions in documents altogether because it only cares about absence or presence ... How can NB be a good text classifier when its model of natural language is so oversimplified?

The answer is that even though the probability estimates of NB are of low quality, its classification decisions are surprisingly good ... It does not matter how accurate the estimates are ... NB classifiers estimate badly, but often classify well.

Even if it is not the method with the highest accuracy for text, NB has many virtues that make it a strong contender for text classification. It excels if there are many equally important features that jointly contribute to the classification decision. It is also somewhat robust to noise features ... and concept drift.

[But,] NB's main strength is its efficiency ... It is often the method of choice if (i) squeezing out a few extra percentage points of accuracy is not worth the trouble in a text classification application, (ii) a very large amount of training data is available and there is more to be gained from training on a lot of data than using a better classifier on a smaller training set, or (iii) if its robustness to concept drift can be exploited.

[Many] have shown that the average effectiveness of NB is uncompetitive with classifiers like SVMs when trained and tested on independent and identically distributed (i.i.d.) data ... However, these differences may be invisible or even reverse themselves when working in the real world where, usually, the training sample is drawn from a subset of the data to which the classifier will be applied, the nature of the data drifts over time ... and there may well be errors in the data (among other problems). Many practitioners have had the experience of being unable to build a fancy classifier for a certain problem that consistently performs better than NB.

On feature selection:

Feature selection [picks] a subset of the terms occurring in the training set and [uses] only this subset as features in text classification. Feature selection serves two main purposes. First, it makes training and applying a classifier more efficient ... this is of particular important for classifiers that, unlike NB, are expensive to train. Second, feature selection often increases classification accuracy by eliminating noise features ... [that] might produce ... overfitting. It may appear counterintuitive that at first that a seemingly weaker classifier is advantageous ... [but] we will see that weaker models are often preferable when limited training data are available.

Of the two NB models, the Bernoulli model is particularly sensitive to noise features. A Bernoulli NB classifier requires some form of feature selection or else its accuracy will be low.

Mutual information and chi-squared represent rather different feature selection methods ... Because its criterion is significance, chi-squared selects more rare terms (which are often less reliable indicators) than mutual information. But the selection criterion of mutual information also does not necessarily select the terms that maximize classification accuracy. Despite the differences, the classification accuracy of feature sets selected with chi-squared and MI does not seem to differ systematically ... As long as all strong indicators and a large number of weak indicators are selected, accuracy is expected to be good. Both methods do this.

On the effectiveness of linear classifiers and why using non-linear classifiers is not an obvious win:

For some problems, there exists a nonlinear classifier with zero classification error, but no such linear classifier. Does that mean we should always use a nonlinear classifier?

It is perhaps surprising that so many of the best-known text classification algorithms are linear. Some of these methods, in particular linear SVMs, regularized logistic regression and regularized linear regression, are among the most effective known methods ... Typical classes in text classification are complex and seem unlikely to be modeled well linearly. However, this intuition is misleading for the high dimensional spaces we typically encounter in text applications. With increased dimensionality, the likelihood of linear separability increases rapidly.

Excellent advice on picking which classifier to use:

If you have fairly little [training] data and you are going to train a supervised classifier, then machine-learning theory says you should stick to a classifier with high bias ... There are theoretical and empirical results that Naive Bayes does well in such circumstances ... A very low bias model like nearest neighbor is probably contraindicated. Regardless, the quality of the model will be adversely affected by the limited training data ... Often, the practical answer is to work our how to get more labeled data as quickly as you can.

If there is a reasonable amount of labeled data, then you are in a perfect position to use ... an SVM. However, if you are deploying a linear classifier such as an SVM, you should probably ... [overlay] a Boolean rule-based classifier over the machine-learning classifier ... If management gets on the phone and wants the classification of a particular document fixed right now, then this is much easier to do by hand-writing a rule than by working out how to adjust the weights of an SVM without destroying overall classification accuracy. This is one reason why ... decision trees, which produce user interpretable Boolean-like models, retain considerable popularity.

If a huge amount of data are available, then the choice of classifier probably has little effect on your results and the best choice may be unclear (cf. Banko and Brill 2001). It may be best to choose a classifier based on the scalability of training or even runtime efficiency.

A nice, intuitive explanation of why support vector machines (SVMs) work well:

For two-class, separable training data sets, there are a lot of possible linear separators ... Although some learning methods such as the perceptron algorithm find just any linear separator, others, like Naive Bayes, search for the best linear separator according to some criterion. The SVM in particular defines the criterion to be looking for a decision surface that is maximally far away from any data point ... Maximizing the margin seems good because points near the decision surface represent very uncertain classification decisions ... A slight error in measurement or a slight document variation will not cause a misclassification.

[Also,] by construction, an SVM classifier insists on a large margin around the decision boundary. Compared with a decision hyperplane, if you have to place a fat separator between the classes, you have fewer choices of where it can be put. As a result of this, the memory capacity of the model has been decreased, and hence we expect that its ability to correctly generalize to test data has been increased.

The superlinear training time of traditional SVM algorithms makes them difficult or impossible to use on very large training sets. Alternative traditional SVM solutions algorithms which are linear in the number of training examples scale badly with a large number of features, which is another standard attribute of text problems ... [and it] remains much slower than simply counting terms as is done in the Naive Bayes model.

Nonlinear SVMs ... [are usually] impractical ... [and] it can often be cheaper to materialize the higher order features and train a linear SVM ... The general idea is to map the original feature space to some higher dimensional feature space where the training set is [linearly] separable ... The easy and efficient way of doing this ... [is] the kernel trick ... 90% of the work with kernels uses ... polynomial kernels and radial basis functions ... Really, we are talking about some quite simple things. A polynomial kernel allows us to model feature conjunctions (up to the order of the polynomial) ... [For example,] pairs of words ... [require] a quadratic kernel. If triples of words give distinctive information, then we need to use a cubic kernel. A radial basis function allows you to have features that pick out circles (hyperspheres), although the decision boundaries become much more complex as multiple such features interact. A string kernel lets you have features that are character subsequences of terms.

On clustering:

K-means is the most important flat clustering algorithm ... The ideal cluster in K-means is a sphere with the centroid as its center of gravity ... The first step of K-means is to select as initial cluster centers K randomly selected documents, the seeds. The algorithm then moves the cluster centers around in space to minimize RSS ... the squared distance of each [item] from its [closest] centroid.

[We easily can get] suboptimal clustering ... from a bad choice of initial seeds ... Effective heuristics for seed selection include (i) excluding outliers ... (ii) trying out multiple starting points ... and (iii) obtaining seeds from ... hierarchical clustering [of] ... a small random sample.

Hierarchical clustering outputs ... a [useful tree] structure ... [and] does not require us to prespecify the number of clusters .... [but is at least] O(N^2) and therefore infeasible for large sets of 1,000,000 or more documents. For such large sets, HAC can only be used in combination with a flat clustering algorithm like K-means ... [which] combines the ... higher reliability of HAC with the efficiency of K-means.

And there is much, much more. This is just a small sample of the insights in those pages. Definitely worth a read.

By the way, the references sections at the end of each chapter offer excellent surveys of recent work on each topic. They are worth their weight in gold and should not be missed.

The authors made the full text of their book available online, but I'd recommend picking up a copy for your shelf too. It is too good of a book to just skim through online; it deserves a more thorough read.

Please see also my June 2006 post, "Foundations of Statistical NLP", which reviews a 1999 book by two of the same authors.

Layoffs and tech layoffs

There has been wide coverage in the press of layoffs across companies, including many technology companies.

I do not want to comment directly, but the writing of Jeffrey Pfeffer, one of my favorite authors on management, may be of interest. From one of his books:

There is no solid evidence that using layoffs rather than less draconian methods to cut costs increases performance, and there is plenty of evidence that involuntary reductions in force damage both displaced workers and "survivors".

A University of Colorado study ... showed no link between downsizing and subsequent return on assets. A Bain study ... found that ... firms that used layoffs primarily for cost cutting suffered a drop in stock price ... A Right Associates study ... reported that layoffs were followed by lower employee morale and trust in management.

This and some of Pfeffer's other work also talk about how to do layoffs effectively if they really must be done. To summarize, the layoffs should hit management harder than workers and should provide "people as much prediction, understanding, control, and compassion" as possible so you "reduce the number of people who feel afraid" and give people, "laid off or not", a "good idea of what steps they would need to take to control their destiny." ([1])

Pfeffer also refers to another book, Responsible Restructuring, for more "evidence on the ineffectiveness of most layoffs."

Details on Yahoo's distributed database

The good folks at Yahoo Research published a paper at VLDB 2008, "PNUTS: Yahoo!'s Hosted Data Serving Platform" (PDF), that has juicy details on the massively distributed database behind most of Yahoo's web applications.

An excerpt:

We describe PNUTS, a massively parallel and geographically distributed database system for Yahoo!'s web applications.

The foremost requirements of web applications are scalability, consistently good response time for geographically dispersed users, and high availability. At the same time, web applications can frequently tolerate relaxed consistency guarantees.

For example, if a user changes an avatar ... little harm is done if the new avatar is not initially visible to one friend .... It is often acceptable to read (slightly) stale data, but occasionally stronger guarantees are required by applications.

PNUTS provides a consistency model that is between the two extremes of general serializability and eventual consistency ... We provide per-record timeline consistency: all replicas of a given record apply all updates to the record in the same order .... The application [can] indicate cases where it can do with some relaxed consistency for higher performance .... [such as reading] a possibly stale version of the record.

Do not miss the related work section of the paper where the authors compare PNUTS to Google Bigtable and Amazon Dynamo, among other things.

When reading the paper, a couple things about PNUTS struck me as surprising:

First, the system is layered on top of the guarantees of a reliable pub-sub message broker which acts "both as our replacement for a redo log and our replication mechanism." I have to wonder if the choice to not build these pieces of the database themselves could lead to missed opportunities for improving performance and efficiency.

Second, as figures 3 and 4 show, the average latency of requests to their database seems quite high, roughly 100 ms. This is high enough that web applications probably would incur too much total latency if they made a few requests serially (e.g. ask for some data, then, depending on what the data looks like, ask for some other data). That seems like a problem.

Please see also my August 2006 post, "Google Bigtable paper", which discusses the distributed database behind many products at Google.

Please see also my earlier post, "Highly available distributed hash store at Amazon", on the distributed database behind some features at Amazon.com.

Please see also my earlier posts, "Cassandra data store at Facebook" and "HBase: A Google Bigtable clone".

Update: One of the developers of PNUTS commented on this post, pointing out that PNUTS performance is much better in practice (1-10ms/request) when caching layers are in place and making a few comparisons to Bigtable.

Where all roads lead

Nick Carr writes about the dominance a few have in our access to information:

What we seem to have here is evidence of a fundamental failure of the Web as an information-delivery service. Three things have happened, in a blink of history's eye: (1) a single medium, the Web, has come to dominate the storage and supply of information, (2) a single search engine, Google, has come to dominate the navigation of that medium, and (3) a single information source, Wikipedia, has come to dominate the results served up by that search engine.

Even if you adore the Web, Google, and Wikipedia - and I admit there's much to adore - you have to wonder if the transformation of the Net from a radically heterogeneous information source to a radically homogeneous one is a good thing. Is culture best served by an information triumvirate?

It's hard to imagine that Wikipedia articles are actually the very best source of information for all of the many thousands of topics on which they now appear as the top Google search result.

What's much more likely is that the Web, through its links, and Google, through its search algorithms, have inadvertently set into motion a very strong feedback loop that amplifies popularity and, in the end, leads us all, lemminglike, down the same well-trod path - the path of least resistance. You might call this the triumph of the wisdom of the crowd. I would suggest that it would be more accurately described as the triumph of the wisdom of the mob.

Please see also my Dec 2007 post, "One Wikipedia to rule them all", which cites a 2007 study that claims that Wikipedia is the first result on about 30% of web searches.

Update: I should have remembered this earlier, but please see also Rich Skrenta's Jan 2007 post, "Winner-Take-All", where he says, among other things, that "Google is the start page of the internet."

How Google crawls the deep web

A googol of Googlers published a paper at VLDB 2008, "Google's Deep-Web Crawl" (PDF), that describes how Google pokes and prods at web forms to see if it can find things to submit in the form that yield interesting data from the underlying database.

An excerpt from the paper:

This paper describes a system for surfacing Deep-Web content; i.e., pre-computing submissions for each HTML form and adding the resulting HTML pages into a search engine index.

Our objective is to select queries for millions of diverse forms such that we are able to achieve good (but perhaps incomplete) coverage through a small number of submissions per site and the surfaced pages are good candidates for selection into a search engine's index.

We adopt an iterative probing approach to identify the candidate keywords for a [generic] text box. At a high level, we assign an initial seed set of words as values for the text box ... [and then] extract additional keywords from the resulting documents ... We repeat the process until we are unable to extract further keywords or have reached an alternate stopping condition.

A typed text box will produce reasonable result pages only with type-appropriate values. We use ... [sampling of] known values for popular types ... e.g. zip codes ... state abbreviations ... city ... date ... [and] price.

Table 5 in the paper shows the effectiveness of the technique, that they are able to retrieve a significant fraction of the records in small and normally hidden databases across the Web with only 500 or less submissions to the form. The authors also say that "the impact on our search traffic is a significant validation of the value of Deep-Web content."

Please see also my April 2008 post, "GoogleBot starts on the deep web".