{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:23:34Z","timestamp":1773887014082,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:p>\n            As nowadays Machine Learning (ML) techniques are generating huge data collections, the problem of how to efficiently engineer their storage and operations is becoming of paramount importance. In this article we propose a new lossless compression scheme for real-valued matrices which achieves efficient performance in terms of compression ratio and time for linear-algebra operations. Experiments show that, as a compressor, our tool is clearly superior to gzip and it is usually within 20% of xz in terms of compression ratio. In addition, our compressed format supports matrix-vector multiplications in time and space proportional to the size of the compressed representation, unlike gzip and xz that require the full decompression of the compressed matrix. To our knowledge our lossless compressor is the first one achieving time and space complexities which match the theoretical limit expressed by the\n            <jats:italic>k<\/jats:italic>\n            -th order statistical entropy of the input.\n          <\/jats:p>\n          <jats:p>To achieve further time\/space reductions, we propose column-reordering algorithms hinging on a novel column-similarity score. Our experiments on various data sets of ML matrices show that our column reordering can yield a further reduction of up to 16% in the peak memory usage during matrix-vector multiplication.<\/jats:p>\n          <jats:p>Finally, we compare our proposal against the state-of-the-art Compressed Linear Algebra (CLA) approach showing that ours runs always at least twice faster (in a multi-thread setting), and achieves better compressed space occupancy and peak memory usage. This experimentally confirms the provably effective theoretical bounds we show for our compressed-matrix approach.<\/jats:p>","DOI":"10.14778\/3547305.3547321","type":"journal-article","created":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T16:09:53Z","timestamp":1662566993000},"page":"2175-2187","source":"Crossref","is-referenced-by-count":10,"title":["Improving matrix-vector multiplication via lossless grammar-compressed matrices"],"prefix":"10.14778","volume":"15","author":[{"given":"Paolo","family":"Ferragina","sequence":"first","affiliation":[{"name":"University of Pisa"}]},{"given":"Giovanni","family":"Manzini","sequence":"additional","affiliation":[{"name":"University of Pisa"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[{"name":"Dalhousie University"}]},{"given":"Dominik","family":"K\u00f6ppl","sequence":"additional","affiliation":[{"name":"Tokyo Medical and Dental University"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"University of Chile"}]},{"given":"Manuel","family":"Striani","sequence":"additional","affiliation":[{"name":"University of Eastern Piedmont"}]},{"given":"Francesco","family":"Tosoni","sequence":"additional","affiliation":[{"name":"University of Pisa"}]}],"member":"320","published-online":{"date-parts":[[2022,9,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2008.105"},{"key":"e_1_2_1_2_1","volume-title":"Data Expo 2009 - Airline on-time performance. https:\/\/community.amstat.org\/jointscsg-section\/dataexpo\/dataexpo2009","author":"Statistical Computing ASA","year":"2009","unstructured":"ASA , Statistical Computing & Graphics Sections 2009 . Data Expo 2009 - Airline on-time performance. https:\/\/community.amstat.org\/jointscsg-section\/dataexpo\/dataexpo2009 . [Online; accessed 21-Sep-2021]. ASA, Statistical Computing & Graphics Sections 2009. Data Expo 2009 - Airline on-time performance. https:\/\/community.amstat.org\/jointscsg-section\/dataexpo\/dataexpo2009. [Online; accessed 21-Sep-2021]."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1314498.1314563"},{"key":"e_1_2_1_4_1","volume-title":"The infinite MNIST dataset. https:\/\/leon.bottou.org\/projects\/infimnist. https:\/\/leon.bottou.org\/projects\/infimnist [Online","author":"Bottou Leon","year":"2021","unstructured":"Leon Bottou . 2007. The infinite MNIST dataset. https:\/\/leon.bottou.org\/projects\/infimnist. https:\/\/leon.bottou.org\/projects\/infimnist [Online ; accessed 21- Sep- 2021 ]. Leon Bottou. 2007. The infinite MNIST dataset. https:\/\/leon.bottou.org\/projects\/infimnist. https:\/\/leon.bottou.org\/projects\/infimnist [Online; accessed 21-Sep-2021]."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950622"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014064"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020558"},{"key":"e_1_2_1_9_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms , 3 rd Edition. MIT Press , One Broadway , 12th Floor, Cambridge, MA 02142. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd Edition. MIT Press, One Broadway, 12th Floor, Cambridge, MA 02142.","edition":"3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Inderjit S. Dhillon. 2001. Co-clustering documents and words using bipartite spectral graph partitioning. In KDD. ACM 269--274.  Inderjit S. Dhillon. 2001. Co-clustering documents and words using bipartite spectral graph partitioning. In KDD. ACM 269--274.","DOI":"10.1145\/502512.502550"},{"key":"e_1_2_1_11_1","unstructured":"Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. https:\/\/archive.ics.uci.edu\/ml. http:\/\/archive.ics.uci.edu\/ml [Online; accessed 21-Sep-2021].  Dheeru Dua and Casey Graff. 2017. UCI Machine Learning Repository. https:\/\/archive.ics.uci.edu\/ml. http:\/\/archive.ics.uci.edu\/ml [Online; accessed 21-Sep-2021]."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0478-1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318221"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2018.00039"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321942"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_28"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.15837\/ijccc.2016.6.2554"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00284-2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-009-0004-6"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"David S. Johnson Shankar Krishnan Jatin Chhugani Subodh Kumar and Suresh Venkatasubramanian. 2004. Compressing Large Boolean Matrices using Reordering Techniques. In VLDB. Morgan Kaufmann 13--23.  David S. Johnson Shankar Krishnan Jatin Chhugani Subodh Kumar and Suresh Venkatasubramanian. 2004. Compressing Large Boolean Matrices using Reordering Techniques. In VLDB. Morgan Kaufmann 13--23.","DOI":"10.1016\/B978-012088469-8.50005-X"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.841160"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366230.1366244"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.892708"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1515\/gcc-2012-0016"},{"key":"e_1_2_1_25_1","volume-title":"Introduction to information retrieval","author":"Manning Christopher D.","unstructured":"Christopher D. Manning , Prabhakar Raghavan , and Hinrich Sch\u00fctze . 2008. Introduction to information retrieval . Cambridge University Press . Christopher D. Manning, Prabhakar Raghavan, and Hinrich Sch\u00fctze. 2008. Introduction to information retrieval. Cambridge University Press."},{"key":"e_1_2_1_26_1","unstructured":"Giovanni Manzini. 2021. A Collection of Some Machine Learning Matrices. https:\/\/www.kaggle.com\/giovannimanzini\/some-machine-learning-matrices. Version 3.  Giovanni Manzini. 2021. A Collection of Some Machine Learning Matrices. https:\/\/www.kaggle.com\/giovannimanzini\/some-machine-learning-matrices. Version 3."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77978-0_11"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3397175"},{"key":"e_1_2_1_29_1","volume-title":"Indexing Highly Repetitive String Collections, Part I: Repetitiveness Measures. ACM Comput. Surv. 54, 2","author":"Navarro Gonzalo","year":"2021","unstructured":"Gonzalo Navarro . 2021. Indexing Highly Repetitive String Collections, Part I: Repetitiveness Measures. ACM Comput. Surv. 54, 2 ( 2021 ), 29:1--29:31. Gonzalo Navarro. 2021. Indexing Highly Repetitive String Collections, Part I: Repetitiveness Measures. ACM Comput. Surv. 54, 2 (2021), 29:1--29:31."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2871452"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM.  Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM.","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3384413"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322346"},{"key":"e_1_2_1_34_1","volume-title":"https:\/\/systemds.apache.org\/. [Online","author":"Software The Apache","year":"2021","unstructured":"The Apache Software Foundation 2021. Apache System DS. https:\/\/systemds.apache.org\/. [Online ; accessed 14- Dec- 2021 ]. The Apache Software Foundation 2021. Apache SystemDS. https:\/\/systemds.apache.org\/. [Online; accessed 14-Dec-2021]."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.016"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3547305.3547321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:16:15Z","timestamp":1672226175000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3547305.3547321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6]]},"references-count":35,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.14778\/3547305.3547321"],"URL":"https:\/\/doi.org\/10.14778\/3547305.3547321","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,6]]}}}