{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:43:37Z","timestamp":1781077417798,"version":"3.54.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,3,21]],"date-time":"2022-03-21T00:00:00Z","timestamp":1647820800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,21]],"date-time":"2022-03-21T00:00:00Z","timestamp":1647820800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010665","name":"H2020 Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["690941"],"award-info":[{"award-number":["690941"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Fundacio para a Ciencia e a Tecnologia","award":["UIDB\/50021\/2020 and PTDC\/CCI-BIO\/29676\/2017"],"award-info":[{"award-number":["UIDB\/50021\/2020 and PTDC\/CCI-BIO\/29676\/2017"]}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["268324"],"award-info":[{"award-number":["268324"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Natural Science and Engineering Research Council","award":["RGPIN-07185-2020"],"award-info":[{"award-number":["RGPIN-07185-2020"]}]},{"name":"Fondecyt","award":["1171058"],"award-info":[{"award-number":["1171058"]}]},{"name":"JSPS KAKENHI","award":["JP21K17701 and JP21H05847"],"award-info":[{"award-number":["JP21K17701 and JP21H05847"]}]},{"name":"AEI and Ministerio de Ciencia e Innovacion","award":["PID2019-105221RB-C41"],"award-info":[{"award-number":["PID2019-105221RB-C41"]}]},{"DOI":"10.13039\/501100010801","name":"Xunta de Galicia","doi-asserted-by":"publisher","award":["ED431C 2021\/53 and ED431G 2019\/01"],"award-info":[{"award-number":["ED431C 2021\/53 and ED431G 2019\/01"]}],"id":[{"id":"10.13039\/501100010801","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ANID \u2013 Millennium Science Initiative Program","award":["Code ICN17_002"],"award-info":[{"award-number":["Code ICN17_002"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:italic>computation-friendly<\/jats:italic>, in the sense that they allow boosting the computation. We focus on the compressed representations of (a) Boldi and Vigna and (b) Hern\u00e1ndez 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.<\/jats:p>","DOI":"10.1007\/s42979-022-01084-2","type":"journal-article","created":{"date-parts":[[2022,3,21]],"date-time":"2022-03-21T11:03:25Z","timestamp":1647860605000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Graph Compression for Adjacency-Matrix Multiplication"],"prefix":"10.1007","volume":"3","author":[{"given":"Alexandre P.","family":"Francisco","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3689-327X","authenticated-orcid":false,"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dominik","family":"K\u00f6ppl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Susana","family":"Ladra","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,3,21]]},"reference":[{"key":"1084_CR1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: An Introduction","author":"M Newman","year":"2010","unstructured":"Newman M. Networks: An Introduction. Oxford: OUP Oxford; 2010."},{"key":"1084_CR2","doi-asserted-by":"crossref","unstructured":"Chung L.L.F. Complex Graphs and Networks. Conference Board of the mathematical science. American Mathematical Society, Providence, 2006.","DOI":"10.1090\/cbms\/107"},{"issue":"5","key":"1084_CR3","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/3318221","volume":"62","author":"A Elgohary","year":"2019","unstructured":"Elgohary A, Boehm M, Haas PJ, Reiss FR, Reinwald B. Compressed linear algebra for declarative large-scale machine learning. Commun ACM. 2019;62(5):83\u201391.","journal-title":"Commun. ACM"},{"key":"1084_CR4","unstructured":"Abboud A, Backurs A, Bringmann K, K\u00fcnnemann M. Impossibility results for grammar-compressed linear algebra. In: Proc. NeurIPS, pp. 1\u201314, 2020."},{"key":"1084_CR5","doi-asserted-by":"crossref","unstructured":"Chakraborty D, Kamma L, Larsen KG. Tight cell probe bounds for succinct Boolean matrix-vector multiplication. In: Proc. STOC, pp. 1297\u20131306, 2018.","DOI":"10.1145\/3188745.3188830"},{"key":"1084_CR6","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.jda.2014.10.003","volume":"32","author":"T Gagie","year":"2015","unstructured":"Gagie T, Gawrychowski P, Puglisi SJ. Approximate pattern matching in LZ77-compressed texts. J Discrete Algorithms. 2015;32:64\u20138.","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"1084_CR7","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/s00453-011-9590-6","volume":"65","author":"D Hermelin","year":"2013","unstructured":"Hermelin D, Landau GM, Landau S, Weimann O. Unified compression-based acceleration of edit-distance computation. Algorithmica. 2013;65(2):339\u201353.","journal-title":"Algorithmica"},{"issue":"3","key":"1084_CR8","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/s00453-007-9128-0","volume":"54","author":"Y Lifshits","year":"2009","unstructured":"Lifshits Y, Mozes S, Weimann O, Ziv-Ukelson M. Speeding up HMM decoding and training by exploiting sequence repetitions. Algorithmica. 2009;54(3):379\u201399.","journal-title":"Algorithmica"},{"key":"1084_CR9","unstructured":"Yang E, Bian J. Bipartite grammar-based representations of large sparse binary matrices: Framework and transforms. In: Proc. ISITA, pp. 241\u2013245, 2016."},{"key":"1084_CR10","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/j.jcss.2016.12.007","volume":"86","author":"M Ganardi","year":"2017","unstructured":"Ganardi M, Hucke D, Jez A, Lohrey M, Noeth E. Constructing small tree grammars and small circuits for formulas. J Comput Syst Sci. 2017;86:136\u201358.","journal-title":"J Comput Syst Sci"},{"issue":"2","key":"1084_CR11","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M Lohrey","year":"2012","unstructured":"Lohrey M. Algorithmics on SLP-compressed strings: a survey. Groups Complex Cryptol. 2012;4(2):241\u201399.","journal-title":"Groups Complex Cryptol"},{"key":"1084_CR12","doi-asserted-by":"crossref","unstructured":"Boldi P, Vigna S. The webgraph framework I: compression techniques. In: Proc. WWW, pp. 595\u2013602, 2004.","DOI":"10.1145\/988672.988752"},{"issue":"2","key":"1084_CR13","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10115-013-0648-4","volume":"40","author":"C Hern\u00e1ndez","year":"2014","unstructured":"Hern\u00e1ndez C, Navarro G. Compressed representations for web and social graphs. Knowl Inf Syst. 2014;40(2):279\u2013313.","journal-title":"Knowl Inf Syst"},{"key":"1084_CR14","doi-asserted-by":"crossref","unstructured":"Francisco AP, Gagie T, Ladra S, Navarro G. Exploiting computation-friendly graph compression methods for adjacency-matrix multiplication. In: Proc. DCC, pp 307\u2013314, 2018.","DOI":"10.1109\/DCC.2018.00039"},{"key":"1084_CR15","unstructured":"Alman J, Williams VV. Further limitations of the known approaches for matrix multiplication. In: Proc. ITCS. LIPIcs, vol 94, pp 25\u201312515, 2018."},{"issue":"3","key":"1084_CR16","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1080\/15427951.2009.10390646","volume":"6","author":"C Karande","year":"2009","unstructured":"Karande C, Chellapilla K, Andersen R. Speeding up algorithms on compressed web graphs. Internet Math. 2009;6(3):373\u201398.","journal-title":"Internet Math."},{"key":"1084_CR17","doi-asserted-by":"crossref","unstructured":"Nishino M, Yasuda N, Minato S, Nagata M. Accelerating graph adjacency matrix multiplications with adjacency forest. In: Proc. SDM, pp. 1073\u20131081, 2014.","DOI":"10.1137\/1.9781611973440.122"},{"key":"1084_CR18","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/j.is.2013.08.003","volume":"39","author":"NR Brisaboa","year":"2014","unstructured":"Brisaboa NR, Ladra S, Navarro G. Compact representation of web graphs with extended functionality. Inf Syst. 2014;39:152\u201374.","journal-title":"Inf Syst"},{"key":"1084_CR19","doi-asserted-by":"crossref","unstructured":"Henzinger M, Krinninger S, Nanongkai D, Saranurak T. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: Proc. STOC, pp. 21\u201330, 2015.","DOI":"10.1145\/2746539.2746609"},{"key":"1084_CR20","doi-asserted-by":"crossref","unstructured":"Larsen KG, Williams RR. Faster online matrix-vector multiplication. In: Proc. SODA, pp. 2182\u20132189, 2017.","DOI":"10.1137\/1.9781611974782.142"},{"issue":"50","key":"1084_CR21","doi-asserted-by":"publisher","first-page":"19735","DOI":"10.1073\/pnas.0708838104","volume":"104","author":"F Chung","year":"2007","unstructured":"Chung F. The heat kernel as the pagerank of a graph. Proc Natl Acad Sci. 2007;104(50):19735\u201340.","journal-title":"Proc Natl Acad Sci"},{"key":"1084_CR22","unstructured":"Page L, Brin S, Motwani R, Winograd T. The PageRank citation ranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab, 1999."},{"key":"1084_CR23","doi-asserted-by":"crossref","unstructured":"Boldi P, Rosa M, Santini M, Vigna S. Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks. In: Proc. WWW, pp. 587\u2013596, 2011.","DOI":"10.1145\/1963405.1963488"},{"key":"1084_CR24","doi-asserted-by":"crossref","unstructured":"Grabowski S, Bieniecki W. Merging adjacency lists for efficient web graph compression. In: Proc. ICMMI. Advances in Intelligent and Soft Computing, vol 103, pp 385\u2013392, 2011.","DOI":"10.1007\/978-3-642-23169-8_42"},{"issue":"4","key":"1084_CR25","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/1841909.1841913","volume":"4","author":"F Claude","year":"2010","unstructured":"Claude F, Navarro G. Fast and compact web graph representations. TWEB. 2010;4(4):16\u201311631.","journal-title":"TWEB"},{"issue":"4","key":"1084_CR26","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1080\/15427951.2005.10129113","volume":"2","author":"P Boldi","year":"2005","unstructured":"Boldi P, Vigna S. Codes for the world wide web. Internet Math. 2005;2(4):407\u201329.","journal-title":"Internet Math"},{"issue":"2","key":"1084_CR27","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/3160017","volume":"12","author":"P Boldi","year":"2018","unstructured":"Boldi P, Marino A, Santini M, Vigna S. Bubing: massive crawling for the masses. ACM Trans Web. 2018;12(2):12\u201311226.","journal-title":"ACM Trans Web"},{"key":"1084_CR28","doi-asserted-by":"crossref","unstructured":"Chierichetti F, Kumar R, Lattanzi S, Mitzenmacher M, Panconesi A, Raghavan P. On compressing social networks. In: Proc. SIGKDD, pp 219\u2013228, 2009.","DOI":"10.1145\/1557019.1557049"},{"key":"1084_CR29","first-page":"3","volume":"14","author":"J Barbay","year":"2010","unstructured":"Barbay J, L\u00f3pez-Ortiz A, Lu T, Salinger A. An experimental investigation of set intersection algorithms for text searching. J Exp Algorithm. 2010;14:3\u20137.","journal-title":"J Exp Algorithm"}],"updated-by":[{"DOI":"10.1007\/s42979-022-01141-w","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2022,4,19]],"date-time":"2022-04-19T00:00:00Z","timestamp":1650326400000}}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01084-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-022-01084-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01084-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,9]],"date-time":"2022-05-09T17:53:04Z","timestamp":1652118784000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-022-01084-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,21]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["1084"],"URL":"https:\/\/doi.org\/10.1007\/s42979-022-01084-2","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s42979-022-01141-w","asserted-by":"object"}]},"ISSN":["2662-995X","2661-8907"],"issn-type":[{"value":"2662-995X","type":"print"},{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,21]]},"assertion":[{"value":"15 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2022","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s42979-022-01141-w","URL":"https:\/\/doi.org\/10.1007\/s42979-022-01141-w","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding authors state that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"193"}}