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.00013122392
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
277	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022320139
663	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00014997516
873	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00013334067
1,614	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB	0.00010067153
1,718	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7983307e-05
1,744	How to Architect a Query Compiler	2016	SIGMOD	9.7332903e-05
2,187	Database Compression on Graphics Processors	2010	VLDB	8.891124e-05
2,954	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	7.8119682e-05
3,300	Compacting Transactional Data in Hybrid OLTP&OLAP Databases	2012	VLDB	7.4408259e-05
3,597	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	7.1759026e-05
3,962	Data-Parallel Query Processing on Non-Uniform Data	2020	VLDB	6.8916038e-05
4,072	SharkDB: An In-Memory Storage System for Massive Trajectory Data	2015	SIGMOD	6.8181285e-05
4,155	LeCo: Lightweight Compression via Learning Serial Correlations	2024	SIGMOD	6.7730383e-05
5,107	Online Deduplication for Databases	2017	SIGMOD	6.2684299e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.222614e-05
5,388	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	6.1520776e-05
5,619	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	6.0602908e-05
6,419	MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model	2020	VLDB	5.7886634e-05
6,447	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	5.7798274e-05
7,473	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	5.5162245e-05
7,497	AHEAD: Adaptable Data Hardening for On-the-Fly Hardware Error Detection during Database Query Processing	2018	SIGMOD	5.5078696e-05
8,389	AWARE: Workload-aware, Redundancy-exploiting Linear Algebra	2023	SIGMOD	5.3396465e-05
8,541	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	5.3190248e-05
8,577	The FastLanes File Format	2025	VLDB	5.3107348e-05
8,615	Adaptive Compression for Fast Scans on String Columns	2021	SIGMOD	5.3011231e-05
9,295	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	5.2003819e-05
9,850	High-Ratio Compression for Machine-Generated Data	2023	SIGMOD	5.1198764e-05
10,272	Shared Load(ing): Efficient Bulk Loading into Optimized Storage	2020	CIDR	5.0469592e-05
10,281	MorphStore — In-Memory Query Processing based on Morphing Compressed Intermediates LIVE	2019	SIGMOD	5.0461162e-05
10,895	Accelerating String-Heavy Queries with LLM Token Tables	2026	VLDB	4.9769913e-05
12,127	Towards Multi-way Join Aware Optimizer in SAP HANA	2020	VLDB	4.9769913e-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.0006897844
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00039236924
68	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00037957995
206	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00024981343
634	Performance Tradeoffs in Read-Optimized Databases	2006	VLDB	0.00015367822
898	Query Optimization In Compressed Database Systems	2001	SIGMOD	0.0001318387
1,105	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00011991167
1,839	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	9.5284548e-05

Semantically Similar Papers

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