Francesco Tosoni from Università di Pisa will give his webtalk on Friday, September 16 at 3 pm.
If you would like to attend, please email to office@csh.ac.at
Title: “Improving matrix-vector multiplication via lossless grammar-compressed matrices”
Abstract:
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 talk 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 𝑘-th order statistical entropy of the input. 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.
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. The results of this work have been the subject of an article recently published in VLDB ’22.
About:
Francesco Tosoni received the MSc degree in computer science and networking from the University of Pisa and Sant’Anna School of Advanced Studies (Italy) in 2020. His master thesis “Algorithms and Data Structures for Efficient Ride Sharing Platforms” attained the con.Scienze 2020 best thesis award. He is currently a PhD student in computer science. His research interests range from string indexing to information retrieval and big data analysis, with a particular focus on lossless data-compression techniques.