Questioning Yahoo Answers

Zoltan Gyongyi, Georgia Koutrika, Jan Pedersen, and Hector Garcia-Molina published a paper at WWW 2008, "Questioning Yahoo Answers", that has an interesting analysis of how people are using Yahoo Answers.

Some excerpts:

The majority of users are askers ... [Only] a small portion of the user population that provides answers or votes .... In practice, a large fraction of best answers are of questionable value .... Most answerers are not domain experts focusing on a particular topic, but rather individuals with diverse interests quite eager to explore questions of different nature.

Many questions are meant to trigger discussions, encourage the users to express their opinions, etc. The expected answers are subjective. Thus, in a traditional sense, there is no bad or good (or best) answer to such "questions." Consider, for example, "What do you think of Red Hot Chili Peppers?"

Note, however, that Yahoo! Answers was not designed with discussions in mind, and so it is an imperfect medium for this purpose. Users cannot answer their own questions, thus cannot participate in a discussion. Similarly, a user may only post at most one answer to a question. Yahoo! Answers has no support for threads that would be essential for discussions to diverge.

Much of the interaction on Yahoo! Answers is just noise. People post random thoughts as questions, perhaps requests for instant messaging. With respect to the latter, the medium is once again inappropriate because it does not support real-time interactions.

This evidence and our results point to the following conclusion: A question answering system, such as Yahoo! Answers, needs appropriate mechanisms and strategies that support and improve the question-answering process per se. Ideally, it should facilitate users finding answers to their information needs and experts providing answers.

Please see also my October 2007 post, "Revisiting Yahoo Answers", where I look at Yahoo Answers not as a question answering site, but as what it primarily seems to be used for, a discussion forum.

Search trails and relevance

Misha Bilenko and Ryen White from Microsoft Research had a paper at WWW 2008, "Mining the Search Trails of Surfing Crowds: Identifying Relevant Websites From User Activity" (PDF), that is a fascinating look at going beyond the first click on search results for improving search results and toward considering all the pages people visit.

An excerpt from the paper:

While query and clickthrough logs from search engines have been shown to be a valuable source of implicit supervision for training retrieval methods, the vast majority of users' browsing behavior takes place beyond search engine interactions.

This paper proposes exploiting a combination of searching and browsing activity of many users to identify relevant resources for future queries. To the best of our knowledge, previous approaches have not considered mining the history of user activity beyond search results, and our experimental results show that comprehensive logs of post-search behavior are an informative source of implicit feedback for inferring resource relevance.

Web browser toolbars have become increasingly popular ... Examples of popular toolbars include those affiliated with search engines (e.g., Google Toolbar, Yahoo! Toolbar, and Windows Live Toolbar) ... Most popular toolbars log the history of users' browsing behavior on a central server for users who consented to such logging. Each log entry includes an anonymous session identifier, a timestamp, and the URL of the visited Web page. From these and similar interaction logs, user trails can be reconstructed.

Training retrieval algorithms on interaction behavior from navigation trails following search engine result click-through leads to improved retrieval accuracy over training on only result click-through or search destinations ... Our research has profound implications for the design of Web search ranking algorithms and the improvement of the search experience for all search engine users.

Please see also Googler Daniel Russel's JCDL 2007 talk, "What are they thinking? Searching for the mind of the searcher" (PDF), which shows, starting on slide 33, that Google is using their toolbar data to analyze user behavior.

Thanks, Ionut Alex Chitu, for the pointer to Daniel's JCDL talk.

Keynotes at WWW 2008

The keynote talks at WWW 2008 promised to be exciting. With names like Google VP Kai-Fu Lee (who's departure from Microsoft famously revealed Ballmer's hidden passion for hurling chairs), Microsoft VP Harry Shum, inventor of the Web Tim Berners-Lee, and AT&T Chief Scientist David Belanger, how could you go wrong?

Surprisingly, it did go wrong. Everyone I talked to gave reviews of the keynotes that ranged from lukewarm to blisteringly negative.

The general conclusion, which also agrees with my perception, seemed to be that Kai-Fu Lee and Harry Shum gave pitches for Google and Microsoft rather than vision. And, in the Great Hall of the People, Tim Berners-Lee seemed woefully unprepared, rambling with such a lack of coherent theme that many buried themselves in alcohol to escape the pain.

