Web Research

This page covers research that's at least peripherally related to the web. For non web-related work, look here.

What's new
Surveys and tutorials
User targeting
Searching and querying large-scale data
Web graph analysis
Communities, blogs, and social networks
WebFountain and content analysis
Taxonomies

What's new

I might be missing a few things here -- drop me a note if you need a paper you don't see. Also, these papers should at some point also appear categorized below, but I haven't yet categorized and entered full cites for the stuff from May 2007 and onwards.

Update from November 2008

We wrote a series of three papers on privacy in query logs. The first paper assesses vulnerabilities in a specific scheme for anonymizing logs: hashing tokens securely into identifiers. The second paper suggests that the removal of personally-identifiable information from logs is problematic, as seemingly innocuous queries can in aggregate reveal personal information. Finally, the third paper covers a family of schemes that seek to provide privacy by grouping users into buckets, and explores certain families of attacks.

This SIGMOD 2008 paper describes the Pig system for large-scale data processing, a more flexible extension of the map-reduce framework.

This paper from WSDM 2008 describes some large-scale experiments on Yahoo! groups, and characterizes people who tend to receive preferential treatment upon joining and group, and then continue on to influence within the group.

Another WSDM 2008 paper gives an approach to studying the macroscopic structure of large bipartite graphs called the KNC-plot, and also describes some algorithms to compute it.

This paper from KDD 2008 gives a detailed study of edge-by-edge evolution of four large social networks, and compared various models of evolution based on likelihood rather than based on aggregate statistics.

A paper from VLDB 2008 describes a new approach to generalization in search: given a universe of, say, restaurants, and a query for a particular cuisine type in a particular location, we give ways to efficiently generalize the location and/or the cuisine type if the initial query returns no results.

Update from January 2008

A paper in IEEE Computer describes the PeopleWeb, in which a user's social environment travels between sites with the user. This paper also gives some trends in the growth of online content.

Update from May 2007

I worked some years ago on a project called CLEVER, which was follow-on work to Jon Kleinberg's HITS algorithm, done at IBM Almaden. We finally put together an end-to-end algorithmic description of the CLEVER system.

We have a poster at WWW 2007 on some alternatives to personalized pagerank; a short two-page poster paper gives an overview.

The last few years have shown some very interesting results on the nature of web crawling; see the work of Junghoo Cho and Chris Olston for some nice examples. A new paper shows an analysis of how efficiently new web content can be discovered, with varying levels of insight into the right places to look for them.

We have a paper in the Data Engineering Bulletin that gives a high-level overview of many of the key research directions that Yahoo! Research is pursuing.

Update from late 2006

We looked at a large social network to understand how friendship relates to geographic separation, and found that two people being friends is a function less of the distance between them than of the number of people between them. We introduced a model of friendship formation based on this intuition, and showed that the model produces social networks with short paths for arbitrary population densities. The results are in a paper in PNAS. The same work also has a more theoretical component, in which we analyze this rank-based friendship and show results for arbitrary metric spaces. These results are in a paper in ESA 2006.

At the same time, we've been looking at various questions about the evolution of social networks. We looked at the contacts networks within Flickr and Yahoo! 360, and found some surprising results about the number of nontrivial disconnected components in the social network over time. The results appear in a short paper in KDD 2006.

A couple of years ago, we did some work on the nature of templates appearing on websites, and showed that roughly half of the content on the web comes from templates. This work appears in an industrial track paper in WWW 2005. Recent work extends the thread of site-level analysis to explore algorithms for segmenting a website into topics based on its hierarchical structure. This new work appears in a paper in KDD 2006.

We've also done some work on clustering objects that evolve over time. There's a short paper in KDD 2006.

In follow-up to various work on measuring the size of collections of objects, we have a new approach appearing in a paper in CIKM 2006.

We've done some recent work on large dense subgraph discovery using a weakened formulation of a dense subgraph. The algorithmic approach is an iterated form of shingling a graph, in which each step concentrates dense subgraphs and removes sparse subgraphs. A paper in VLDB 2005 covers the results.

General audience surveys

This article from Scientific American gives an overview of search and related techniques that make use of link analysis over hyperlinked corpora. S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Hypersearching the web. Scientific American, June 1999. ( html )

This is a brief summary of some results on web structure, covering HITS, the bow tie model, and the fractal structure of the web. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins: The Web and Social Networks. IEEE Computer 35(11): 32-36 (2002) (pdf)

This is a slightly more detailed view of applications that make use of the web's link structure; it's getting a little dated. S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Mining the web's link structure. IEEE Computer, August 1999. ( pdf )

This paper in CACM 2004 gives an analysis of the bloggers on the LiveJournal blog-hosting site: their interests, locations, and demographics, from the perspective of the social network.

Tutorials

This is a tutorial that Jon Kleinberg and I gave at PODS99 on linear algebra techniques in information retrieval -- it's a broad introduction to the area that assumes little background beyond basic linear algebra. J. Kleinberg and A. Tomkins. Applications of linear algebra in information retrieval and hypertext analysis. In Proceedings of the 18th ACM Symposium on Principles of Database Systems, 1999. ( pdf )

R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Social networks: From the web to knowledge management. Book chapter in Web Intelligence, editors: Ning Zhong, Jiming Liu, Yiyu Yao, by Springer-Verlag, pages 367--379, January 2003. (pdf)

These slides are from part of an AMS tutorial. They cover some basic introductory remaks about power laws and related heavy-tailed distributions, and discuss a set of generative models for these distributions. Slides from an AMS tutorial on power laws and generative models.