PAPERThis paper was unfortunately omitted from the print version of the June 2008 issue of Sigir Forum.
Please cite as SIGIR Forum June 2008, Volume 42 Number 1, pp 78-83

A Large TimeAware Web Graph
Paolo Boldi
boldi@dsi.unimi.it

Massimo Santini
santini@dsi.unimi.it

Sebastiano Vigna
vigna@dsi.unimi.it
Dipartimento di Scienze dell'Informazione
Università di Milano, Italy
Abstract
We describe the techniques developed to gather and distribute in a highly compressed, yet accessible, form a series of twelve snapshot of the .uk web domain. Ad hoccompression techniques made it possible to store the twelve snapshots using just 1.9 bits
per link, with constant-time access to temporal information. Our collection makes it
possible to study the temporal evolution link-based scores (e.g., PageRank), the growthof online communities, and in general time-dependent phenomena related to the link
structure.

1 Introduction
By now, several sources provide accessible snapshots of web data. The Stanford WebBase
project, for instance, provides hundreds of Terabytes of such data. In the last years, theLAW (Laboratory for Web Algorithmics) focused its eorts on web graphs instead.
Within the DELIS project, interest rose about temporal link analysis, that is, studying
how the web-graph nodes and arcs evolves in time. Since without proper bounds the amountof information required by this activity is staggering, we decided to concentrate our eorts
on gathering twelve monthly 100 Mpages snapshots of the .uk domain and store them in aformat that would make temporal link information accessible on a standard workstation.
The basis of our work is WebGraph [2], a framework for web graph compression thatcurrently provides the best compression available (in terms of bits per link) and whose data
can be accessed using free Java or C++ code [6]. One of the main challenges of this work
was to extend WebGraph so that it would compress eciently labels representing temporal
information. Moreover, we wanted to extend the standard WebGraph exible approach, thatACM SIGIR Forum

33

Vol. 42 No. 2 December 2008

makes it always possible to load data into main memory or access it in oine form (with aperformance drop, of course).

2 Gathering the Snapshots
The snapshots have been taken at the start of each month, during a period of 7 − 10 days,
using the bandwidth provided by the Università degli Studi di Milano and a cluster of PCs
that has been funded by the DELIS project. Some basic information about the snapshots isshown in Table 1.
Crawling parameters. As in any limited-size crawl, it is essential to dene the crawl
parameters (the stopping criterion is clearly that of reaching about 100 Mpages, without
counting duplicates). We highlight the main features:

Crawl policy. We use UbiCrawler's [1] built-in per-host breadth-rst visit. A number ofthreads scan in parallel distinct hosts, and newly discovered URLs are added to a queue.
When a thread completes its visit, it extracts from the queue the rst URL whose hosthas an IP address that is not currently being visited, and starts visiting that host inbreadth-rst fashion.

Seed. The seed is a large (190 000 elements) set of URLs obtained from the Open Directory
Project. The reason for such a large seed is that of making the crawl more stable andrepeatable, and reduce the amount of spam (as links in the Open Directory Project arejudged by humans).

Maximum number of pages per host. We limited each host to a maximum of 50 000pages. This guarantees that we shall crawl at least 2 000 hosts, and limits the impact
of web traps and database-driven sites.

Maximum inter-host depth. We do not delve more than 16 levels in a host. The main
reason for a limit in depth is avoiding traps and also badly congured 404 pages, whichsometimes generate an innite number of links by prex buildup.

URL normalisation. URLs are normalised following the strategy explained in the BURL1

Java class. We apply all safe normalisations, escape all illegal characters, and treat ina special way square brackets as they are ubiquitously (although erroneously) used in
an unescaped form.

Duplicate detection. Many pages are duplicates, and to detect their presence we maintaina set of 64-bit ngerprints obtained after stripping attributes (of HTML elements) andother non-relevant parts of the page. When a duplicate is detected we just store apointer to the original page. About 25% of the overall pages happen to be duplicates.

1 The class is available in bundle with the LAW software, downloadable at http://law.dsi.unimi.it/.

ACM SIGIR Forum34Vol. 42 No. 2 December 2008

June
July
AugustSeptember
OctoberNovember
DecemberJanuary
February
MarchApril
May