Nevertheless, there were tidbits that could be extracted. Comparing Kai-Fu Lee's and Harry Shum's talks, I was struck by the way Harry Shum focused entirely on search while Kai-Fu seemed to be looking beyond search.

Kai-Fu talked mostly about cloud computing and showed Google products as examples of a shift toward cloud computing. For example, Kai-Fu pointed at GMail and Google Docs as applications moving to the browser, and integration of those applications as examples of how the browser can make applications more "task-focused" (an argument I found quite weak, by the way, even though I tend to support the ideas behind cloud computing).

Harry Shum focused on improving search, noting that "40% of queries go unanswered" and "50% require refinement", and then saying we need to look at concepts, topics, entities, and tasks to try to figure out "what the user really wants to do".

On the one hand, both talks seemed odd to me that the search giant Google offered a keynote at a Web conference not about search whereas Microsoft used their keynote to talk about little else.

On the other hand, both talks may have been looking at what the companies need to do to expand beyond where they currently are on the Web. Google needs to move beyond search and advertising. Microsoft needs to get into search and advertising. In that framework, the two speeches make a lot of sense.

David Belanger's sparsely attended talk was about how we can integrate data across three distinct interfaces, mobile, PC, and television. Unlike some who claim these three are converging, David argued that TV, PC, and mobile will stay separate and the key question will be interfacing them with each other. I was pleased that David pushed recommendations for information as necessary "in the not to distant future" when we have "access to any video ever made" and only weak ability to specify our interests beyond a desire to watch something fun and interesting. Sadly, he did not expand much on that point, instead devoting much of the talk to promoting AT&T and discussing low level networking details of data sharing and synchronization.

It is hard to say much about Tim's talk other than that he was enthusiastic about globalization, internationalization, and the semantic web. Tim pointed that Chinese was poised to become the dominant language on the Web and urged everyone to think about the changes that would cause. He promoted the semantic web, but offered nothing new. The remainder of talk was so badly unstructured -- nearly a stream of consciousness -- that it was hard to follow despite the passion he tried to put behind it.

GoogleBot starts on the deep web

Jayant Madhavan and Alon Halevy have the post on the Official Google Blog, "Crawling through HTML forms", announcing that the crawler will start submitting queries in forms in order to pull data out of databases that otherwise would not be visible.

Please see also my March 2007 posts, "The end of federated search?" and "Google and the deep web", which discuss several papers out of Google (that Jayant and Alon authored) that appear to describe Google's thoughts on what to do about the deep web.

Mousetracking in web search

Googlers Kerry Rodden, Xin Fu, Anne Aula, and Ian Spiro had a short paper last week at CHI 2008, "Eye-mouse coordination patterns on web search results pages" (ACM site), with some some very nice graphs showing common behaviors using the mouse on web search results and how they correspond to eye movements over the page (see Figure 1, 2, and 3).

Unfortunately, their results seem to indicate that mouse tracking is only weakly correlated with eye tracking, so mouse tracking might be less useful than one would hope for determining which items on a web search result page were never even seen by a searcher.

For more on using mouse tracking as a replacement for eye tracking to understand what people look at on web search result pages, please see my earlier post, "Cheap eyetracking using mouse tracking", and its discussion of a SIGIR 2007 paper by some of the same Google authors.

Udi Manber interview in Popular Mechanics

Google VP Udi Manber has an interesting interview in Popular Mechanics.

An excerpt on learning to rank from searcher behavior:

Our goal is very simple: We want to return to the user the answer that they need.

The results we show you are based not only on what we know of the Web, but also what other people have searched for .... Signals from people are the best signals.

An excerpt on personalization:

If you allow us to keep your Web history, we will improve your search ... in two ways. One is, we will tune the result for you slightly. We're not going to change the whole page -- we might change position 5 to position 3 here and there, but we'll use whatever we can from your previous searches to adapt the current search to you.

The second is, we allow you to search within your Web history ... You may remember something you did three months ago and you don't remember exactly how you did it.

And, an excerpt on how improving overall relevance requires accumulating many small twiddles that apply to specific types of searches and needs:

Last year we made over 450 improvements to the algorithm .... We have to find what weakness in the algorithm caused that result and find a general solution to that, evaluate whether a general solution really works and if it's better, and then launch a general solution.

