Lossless Compression of Unordered Data Structures

We develop an elegant and fast method for lossless compression of unordered objects, which we call ‘shuffle coding’. Data structures that can be compressed using shuffle coding include multisets, graphs, hypergraphs, and others. It is an entropy coding method based on bits-back with asymmetric numeral systems. Shuffle coding achieves state-of-the-art compression rates at practical speeds on a wide range of graph datasets, including molecular datasets and large social network graphs, as well as multisets. We release a high-performance implementation that can easily be adapted to different data types and statistical models.