Modeling how searchers look at search results

Georges Dupret and Benjamin Piwowarski from Yahoo Research had a great paper at SIGIR 2008, "A User Browsing Model to Predict Search Engine Click Data from Past Observations" (ACM page). It nicely extends earlier models of searcher behavior to allow for people skipping results after hitting a lot of uninteresting results.

An extended excerpt:

Click data seems the perfect source of information when deciding which documents (or ads) to show in answer to a query. It can be thought of as the results of users voting in favor of the documents they find interesting.

Nevertheless, [click data] cannot be used without further processing: A fundamental problem is the position bias. The probability of a document being clicked depends not only on its relevance, but on other factors as its position on the result page ... Eye-tracking experiments show that a user is less likely to examine results near the bottom of the list ... [and] that a document is not clicked with the same frequency if situated after a highly relevant or mediocre document.

The Cascade Model assumes that users view search results from top to bottom, deciding whether to click each result before moving to the next ... The cascade model is based on a simplistic behavior model: Users examine all the documents sequentially until they find a relevant document and then abandon the search.

We generalize this and allow for the possibility that a user skips a document without examining it .... We propose that the probability of examination is dependent on the distance d from the last click as well as on the position r in the ranking. The intuition behind using the distance is that a user tends to abandon the search after seeing a long sequence of unattractive snippets on the page.

Our solution outperforms very significantly all previous models ... Our findings confirm that [users] almost always see the document directly after the clicked document .. and explain why documents situated just after a very relevant document are clicked more often.

The paper also discusses a "multiple browsing model" that attempts to capture that different people browse differently on different types of queries (e.g. navigational vs. informational), but that model, surprisingly, failed to yield an improvement.

Please see also Craswell et al., "An Experimental Comparison of Click-Position Bias Models" (PDF), a fun WSDM 2008 paper that proposes a Cascade Model for how searchers review search results.

Read More

Easy processing of massive data sets

Ronnie Chaiken, Bob Jenkins, Per-Ake Larson, Bill Ramsey, Darren Shakib, Simon Weaver, and Jingren Zhou have an upcoming paper at VLDB 2008, "SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets" (PDF), that describes a parallel data processing tool "being used daily ... inside Microsoft" on "large clusters ... of thousands of commodity servers" over "petabytes of data".

Scope is similar to Yahoo's Pig, which is a higher level language on top of Hadoop, or Google's Sawzall, which is a higher level language on top of MapReduce. But, where Pig focuses on and advocates a more imperative programming style, Scope looks much more like SQL.

Some excerpts from the paper:

Internet companies store and analyze massive data sets, such as search logs, web content collected by crawlers, and click streams collected from a variety of web services .... Several companies have developed distributed data storage and processing systems on large clusters of shared nothing commodity services including Google's File System, Bigtable, MapReduce, Hadoop, Yahoo!'s Pig system, Ask.com's Neptune, and Microsoft's Dryad.

We present a new scripting language, SCOPE. Users familiar with SQL require little or no training to use SCOPE. Like SQL, data is modeled as a set of rows composed of typed columns. Every rowset has a well-defined schema ... It allows users to focus on the data transformations required to solve the problem at hand and hides the complexity of the underlying platform and implementation details.

SCOPE [also] is highly extensible ... users can easily define their own ... operators: extractors (parsing and constructing rows from a file), processors (row-wise processing), reducers (group-wise processing), and combiners (combining rows from two inputs) ... [which] allows users to solve problems that cannot easily be expressed in traditional SQL.

The paper goes on to provide many examples of code written in Scope, describe the underlying Cosmos append-only distributed file system, discuss query plans for executing Scope programs, and touch on some of Scope's compile and run-time optimizations.

Though I probably shouldn't, let me add that, in my experience, Scope is great fun. It's like all the data and computation I can eat. And I can eat a lot.

Please see also my past posts on related work, including "Yahoo, Hadoop, and Pig Latin", "Sample programs in DryadLINQ", "Automatic optimization on large Hadoop clusters", and "Yahoo Pig and Google Sawzall".

Please see also my Dec 2005 post, "Making the impossible possible", which quotes Nobel Prize winner Tjalling Koopmans as saying, "Sometimes the solution to important problems ... [is] just waiting for the tool. Once this tool comes, everyone just flips in their head."

Read More

Kai-Fu Lee keynote at SIGIR

Googler Kai-Fu Lee gave a keynote talk yesterday at SIGIR 2008 on "The Google China Experience".

The Google China experience has been fraught with difficulties. As Kai-Fu said, Google was expecting that their search engine could succeed in China with the same interface and approach that had worked so well elsewhere, but was "humbled" by the lack of uptake.

Why did a Google that had worked well elsewhere not succeed in China?

Kai-Fu argued that two unusual features of Chinese internet users, their youth and their language, appears to explain the difference.

While showing examples of sites that did succeed in China, Kai-Fu argued that the young, novice, hurried average Chinese user is looking less for navigation or one authoritative sources of information and more for entertainment and broad surveys of information.

Google China was optimized for finding the one site you need to go to, as it is elsewhere, but, Kai-Fu said, according to eyetracking studies and log data, Chinese users tend to be much less task-oriented, read much more of the page, and click many more links than US users.

