Graph Compression by BFS

Algorithms

Alberto Apostolico¹ 

[1] College of Computing, Georgia Institute of Technology, 801 Atlantic Drive, Atlanta, GA 30332, USA; E-Mail:

关键词: data compression;    web graph;    graph compression;    breadth first search;    universal codes;   

DOI  :  10.3390/a2031031

来源: mdpi

【 摘 要 】

The Web Graph is a large-scale graph that does not fit in main memory, so that lossless compression methods have been proposed for it. This paper introduces a compression scheme that combines efficient storage with fast retrieval for the information in a node. The scheme exploits the properties of the Web Graph without assuming an ordering of the URLs, so that it may be applied to more general graphs. Tests on some datasets of use achieve space savings of about 10% over existing methods.

【 授权许可】

CC BY   
© 2009 by the authors; licensee Molecular Diversity Preservation International, Basel, Switzerland.