A large time-aware web graph

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 hoc compression 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 growth of online communities, and in general time-dependent phenomena related to the link structure.

REFERENCES

• 1: Paolo Boldi , Bruno Codenotti , Massimo Santini , Sebastiano Vigna, UbiCrawler: a scalable fully distributed web crawler, Software—Practice & Experience, v.34 n.8, p.711-726, 10 July 2004 [doi>10.1002/spe.587]
• 2: P. Boldi , S. Vigna, The webgraph framework I: compression techniques, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988752]
• 3: Peter Elias, Efficient Storage and Retrieval by Content and Address of Static Files, Journal of the ACM (JACM), v.21 n.2, p.246-260, April 1974 [doi>10.1145/321812.321820]
• 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: Daniel S. Hirschberg , Debra A. Lelewer, Efficient decoding of prefix codes, Communications of the ACM, v.33 n.4, p.449-459, April 1990 [doi>10.1145/77556.77566]
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.2 Compression (Coding)

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Image databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

          Nouns: World Wide Web (WWW)
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.4 Hypertext/Hypermedia

General Terms:
Algorithms, Design, Management