I'll give you an example of something that came last week. We were evaluating a certain algorithm that adds diversity to the result. We did live experiments, which means we launched the algorithm to a very small percentage of users and then see how that compares to the result without the algorithm.

One of the queries that made a difference: The query was, New York Times address ... The first result right there on the snippet gives you The New York Times. It turns out that's not what the user was looking for. They were looking for an address given out by a New York Times reporter the day before. And because of this diversity and because of our emphasis on freshness and highlighting fresh results, that particular address appeared somewhere in the results, and that's what the user wanted -- that's what they went to and got the result.

That was something that surprised even us. You don’t think that when someone searches for New York Times address that they’re not looking for the address. Language is like that. Intention can be ambiguous.

There is a re-occurring theme in Udi's comments, learning from searcher's behavior. Google learns from what people searched for. Google learns from a searcher's history. Google learns what works and what does not from what people click on. Google learns from what people do when they use Google.

For more on that, please see also my previous post, "Actively learning to rank".

Please see also my earlier post, "The perils of tweaking Google by hand", which talks about whether these thousands of twiddles to the search engine and variations of them probably should be constantly tested rather than just evaluated at the time they are created.

Detecting near duplicates in big data

I finally got to a WWW 2007 paper out of Google I have been meaning to read, "Detecting Near-Duplicates for Web Crawling" (PDF) by Gurmeet Manku, Arvind Jain, and Anish Sarma.

The paper takes more theoretical work from Moses Charikar back in 2002, "Similarity Estimation Techniques from Rounding Algorithms" (ACM site), which describes a form of locality sensitive hashing, and applies it at very large scale (8B documents), dealing with all the practical issues along the way.

In that sense, this Google WWW 2007 paper has a lot of similarities with Monika Henzinger's excellent SIGIR 2006 paper, "Finding Near-Duplicate Web Pages: A Large-Scale Evaluation of Algorithms" (ACM site). That paper evaluated the shingles method of creating fingerprints of substrings from a document against Charikar's technique on a 1.6B document data set and found the latter to be superior.

Some excerpts from the Google WWW 2007 paper:

Documents that are exact duplicates of each other ... are easy to identify ... A more difficult problem is the identification of near-duplicate documents ... [that] differ in a small portion of the document such as advertisements, counters and timestamps.

Charikar's simhash ... is a fingerprinting technique that enjoys the property that fingerprints of near-duplicates differ in a small number of bit positions.

We maintain an f-dimensional vector V, each of whose dimensions is initialized to zero. A feature is hashed into an f-bit hash value. These f bits (unique to the feature) increment/decrement the f components of the vector by the weight of that feature as follows: if the i-th bit of the hash value is 1, the i-th component of V is incremented by the weight of that feature; if the i-th bit of the hash value is 0, the i-th component of V is decremented by the weight of that feature. When all features have been processed, some components of V are positive while others are negative. The signs of components determine the corresponding bits of the final fingerprint.

Simhash possesses two conflicting proporties: (A) The fingerprint of a document is a "hash" of its features, and (B) Similar documents have similar has values.

The paper goes on to describe how they efficiently find nearby but different hash values that represent similar documents, how they rapidly build the simhash using MapReduce, and metrics on the effectiveness of the technique.

Going to WWW

I will be at the WWW 2008 Conference in Beijing next week.

Very much looking forward to it! If you see me there, please say hello!

Google engEdu talk on Bloom filters

Ely Porat gave a Google engEdu talk, "The Bloom filter", with a good survey of Bloom filters and variants on Bloom filters.

Bloom filters let you quickly determine if an item is a member of a set with no false negatives but some false positives. They work well for very large data sets since they require about 10 bits per item for a 1% false positive rate and offer constant time inserts and lookups.

Ely's talk provides some useful motivation at the beginning, then has a nice, light introduction to Bloom filters starting at 8:40. The discussion of variants that support deletion or compression is interesting but, if you find yourself dragging, make sure to at least jump to 30:40 for the cute discussion of Cukoo Hashing and the Cukoo Bloom Filter.

Please see also the "Bloom filter" Wikipedia page which contains a nice summary of Bloom filters and many of the variants described in Ely's talk.

Contextual advertising and social networks

Anand Rajaraman makes a counter-intuitive but compelling argument that having a close relationship between people who view a page reduces the value of the page for contextual advertising.

