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.9715832e-05
Overall Rank: 2,819 | 81.05%
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,529	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.00010348765
2,201	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.8726671e-05
3,597	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	7.1788912e-05
3,750	NET-FLi: On-the-fly Compression, Archiving and Indexing of Streaming Network Traffic	2010	VLDB	7.0527908e-05
5,600	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB	6.0709132e-05
6,283	Supporting RFID-based Item Tracking Applications in Oracle DBMS Using a Bitmap Datatype	2005	VLDB	5.8236456e-05
7,471	Fast Detection of Denial Constraint Violations	2022	VLDB	5.5176505e-05
8,500	Tree-Encoded Bitmaps	2020	SIGMOD	5.3296886e-05
12,780	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.9793485e-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.00033460288
773	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00014084831
1,151	Bit Transposed Files	1985	VLDB	0.00011808563
1,497	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010478458
1,896	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.4099587e-05
1,930	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.351027e-05

Semantically Similar Papers

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