Show simple item record

Authordc.contributor.authorFrancisco, Alexandre 
Authordc.contributor.authorGagie, Travis 
Authordc.contributor.authorLadra, Susana 
Authordc.contributor.authorNavarro, Gonzalo 
Cita de ítemdc.identifier.citationData Compression Conference Proceedings, 2018.
Abstractdc.description.abstractComputing the product of the (binary) adjacency matrix of a large graph with a real-valued vector is an important operation that lies at the heart of various graph analysis tasks, such as computing PageRank. In this paper we show that some well-known Web and social graph compression formats are computation-friendly, in the sense that they allow boosting the computation. In particular, we show that the format of Boldi and Vigna allows computing the product in time proportional to the compressed graph size. Our experimental results show speedups of at least 2 on graphs that were compressed at least 5 times with respect to the original. We show that other successful graph compression formats enjoy this property as well.
Publisherdc.publisherInstitute of Electrical and Electronics Engineers Inc.
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile
Link to Licensedc.rights.uri
Sourcedc.sourceData Compression Conference Proceedings
Keywordsdc.subjectcomputation friendly compression
Keywordsdc.subjectgraph compression
Keywordsdc.subjectmatrix multiplications
Títulodc.titleExploiting computation-friendly graph compression methods for adjacency-matrix multiplication
Document typedc.typeArtículo de revista
Indexationuchile.indexArtículo de publicación SCOPUS

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Chile
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile