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: h423ec48f866c127e
Venue: SIGMOD
Year: 2009
Pagerank: 0.00013123912
Overall Rank: 910 | 93.89%
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 31 of 31 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
282	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022264207
661	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015003815
873	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00013338838
1,614	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB	0.00010071891
1,723	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7931223e-05
1,742	How to Architect a Query Compiler	2016	SIGMOD	9.7378418e-05
2,185	Database Compression on Graphics Processors	2010	VLDB	8.8948351e-05
2,952	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	7.8153507e-05
3,308	Compacting Transactional Data in Hybrid OLTP&OLAP Databases	2012	VLDB	7.4411187e-05
3,599	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	7.1773938e-05
3,961	Data-Parallel Query Processing on Non-Uniform Data	2020	VLDB	6.8948667e-05
4,070	SharkDB: An In-Memory Storage System for Massive Trajectory Data	2015	SIGMOD	6.8213576e-05
4,153	LeCo: Lightweight Compression via Learning Serial Correlations	2024	SIGMOD	6.776246e-05
5,105	Online Deduplication for Databases	2017	SIGMOD	6.2713269e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2250048e-05
5,397	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	6.1490013e-05
5,618	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	6.0630987e-05
6,417	MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model	2020	VLDB	5.791405e-05
6,444	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	5.7825648e-05
7,491	AHEAD: Adaptable Data Hardening for On-the-Fly Hardware Error Detection during Database Query Processing	2018	SIGMOD	5.5104779e-05
7,495	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	5.5091753e-05
8,384	AWARE: Workload-aware, Redundancy-exploiting Linear Algebra	2023	SIGMOD	5.3421754e-05
8,533	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	5.3215439e-05
8,569	The FastLanes File Format	2025	VLDB	5.3132501e-05
8,608	Adaptive Compression for Fast Scans on String Columns	2021	SIGMOD	5.3036338e-05
9,699	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	5.138658e-05
9,843	High-Ratio Compression for Machine-Generated Data	2023	SIGMOD	5.1223012e-05
10,266	Shared Load(ing): Efficient Bulk Loading into Optimized Storage	2020	CIDR	5.0493495e-05
10,275	MorphStore — In-Memory Query Processing based on Morphing Compressed Intermediates LIVE	2019	SIGMOD	5.0485061e-05
10,886	Accelerating String-Heavy Queries with LLM Token Tables	2026	VLDB	4.9793485e-05
12,121	Towards Multi-way Join Aware Optimizer in SAP HANA	2020	VLDB	4.9793485e-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.00068998927
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.000392237
69	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00037950385
207	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00024970987
634	Performance Tradeoffs in Read-Optimized Databases	2006	VLDB	0.00015373122
900	Query Optimization In Compressed Database Systems	2001	SIGMOD	0.00013186558
1,107	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00011993663
1,841	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	9.5268075e-05

Semantically Similar Papers

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