Efficient Compression of Web Graphs

摘要：

Several methods have been proposed for compressing the linkage data of a Web graph. Among them, the method proposed by Boldi and Vigna is known as the most efficient one. In the paper, we propose a new method to compress a Web graph. Our method is more efficient than theirs with respect to the size of the compressed data. For example, our method needs only 1.99 bits per link to compress a Web graph containing 3,216,152 links connecting 325,557 pages, while the method of Boldi and Vigna needs 2.84 bits per link to compress the same Web graph.

作者: Yasuhito Asano Yuya Miyawaki Takao Nishizeki

作者单位: Graduate School Informatics, Kyoto University,Yoshidahonmachi,Sakyo-ku, Kyoto, 606-8051, Japan Graduate School of Information Sciences, Tohoku University, Aza-Aoba 6-6-05,Aramaki, Aoba Graduate School of Information Sciences, Tohoku University, Aza-Aoba 6-6-05,Aramaki,Aoba

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 1-11

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）