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.00013092547
Overall Rank: 912 | 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
280	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022267903
662	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00014972958
871	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00013313281
1,615	Compressed Linear Algebra for Large-Scale Machine Learning	2016	VLDB	0.00010054378
1,720	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7828414e-05
1,756	How to Architect a Query Compiler	2016	SIGMOD	9.7053947e-05
2,104	Database Compression on Graphics Processors	2010	VLDB	9.0262021e-05
2,965	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	7.7894987e-05
3,308	Compacting Transactional Data in Hybrid OLTP&OLAP Databases	2012	VLDB	7.4195851e-05
3,606	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	7.1528863e-05
3,968	Data-Parallel Query Processing on Non-Uniform Data	2020	VLDB	6.8770248e-05
4,093	SharkDB: An In-Memory Storage System for Massive Trajectory Data	2015	SIGMOD	6.7956344e-05
4,169	LeCo: Lightweight Compression via Learning Serial Correlations	2024	SIGMOD	6.7526687e-05
5,125	Online Deduplication for Databases	2017	SIGMOD	6.2497801e-05
5,236	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2037372e-05
5,398	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	6.1338952e-05
5,632	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	6.0402517e-05
6,425	MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model	2020	VLDB	5.7716425e-05
6,459	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	5.7607157e-05
7,492	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	5.4981253e-05
7,515	AHEAD: Adaptable Data Hardening for On-the-Fly Hardware Error Detection during Database Query Processing	2018	SIGMOD	5.4899436e-05
7,771	The FastLanes File Format	2025	VLDB	5.4390723e-05
8,407	AWARE: Workload-aware, Redundancy-exploiting Linear Algebra	2023	SIGMOD	5.3219903e-05
8,560	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	5.3014368e-05
8,633	Adaptive Compression for Fast Scans on String Columns	2021	SIGMOD	5.2835943e-05
9,318	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	5.1831862e-05
9,874	High-Ratio Compression for Machine-Generated Data	2023	SIGMOD	5.1049732e-05
10,299	Shared Load(ing): Efficient Bulk Loading into Optimized Storage	2020	CIDR	5.0302708e-05
10,308	MorphStore — In-Memory Query Processing based on Morphing Compressed Intermediates LIVE	2019	SIGMOD	5.0294306e-05
10,956	Accelerating String-Heavy Queries with LLM Token Tables	2026	VLDB	4.9605343e-05
12,171	Towards Multi-way Join Aware Optimizer in SAP HANA	2020	VLDB	4.9605343e-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.00068985264
61	Integrating Compression and Execution in Column-Oriented Database Systems	2006	SIGMOD	0.00039323387
68	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00037861537
209	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00024915373
635	Performance Tradeoffs in Read-Optimized Databases	2006	VLDB	0.00015334073
900	Query Optimization In Compressed Database Systems	2001	SIGMOD	0.00013152699
1,106	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00011960288
1,849	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	9.5008844e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,532	Column Imprints: A Secondary Index Structure	2013	SIGMOD
2	6,101	Column Partition and Permutation for Run Length Encoding in Columnar Databases	2020	SIGMOD
3	5,866	Compression Aware Physical Database Design	2011	VLDB
4	12,518	Multi-dimensional Data Statistics for Columnar In-Memory Databases	2014	SIGMOD
5	9,138	On Searching Compressed String Collections Cache-Obliviously	2008	PODS
6	5,398	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD
7	9,824	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,633	Adaptive Compression for Fast Scans on String Columns	2021	SIGMOD