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".

My father, Ted Linden, 1938 - 2009

My father, Theodore Linden, died on Tuesday, January 20, 2009, a few months after being diagnosed with brain cancer.

My father valued reason and rationality above all else, which made particularly cruel the cancer that pulled his mind from him in pieces. During his lifetime, that mind had remarkable influence, including seminal work in computer security and object-oriented programming, helping to build the earliest graphical operating systems at Xerox, and designing early AIs for robotic vehicles.

The eyes of a child are not a mirror for the life of a father, but my earliest memories of my father's work is in the computer terminal he brought home with him from Xerox PARC. We would dial in to the mainframe using a funky acoustic modem, the kind where you would pick up a phone handset and plop it down into little soft cups so the computer could talk with little beeps into the phone. The reason I loved that terminal as a young child is that Dad would occasionally let me use it to play Haunt, an early, clever, and amusing game set in a haunted house that, to this day, remains my favorite text adventure of all time.

Later, he took me into Xerox and let me try a Xerox Star. I still remember the enormous removable hard drives, shaped like the saucer section of the Star Trek Enterprise, nearly a meter across. A child being a child, the main thing that sticks in my mind again was the games, such as Maze War, Draw, Trek, and Pinball. Those early experiences made me want to write computer games myself and eventually pushed me into computer science. History may not repeat, but it echoes, and I look on curiously as I see my own son starting down this same path.

The window through which a child sees is small. As an adult, I can more fully see the impact my father had. The Xerox Star and Alto were the foundation for all modern operating systems. The desktop metaphor, the mouse, all that we see on our computers in our daily lives today was built on the shoulders of research at Xerox. My father's work at Xerox (ACM) was a part of that on which others now stand.

After Xerox, in the early 1980's, he worked on the DARPA Autonomous Land Vehicle project (IEEE), an early attempt to build a car that drove itself. His research included replanning when the robot encountered unexpected conditions ([1]), work that much later would influence the planning systems used in the Mars Rover (IEEE). The ALV was too ambitious of a project to succeed with the technology available in the 1980's, but, in 2005, he looked on with pride and joy at the remarkable success of the nearby Stanford team when their car drove itself 150 miles down twisty desert roads in the DARPA Grand Challenge.

Even as an adult, I did not know about all my father did until recently. He lived his life with a quiet competence -- things just got done -- and never bragged or boasted. I was surprised, for example, to discover that he did seminal work in computer security (ACM) and object-oriented programming (ACM) way back in the 1970's. All of this from a man who was the son of a millwright, only in America.

My father spent much of his life in the study of intelligent systems. His children follow his footsteps. My sister has devoted her life's work to neurobiology and the study of the mind at University College London. I work in artificial intelligence and machine learning. As we look back at my father and a life well lived, we can only hope we might have a fraction of the positive impact he did. Ted Linden will be remembered and sorely missed.

If you knew my father or his work, please comment on this post. I would much enjoy hearing from you.

Update: Thank you, all of you, who posted comments on this post. I appreciate your thoughts and stories about my father.

Update: Two months later, on March 21, 2009, we held my father's memorial. It was our celebration and remembrance of his life. Below is my speech on that day:

In his retirement, in the wee hours of the morning, it was not unusual to find my father out of bed, downstairs, playing Civilization in his office. Basking in the gentle glow of his computer screen, he would relive the never-ending struggles of men and nations against each other, the competition for wealth, power, and influence we see throughout history.

Earlier, when I was at college, we both started looking at game theory. As part of my work, I built little simulations of people interacting that showed that, even when people have short-term incentives to hurt each other, they often cooperate. My Dad saw this and started devouring texts on the topic, looking at game theory, evolutionary economics, the incentives created by societies, and the emergence of cooperation. In all of this, he was seeking to understand how normally competing actors suddenly could start working together.

Throughout his life, my father was fascinated with the goodness of man. Why are people good to each other? Is it somehow innate? Can it be derived from reason? Is it part of the rules that successful societies build? How is it that altruism can exist?

Perhaps it was born of his Jesuit upbringing, looking to reason to explain the nature of man. It lived on in his career in computers and early artificial intelligence. He built robotic cars that attempted to learn about and navigate through the world. He studied how little programs running on different computers, without really trusting the other programs to do the right thing, could share knowledge to protect each other from outside threats. In his career, much of his work involved trying to build robots and agents that understand the world and cooperate with each other.

In all of it, he was motivated by the same questions: Why are people good? Why do people cooperate? In this world, how can altruism exist?

Like so many before him, my father only gained partial answers these questions. He saw rational people as able to see the benefits of cooperation in the long-term. He noted the societies we build reward cooperation and penalize cheating. He read of the benefits of altruism that accrue not only to ourselves, but to our families and societies. And he wondered if this was enough to explain the kindness we see around us.

Looking back as a son, I am inspired by my father's pursuit of such great questions. A life inquiring about the very essence of human nature, that is a life well lived.

Preferred sites feature in Google search

Alex Chitu describes an experimental feature currently in A/B testing on Google where searchers can add "a list of sites you want to appear more often when you search."

More information on the Google help page for the new feature.

Seems like an interesting blend of SearchWiki (which lets people manually reorder Google search results) and Google Personalized Search (which automatically reorders search results based on your past search and visit behavior).

2008 prediction and looking to 2009

In January of 2008, I laid out my prediction for what would happen in the rest of the year. Unfortunately, it turns out to be largely correct.

We will see a dot-com crash in 2008 ... The crash will be driven by a recession and prolonged slow growth in the US. Global investment capital will flee to quality.

Most startups will find their revenue models were unrealistic and will rapidly have to seek change. Many will jump over to advertising, but the advertising market will have constricted.

The big players will not be immune from this contagion. Google, in particular, will find its one-trick pony lame, with the advertising market suddenly stagnant or contracting and substantial new competition ... Google and Yahoo will do ... substantial layoffs.

Parts of the prediction did not come true yet in 2008, but may in 2009.

It will be more prolonged and deeper than the crash of 2000.

Desperate competition with dwindling opportunity will drive profits in online advertising to near zero. Google ... will find their available cash dropping.

It is likely that those with little to lose will attempt scary new forms of advertising. The Web will become polluted with spyware, intrusiveness, and horrible annoyances. None of this will work, of course, and there will be lawsuits and new privacy legislation, but we will have to endure it while it lasts.

Underlying the prediction of a dot com crash was a prediction of the broader economy. While the direction was correct, I have to admit, I got parts of that prediction wrong. In particular, I did not expect huge multinational banks to be so rash as to make gambles that could drive them to insolvency, nor did I expect the normally more considered Europeans to follow the foolhardy practices of we Americans. I did expect hedge fund failures and a housing price fall, but I was as amazed as everyone else that the ratings on bonds would become completely unreliable and that one particularly prestigious fund was actually just a Ponzi scheme. Where I was wrong, it appears my mistake was assuming Wall Street still had some lines it still would not cross.

I do want to say that I am in no way happy that my 2008 prediction turned out to be largely true. It is awful, truly awful.

It also is sad to look back at the irrationality and willful blindness of early 2008. A glance over the comments on my January 2008 post gives a feel for how people reacted to anyone who tried to send up the red flags. It is not true that no one saw this recession coming -- economists like Nourel Roubini, Paul Krugman, Robert Shiller, and Dean Baker were quite vocal -- but they were marginalized and maligned.

I hope that the early warning I tried to give had at least some positive impact. It seemed that some startups were looking to secure funding rounds earlier than they might otherwise and build up cash, but, as much as I might hope it was helpful, I have no evidence that what I posted influenced any startups to be more cautious.

As for predictions for 2009, given the vitriol my 2008 post attracted, I am going to leave this game to others. If you really do want to see things fairly close to what I think will happen in 2009, please see [1], [2], [3], [4], [5], and [6].

Blending the link and query-click graphs

A fun paper out of Yahoo Research, "Dr. Searcher and Mr. Browser: A Unified Hyperlink-Click Graph" (PDF), looks at the value of combining two graphs that search engines typically use as part of static and dynamic ranking, the query-click bipartite graph (which shows what pages people click on immediately after searching) and the link graph (which shows hyperlinks between pages on the Web).