So, Google started to offer up more opportunities for exploration and discovery -- by being much more aggressive with query suggestions and universal search, for example, and by adding browse links to the Google front page rather than just having a stark page with just a search box -- rather than just trying to give a quick answer and let people move on.

Kai-Fu suggested that the Chinese interest in browsing and exploration also may have roots in the Chinese language itself. Chinese is slower and more work to type than other languages, but more compact to read. This seems to cause a preference for clicking over typing and a preference for pages dense with information over the sparsity Google tended to favor in other countries.

One curious question that Kai-Fu raised was whether these preferences will remain true over time. Expert internet users tend to be more task-oriented than novice users. Google China has had much more success in gaining market share in China among expert users.

It may be the case that, as people gain more experience with the Web and what is available on the Web, their behavior shifts from browse to search, from exploration of what is out there to finding the information they know must exist.

Update: Paul Heymann at Stanford Infolab posts an excellent summary of Kai-Fu Lee's talk, as well as notes on other talks at SIGIR.

Read More

Learning diversity when learning to rank

Filip Radlinski, Robert Kleinberg, and Thorsten Joachims have a ICML 2008 paper, "Learning Diverse Rankings with Multi-Armed Bandits" (PDF), that attempts to "directly learn a diverse ranking of documents based on users' clicking behavior."

An excerpt:

[We] show how clickthrough data can be used to learn rankings maximizing the probability that any new user will find at least one relevant document high in the ranking .... [even though] web queries often have different meanings for different users.

We propose an online learning approach for learning from usage data. As training data is being collected, it immediately impacts the rankings shown ... The goal is to minimize the total number of poor rankings displayed over all time.

The work appears to be largely theoretical due to very long convergence times -- sadly, investigating "how prior knowledge can be incorporated ... to improve the speed of convergence" is left to future work -- but still is a worthwhile and enjoyable read.

Please see my previous post, "Actively learning to rank", that discusses a fun KDD 2007 paper also by Filip Radlinski and Thorsten Joachims on learning to rank from click data.

Update: Two years later, Filip publishes a paper that appears to have a more practical and scalable technique for learning diversity from click data, "Learning optimally diverse rankings over large document collections". More nice work there from Filip.

Read More

Automatic optimization on large Hadoop clusters

Chris Olston, Benjamin Reed, Adam Silberstein, and Utkarsh Srivastava at Yahoo Research had a USENIX 2008 paper, "Automatic Optimization of Parallel Dataflow Programs" (PDF), that looks at optimizations for large-scale Hadoop clusters using Pig.

The paper says that it is only attempting "to suggest some jumping-off points for [optimization] work." With much of the paper spending a fair amount of time on "textbook ... optimizations" such as early projection and filtering, operator rewrites, and physical execution plans for joins, parts do read like a survey.

The part that looks at work sharing between jobs, however, goes beyond a survey and is quite interesting. I was particularly intrigued by the discussion of materialized views, which the authors suggest could be used to cache the results of common operations. One common early computation in these cluster is to extract a few fields from a file and then sort the extract based on one or more of the fields before doing additional processing. If that were cached, this could look a bit like lazily creating indexes over the data the first time they are needed. A fun idea, and one that could narrow the gap between Map-Reduce databases and more traditional databases.

One other interesting tidbit in the paper is that the authors argue that high level languages like Pig for programming large-scale parallel computations will become dominant over "direct Map-Reduce or Dryad programs" in a "mass migration" as "good optimization technology" is implemented, "analogous to the migration from assembly to C-style languages to Java-style languages."

Please see also a paper by some of the same authors, "Parallel Evaluation of Composite Aggregate Queries" (PDF). That paper looks at reducing expensive data combining operations in Hadoop clusters by implementing a "cross-node data redistribution strategy that takes into account the nested structure of a query ... such that aggregations can be generated locally" for a type of aggregation query.

Please see also my earlier post, "Hadoop and scheduling", that discusses another paper by some of the same authors and its look at a method of combining many jobs on a Hadoop cluster that all want to access the same raw data files.

Read More

Social peer-to-peer and Tribler

I finally got to a fun paper I have been meaning to read for some time, "Tribler: A social-based peer-to-peer system" (PDF).

What is interesting about the paper is that it proposes a combination of social networking and P2P for content sharing that not only is designed to produce recommendations from friends and users with similar tastes in the network, but also uses those friend relationships to speed downloads, reduce free-riding, and encourage good behavior.

An excerpt:

Most current P2P file-sharing systems treat their users as anonymous, unrelated entities ... [Tribler is] a novel social-based P2P file-sharing paradigm that exploits social phenomena by maintaining social networks and using these in content discovery, content recommendations, and downloading.

Tribler performs content discovery and recommendation based on the notion of taste buddies, that is, users with the same tastes or interests .... The ... interface facilitate[s] the formation of social groups ... [which] may help reduce anti-social behavior.

A user invokes the help of his friends to speed up downloads ... Peers contribute their bandwidth by joining a swarm even if they are not interested in the content being distributed in this swarm ... [Past work assumed] sufficient altruism ... [which] makes ... [it] impractical ... Our [approach] solves this problem by introducing social-group incentives.

Tribler is an open source project. More information at tribler.org, especially on their research page.

Read More

Going to SIGIR

I will be at SIGIR 2008 next week in Singapore. If you make it to what is very nearly the antipode for those of us in the US, please say hello!

Read More