ComputingComputer ScienceAlgorithmsData StructuresDatabasesData CompressionGraph AlgorithmsGraph AnalyticsGraph TheoryLossy Data CompressionCompressionCompression AlgorithmsCompression TechniquesGraph CompressionGraph IndexingGraph Sparsification
Web graphs are extremely large, making them difficult to study, but recent methods exploit internal redundancies to compress them into limited memory. The WebGraph framework provides a suite of tools and algorithms to simplify manipulation of large web graphs. It achieves compression through referentiation and intervalisation techniques, which are dual to each other. WebGraph compresses the WebBase graph (118 M nodes, 1 G links) to 3.08 bits per link and its transposed version to 2.89 bits per link.
Studying web graphs is often difficult due to their large size. Recently,several proposals have been published about various techniques that allow tostore a web graph in memory in a limited space, exploiting the inner redundancies of the web. The WebGraph framework is a suite of codes, algorithms and tools that aims at making it easy to manipulate large web graphs. This papers presents the compression techniques used in WebGraph, which are centred around referentiation and intervalisation (which in turn are dual to each other). WebGraph can compress the WebBase graph (118 Mnodes, 1 Glinks)in as little as 3.08 bits per link, and its transposed version in as littleas 2.89 bits per link.
11
The PageRank Citation Ranking : Bringing Order to the Web
Lawrence M. Page, Sergey Brin, Rajeev Motwani et al. · 1999 · 12.7K citations
Authoritative sources in a hyperlinked environment
Jon Kleinberg · Journal of the ACM · 1999 · 9.1K citations · Full text
UbiCrawler: a scalable fully distributed Web crawler
Paolo Boldi, Bruno Codenotti, Massimo Santini et al. · Software Practice and Experience · 2004 · 564 citations
Towards compressing Web graphs
Micah Adler, Michael Mitzenmacher · 2002 · 225 citations · Full text