Graph Compression for Adjacency-Matrix Multiplication

Simple item page
UDC.coleccionInvestigaciónes_ES
UDC.departamentoCiencias da Computación e Tecnoloxías da Informaciónes_ES
UDC.grupoInvLaboratorio de Bases de Datos (LBD)es_ES
UDC.journalTitleSN Computer Sciencees_ES
UDC.startPage193es_ES
UDC.volume3es_ES
dc.contributor.authorFrancisco, Alexandre P.
dc.contributor.authorGagie, Travis
dc.contributor.authorKöppl, Dominik
dc.contributor.authorLadra, Susana
dc.contributor.authorNavarro, Gonzalo
dc.date.accessioned2022-07-13T16:46:50Z
dc.date.available2022-07-13T16:46:50Z
dc.date.issued2022
dc.description19 April 2022 A Correction to this paper has been published: https://doi.org/10.1007/s42979-022-01141-wes_ES
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 webgraph and social graph compression formats are computation-friendly, in the sense that they allow boosting the computation. We focus on the compressed representations of (a) Boldi and Vigna and (b) Hernández and Navarro, and show that the product computation can be conducted 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.es_ES
dc.description.sponsorshipWe thank Cecilia Hernández for providing us with her software extracting the bicliques, and a helpful description in how to run it. This research has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie [grant agreement No 690941], namely while the first author was visiting the University of Chile, and while the second author was affiliated with the University of Helsinki and visiting the University of A Coruña. The first author was funded by Fundação para a Ciência e a Tecnologia (FCT) [grant number UIDB/50021/2020 and PTDC/CCI-BIO/29676/2017]; the second author was funded by the Academy of Finland [Grant number 268324], Fondecyt [Grant number 1171058] and NSERC [Grant number RGPIN-07185-2020]; the third author was funded by JSPS KAKENHI [grant numbers JP21K17701 and JP21H05847]; the fourth author was funded by AEI and Ministerio de Ciencia e Innovación (PGE and FEDER) [grant number PID2019-105221RB-C41] and Xunta de Galicia (co-funded with FEDER) [Grant numbers ED431C 2021/53 and ED431G 2019/01]; and the fifth author was funded by ANID – Millennium Science Initiative Program – Code ICN17_002es_ES
dc.description.sponsorshipXunta de Galicia; ED431C 2021/53es_ES
dc.description.sponsorshipXunta de Galicia; ED431G 2019/01es_ES
dc.identifier.citationFrancisco, A.P., Gagie, T., Köppl, D. et al. Graph Compression for Adjacency-Matrix Multiplication. SN COMPUT. SCI. 3, 193 (2022). https://doi.org/10.1007/s42979-022-01084-2es_ES
dc.identifier.doi10.1007/s42979-022-01084-2
dc.identifier.urihttp://hdl.handle.net/2183/31180
dc.language.isoenges_ES
dc.publisherSpringeres_ES
dc.relation.urihttps://doi.org/10.1007/s42979-022-01084-2es_ES
dc.rightsAtribución 3.0 Españaes_ES
dc.rights.accessRightsopen accesses_ES
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/es/*
dc.subjectMatrix multiplicationes_ES
dc.subjectWebgraphes_ES
dc.subjectBicliqueses_ES
dc.subjectData compressiones_ES
dc.titleGraph Compression for Adjacency-Matrix Multiplicationes_ES
dc.typejournal articlees_ES
dspace.entity.typePublication
relation.isAuthorOfPublication55bfba4e-d15b-4c84-9894-ac53c2278caf
relation.isAuthorOfPublication.latestForDiscovery55bfba4e-d15b-4c84-9894-ac53c2278caf

Files

Original bundle

Now showing 1 - 2 of 2
Thumbnail Image
Name:
Francisco_Alexandre_P_2022_Graph_Compression_For_Adjacency.pdf
Size:
1.05 MB
Format:
Adobe Portable Document Format
Description:
Download
Thumbnail Image
Name:
Francisco_Alexandre_P_2022_Correction_to_Graph_Compression_For_Adjacency.pdf
Size:
331.69 KB
Format:
Adobe Portable Document Format
Description:
Download

Collections

Investigación (FIC)