An excerpt:

Consider the difference between a Facebook profile and a TripAdvisor travel review. A typical [Facebook] pageview ... is by someone known very well to the creator of the profile – a close friend or acquaintance ... A TripAdvisor travel review is seen by people completely unrelated in any way to the person or persons who wrote the reviews on the page.

The "affinity" of a social media service is the average closeness of relationship between a content creator and someone who views that content. The affinity of Facebook is very high, while the affinity of TripAdvisor is very low.

There is an inverse relationship between the affinity of a social media service and its targetability. Why is this true? The act of viewing a Facebook profile gives us very little information about the viewer, other than the fact that she is friends with the profile creator; when someone views a TripAdvisor travel review, she is definitely interested in traveling to that location.

When a page draws from a wide audience, the people who manage to get to that page often will come from search and will be interested in the content of that page. So, they can easily be targeted by targeting the content of the page.

When a page draws from a narrow audience, like a group of friends, those people are not as interested in the content as the person. So, targeting the content, as contextual advertising does, will be less effective than targeting the people.

I have said before that lack of commercial intent is the problem on social networking sites, but Anand makes the good point that diversity of interest may be a better way of describing the problem. By summarizing why people come to a page, affinity may explain the difficulty of targeting advertising to that page.

Cheap personalization using the referrer

Danny Sullivan at Search Engine Land writes:

Previous Query refinement is now coming to unpaid or "organic" search results, [Google VP Marissa Mayer] said.

For example, if someone were to search for [spain] and then [travel] after that, BOTH the ads and the organic results will be altered to take the previous query into account. To some degree, it will be as if the second query was for [spain travel].

This is a big deal. Big deal. It means that the results for many "single word" queries, which can be hard for sites to rank for when billions of listings come back, will become queries involving two or more words -- and much more specific ones.

This is a cheap and easy form of personalized search and personalized advertising that uses the history stored in the referrer instead of maintaining a separate, longer history.

As Danny says, the goal of personalized search is to help us find what we need faster and more easily by creating a dialogue with our search engine. No longer is each search treated as independent, but what we find or do not find in earlier searches impacts our future searches.

Replication, caching, and partitioning

Brian Aker (who is a Director at MySQL) posts about "The Death of Read Replication".

It is a bit of a ramble, but Brian's thoughts are always worth a read. Brian's main point is that people have moved away from read-only replication and toward caching layers in front of the database like memcached.

My opinion on this differs somewhat. I agree that read-only replication is at best a temporary scaling solution, but I disagree that object caches are the solution.

I think caching is way overdone, to the point that, in some designs, the caching layers sometimes contains more machines than the database layer. Caching layers add complexity to the design, latency on a cache miss, and inefficiency to use of cluster resources.

I tend to be more of a fan of partitioning. I often suspect the design of the data store could be both simpler and faster if the database layer was massively partitioned, the data sharded, the caching layer removed, and the machines allocated to the caching layer moved to the database layer instead.

If the database layer can keep its working set in memory and its own caches are well designed, it should be able to exceed the performance and scalability of an architecture with a separate caching layer. It is only when a database is horribly slow (because, for example, it is always hitting disk) that caching layers look so attractive. Rather than putting layers in front to hide your shame, why not fix that slow database?

Please see also my May 2006 post, "Wikipedia and databases", which discusses their architecture which, at the time, had one huge, overwhelmed I/O bound database using read-only replication to other databases and a large caching layer.

Update: In the comments, Brian swings by and argues for a balance between partitioning and caching (and kindly forgives me for my use of "ramble").

Update: François Schiettecatte writes ([1] [2]):

At Feedster ... once we got powerful enough servers for the DBMS, we found ... memcached ... was a hinderance more than anything.

Ideally you want to ... [not] need to use caching because you get .. to your data fast enough ... That ... means having an optimized schema and a sharded database ... Take the memory you would use for caching and give it to [your] database servers.

Massively distributed Ajax profiling

Emre Kiciman and Ben Livshits have a SOSP 2007 paper, "AjaxScope: A Platform for Remotely Monitoring the Client-Side Behavior of Web 2.0 Applications" (PDF), with the clever idea of using web browser clients to help do massively distributed instrumentation and performance optimization of Web 2.0 applications.

