Stanford InfoLab Publication Server

Representing Web Graphs

Raghavan, Sriram and Garcia-Molina, Hector (2002) Representing Web Graphs. Technical Report. Stanford.




A Web repository is a large special-purpose collection of Web pages and associated indexes. Many useful queries and computations over such repositories involve traversal and navigation of the Web graph. However, efficient traversal of huge Web graphs containing several hundred million vertices and a few billion edges is a challenging problem. This is further complicated by the lack of a schema to describe the structure of Web graphs. As a result, naive graph representation schemes can significantly increase query execution time and limit the usefulness of Web repositories. In this paper, we propose a novel representation for Web graphs, called an \textit{S-Node representation}. We demonstrate that S-Node representations are highly space-efficient, enabling in-memory processing of very large Web graphs. In addition, we present detailed experiments that show that by exploiting some empirically observed properties of Web graphs, S-Node representations significantly reduce query execution times when compared with other schemes for representing Web graphs.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:S-Node representation, Web graphs, Web repositories, graph traversal, WebBase, navigation queries
Subjects:Computer Science > Databases and the Web
Projects:Digital Libraries
Related URLs:Project Homepage
ID Code:541
Deposited By:Import Account
Deposited On:11 Jun 2002 17:00
Last Modified:30 Jul 2009 12:10

Download statistics

Repository Staff Only: item control page