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.

The ugly complexities of browser security

Googler Michal Zalewski wrote a "Browser Security Handbook" with a detailed look at many of the security issues in current browsers.

For me, the most interesting part was everything at and after the section "Life outside same origin rules".

As a teaser, here is just one of many examples that Michal discusses:

[An] attacker may cleverly decorate portions of such a third-party UI to make it appear as if they belong to his site instead, and then trick his visitors into interacting with this mashup. If successful, clicks would be directed to the attacked domain, rather than attacker's page -- and may result in undesirable and unintentional actions being taken in the context of victim's account.

[For example,] the attacker may also opt for showing the entire UI of the targeted application in a large <IFRAME>, but then cover portions of this container with opaque <DIV> or <IFRAME> elements placed on top ... [Or] the attacker may simply opt for hiding the target UI underneath his own, and reveal it only miliseconds before the anticipated user click, not giving the victim enough time to notice the switch, or react in any way.

Well worth reading the whole thing.

[Found via Philipp Lenssen]

E-mail as the social network

Om Malik writes that:

Yahoo ... is planning to .... launch in beta relatively soon with half a dozen small applications running in a sidebar inside the Yahoo mail client (Evite is one of the services that is said to be building a nano-app for this new Yahoo Mail-as-a-platform). Users' address books would act as a social graph, essentially turning Yahoo Mail into the basis of a whole new social networking experience.

The only way for Yahoo or Google to challenge the social networking incumbents like Facebook [is] to leverage their email infrastructure ... With relationship buckets pre-defined by the address book, which contains everything from web-based addresses to geo-local data (physical address) to mobile numbers, email clients are already rich with the very data set that Facebook [has].

I liked this idea back when Om talked about it last year and still like it now.

The address book is essentially a social network. Not only does it have friend relationships, but also we can determine the importance of the relationships, the weights of the social connections. Oddly, surprisingly little has been done with that information in e-mail clients.

Perhaps it is fear of breaking something that so many people use and depend on, but e-mail clients have largely stood still over the last several years while social networking applications nibbled away at their market and mind share. What experimentation has occurred seems stuck in startups and research (e.g. Xobni or Inner Circle).

Meanwhile, there seems to be a trend where social networks are creeping toward e-mail clients. For example, Facebook has added limited e-mail functionality within their site as well as Twitter-like microblogging. These features seem intended to make communication dwell within Facebook.com rather than inside e-mail and IM clients.

I admit I am a bit outside of the demographic for heavy social network users, but, from what I can tell, the primary use of social networks is for communication, perhaps with the twist of being focused primarily on dating and entertainment. It makes me wonder if social networks really are a different app from communication apps like e-mail clients or just a different facet of the same idea.

If they are nearly the same, I would expect Yahoo will do much better from implementing social networking features in Yahoo Mail than from attempting to create a new social network such as Yahoo 360. Something similar probably could be said for Orkut and GMail.

Please see also my earlier post, "E-mail versus social networks".

Yahoo's automatic content optimization

Deepak Agarwal along with many others from Yahoo Research have a paper at the upcoming NIPS 2008 conference, "Online Models for Content Optimization", with a fun peek inside of a system at Yahoo that automatically tests and optimizes which content to show to their readers.

It is not made entirely clear which pages at Yahoo use the system, but the paper says that it is "deployed on a major Internet portal and selects articles to serve to hundreds of millions of user visits per day."

The system picks which article to show in a slot from 16 potential candidates where the pool of candidates are picked by editors and change rapidly. The system seeks to optimize the clickthrough rate in the slot. The problem is made more difficult by the way the clickthrough rate on a given article changes rapidly as the article ages and as the audience coming to Yahoo changes over the course of a day, which means the system needs to adapt rapidly to new information.

The paper describes a few variations of algorithms that do explore/exploit by showing the article that performed best recently while constantly testing the other articles to see if they might perform better.

The result was that the CTR increased by 30-60% over editors manually selecting the content that was shown. Curiously, their attempt to show different content to different user segments (a coarse-grained version of personalization) did not generate additional gains, but they say this is almost certainly due to the very small pool of candidate articles (only sixteen articles) from which the algorithm was allowed to pick.

One amusing tidbit in the paper how they describe the culture clash that occurred between maintaining the control the editors were used to and giving the algorithms freedom to pick the content users really seem to want.

