Efficient Compression of Web Graphs

• ASANO Yasuhito

  Graduate School of Informatics, Kyoto University

• MIYAWAKI Yuya

  Graduate School of Information Sciences, Tohoku University

• NISHIZEKI Takao

  Graduate School of Information Sciences, Tohoku University

抄録

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.99bits 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.84bits per link to compress the same Web graph.

収録刊行物

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E92-A (10), 2454-2462, 2009

  一般社団法人 電子情報通信学会

キーワード

• Web graph
• compression
• intra-host links
• localities

詳細情報

• CRID: 1390001206312183424
• NII論文ID: 10026860065
• NII書誌ID: AA10826239
• DOI: 10.1587/transfun.e92.a.2454
• ISSN: 17451337
• ISSN: 09168508
• Web Site: http://www.jstage.jst.go.jp/article/transfun/E92.A/10/E92.A_10_2454/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可