Tree-Encoded Bitmaps

Summary: Tree-Encoded Bitmaps store 0/1 runs in a binary-tree: longer runs sit higher, shorter runs lower. It supports fast random access and intersections; experiments show gains over prior compression for dense or weakly clustered bitmaps, with up to 33% space savings on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h4a7b10c297a1f1e2
Venue: SIGMOD
Year: 2020
Pagerank: 5.3286931e-05
Overall Rank: 8,500 | 42.88%
DOI: 10.1145/3318464.3380588

Incoming Non-self Citations Over Time

Authors

1. Harald Lang (Technical University of Munich)
2. Alexander Beischl (Technical University of Munich)
3. Viktor Leis (Friedrich Schiller University of Jena)
4. Peter Boncz (Centrum Wiskunde & Informatica)
5. Thomas Neumann (Technical University of Munich)
6. Alfons Kemper (Technical University of Munich)

BibTeX Citation

@inproceedings{lang_sigmod20,
        title = {{Tree-Encoded Bitmaps}},
        author = {Lang, Harald and Beischl, Alexander and Leis, Viktor and Boncz, Peter and Neumann, Thomas and Kemper, Alfons},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3380588},
        url = {https://dl.acm.org/doi/10.1145/3318464.3380588},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,755	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB	6.4309508e-05
7,486	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	5.5102404e-05
9,295	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	5.2003819e-05
9,746	LES3: Learning-based Exact Set Similarity Search	2021	VLDB	5.1325223e-05

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033459417
216	Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing	1998	VLDB	0.00024485637
769	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00014106166
873	BitWeaving: Fast Scans for Main Memory Data Processing	2013	SIGMOD	0.00013334067
889	SuRF: Practical Range Query Filtering with Fast Succinct Tries	2018	SIGMOD	0.00013243846
907	Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation	2016	SIGMOD	0.00013157412
980	Sybase IQ Multiplex – Designed For Analytics	2004	VLDB	0.00012717512
1,117	Adaptive Range Filters for Cold Data: Avoiding Trips to Siberia	2013	VLDB	0.00011952597
1,495	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010493769
1,531	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.00010344951
1,718	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7983307e-05
1,896	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.4103502e-05
2,011	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	9.1924806e-05
2,803	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB	7.9863094e-05
2,954	Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation	2018	SIGMOD	7.8119682e-05
3,592	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	7.1807308e-05
3,667	Bit-Sliced Index Arithmetic	2001	SIGMOD	7.1151219e-05
4,771	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD	6.4223645e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.222614e-05
8,422	Lightweight Indexing of Observational Data in Log-Structured Storage	2014	VLDB	5.3324909e-05
9,948	Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads	2015	VLDB	5.1038649e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,932	Optimizing Queries On Compressed Bitmaps	2000	VLDB
2	9,792	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
3	2,803	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB
4	1,495	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD
5	6,380	Compact B-Trees	1979	SIGMOD
6	1,329	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD
7	1,896	Performance Measurements of Compressed Bitmap Indices	1999	VLDB
8	9,295	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD
9	2,011	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD
10	5,601	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB