Towards compressing Web graphs
Micah Adler, Michael Mitzenmacher · DCC · 2002
We consider the problem of compressing graphs of the link structure of the World Wide Web. We provide efficient algorithms for such compression that are motivated by random graph models for describing the Web. The algorithms are based on reducing the compression problem to the problem of finding a minimum spanning free in a directed graph related to the original link graph. The performance of the algorithms on graphs generated by the random graph models suggests that by taking advantage of the link structure of the Web, one may achieve significantly better compression than natural Huffman-based schemes. We also provide hardness results demonstrating limitations on natural extensions of our approach.
Cited by 223 works. doi:10.1109/dcc.2001.917151
Authors
References
- The anatomy of a large-scale hypertextual Web search engine
- Authoritative sources in a hyperlinked environment
- Graph structure in the Web
- Trawling the Web for emerging cyber-communities
- A random graph model for massive graphs
- The Web as a Graph: Measurements, Models, and Methods
- Extracting Large-Scale Knowledge Bases from the Web
- Managing gigabytes (2nd ed.): compressing and indexing documents and images
- The Connectivity Server: fast access to linkage information on the Web
- Finding optimum branchings