Mostrar o rexistro simple do ítem
Exploiting Computation-Friendly Graph Compression Methods for Adjacency-Matrix Multiplication
dc.contributor.author | Francisco, Alexandre P. | |
dc.contributor.author | Gagie, Travis | |
dc.contributor.author | Ladra, Susana | |
dc.contributor.author | Navarro, Gonzalo | |
dc.date.accessioned | 2021-01-12T16:00:50Z | |
dc.date.available | 2021-01-12T16:00:50Z | |
dc.date.issued | 2018-03 | |
dc.identifier.citation | A. Francisco, T. Gagie, S. Ladra and G. Navarro, "Exploiting Computation-Friendly Graph Compression Methods for Adjacency-Matrix Multiplication," 2018 Data Compression Conference, Snowbird, UT, USA, 2018, pp. 307-314, doi: 10.1109/DCC.2018.00039. | |
dc.identifier.uri | http://hdl.handle.net/2183/27090 | |
dc.description.abstract | [Abstract] Computing 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. | es_ES |
dc.description.sponsorship | Fundação para a Ciência e a Tecnologia (Portugal); UID/CEC/50021/2013 | es_ES |
dc.description.sponsorship | Academy of Finland; 268324 | |
dc.description.sponsorship | Fondo Nacional de Desarrollo Científico y Tecnológico (Chile); 1171058 | |
dc.description.sponsorship | Ministerio de Economía y Competitividad; TIN2016-77158-C4-3-R | |
dc.description.sponsorship | Xunta de Galicia; ED431C 2017/58 | |
dc.description.sponsorship | Xunta de Galicia; ED431G/01 | |
dc.description.sponsorship | Agencia Nacional de Investigación y Desarrollo (Chile); ICM/FIC RC130003 | |
dc.language.iso | eng | es_ES |
dc.publisher | IEEE Computer Society | es_ES |
dc.relation | info:eu-repo/grantAgreement/EC/H2020/690941 | es_ES |
dc.relation.uri | https://doi.org/10.1109/DCC.2018.00039 | |
dc.rights | Atribución-NoComercial-SinDerivadas 4.0 Internacional | es_ES |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Graph compression | es_ES |
dc.subject | Adjacency-matrix multiplication | es_ES |
dc.subject | Compact data structures | es_ES |
dc.subject | Computation-friendly representation | es_ES |
dc.title | Exploiting Computation-Friendly Graph Compression Methods for Adjacency-Matrix Multiplication | es_ES |
dc.type | info:eu-repo/semantics/conferenceObject | es_ES |
dc.rights.access | info:eu-repo/semantics/openAccess | es_ES |
dc.identifier.doi | 10.1109/DCC.2018.00039 | |
UDC.conferenceTitle | Data Compression Conference (28, 2018, Cliff Lodge, Snowbird, UT, USA) | es_ES |
Ficheiros no ítem
Este ítem aparece na(s) seguinte(s) colección(s)
-
GI-LBD - Congresos, conferencias, etc. [18]
-
OpenAIRE [266]