June
July
AugustSeptember
OctoberNovember
DecemberJanuary
February
March
April
May

Pages
112 386 763
136 956 559
141 395 895
148 965 298
129 558 491
150 146 132
144 489 446
151 578 113
153 966 540
151 427 461
150 606 689
150 054 551
Nodes
80 644 902
96 395 298
100 751 978106 288 541
93 463 772
106 783 458
103 098 631
108 563 230
110 123 614
107 565 084
106 867 191
105 896 555

Size (GB)
1 893
2 287
2 424
2 756
2 336
2 637
2 552
2 651
2 692
2 568
2 700
2 658
Arcs
2 481 281 617
3 030 665 444
3 250 153 746
3 871 625 613
3 130 910 405
3 479 400 938
3 768 836 665
3 929 837 236
3 944 932 566
3 642 701 825
3 790 305 474
3 738 733 648

GZip'd Size (GB)
402
477
507
546
478
546
525
553
564
545
559
556
Size (GB)
0.89
1.16
1.23
1.321.03
1.16
1.34
1.38
1.39
1.34
1.36
1.30

bit/arc
3.07
3.30
3.25
2.93
2.83
2.86
2.77
2.72
2.74
2.84
2.79
2.69

Table 1: Per-snapshot full-text and web-graph stats.

ACM SIGIR Forum

35

Vol. 42 No. 2 December 2008

Jun
JulAug
Sep
Oct
Nov
Dec
JanFebMar
AprMay

Jun
94.9

Jul
73.3
130.7

Aug
71.6
102.2
128.5

Sep
69.8
99.4
102.8
136.6

Oct
65.5
89.9
84.9
88.0
109.9

Nov
64.5
90.9
90.3
94.6
86.1
121.2

Dec
59.4
81.4
81.0
84.3
75.8
86.7
113.4

Jan
62.4
86.786.4
90.8
81.1
91.4
88.8
125.1

Feb
62.4
88.1
86.7
89.6
81.6
91.5
84.3
94.2
122.9

Mar
58.9
84.0
81.9
84.9
76.6
84.1
79.2
86.4
91.0
122.5

Apr
57.6
82.7
80.0
82.0
75.6
82.3
76.2
84.4
87.8
84.9
113.1

May
57.7
82.1
79.6
81.1
75.1
81.6
75.8
83.1
86.7
83.8
91.6
114.5

Table 2: Host overlap, in thousands.

3 Aligning the Snapshots
The web is constantly changing, and network errors can aect the presence of a site or pageduring a given crawl, Nonetheless, Table 2 shows that we have a signicant host overlap in
the chosen twelve-months time span.
The rst important step in getting a temporally labelled collection is alignment : identifying URLs in dierent snapshots that correspond to the same web page. Alignment is a
non-trivial issue because if a URL is not static it might contain session-generated data (e.g.,a session ID) that makes de facto identical URLs appear as syntactically distinct.
For the present collection, a radical choice was made: the only allowed URLs are staticURLs (i.e., URLs that do not contain a question mark2 ), although we plan to develop somereasonably sound alignment technique for dynamic URLs in the future. Table 3 shows that,as a rst attempt, this choice is not unreasonable.

4 Temporal Labelling a Graph
Once URLs are aligned, it is possible to build a global graph G that includes all static pages(and related links) appearing in each snapshot. The graph G must be labelled so that, foreach node and each link, we can detect whether it was present or not in any a given snapshot.
Essentially, we need to store twelve bits of information per node and per arc.
We decided to use the labelling facility implemented in WebGraph to store a twelve-bit
label for each node and arc. To reduce signicantly the space occupied, we generated 212
2 This choice, unfortunately, cannot prevent opaque session-dependent URLs from generating noise in thecollection.

ACM SIGIR Forum36

Vol. 42 No. 2 December 2008

JunJulAug
Sep
Oct
Nov
Dec
JanFebMar
AprMay

Jun
31.3

Jul
19.0
35.2

Aug
18.3
23.3
37.3

Sep
17.2
21.7
24.3
39.9

Oct
15.3
18.5
19.4
21.2
33.8

Nov
15.018.3
19.4
21.2
22.2
37.3

Dec
13.8
16.2
17.1
18.7
19.0
22.3
36.6

Jan
13.7
16.4
17.3
19.0
19.1
21.9
23.5
39.0

Feb
13.2
16.0
16.7
18.1
18.3
21.3
21.0
23.7
37.7

Mar
12.3
15.2
15.5
16.9
16.6
18.8
19.0
20.8
23.1
38.1

Apr
11.9
14.5
15.0
16.3
16.4
18.3
17.9
19.9
22.2
22.4
36.9

May
11.1
13.6
13.8
14.7
15.0
16.6
16.6
18.4
20.0
20.2
24.2
36.9

Table 3: Static URLs overlap, in millions.

canonical Human coders [5], one for each possible node label. Each coder contains anoptimal, canonical code for the distribution of the labels of the arcs going out of nodes witha xed label. The distribution on the outgoing arc is strongly dependent on the label of thesource, and we exploit this fact to increase the compression ratio.

5 Memory and disk footprint
Memory and disk occupation depend on which components are loaded in memory (as opposed
to being accessed directly on disk). The underlying graph (representing each node and arc
ever met during the twelve crawls) has 133.6 millions of nodes and 5.5 billions of arcs.
WebGraph uses in this case ≈ 2.6 bits per link, resulting in a bitstream with a memory
footprint of 1.7 GiB.
As we discussed previously, we use 212 canonical Human decoders, which require around
66 MiB of core memory. Node and arc labels occupy around 1.2 GiB, implying a cost of just
2.16 bits per label. Since the overall graph represents 13.8 billion links, the cost per link of
the overall representation is just 1.9 bits per link.
We still have to consider the about 267 million pointers that are necessary to accessthe graph bitstream and the arc-label bit stream. WebGraph exploits a broadword implementation [7] of the EliasFano representation of monotone functions [3, 4], which provides
constant-time pointer access with minimal space occupancy. As a result, we use 9 bits pergraph bitstream pointer and 8.3 bits per label pointera memory footprint of about 274 MiB.
Finally, random access to a labelled arc requires about 250 ns on an Opteron at 2.8 Ghz,
making it possible to apply standard algorithmic techniques requiring random access to thegraph (for instance, visits over the whole graph) using a commodity workstation.

ACM SIGIR Forum

37Vol. 42 No. 2 December 2008

6 Conclusions
We have presented the rst large-scale time-aware publicly available web graph. Our softwareand data representation make it possible to access randomly structural and temporal data
quickly on a standard workstation. There are however several possible improvements:• dynamic URL alignment is dicult, but not impossible, and it is clearly necessary if
one wants to conduct a more precise analysis;• it is imperative to provide statistical evidence of the bias due to crawling policies andto inuence of the crawling limits imposed.
Work is under way to tackle both issues. We are providing, in the mean time, the raw
data we gathered. The twelve graphs are also available independently, and a separate notein this SIGIR Forum issue describes a method and Java implementation for distributing partof the page content, which, due to its very large size (7 TB) would be very dicult to serveon the network.

References[1] P. Boldi, B. Codenotti, M. Santini, and S. Vigna. Ubicrawler: A scalable fully distributed
web crawler. Software: Practice & Experience, 34(8):711726, 2004.
[2] P. Boldi and S. Vigna. The WebGraph framework I: Compression techniques. In Proc.
of the Thirteenth International World Wide Web Conference, pages 595601, Manhattan,
USA, 2004. ACM Press.
[3] P. Elias. Ecient storage and retrieval by content and address of static les. J. Assoc.
Comput. Mach., 21(2):246260, 1974.
[4] R. M. Fano. On the number of bits required to implement an associative memory. Memorandum 61, Computer Structures Group, Project MAC, MIT, Cambridge, Mass., n.d.,1971.
[5] D. S. Hirschberg and D. A. Lelewer. Ecient decoding of prex codes. Comm. ACM,33(4):449459, 1990.
[6] J. Ratkiewicz. WebGraph++, 2006. http://homer.informatics.indiana.edu/~nan/webgraph/.
[7] S. Vigna. Broadword implementation of rank/select queries. In WEA 2008: Proc. of the
7th International Workshop on Experimental Algorithms, number 5038 in Lecture Notes
in Computer Science, pages 154168. SpringerVerlag, 2008.

ACM SIGIR Forum38

Vol. 42 No. 2 December 2008