Compressed linear algebra for large-scale machine learning

• DOI: 10.1007/s00778-017-0478-1
• Publication Date: 2017-09-12T10:47:29Z
• Authors: Ahmed Elgohary; Matthias Boehm; Peter J. Haas; Frederick R. Reiss; Berthold Reinwald
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

Large-scale machine learning (ML) algorithms are often iterative, using repeated read-only data access and I/O-bound matrix-vector multiplications to converge to an optimal model. It is crucial for performance to fit the data into single-node or distributed main memory. General-purpose, heavy- and lightweight compression techniques struggle to achieve both good compression ratios and fast decompression speed to enable block-wise uncompressed operations. Hence, we initiate work on compressed linear algebra (CLA), in which lightweight database compression techniques are applied to matrices and then linear algebra operations such as matrix-vector multiplication are executed directly on the compressed representations. We contribute effective column compression schemes, cache-conscious operations, and an efficient sampling-based compression algorithm. Our experiments show that CLA achieves in-memory operations performance close to the uncompressed case and good compression ratios that allow us to fit larger datasets into available memory. We thereby obtain significant end-to-end performance improvements up to 26x or reduced memory requirements.