Compressed Computation on Highly-Repetitive Data

Data compression is an essential tool for storing and communicating large data-sets. Especially, for highly-repetitive data compression tools can dramatically reduce the size of the data to a tiny fraction of the original size. To perform computation on compressed data, the standard approach is to first decompress the data, incurring a huge overhead in space and time and limiting the amount of data we can feasibly handle. This project explores algorithmic techniques to perform the computation directly on the compressed data without decompressing it first, thus eliminating this overhead. The goal of the project is to design and develop new techniques for compressed computation.



Funded by The Danish Council for Independent Research (DFF) under the Sapere Aude Program. Project ID: DFF - 4005-00267.

Time period

November 2014 - April 2018.