Last updated 12 October 2026
How Polypress works
Polypress parses its input into columns, models each column and the dependencies between columns, and compresses the resulting streams with LZMA2.
Ordering by parent columns
In many tables, the value in one column largely determines the value in another. A postal code, for example, usually determines the city. For each column, Polypress can select another column as its parent. The choice is based on an estimate of the column's conditional entropy given each candidate, and on a trial compression when the estimates for several candidates are close.
The column is then stored in the order given by sorting the rows on its parent, so that rows with equal parent values are adjacent and, where the dependency is strong, the column forms long runs of repeated values. Different columns may have different parents, and a numeric column may be ordered by a categorical parent: in panel data, for example, readings may be ordered by a station identifier.
The sort order is not stored. The decoder reconstructs the parent column first, recomputes the sort and uses it to return the column to the original row order.
Numeric columns
Each numeric column is coded as finite differences of a low order chosen for that column, so that only the residuals are stored. Where three or more adjacent numeric columns have the same number of decimal places and similar magnitudes, each value is predicted from the value to its left, the value above it and the value above and to the left.
Values repeated across columns
Some columns contain numbers that also appear in other columns. A common example is a column
of the form POINT(longitude latitude) in a table that also has separate longitude
and latitude columns. Polypress stores such numbers as references to the column that holds
them.
Final-stage compression
The modelled streams are compressed with LZMA2 at preset 9 with the extreme option, which is
equivalent to xz -9e.
Prior work
The use of dependencies between columns to compress tables has been studied by Buchsbaum, Fowler and Giancarlo, and by Vo and Vo. Reordering rows by a parent column is described in a patent by Vo, which is listed as expired. Polypress was developed independently of this work.
- Buchsbaum, A. L., Fowler, G. S. and Giancarlo, R. (2003). Improving table compression with combinatorial optimization. Journal of the ACM, 50(6), 825–851.
- Vo, B. D. and Vo, K.-P. (2007). Compressing table data with column dependency. Theoretical Computer Science, 387(3), 273–283.
- Vo, K.-P. (2012). Compressing massive relational data. United States patent 8,312,026 B2, assigned to AT&T. Filed 2009, granted 2012; listed as expired for non-payment of maintenance fees.