I remember similar issues at Amazon way back when we first started use algorithms to pick content rather than editors. It is hard for editors to give up control even to the collective voice of people voting on what they want. While I always have been sympathetic to the need for editorial voice, if it is forcing content on users that they do not actually want, it is important to understand its full cost.

Finding task boundaries in search logs

There has been more talk lately, it seems to me, on moving away from stateless search where each search is independent and toward a search engine that pays attention to your previous searches when it tries to help you find the information you seek.

Which makes that much more relevant a paper by Rosie Jones and Kristina Klinkner from Yahoo Research at CIKM 2008, "Beyond the Session Timeout: Automatic Hierarchical Segmentation of Search Topics in Query Logs" (PDF).

Rosie and Kristina looked at how to accurately determine when a searcher stops working on one task and starts looking for something new. The standard technique people have used in the past for finding task boundaries is to simply assume that all searches within a fixed period of time are part of the same task. But, in their experiments, they find that "timeouts, whatever their length, are of limited utility in identifying task boundaries, achieving a maximum precision of only 70%."

Looking at the Yahoo query logs more closely to explain this low accuracy, they find some surprises, such as the high number of searchers that work on multiple tasks simultaneously, even interleaving the searches corresponding to one task with the searches for another.

So, when the simple stuff fails, what do most people do? Think up a bunch of features and train a classifier. And, there you go, that's what Rosie and Kristina did. They trained a classifier using a set of features that combined characteristics of searcher behavior (e.g. people searching for [tribeca salon] after [new york hairdresser]) with characteristics of the queries (e.g. lexically similar or return similar results from a search engine), eventually achieving much higher accuracy rates on finding task boundaries.

As the authors say, being able to accurately segment tasks could improve our ability to evaluate search engines. In particular, we could seek to minimize the amount of time needed by searchers "to satisfy an information need or fulfill a more complex objective" rather than just looking at click and usage data for one query at a time. Judging search engines by how well they help people get things done is something that, in my opinion, is long overdue.

Please see also my earlier post, "Tasks, not search, at DEMOfall2008", where Head of Yahoo Research Prabhakar Raghavan said that people really don't want to search; what they really want is to fulfill their tasks and get things done.

Detecting spam just from HTTP headers

You have to love research work that takes some absurdly simple idea and shows that it works much better than anyone would have guessed.

Steve Webb, James Caverlee, and Calton Pu had one of these papers at CIKM 2008, "Predicting Web Spam with HTTP Session Information" (PDF). They said, everyone else seems to think we need the content of a web page to see if it is spam. I wonder how far we can get just from the HTTP headers?

Turns out surprisingly far. From the paper:

In our proposed approach, the [crawler] only reads the response line and HTTP session headers ... then ... employs a classifier to evaluate the headers ... If the headers are classified as spam, the [crawler] closes the connection ... [and] ignores the [content] ... saving valuable bandwidth and storage.

We were able to detect 88.2% of the Web spam pages with a false positive rate of only 0.4% ... while only adding an average of 101 [microseconds] to each HTTP retrieval operation .... [and saving] an average of 15.4K of bandwidth and storage.

It appears that web spammers tend to use specific IP ranges and put unusual gunk into their headers (e.g. "X-Powered-By" and "Link" fields), which makes it fairly easy to pick them out just from their headers. As one person suggested during the Q&A for the talk, spammers probably would quickly correct these oversights if it became important, but you still have to give credit to the authors for this cute and remarkably effective idea.

If you might enjoy another example of making remarkable progress using a simple idea, please see my earlier post, "Clever method of near duplicate detection". It summarizes a paper about uniquely identifying the most important content in a page by looking around the least important words on the page, the stop words.

Measuring offline ads by their online impact

Googlers Diane Lambert and Daryl Pregibon had a paper at AdKDD 2008, "Online Effects of Offline Ads" (PDF), with a fun look at how far we can get measuring the impact of offline advertising by increases in search queries or website visits.

Some excerpts:

One measure of offline ad effectiveness is an increase in brand related online activity .... As people spend more time on the web, [the] steps toward purchase increasingly include searching for the advertiser's brand or visiting the advertiser's websites, even if the ad campaign was in an offline medium such as print, radio, or TV.

There are two obvious strategies for estimating the [gain] ... We can assume that the past is like the present and use daily outcomes before the campaign ran ... [but] the "before" number of visits ... is not necessarily a good estimate ... if interest in the product is expected to change over time even if no ad campaign is run. For example, if an ad is more likely to be run when product interest is high, then comparing counts-after to counts-before overstates the effect of the campaign.

