Graph Compression by BFS
Open Access
- 25 August 2009
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 2 (3) , 1031-1044
Abstract
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.Keywords
This publication has 13 references indexed in Scilit:
- A scalable pattern mining approach to web graph compression with communities2008
- Codes for the World Wide WebInternet Mathematics, 2005
- UbiCrawler: a scalable fully distributed Web crawlerSoftware: Practice and Experience, 2004
- Off-line dictionary-based compressionProceedings of the IEEE, 2000
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- Clique Partitions, Graph Compression and Speeding-Up AlgorithmsJournal of Computer and System Sciences, 1995
- On the succinct representation of graphsDiscrete Applied Mathematics, 1984
- Universal codeword sets and representations of the integersIEEE Transactions on Information Theory, 1975
- Efficient Storage and Retrieval by Content and Address of Static FilesJournal of the ACM, 1974
- In MemorandumAmerican Journal of EEG Technology, 1971