The query-click graph is a bipartite graph with queries on one side and clicked documents on the other. A query (e.g. [greg linden]) is linked to a document (e.g. http://glinden.blogspot.com) if people who make the query click on that document. The links are usually weighted by the probability that someone clicks on the document given that search query. Search engines get the query-click graph by parsing their query logs. Random walks of the query-click graph have been a popular research topic for finding similar queries and similar documents.

The hyperlink graph is a graph where web pages are nodes and a link from one page to another is a directed edge in the graph. Search engines get a link graph by crawling the Web and parsing all the html of all the pages. Random walks of the link graph are used to find related documents and by algorithms such as PageRank to compute the authority of web pages.

The authors of this Yahoo paper had the idea of combining the two graphs and doing random walks of the combined graph. In particular, they model searchers starting with a query, then clicking, then randomly walking the hyperlink graph, until they eventually search again. The goal is to more accurately model searcher behavior and more accurately find the pages people actually want when they search.

I really like the idea and think it should be useful, but I cannot help but notice that the combined hyperlink and query-click graphs are trying to approximate how people actually move across the Web. If a search engine had good data on how people actually moved across the Web, it might not need this approximation.

For more on using data on how people actually move across the Web, please see my earlier posts, "Google Toolbar and the actual surfer model" and "Search trails and relevance".

Danny Sullivan on Microsoft's Live Search

Danny Sullivan wrote up a version of a talk he gave at Microsoft in June 2008 in his recent post, "Tough Love for Microsoft Search".

Danny Sullivan is an insightful writer, long-time watcher of the search industry, and founder of Search Engine Watch, Search Engine Land, and the popular Search Engine Strategies (SES) conference. His thoughts are well worth reading.

[Found via Todd Bishop]

Considering consistency at Amazon

Amazon CTO Werner Vogels posted an copy of his recent ACM Queue article, "Eventually Consistent - Revisited". It is a nice overview of the trade-offs in large scale distributed databases and focuses on availability and consistency.

An extended excerpt:

Database systems of the late '70s ... [tried] to achieve distribution transparency -- that is, to the user of the system it appears as if there is only one system instead of a number of collaborating systems. Many systems during this time took the approach that it was better to fail the complete system than to break this transparency.

In the mid-'90s, with the rise of larger Internet systems ... people began to consider the idea that availability was perhaps the most important property ... but they were struggling with what it should be traded off against. Eric Brewer ... presented the CAP theorem, which states that of three properties of shared-data systems -- data consistency, system availability, and tolerance to network partition -- only two can be achieved at any given time .... Relaxing consistency will allow the system to remain highly available under the partitionable conditions, whereas making consistency a priority means that under certain conditions the system will not be available.

If the system emphasizes consistency, the developer has to deal with the fact that the system may not be available to take, for example, a write ... If the system emphasizes availability, it may always accept the write, but under certain conditions a read will not reflect the result of a recently completed write ... There is a range of applications that can handle slightly stale data, and they are served well under this model.

[In] weak consistency ... The system does not guarantee that subsequent accesses will return the updated value. Eventual consistency ... is a specific form of weak consistency [where] the storage system guarantees that if no new updates are made to the object, eventually all accesses will return the last updated value ... The most popular system that implements eventual consistency is DNS (Domain Name System).

[In] read-your-writes [eventual] consistency ... [a] process ... after it has updated a data item, always accesses the updated value ... Session [eventual] consistency ... is a practical version of [read-your-writes consistency] ... where ... as long as [a] session exists, the system guarantees read-your-writes consistency. If the session terminates because of a certain failure scenario, a new session needs to be created and the guarantees do not overlap the sessions.

As Werner points out, session consistency is good enough for many web applications. When I make a change to the database, I should see it on subsequent reads, but anyone else who looks often does not need to see the latest value right away. And most apps are happy if this promise is violated in rare cases as long as we acknowledge it explicitly by terminating the session; that way, the app can establish a new session and either decide to wait for eventual consistency of any past written data or take the risk of a consistency violation.

Session consistency also has the advantage of being easy to implement. As long as a client reads and writes from the same replica in the cluster for the duration of the session, you have session consistency. In the event that node goes down, you terminate the session and force the client to start a new session on a replica that is up.

Werner did not talk about it, but some implementations of session consistency can cause headaches if a lot of clients doing updates to the same data where they care what the previous values were. The simplest example is a counter where two clients with sessions on different replicas both try to increment a value i and end up with i+1 in the database rather than i+2. However, there are ways to deal with this kind of data. For example, just for the data that needs it, we can use multiversioning while sending writes to all replicas or forcing all read-write sessions to the same replica. Moreover, a surprising vast amount of application data does not have this issue because there is only one writer, there are only inserts and deletes not updates, or the updates do not depend on previous values.

Please see also Werner's older post, "Amazon's Dynamo", which, in the full version of their SOSP 2007 paper at the bottom of his post, describes the data storage system that apparently is behind Amazon S3 and Amazon's shopping cart.