Compressed linear algebra for declarative large-scale machine learning

Ahmed Elgohary, Matthias Boehm, Peter J. Haas, Frederick R. Reiss, Berthold Reinwald

Research output: Contribution to journalArticlepeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)83-91
JournalCommunications of the ACM
Volume62
Issue number5
DOIs
Publication statusPublished - 2019

Fingerprint

Dive into the research topics of 'Compressed linear algebra for declarative large-scale machine learning'. Together they form a unique fingerprint.

Cite this