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
5801
Venue
SIGMOD
Year
2020
Pagerank
4.5154973e-05
Overall Rank
8,430 | 41.36%
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,315 Cuckoo Index: A Lightweight Secondary Index Structure 2020 VLDB 5.5723424e-05
7,831 CUBIT: Concurrent Updatable Bitmap Indexing 2025 VLDB 4.6387445e-05
9,404 Revisiting B-tree Compression: An Experimental Study 2024 SIGMOD 4.3441378e-05
11,504 LES3: Learning-based Exact Set Similarity Search 2021 VLDB 4.1945683e-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.00045447517
368 Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing 1998 VLDB 0.000254931
1,035 Bitmap Index Design and Evaluation 1998 SIGMOD 0.00014532778
1,111 Sybase IQ Multiplex – Designed For Analytics 2004 VLDB 0.00013936696
1,169 SuRF: Practical Range Query Filtering with Fast Succinct Tries 2018 SIGMOD 0.00013536447
1,263 Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation 2016 SIGMOD 0.00012982857
1,270 BitWeaving: Fast Scans for Main Memory Data Processing 2013 SIGMOD 0.00012926086
1,471 Adaptive Range Filters for Cold Data: Avoiding Trips to Siberia 2013 VLDB 0.00011830111
1,704 An Efficient Bitmap Encoding Scheme for Selection Queries 1999 SIGMOD 0.000108332
1,951 Performance Measurements of Compressed Bitmap Indices 1999 VLDB 9.9685919e-05
1,989 Column Imprints: A Secondary Index Structure 2013 SIGMOD 9.8478437e-05
2,390 ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout 2015 SIGMOD 8.9084657e-05
2,862 An Experimental Study of Bitmap Compression vs. Inverted List Compression 2017 SIGMOD 7.9898539e-05
2,986 On the Performance of Bitmap Indices for High Cardinality Attributes 2004 VLDB 7.778912e-05
3,608 Column Sketches: A Scan Accelerator for Rapid and Robust Predicate Evaluation 2018 SIGMOD 6.924272e-05
3,856 Bit-Sliced Index Arithmetic 2001 SIGMOD 6.6942616e-05
3,912 Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems 2017 VLDB 6.6354964e-05
5,346 UpBit: Scalable In-Memory Updatable Bitmap Indexing 2016 SIGMOD 5.5561846e-05
5,532 A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew 2015 SIGMOD 5.4548897e-05
8,266 Lightweight Indexing of Observational Data in Log-Structured Storage 2014 VLDB 4.5458861e-05
9,633 Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads 2015 VLDB 4.3131863e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,061 Optimizing Queries On Compressed Bitmaps 2000 VLDB 9.6529345e-05
9,498 Memory-Efficient Search Trees for Database Management Systems 2021 SIGMOD 4.3341665e-05
2,986 On the Performance of Bitmap Indices for High Cardinality Attributes 2004 VLDB 7.778912e-05
1,704 An Efficient Bitmap Encoding Scheme for Selection Queries 1999 SIGMOD 0.000108332
4,324 Compact B-Trees 1979 SIGMOD 6.2885419e-05
1,553 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011402871
1,951 Performance Measurements of Compressed Bitmap Indices 1999 VLDB 9.9685919e-05
9,404 Revisiting B-tree Compression: An Experimental Study 2024 SIGMOD 4.3441378e-05
2,862 An Experimental Study of Bitmap Compression vs. Inverted List Compression 2017 SIGMOD 7.9898539e-05
5,596 Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps 2006 VLDB 5.4181535e-05