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.9609074e-05
Overall Rank: 2,810 | 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,532	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.00010312002
2,017	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	9.169662e-05
3,601	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	7.1582591e-05
3,744	NET-FLi: On-the-fly Compression, Archiving and Indexing of Streaming Network Traffic	2010	VLDB	7.0372503e-05
5,614	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB	6.0483079e-05
6,301	Supporting RFID-based Item Tracking Applications in Oracle DBMS Using a Bitmap Datatype	2005	VLDB	5.8016413e-05
7,496	Fast Detection of Denial Constraint Violations	2022	VLDB	5.4968024e-05
8,516	Tree-Encoded Bitmaps	2020	SIGMOD	5.3110731e-05
12,829	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.9605343e-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.00033376274
776	Bitmap Index Design and Evaluation	1998	SIGMOD	0.0001406101
1,149	Bit Transposed Files	1985	VLDB	0.00011771401
1,496	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010460047
1,902	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.3884754e-05
1,939	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.3280163e-05

Semantically Similar Papers

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