Database Paper Browser

Back to papers

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
5802
Venue
SIGMOD
Year
2020
Pagerank
4.5111681e-05
Overall Rank
8,424 | 41.46%
DOI
10.1145/3318464.3380588

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank Citing Paper Year Venue Pagerank
5,316 Cuckoo Index: A Lightweight Secondary Index Structure 2020 VLDB 5.5688295e-05
7,837 CUBIT: Concurrent Updatable Bitmap Indexing 2025 VLDB 4.6342964e-05
9,410 Revisiting B-tree Compression: An Experimental Study 2024 SIGMOD 4.3399748e-05
11,508 LES3: Learning-based Exact Set Similarity Search 2021 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

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
121 Improved Query Performance with Variant Indexes 1997 SIGMOD 0.00045429472
367 Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing 1998 VLDB 0.00025518228
1,033 Bitmap Index Design and Evaluation 1998 SIGMOD 0.0001453376
1,109 Sybase IQ Multiplex – Designed For Analytics 2004 VLDB 0.00013927106
1,169 SuRF: Practical Range Query Filtering with Fast Succinct Tries 2018 SIGMOD 0.00013530267
1,260 Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation 2016 SIGMOD 0.00012990853
1,267 BitWeaving: Fast Scans for Main Memory Data Processing 2013 SIGMOD 0.00012917585
1,468 Adaptive Range Filters for Cold Data: Avoiding Trips to Siberia 2013 VLDB 0.00011831457
1,701 An Efficient Bitmap Encoding Scheme for Selection Queries 1999 SIGMOD 0.00010828605
1,955 Performance Measurements of Compressed Bitmap Indices 1999 VLDB 9.9641178e-05
1,993 Column Imprints: A Secondary Index Structure 2013 SIGMOD 9.8403548e-05
2,390 ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout 2015 SIGMOD 8.9006978e-05
2,821 An Experimental Study of Bitmap Compression vs. Inverted List Compression 2017 SIGMOD 8.0639288e-05
2,984 On the Performance of Bitmap Indices for High Cardinality Attributes 2004 VLDB 7.7768363e-05
3,611 Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation 2018 SIGMOD 6.9178844e-05
3,858 Bit-Sliced Index Arithmetic 2001 SIGMOD 6.6893766e-05
3,906 Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems 2017 VLDB 6.6413008e-05
5,341 UpBit: Scalable In-Memory Updatable Bitmap Indexing 2016 SIGMOD 5.5592799e-05
5,541 A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew 2015 SIGMOD 5.4501856e-05
8,262 Lightweight Indexing of Observational Data in Log-Structured Storage 2014 VLDB 4.5415271e-05
9,633 Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads 2015 VLDB 4.309053e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,065 Optimizing Queries On Compressed Bitmaps 2000 VLDB 9.6467359e-05
9,499 Memory-Efficient Search Trees for Database Management Systems 2021 SIGMOD 4.3300131e-05
2,984 On the Performance of Bitmap Indices for High Cardinality Attributes 2004 VLDB 7.7768363e-05
1,701 An Efficient Bitmap Encoding Scheme for Selection Queries 1999 SIGMOD 0.00010828605
4,317 Compact B-Trees 1979 SIGMOD 6.2824978e-05
1,551 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011395294
1,955 Performance Measurements of Compressed Bitmap Indices 1999 VLDB 9.9641178e-05
9,410 Revisiting B-tree Compression: An Experimental Study 2024 SIGMOD 4.3399748e-05
2,821 An Experimental Study of Bitmap Compression vs. Inverted List Compression 2017 SIGMOD 8.0639288e-05
5,605 Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps 2006 VLDB 5.413565e-05