Alternatively, we could estimate the [gain] ... by the outcome in control DMAs, which are markets in which the ad did not appear ... One problem, though, is that the advertiser may be more likely to advertise in DMAs where the interest in the product is likely to be high.

The paper goes on to detail the technique used and the ability of the technique to detect changes in very noisy traffic data.

This paper is part of a larger group of fun and remarkably successful work that tries to predict offline trends from online behavior. One example that recently received much press attention is Google Flu Trends, which uses searches for flu-related terms to predict real flu outbreaks. Another example is recent work out of Yahoo Research and Cornell to find the physical location of objects of interest from a combination of search terms and geolocation data.

Learning not to advertise

Andrei Broder and a large crew from Yahoo Research had a paper at CIKM 2008, "To Swing or not to Swing: Learning when (not) to Advertise" (PDF), that is a joy to see for those of us that are hoping to make advertising more useful and less annoying.

The paper starts by motivating the idea of sometimes not showing ads:

In Web advertising it is acceptable, and occasionally even desirable, not to show any [ads] if no "good" [ads] are available.

If no ads are relevant to the user's interests, then showing irrelevant ads should be avoided since they impair the user experience [and] ... may drive users away or "train" them to ignore ads.

The paper looks at a couple approaches on when to show ads, one based on a simple threshold on the relevance score produced by Yahoo's ad ranking system, another training a more specialized classifier based on a long list of features.

An unfortunate flaw in the paper is that the system was evaluated using a manually labeled set of relevant and irrelevant ads. As the paper itself says, it would have been better to consider expected revenue and user utility, preferably using data from actual Yahoo users. But, with the exception of a brief mention of "preliminary experiments ... using click-through data" that they "are unable to include ... due to space constraints", they leave the question of the revenue and user satisfaction impact of not showing ads to future work.

Please see also the related work out of Google on limiting the damage from irrelevant ads that I describe in my previous posts, "Advertising auctions and modeling externalities" and "Hal Varian on advertising auctions".

Please see also my summary of Andrei Broder's industry day talk at CIKM 2008 in my earlier post, "More on computational advertising".

Baidu on next generation search

Baidu Chief Scientist William Chang gave an industry day talk at CIKM 2008 on the next generation of search where he predicted an industry-wide move toward personalized web search.

William first described two earlier generations of search, then said the upcoming third generation of search would be the "internet as a matching network". He expected to see an integration of search and recommendations, where recommendations are used to find related concepts, entities, phrases, documents, and sources.

As part of this, he expected to see a renewed interest in the diversity of search results -- he described it as relevance versus user satisfaction -- that appeared to be going down the path of information exploration and search as a dialogue to better help searchers with the task behind the search phrase.

William also briefly mentioned personalized spidering. While he did not elaborate, I would guess he meant software agents gathering, synthesizing, and summarizing information from several deep web sources to satisfy a complicated task.

This talk was one of the ones recorded by videolectures.net and should appear there in a week or so.

Please see also my earlier post, "Rakesh Agrawal at CIKM 2008", that summarizes Rakesh's predictions about a new interest in diversity and discovery in web search.

Please see also my earlier post, "More on computational advertising", which summarizes Andrei Broder's CIKM talk on integrating of advertising and recommendations.

Update: William Chang asked me to add that "this talk reflects my personal views on cutting-edge search, not necessarily the company's."

As the Internet grows, so does Google

In two insightful posts, "The Omnigoogle" and "The cloud's Chrome lining", Nick Carr cleanly summarizes how Google benefits from the growth of the Web and why expanding Web use makes sense as a large part of their business strategy.

Some excerpts:

