Bitmap Index Design and Evaluation

Summary: Proposes a two-axis bitmap-index framework linking schemes to number representations and delineating space-time tradeoffs for selection queries. Identifies time-, space-, knee-, and space-constrained optima; analyzes compression and buffering and presents an improved bitmap-index evaluation algorithm for physical design guidelines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h375fc21667ae51be
Venue: SIGMOD
Year: 1998
Pagerank: 0.00014084831
Overall Rank: 773 | 94.81%
DOI: 10.1145/276304.276336

Incoming Non-self Citations Over Time

Authors

1. Chee-Yong Chan (University of Wisconsin)
2. Yannis E. Ioannidis (University of Athens; University of Wisconsin)

BibTeX Citation

@inproceedings{chan_sigmod98,
        title = {{Bitmap Index Design and Evaluation}},
        author = {Chan, Chee-Yong and Ioannidis, Yannis E.},
        series = {{SIGMOD} '98},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/276304.276336},
        url = {https://dl.acm.org/doi/10.1145/276304.276336},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 34 of 34 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
463	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017804544
779	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014030069
971	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012766019
1,497	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD	0.00010478458
2,201	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.8726671e-05
2,422	Parallel Data Analysis Directly on Scientific File Formats	2014	SIGMOD	8.4891004e-05
2,819	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB	7.9715832e-05
3,295	Lightning Fast and Space Efficient Inequality Joins	2015	VLDB	7.448168e-05
3,666	Bit-Sliced Index Arithmetic	2001	SIGMOD	7.1179861e-05
3,841	High-Dimensional OLAP: A Minimal Cubing Approach	2004	VLDB	6.9904505e-05
4,391	Bitvector-aware Query Optimization for Decision Support Queries	2020	SIGMOD	6.6214093e-05
4,648	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	6.4867043e-05
4,748	Query Optimization for Selections using Bitmaps	1999	SIGMOD	6.4371799e-05
4,810	UpBit: Scalable In-Memory Updatable Bitmap Indexing	2016	SIGMOD	6.4050834e-05
4,885	Design Tradeoffs of Data Access Methods	2016	SIGMOD	6.3706825e-05
5,021	Adaptive Sampling for Rapidly Matching Histograms	2018	VLDB	6.3106761e-05
5,530	Generalized Hash Teams for Join and Group-by	1999	VLDB	6.0935245e-05
5,600	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB	6.0709132e-05
5,618	BinDex: A Two-Layered Index for Fast and Robust Scans	2020	SIGMOD	6.0630987e-05
6,283	Supporting RFID-based Item Tracking Applications in Oracle DBMS Using a Bitmap Datatype	2005	VLDB	5.8236456e-05
7,285	Processing Star Queries on Hierarchically-Clustered Fact Tables	2002	VLDB	5.5662445e-05
7,481	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	5.5128501e-05
8,500	Tree-Encoded Bitmaps	2020	SIGMOD	5.3296886e-05
8,533	Cabin: a Compressed Adaptive Binned Scan Index	2024	SIGMOD	5.3215439e-05
9,038	Bringing Cloud-Native Storage to SAP IQ	2021	SIGMOD	5.2331918e-05
9,360	Extending SQL to Return a Subdatabase	2025	SIGMOD	5.1868213e-05
10,591	RABIT: Efficient Range Queries with Bitmap Indexing	2026	SIGMOD	4.9793485e-05
10,592	Regular Expression Indexing for Log Analysis	2026	SIGMOD	4.9793485e-05
10,655	LiveBin: A Localized and Version-Aware Binned Scan Index	2026	SIGMOD	4.9793485e-05
10,826	FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism	2026	VLDB	4.9793485e-05
10,830	Bridging the Indexing Gap in Fused GPU Query Engines	2026	VLDB	4.9793485e-05
10,901	Overlay Bitmap Encoding for Efficient Consumption of Apache Parquet Files	2026	VLDB	4.9793485e-05
12,780	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.9793485e-05
13,157	A Data Warehousing Architecture for Enabling Service Provisioning Process	2001	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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
611	"One Size Fits All" Database Architectures Do Not Work For DSS	1995	SIGMOD	0.00015574329
1,151	Bit Transposed Files	1985	VLDB	0.00011808563
3,863	Database Buffer Size Investigation for OLTP Workloads	1997	SIGMOD	6.9627352e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,527	On the Analysis of Indexing Schemes	1997	PODS
2	2,201	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD
3	6,715	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
4	9,941	Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads	2015	VLDB
5	2,819	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB
6	5,600	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB
7	4,748	Query Optimization for Selections using Bitmaps	1999	SIGMOD
8	1,930	Optimizing Queries On Compressed Bitmaps	2000	VLDB
9	1,896	Performance Measurements of Compressed Bitmap Indices	1999	VLDB
10	1,497	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD