AMP: Total Variation Reduction for Lossless Compression via Approximate Median-based Preconditioning

What is it about?

With the increasing scale of cloud computing applications of next-generation embedded systems, a major challenge that domain scientists are facing is how to efficiently store and analyze the vast volume of output data. Compression can reduce the amount of data that needs to be transferred and stored. However, most of the large datasets are in floating-point format, which exhibits high entropy. As a result, existing lossless compressors can not provide enough performance for such applications. To address this problem, we propose a total variation reduction method for improving the compression ratio of lossless compressors (namely, FPC+ and FPZIP+), which employs a median-based hyperplane to precondition the data. Moreover, through observing the time composition of the proposed method, it is found that the median finding holds a high percentage of the execution time. Hence, we further introduce an approximate median finding algorithm, providing a linear-time overhead reduction scheme.

Featured Image