[Google] knows that its future ... hinges on the continued rapid expansion of the usefulness of the Internet, which in turn hinges on the continued rapid expansion of the capabilities of web apps, which in turn hinges on rapid improvements in the workings of web browsers .... [Chrome's] real goal ... is to upgrade the capabilities of all browsers.

The way Google makes money is straightforward: It brokers and publishes advertisements through digital media. More than 99 percent of its sales have come from the fees it charges advertisers for using its network to get their messages out on the Internet.

For Google, literally everything that happens on the Internet is a complement to its main business. The more things that people and companies do online, the more ads they see and the more money Google makes.

Just as Google controls the central money-making engine of the Internet economy (the search engine), Microsoft controlled the central money-making engine of the personal computer economy (the PC operating system).

In the PC world, Microsoft had nearly as many complements as Google now has in the Internet world, and Microsoft, too, expanded into a vast number of software and other PC-related businesses - not necessarily to make money directly but to expand PC usage. Microsoft didn't take a cut of every dollar spent in the PC economy, but it took a cut of a lot of them.

In the same way, Google takes a cut of many of the dollars that flow through the Net economy. The goal, then, is to keep expanding the economy.

Testing rankers by interleaving search results

Filip Radlinski, Madhu Kurup, and Thorsten Joachims had a paper at CIKM 2008, "How Does Clickthrough Data Reflect Retrieval Quality?" (PDF), with a surprising result on learning to rank using click data.

Specifically, they found that, instead of testing two search rankers in a normal A/B test (e.g. 50% of users see ranker A, 50% see ranker B), showing all searchers an interleaved combination of the two possible search result orderings makes it much easier to see which ranker people prefer. The primary explanation the authors give for this is that interleaving the results gives searchers the easier task of expressing a relative preference between the two rankers.

Some excerpts from the paper:

Unlike expert judgments, usage data ... such as clicks, query reformulations, and response times ... can be collected at essentially zero cost, is available in real time, and reflects the value of the users, not those of judges far removed from the users' context. The key problem with retrieval evaluation based on usage data is its proper interpretation.

We explored and contrasted two possible approaches to retrieval evaluation based on implicit feedback, namely absolute metrics and paired comparison tests ... None of the absolute metrics gave reliable results for the sample size collected in our study. In contrast, both paired comparison algorithms ... gave consistent and mostly significant results.

Paired comparison tests are one of the central experiment designs used in sensory analysis. When testing a perceptual quality of an item (e.g. taste, sound) ... absolute (Likert scale) evaluations are difficult to make. Instead, subjects are presented with two or more alternatives and asked ... which of the two they prefer.

This work proposes a method for presenting the results from two [rankers] so that clicks indicate a user's preference between the two. [Unlike] absolute metrics ... paired comparison tests do not assume that observable user behavior changes with retrieval quality on some absolute scale, but merely that users can identify the preferred alternative in direct comparison.

Please see also my older post, "Actively learning to rank", which summarizes some earlier very interesting work by Filip and Thorsten.

Update: Filip had a nice update to this work in a SIGIR 2010 paper, "Comparing the Sensitivity of Information Retrieval Metrics". Particularly notable is that only x10 as many clicks are required as explicit judgments to detect small changes in relevance. Since click data is much easier and cheaper to acquire than explicit relevance judgments, this is another point in favor of using online measures of relevance rather than the older technique of asking judges (often a lot of judges) to compare the results.

Tasks, not search, at DEMOfall08

Philipp Lenssen points to a video of a DEMOfall08 panel on "Where the Web is Going" that included Peter Norvig from Google and Prabhakar Raghavan from Yahoo.

What is notable in the talk is that (starting at 12:32) Prabhakar and Peter agree that, rather than supporting only one search at a time, search engines will soon focus on helping people get a bigger task done.

Prabhakar says:

I think the next step that faces us ... is divining the intent of what people are doing [and] fulfilling their tasks, getting what they need to get done.

People intrinsically don't want to search. People don't come to work every day saying I need to search ... They want to run their lives.

The notion of a [mere] retrieval engine as the ultimate [tool] is incredibly limiting. We have to get much further along to task completion and fulfillment.

The current world of search engines [are] stateless ... In the act of completing a task -- booking a vacation, finding a job -- you spend hours and days start to end. In the process, you make repeated invocations of search engines ... And all the while the search engine has no state about you. It doesn't recognize that you are in the midst of a task.

What does it take to recognize an intent and synthesize an experience that satisfies an intent? So, if it is a vacation you are planning, it should say ... here is a package I recommend that is based on your budget, the fact that you have two kids, that you don't want to go to too many museums. That's the future we have to get to.

Peter says:

We have to get a lot farther in saying what is it that the user means both in ... tasks where there is a clear intent ... and [even] more so in cases where it is exploratory.

We see this all the time that the user has some area he wants to figure out -- let's say a medical problem -- and the user starts out by kind of floundering around not sure what to talk about and then he reads some document and then he starts to learn the lingo. And, now they say, I don't say funny red splotch, I use this medical term and now I'm on the right track.

We have to accelerate that process ... not make the user do all the work.

There is an interesting shift here from a model where each search is independent to one where a search engine may expect searchers to do multiple searches when trying to accomplish their tasks.

That new model could take the form of search as a dialogue (a back-and-forth with the search engine focused on helping you understand what information is out there), personalized search (re-ranking your results based on your past actions, interests, and goals), or recommender systems (helping you discover interesting things you might not know exist using what people like you found interesting). Most likely, I would expect, it would require a combination of all three.

More on computational advertising

Yahoo Fellow, VP, and computational advertising guru Andrei Broder gave a talk at CIKM 2008 on "The Evolving Computational Advertising Landscape" with some notable details that were missing from his previous talks on this topic.

Specifically, Andrei described "the recommender system connection" with advertising where we want "continuous CTR feedback" for each (query, ad) pair to allow us to learn the "best match between a given user in a given context and a suitable advertisement". He said this was "closest to a recommender system" because, to overcome sparse data and get the best match, we need to find similar ads, pages, and users.

At this point, Andrei offered a bit of a tease that an upcoming (and not yet available) paper that has Yehuda Koren as a co-author will talk more on this topic of treating advertising as a recommender problem. Yehuda Koren recently joined Yahoo Research and is one of the members of the top-ranked team in the Netflix recommender contest.

Andrei continued on the theme of personalization and recommendations for advertising, talking briefly about personalized ad targeting and saying that he thought short-term history (i.e. the last few queries) likely would be more useful than long-term history (i.e. a subject-interest profile).

Andrei also talked about several other topics that, while covered in his older talks, also are quite interesting. He contrasted computational advertising and classical advertising, saying that the former uses billions of ads and venues, has liquid market, and is personalizable, measurable, and low cost. He described the four actors in an advertising market -- advertisers, ad agencies, publishers, and users -- and said they advertising engines have the difficult task of optimizing the four separate and possibly conflicting utility functions of these actors. He talked about the ideal of "advertising as a form of information" rather than as an annoyance, the key there being making it as useful and relevant as possible. And, he spent some time on mobile advertising, talking about the very interesting but slightly scary possibilities of using precise locations of individuals and groups over time to do "instant couponing" to nearby stores (where what we mean by nearby is determined by your current speed and whether that makes it clear that you are in a car), to recognize which stores are open and which stores are popular, to predict lifestyle choices and interests of individuals and groups, and to make recommendations.

This talk was one of the ones recorded by videolectures.net and should appear there in a week or so.

Please see also my previous posts on related topics including "Google describes perfect advertising", "Recommending advertisements", and "What to advertise when there is no commercial intent?"

Data is good, code is a liability

Googler Peter Norvig gave a talk at industry day at CIKM 2008 that, despite my fascination with all things Peter Norvig, almost frightened me off by including the phrase "the Ultimate Agile Development Tool" in its title.

The talk redeemed itself in the first couple minutes, citing Steve Yegge's "Good Agile, Bad Agile" and making it clear that Peter more meant being agile than Agile.

His core point was that "code is a liability". Relying on data over code as much as possible allows simpler code that is more flexible, adaptive, and robust.

In one of several examples, Peter put up a slide showing an excerpt for a rule-based spelling corrector. The snippet of code, that was just part of a much larger program, contained a nearly impossible to understand let alone verify set of case and if statements that represented rules for spelling correction in English. He then put up a slide containing a few line Python program for a statistical spelling correction program that, given a large data file of documents, learns the likelihood of seeing words and corrects misspellings to their most likely alternative. This version, he said, not only has the benefit of being simple, but also easily can be used in different languages.

For another example, Peter pulled from Jing et al, "Canonical Image Selection from the Web" (ACM), which uses a clever representation of the features of an image, a huge image database, and clustering of images with similar features to find the most representative image of, for example, the Mona Lisa on a search for [mona lisa].

Peter went on to say to say that more data seems to help in many problems more than complicated algorithms. More data can hit diminishing returns at some point, but the point seems to be fairly far out for many problems, so keeping it simple while processing as much data as possible often seems to work best. Google's work in statistical machine translation works this way, he said, primarily using the correlations discovered between the words in different languages in a training set of 18B documents.

The talk was one of the ones recorded by videolectures.net and should appear there in a week. If you cannot wait, the CIKM talk was similar to Peter's startup school talk from a few months ago, so you could use that as a substitute.