Rearranging Data to Maximize the Efficiency of Compression

Summary: Permute categories per attribute to maximize compression of multi-attribute categorical data; deterministic RLE category-rearrangement is NP‑complete via a reduction from rectilinear TSP. Under a probabilistic model the optimal order is a “double pipe organ”, with an O(n^2) algorithm for k‑dimensional data (fixed k). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hd26809856b364ee9
Venue: PODS
Year: 1986
Pagerank: 5.6186038e-05
Overall Rank: 7,024 | 52.78%
DOI: 10.1145/6012.15407

Incoming Non-self Citations Over Time

Authors

1. Frank Olken (Lawrence Berkeley National Laboratory)
2. Doron Rotem (Lawrence Berkeley National Laboratory; University of Waterloo)

BibTeX Citation

@inproceedings{olken_pods86,
        address = {New York, NY, USA},
        series = {{PODS} '86},
        title = {{Rearranging Data to Maximize the Efficiency of Compression}},
        url = {https://dl.acm.org/doi/10.1145/6012.15407},
        doi = {10.1145/6012.15407},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Olken, Frank and Rotem, Doron},
        year = {1986}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,756	Semantic Compression and Pattern Extraction with Fascicles	1999	VLDB	9.7140303e-05
11,601	Partition, Don’t Sort! Compression Boosters for Cloud Data Ingestion Pipelines	2024	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	910	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD
2	1,242	Compressing SQL Workloads	2002	SIGMOD
3	61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD
4	9,843	High-Ratio Compression for Machine-Generated Data	2023	SIGMOD
5	3,815	Comprehensive and Efficient Workload Compression	2021	VLDB
6	8,563	Robust and Budget-Constrained Encoding Configurations for In-Memory Database Systems	2022	VLDB
7	3,987	Compressing Large Boolean Matrices Using Reordering Techniques	2004	VLDB
8	900	Query Optimization In Compressed Database Systems	2001	SIGMOD
9	13,493	Transposition Algorithms on Very Large Compressed Databases	1986	VLDB
10	6,095	Column Partition and Permutation for Run Length Encoding in Columnar Databases	2020	SIGMOD