# Entropy Coding of Unordered Data Structures

arXiv: https://arxiv.org/abs/2408.08837 · HTML: https://mlsanity.com/paper/2408.08837/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 28 references that are in the map.
- First posted on arXiv 16 Aug 2024.

## Builds on (most cited first, 11 of 11)

- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Practical Lossless Compression with Latent Variables using Bits Back Coding](https://mlsanity.com/paper/1901.04866/) (2019)
- [A Survey on Deep Graph Generation: Methods and Applications](https://mlsanity.com/paper/2203.06714/) (2022)
- [Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables](https://mlsanity.com/paper/1905.06845/) (2019)
- [Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation](https://mlsanity.com/paper/2106.06189/) (2021)
- [Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations](https://mlsanity.com/paper/1806.01799/) (2018)
- [Partition and Code: learning how to compress graphs](https://mlsanity.com/paper/2107.01952/) (2021)
- [Lossless Compression with Latent Variable Models](https://mlsanity.com/paper/2104.10544/) (2021)
- [Compressing Multisets with Large Alphabets using Bits-Back Coding](https://mlsanity.com/paper/2107.09202/) (2021)
- [Parallel Computation of Combinatorial Symmetries](https://mlsanity.com/paper/2108.04590/) (2021)
- [Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs](https://mlsanity.com/paper/2305.09705/) (2023)

## Built on by (most cited first, 3 of 3)

- [Getting Free Bits Back from Rotational Symmetries in LLMs](https://mlsanity.com/paper/2410.01309/) (2024)
- [Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2501.10479/) (2025)
- [Learning Distributions over Permutations and Rankings with Factorized Representations](https://mlsanity.com/paper/2505.24664/) (2025)

## Abstract (arXiv)

We present shuffle coding, a general method for optimal compression of sequences of unordered objects using bits-back coding. Data structures that can be compressed using shuffle coding include multisets, graphs, hypergraphs, and others. We release an implementation that can easily be adapted to different data types and statistical models, and demonstrate that our implementation achieves state-of-the-art compression rates on a range of graph datasets including molecular data.