On the Performance of Bitmap Indices for High Cardinality Attributes

Summary: Systematic analysis of BBC and WAH bitmap compression for high-cardinality attributes; proposes a strategy to select the optimal scheme. Compressed bitmap indices remain smaller than B-trees and viable for both low and high cardinalities. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h0714f9600324e068
Venue: VLDB
Year: 2004
Pagerank: 7.9863094e-05
Overall Rank: 2,803 | 81.17%
DOI: 10.1016/B978-012088469-8.50006-1

Incoming Non-self Citations Over Time

Authors

1. Kesheng Wu (Lawrence Berkeley National Laboratory)
2. Ekow Otoo (Lawrence Berkeley National Laboratory)
3. Arie Shoshani (Lawrence Berkeley National Laboratory)

BibTeX Citation

@article{wu_vldb04,
        title = {{On the Performance of Bitmap Indices for High Cardinality Attributes}},
        author = {Wu, Kesheng and Otoo, Ekow and Shoshani, Arie},
        journal = {PVLDB},
        series = {{VLDB} '04},
        pages = {24--35},
        doi = {10.1016/B978-012088469-8.50006-1},
        url = {https://doi.org/10.1016/B978-012088469-8.50006-1},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,531	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.00010344951
2,011	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	9.1924806e-05
3,592	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	7.1807308e-05
3,748	NET-FLi: On-the-fly Compression, Archiving and Indexing of Streaming Network Traffic	2010	VLDB	7.0523418e-05
5,601	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB	6.0682354e-05
6,287	Supporting RFID-based Item Tracking Applications in Oracle DBMS Using a Bitmap Datatype	2005	VLDB	5.8208888e-05
7,476	Fast Detection of Denial Constraint Violations	2022	VLDB	5.5150385e-05
8,500	Tree-Encoded Bitmaps	2020	SIGMOD	5.3286931e-05
12,786	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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
769	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00014106166
1,148	Bit Transposed Files	1985	VLDB	0.00011809942
1,495	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010493769
1,896	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.4103502e-05
1,932	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.349258e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,856	Compression Aware Physical Database Design	2011	VLDB
2	898	Query Optimization In Compressed Database Systems	2001	SIGMOD
3	9,948	Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads	2015	VLDB
4	9,295	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD
5	1,932	Optimizing Queries On Compressed Bitmaps	2000	VLDB
6	1,495	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD
7	2,011	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD
8	769	Bitmap Index Design and Evaluation	1998	SIGMOD
9	5,601	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB
10	1,896	Performance Measurements of Compressed Bitmap Indices	1999	VLDB