{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:49:10Z","timestamp":1773481750010,"version":"3.50.1"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T00:00:00Z","timestamp":1556064000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2019,4,24]]},"abstract":"<jats:p>Large-scale Machine Learning (ML) algorithms are often iterative, using repeated read-only data access and I\/O-bound matrix-vector multiplications. Hence, it is crucial for performance to fit the data into single-node or distributed main memory to enable fast matrix-vector operations. General-purpose compression struggles to achieve both good compression ratios and fast decompression for block-wise uncompressed operations. Therefore, we introduce Compressed Linear Algebra (CLA) for lossless matrix compression. CLA encodes matrices with lightweight, value-based compression techniques and executes linear algebra operations directly on the compressed representations. We contribute effective column compression schemes, cache-conscious operations, and an efficient sampling-based compression algorithm. Our experiments show good compression ratios and operations performance close to the uncompressed case, which enables fitting larger datasets into available memory. We thereby obtain significant end-to-end performance improvements.<\/jats:p>","DOI":"10.1145\/3318221","type":"journal-article","created":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T16:17:28Z","timestamp":1556122648000},"page":"83-91","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Compressed linear algebra for declarative large-scale machine learning"],"prefix":"10.1145","volume":"62","author":[{"given":"Ahmed","family":"Elgohary","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Boehm","sequence":"additional","affiliation":[{"name":"IBM Research---Almaden, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter J.","family":"Haas","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frederick R.","family":"Reiss","sequence":"additional","affiliation":[{"name":"IBM Research---Almaden, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Berthold","family":"Reinwald","sequence":"additional","affiliation":[{"name":"IBM Research---Almaden, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,24]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"OSDI","author":"Abadi M.","year":"2016","unstructured":"Abadi , M. et al. TensorFlow: A system for large-scale machine learning . In OSDI ( 2016 ). Abadi, M. et al. TensorFlow: A system for large-scale machine learning. In OSDI (2016)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0357-y"},{"key":"e_1_2_1_3_1","unstructured":"American Statistical Association (ASA). Airline on-time performance dataset. stat-computing.org\/dataexpo\/2009.  American Statistical Association (ASA). Airline on-time performance dataset. stat-computing.org\/dataexpo\/2009."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007279"},{"key":"e_1_2_1_5_1","unstructured":"Bottou L. The infinite MNIST dataset. leon.bottou.org.  Bottou L. The infinite MNIST dataset. leon.bottou.org."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020558"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687576"},{"key":"e_1_2_1_8_1","volume-title":"CIDR","author":"Elgamal T.","year":"2017","unstructured":"Elgamal , T. et al. SPOOF: Sum-product optimization and operator fusion for large-scale machine learning . In CIDR ( 2017 ). Elgamal, T. et al. SPOOF: Sum-product optimization and operator fusion for large-scale machine learning. In CIDR (2017)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994515"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0478-1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093754.3093765"},{"key":"e_1_2_1_12_1","volume-title":"The population frequencies of species and the estimation of population parameters. Biometrika","author":"Good I.J.","year":"1953","unstructured":"Good , I.J. The population frequencies of species and the estimation of population parameters. Biometrika ( 1953 ). Good, I.J. The population frequencies of species and the estimation of population parameters. Biometrika (1953)."},{"key":"e_1_2_1_13_1","first-page":"444","volume":"93","author":"Haas P.J.","year":"1998","unstructured":"Haas , P.J. and Stokes , L. Estimating the number of classes in a finite population. JASA 93 , 444 ( 1998 ). Haas, P.J. and Stokes, L. Estimating the number of classes in a finite population. JASA 93, 444 (1998).","journal-title":"JASA"},{"key":"e_1_2_1_14_1","volume-title":"et al. Univariate Discrete Distributions","author":"Johnson N.L.","year":"1992","unstructured":"Johnson , N.L. et al. Univariate Discrete Distributions , 2 nd edn. Wiley , New York , 1992 . Johnson, N.L. et al. Univariate Discrete Distributions, 2nd edn. Wiley, New York, 1992.","edition":"2"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366230.1366244"},{"key":"e_1_2_1_16_1","volume-title":"US census","author":"Lichman M.","year":"1990","unstructured":"Lichman , M. UCI machine learning repository: Higgs, covertype , US census ( 1990 ). archive.ics.uci.edu\/ml\/. Lichman, M. UCI machine learning repository: Higgs, covertype, US census (1990). archive.ics.uci.edu\/ml\/."},{"key":"e_1_2_1_17_1","volume-title":"et al. Samsara: Declarative machine learning on distributed dataflow systems. NIPS ML Systems","author":"Schelter S.","year":"2016","unstructured":"Schelter , S. et al. Samsara: Declarative machine learning on distributed dataflow systems. NIPS ML Systems ( 2016 ). Schelter, S. et al. Samsara: Declarative machine learning on distributed dataflow systems. NIPS ML Systems (2016)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498765.1498785"},{"key":"e_1_2_1_19_1","volume-title":"KDD","author":"Zadeh R.B.","year":"2016","unstructured":"Zadeh , R.B. et al. Matrix computations and optimization in apache spark . In KDD ( 2016 ). Zadeh, R.B. et al. Matrix computations and optimization in apache spark. In KDD (2016)."},{"key":"e_1_2_1_20_1","volume-title":"NSDI","author":"Zaharia M.","year":"2012","unstructured":"Zaharia , M. et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing . In NSDI ( 2012 ). Zaharia, M. et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In NSDI (2012)."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3318221","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3318221","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:40Z","timestamp":1750204480000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3318221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,24]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,4,24]]}},"alternative-id":["10.1145\/3318221"],"URL":"https:\/\/doi.org\/10.1145\/3318221","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,24]]},"assertion":[{"value":"2019-04-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}