Some excerpts from the paper:

AjaxScope ... [allows] instrumenting and remotely monitoring the client-side execution of web applications within users' browsers .... at the source code level to improve developers' visibility into ... correctness and performance.

We take advantage of ... the ability to dynamically serve new, different versions of the code each time any user runs a web application ... to ... provide differently instrumented code per user and per execution of an application.

Instrumentation is dynamically added or removed from a program as its real-world behavior is observed across users. We [also] distribute instrumentation and run-time analyses across many users' execution of an application ... A combination of these techniques allows us to take ... runtime monitoring policies that would normally impose a prohibitively high overhead and instead spread the overhead across users and time.

Because our prototype can parse and rewrite standard JavaScript code, it does not require changes to the server-side infrastructure of web applications, nor does it require any extra plug-ins or extensions on the client browser.

To our knowledge, AjaxScope is the first to extend the developer's visibility into web application behavior onto the end-user's desktop ... in that it allows developers to gain insight into application behavior in a wide-area setting.

The paper goes on to give several examples of doing instrumentation with AjaxScope including reporting client-side errors, detecting infinite loops, optimizing string concatenation, finding memory leaks, and looking for opportunities for static caching.

Update: About a year later, Microsoft made parts of AjaxView, a similar toolkit, available for download.

The death and life of newspapers

Eric Alterman writes an article, "Out of Print", in the March 31 New Yorker about "the death and life of the American newspaper."

An excerpt:

Until recently, newspapers were accustomed to operating as high-margin monopolies. To own the dominant, or only, newspaper in a mid-sized American city was, for many decades, a kind of license to print money.

Most managers in the industry have reacted to the collapse of their business model with a spiral of budget cuts, bureau closings, buyouts, layoffs, and reductions in page size and column inches ... Molly Ivins complained ... the newspaper companies' solution to their problem was to make "our product smaller and less helpful and less interesting" ... [and] that may help explain ... the dwindling number of Americans who buy and read a daily paper.

While the localized monopolies newspapers enjoyed are not coming back, I do think there is a lot newspapers could do to make their product more comprehensive, more helpful, and more interesting. In particular, I think newspapers should focus on local news and advertising and make their websites adaptive to the needs and interests of their readers.

For more on that, please see my earlier posts, "Newspapers and local content", "People who read this article also read", "Personalizing the newspaper", and "What to advertise when there is no commercial intent?"

Hadoop Summit notes

James Hamilton posts detailed notes ([1] [2] [3] [4] [5]) on the talks at the Hadoop Summit.

Hadoop is the open source version of Google GFS and MapReduce. Yahoo is pushing a lot of the development of Hadoop.

The notes cover talks on Hadoop, Yahoo Pig, Microsoft Dryad, Yahoo HBase, Facebook Hive, Yahoo ZooKeeper, and a few applications using these platforms.

James' notes are excellent, long, and detailed. I found several noteworthy tidbits in there.

Most of the Hadoop clusters are small, 2k nodes or less, often just tens of nodes. They have plans to expand to 5k. However, this seems to conflict with Yahoo's earlier announcement that they have Hadoop running on a "10,000 core Linux cluster".

They have hit problems with scheduling jobs -- "FIFO scheduling doesn't scale for large, diverse user bases", "We're investing heavily in scheduling to handle more concurrent jobs" -- but an attempt to deal with this by breaking one cluster into many virtual clusters called Hadoop on Demand is not working well -- "HoD scheduling implementation has hit the wall ... HoD was a good short term solution but not adequate for current usage levels. It's not able to handle the large concurrent job traffic Yahoo! is currently experiencing."

Joins are "hard to write in Hadoop" and even harder to optimize, which is part of the motivation for the higher level Pig language built on top of Hadoop. While the Pig team argues that their language is simpler and easier to use than SQL, they do have plans to write an SQL-like processing layer on top of Pig.

On the topic of joins, there apparently was a brief discussion comparing Hadoop/MapReduce data processing to more traditional databases where the primary difference mentioned was that databases have indexes where Hadoop and MapReduce have to create the equivalent of those indexes ad hoc for each job. While that is not a new point, considering it again makes me wonder if there might be a middle ground here where we retain older extracts and other intermediate results and reuse them for similar computations over the same data. That would have a similar effect as an index, but would have the advantages of being built on demand and targeted to the current workloads.

