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: 751
Venue: PODS
Year: 1986
Pagerank: 5.7469443e-05
Overall Rank: 6,882 | 52.79%
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,721	Semantic Compression and Pattern Extraction with Fascicles	1999	VLDB	9.9258415e-05
11,274	Partition, Don’t Sort! Compression Boosters for Cloud Data Ingestion Pipelines	2024	VLDB	5.093636e-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	925	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD
2	1,266	Compressing SQL Workloads	2002	SIGMOD
3	60	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD
4	9,673	High-Ratio Compression for Machine-Generated Data	2023	SIGMOD
5	4,084	Comprehensive and Efficient Workload Compression	2021	VLDB
6	8,410	Robust and Budget-Constrained Encoding Configurations for In-Memory Database Systems	2022	VLDB
7	3,912	Compressing Large Boolean Matrices Using Reordering Techniques	2004	VLDB
8	921	Query Optimization In Compressed Database Systems	2001	SIGMOD
9	13,203	Transposition Algorithms on Very Large Compressed Databases	1986	VLDB
10	5,985	Column Partition and Permutation for Run Length Encoding in Columnar Databases	2020	SIGMOD