The webgraph framework I: compression techniques

By Paolo Boldi, Sebastiano Vigna. The Web Conference, 2004

1,400 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Information Systems

View Paper: https://www.semanticscholar.org/paper/73b59a9a5e9642d3b80469dce828b626d85457b8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Information Systems

Citations in the corpus

Efficient semi-streaming algorithms for local triangle counting in massive graphs (2008, methodology): “We used the WebGraph framework [5] to manipulate the graphs in compressed form.”
Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments (2005, methodology): “Though with the latest compression techniques [Boldi and Vigna 04] the entire web graph may ﬁt into main memory, we still have a signiﬁcant computational overhead for decompression in case of random access.”
Connected Components at Scale via Local Contractions (2018, background): “Clueweb [BV04, BRSV11] is publicly available web-crawl graph.”
Scalability! But at what COST? (2015, neutral): “name twitter rv [13] uk-2007-05 [5, 6] nodes 41,652,230 105,896,555 edges 1,468,365,182 3,738,733,648 size 5.”
Fast exact shortest-path distance queries on large networks by pruned landmark labeling (2013, background): “Indochina: This is a web graph of web pages in the country domains of Indochina countries, crawled in 2004 [9,8].”
The Limits of Popularity-Based Recommendations, and the Role of Social Ties (2016, neutral): “Twitter LAW The twitter-2010 graph by the Laboratory for Web Algorithmics, Univ. Milan [4, 3].”
Binary RDF representation for publication and exchange (HDT) (2013, methodology): “These resultsmotivate the application toRDFof thewell-known Web distribution, where power-law is present in successors list of a given domain, playing an important role in Web graphs compression [45,46].”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, methodology): “Following [6], we optimize a quadratic penalty relaxation for vertex cover eswiki-2013 where n ≈ 970K, and d ≈ 23M and wordassociation-2011 with n ≈ 10K and d ≈ 72K [18, 19, 20].”
Main-memory triangle computations for very large (sparse (power-law)) graphs (2008, methodology): “It is also important to notice that other approaches exist, based for instance on streaming algorithmics (avoiding to store the graph in main memory) [23,4,25] and/or approximate algorithms [32,25,35], and/or various methods to compress the graph [8,9].”
Learning the Structural Vocabulary of a Network (2017, neutral): “Another option could be to use graph summarization methods to present a compressed version of the network to the input layer (Boldi & Vigna, 2004; Navlakha et al., 2008).”
Deeper Inside PageRank (2004, methodology): “These techniques are freely available in the graph compression tool WebGraph, which is produced by Paolo Boldi and Sebastiano Vigna [22, 23].”
iRun: Horizontal and Vertical Shape of a Region-Based Graph Compression (2022, methodology): “[15] suggested a compression technique for graphs on the web.”
Know your neighbors: web spam detection using the web topology (2007, methodology): “The full graph has over 3 billion edges and is stored in the compressed format described in Boldi and Vigna [ 10 ] using 2.9 bits per edge, for a total size of about 1.2 GB. The page content is stored in WARC/0.9 format.3 The content data is distributed in 8 compressed volumes of about 55 GB each.”
Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks (2010, methodology): “Experiments performed on a wide array of web graphs and social networks show that combining the order produced by the proposed algorithm with the WebGraph compression framework provides a major increase in compression with respect to all currently known techniques, both on web graphs and on soc”
Direction-optimizing Breadth-First Search (2012, background): “The real social networks are taken from a variety of web crawls [6, 7, 12, 16, 21, 23, 25, 26].”