Towards compressing Web graphs

Author

Adler, Micah ; Mitzenmacher, Michael

Author_Institution

Dept. of Comput. Sci., Massachusetts Univ., Amherst, MA, USA

fYear

2001

fDate

2001

Firstpage

203

Lastpage

212

Abstract

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

Keywords

computational complexity; data compression; directed graphs; information resources; Huffman-based schemes; NP-hard problems; Web graphs compression; World Wide Web; algorithms; directed graph; efficient algorithms; hardness results; link structure; minimum spanning free; performance; random graph models; Compression algorithms; Computer science; Electronic mail; Engineering profession; Prototypes; Search engines; Testing; Tree graphs; Web pages; Web sites;

fLanguage

English

Publisher

ieee

Conference_Titel

Data Compression Conference, 2001. Proceedings. DCC 2001.

Conference_Location

Snowbird, UT

ISSN

1068-0314

Print_ISBN

0-7695-1031-0

Type

conf

DOI

10.1109/DCC.2001.917151

Filename

917151