If there are other tidbits you found of interest in the notes (or you attended the conference and found other things to be of interest), please add a comment to this post!

Update: James adds a summmary post with a few more thoughts.

Update: As Doug Cutting and Chad Walters point out in the comments, a 2k node cluster easily could have 10k cores, so I struck my statement that only having 2k nodes seems to be in conflict with Yahoo's earlier announcement.

Talk on disk as the new RAM

Northeastern Professor Gene Cooperman recently gave a curious Google engEdu tech talk, "Disk-Based Parallel Computation, Rubik's Cube, and Checkpointing".

Gene's starting point is that "disk is the new RAM" and the "disks of a cluster can serve as if they were RAM" because the bandwidth to 50 disks is 5G/second, same as the bandwidth to RAM.

The talk just gets more fun from there, with Gene claiming that "a compute cluster with 32 quad core nodes, each with 500G of local disk, is a good approximation of ... a single computer with 10 terabytes of RAM and 200 CPU cores."

The premise is, of course, outlandish. The obvious issue to come up is that the latency characteristics of 10T of RAM is totally different than the latency characteristics of 32 500G disks.

But, as long as long as we can batch the reads and writes to the disk, this difference does not matter. Gene gives a few classes of algorithms -- breadth first state-space search, some algorithms that involve millions of accesses to hash tables, some types of pointer chasing -- that they have found amenable to the model.

This has parallels to MapReduce and the changes we need to do to algorithms to make them work well in a MapReduce framework, as one Googler pointed out during the Q&A.

If you only have time for a few minutes and want the gist of the talk, I would recommend you at least watch from 31:48 for 5-10 minutes.

Using dwell times for search relevance

UNC Professor Diane Kelly gave a Google engEdu talk recently titled "Relevance Feedback: Getting the Most out of Your User".

I found the discussion of implicit relevance feedback in search -- using click and display times to determine whether a page was relevant -- that starts around 33:00 to be particularly interesting.

One noteworthy tidbit is that Diane says (at 58:00) that their work found "no direct relationship between display time and usefulness" of web pages.

I was surprised to hear that. I thought dwell times were a good indicator of the relevance of a page.

There appear to be more details on that in her 2004 SIGIR paper, "Display time as implicit feedback: Understanding task effects" (PDF). That paper, in a small user study, found "great variation between subjects in the relationship of display time and usefulness rating ... [and a] lack of any significant relationship between these two factors ... [which] indicates that using display times averaged over a group of users as a measure of usefulness is unlikely to work."

Please see also Joachims et al. 2005, "Accurately interpreting clickthrough data as implicit feedback", which discusses (in Section 2) this study and other studies on the usefulness of the time spent reading a page for determining relevance.

Please see also my earlier posts, "Actively learning to rank" and "Ranking using Indiana University's user traffic".

Using IMDb data for Netflix Prize

In a post titled "More data usually beats better algorithms", Anand Rajaraman talks about the success a team from his data mining class at Stanford found in the Netflix recommendation contest by using IMDb data to supplement the Netflix ratings training set.

Some excerpts:

Team A came up with a very sophisticated algorithm using the Netflix data. Team B used a very simple algorithm, but they added in additional data beyond the Netflix set: information about movie genres from the Internet Movie Database (IMDB). Guess which team did better?

Team B got much better results, close to the best results on the Netflix leaderboard! I'm really happy for them, and they're going to tune their algorithm and take a crack at the grand prize.

But the bigger point is, adding more, independent data usually beats out designing ever-better algorithms to analyze an existing data set. I'm often surprised that many people in the business, and even in academia, don't realize this.

I do suspect that adding more data from IMDb, Amazon, or some other source will be necessary for anyone to win the Netflix Prize. As I said after working on the data a bit last year, "In my analyses, data simply seemed too sparse in some areas to make any predictions, and supplementing with another data set seemed like the most promising way to fill in the gaps."

Please see also my previous posts, "The advantages of big data and big clusters", "Better understanding through big data", Netflix Prize enabling recommender research", and "The Netflix Prize and big data".

Update: Yehuda Koren from the currently top-ranked BellKor team swung by and commented:

Our experience with the Netflix data is different.

