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: 9372
Venue: VLDB
Year: 2004
Pagerank: 8.1382209e-05
Overall Rank: 2,773 | 80.98%
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,507	Column Imprints: A Secondary Index Structure	2013	SIGMOD	0.0001054177
2,224	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.9183396e-05
3,576	Two Birds, One Stone: A Fast, yet Lightweight, Indexing Scheme for Modern Database Systems	2017	VLDB	7.2936598e-05
3,722	NET-FLi: On-the-fly Compression, Archiving and Indexing of Streaming Network Traffic	2010	VLDB	7.1726862e-05
5,472	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB	6.2058219e-05
6,152	Supporting RFID-based Item Tracking Applications in Oracle DBMS Using a Bitmap Datatype	2005	VLDB	5.9573045e-05
7,396	Fast Detection of Denial Constraint Violations	2022	VLDB	5.6257228e-05
8,349	Tree-Encoded Bitmaps	2020	SIGMOD	5.4460774e-05
12,490	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	5.093636e-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
104	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033932213
794	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00013969303
1,136	Bit Transposed Files	1985	VLDB	0.00012027691
1,464	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010689981
1,867	Performance Measurements of Compressed Bitmap Indices	1999	VLDB	9.5903618e-05
1,894	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.5268052e-05

Semantically Similar Papers

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