Dictionary-based Order-preserving String Compression for Main Memory Column Stores

Summary: Introduces order-preserving dictionary compression for variable-length strings with large, evolving domains in main-memory column stores. Models the dictionary as a mapping table with a novel index for fast string↔code lookups and compressed index data, delivering competitive speed with lower memory usage than prior approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4188
Venue: SIGMOD
Year: 2009
Pagerank: 0.00013182044
Overall Rank: 925 | 93.66%
DOI: 10.1145/1559845.1559877

Incoming Non-self Citations Over Time

Authors

1. Carsten Binnig (ETH Zurich)
2. Stefan Hildenbrand (ETH Zurich)
3. Franz Färber (SAP)

BibTeX Citation

@inproceedings{binnig_sigmod09,
        title = {{Dictionary-based Order-preserving String Compression for Main Memory Column Stores}},
        author = {Binnig, Carsten and Hildenbrand, Stefan and Färber, Franz},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559877},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559877},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 30 of 30 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
278	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022476841
678	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015061068
870	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.0001350293
1,644	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB	0.00010132912
1,761	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.8154969e-05
1,797	How to Architect a Query Compiler	2016	SIGMOD	9.7368925e-05
2,232	Database Compression on Graphics Processors	2010	VLDB	8.8970926e-05
2,937	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	7.9435581e-05
3,292	Compacting Transactional Data in Hybrid OLTP&OLAP Databases	2012	VLDB	7.5518441e-05
3,598	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	7.2718988e-05
4,065	LeCo: Lightweight Compression via Learning Serial Correlations	2024	SIGMOD	6.930275e-05
4,585	Data-Parallel Query Processing on Non-Uniform Data	2020	VLDB	6.6175897e-05
4,806	SharkDB: An In-Memory Storage System for Massive Trajectory Data	2015	SIGMOD	6.4994869e-05
5,021	Online Deduplication for Databases	2017	SIGMOD	6.3982122e-05
5,122	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.3573169e-05
5,285	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	6.2821588e-05
5,512	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	6.1913331e-05
6,665	MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model	2020	VLDB	5.8089595e-05
7,242	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	5.6641994e-05
7,412	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	5.624223e-05
7,458	AHEAD: Adaptable Data Hardening for On-the-Fly Hardware Error Detection during Database Query Processing	2018	SIGMOD	5.6121707e-05
8,370	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	5.4409293e-05
8,436	Adaptive Compression for Fast Scans on String Columns	2021	SIGMOD	5.4253644e-05
8,794	AWARE: Workload-aware, Redundancy-exploiting Linear Algebra	2023	SIGMOD	5.370464e-05
9,038	The FastLanes File Format	2025	VLDB	5.3270943e-05
9,518	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	5.256602e-05
9,673	High-Ratio Compression for Machine-Generated Data	2023	SIGMOD	5.2383683e-05
10,067	Shared Load(ing): Efficient Bulk Loading into Optimized Storage	2020	CIDR	5.1643809e-05
10,068	MorphStore — In-Memory Query Processing based on Morphing Compressed Intermediates LIVE	2019	SIGMOD	5.1643809e-05
11,819	Towards Multi-way Join Aware Optimizer in SAP HANA	2020	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00069513174
60	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.0003955489
67	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00038461275
204	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00025342994
630	Performance Tradeoffs in Read-Optimized Databases	2006	VLDB	0.00015591796
921	Query Optimization In Compressed Database Systems	2001	SIGMOD	0.00013209503
1,110	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00012140661
1,813	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	9.6941032e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,507	Column Imprints: A Secondary Index Structure	2013	SIGMOD
2	5,985	Column Partition and Permutation for Run Length Encoding in Columnar Databases	2020	SIGMOD
3	5,755	Compression Aware Physical Database Design	2011	VLDB
4	12,178	Multi-dimensional Data Statistics for Columnar In-Memory Databases	2014	SIGMOD
5	8,951	On Searching Compressed String Collections Cache-Obliviously	2008	PODS
6	5,285	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD
7	9,635	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
8	60	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD
9	921	Query Optimization In Compressed Database Systems	2001	SIGMOD
10	8,436	Adaptive Compression for Fast Scans on String Columns	2021	SIGMOD