IMDB data and the likes gives more information only about the movies, not about the users ... The test set is dominated by heavily rated movies (but by sparsely rating users), thus we don't really need this extra information about the movies.

Our experiments clearly show that once you have strong CF models, such extra data is redundant and cannot improve accuracy on the Netflix dataset.

Update: Anand has a follow-up post. Some choice excerpts:

Why not have more data and better algorithms?

Scalable algorithms involve only a fixed number of sequential scans and sorts of data (since large data sets must necessarily reside on disk and not RAM). Most algorithms that require random access to data or take time greater than O(N log N) are not scalable to large data sets. For example, they cannot easily be implemented using methods such as MapReduce.

Thus, choosing a more complex algorithm can close the door to using large data sets, at least at reasonable budgets that don't involve terabytes of RAM.

In the case of web search, Google made a big leap by adding links and anchor text, which are independent data sets from the text of web pages. In the case of AdWords, the CTR data was an independent data set from the bid data. And Google ... became a domain registrar so they could add even more data about domain ownership and transfers into their ranking scheme. Google consistently has believed and bet on more data, while trumpeting the power of their algorithms.

You might think that it won't help much to add more of the same data, because diminishing returns would set in ... In many important cases, adding more of the same data makes a bigger difference than you'd think ... [such as when] the application sees the data embedded in a very-high-dimensional space.

Designing for internet scale

James Hamilton wrote a LISA 2007 paper, "On Designing and Deploying Internet-Scale Services" (PDF) with a remarkable brain dump of good advice on building large scale services.

The paper does read like a laundry list, so let me point at what I consider the most important recommendations.

Expect failures and test for them, to the point of never shutting down the system normally -- "crash only software" -- and designing and testing your system so that the "operations team [is] willing and able to bring down any server in the service at any time without draining the workload first."

Automate everything and keep it simple. Failover should be automatic, nothing should require human intervention, and this should be constantly tested. Complexity and dependencies are your enemy when trying to manage all possible failure modes automatically, and James rightly insists on keeping it simple, to the point that he argues that anything that would add complexity without producing order of magnitude improvements should not be implemented.

Test live with rollback, versioning, and incremental rollouts. As long as problems can be quickly reverted, rolling out code live early and often is not expensive or dangerous. More dangerous is "big-bang changes" where many things change at once, making it hard to determine where problems lie and hard to revert to the older version of the code base.

While I agree with almost everything James wrote, I found a few areas where I disagree based on my own experience at Amazon.

First, James wrote that "we like shipping on a 3-month cycle." That hardly seems like early and often to me. I think code should be shipped constantly, multiple times a week or even multiple times a day across different services. On the Web, there is no reason to not ship frequently, and launching continuously forces developers to eliminate any dependencies with other code in their launch while correctly adding pressure on high quality tools for monitoring and debugging the health of the system, versioning, rapid rollbacks, incremental rollouts, and live experiments.

Second, James says we should not "affinitize requests or clients to specific servers". Depending on what he means here, we may disagree, because I think this potentially could conflict with simplifying database design. In particular, it is much easier to do database replication (and James acknowledges that "database scaling remains one of the hardest problems in designing internet scale services") if we stick a user to a specific server for their writes. Then, we can just guarantee the much simpler eventual consistency with rather loose requirements on what eventual means. The counter-argument here is that sticking users to specific servers can create hot spots, but I think that largely can be avoided if we pick the server to stick to for writes in part based on load.

Finally, James advocates for a manual "big red switch" that allows us to throttle our system manually. I think this is in conflict with the idea of automating everything. What I would prefer to see is that the system automatically responds to low load by using more resources and less load by using less, with monitoring, warnings, and ability to override. As James says, "People make mistakes. People need sleep. People forget things." I think it is optimistic to believe that, in the middle of a crisis, people could quickly decide how to optimally throttle back a system so it can maintain the highest level of quality of service at unusual load. But an automated system that has even limited understanding of the cost of its parts could do that.

In all, a great paper, thought-provoking and well worth reading.

Attending ICSWM 2008

I will be at the "International Conference on Weblogs and Social Media" March 30 to April 2 here in Seattle.

If you are interested in weblogs, the networks formed between weblogs, and using those networks for helping people find information and other people, it looks to be a fun conference.

For anyone in Seattle or the SF Bay Area, this is an easy one to attend. Please say hello if you see me there!