An Efficient Bitmap Encoding Scheme for Selection Queries

Summary: Proposes a bitmap encoding for selection queries and shows existing schemes are not optimal for two-sided range queries. Experiments show the encoding yields better space-time tradeoffs versus existing schemes and four hybrids for membership queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h6db4bc6be92eacfb
Venue: SIGMOD
Year: 1999
Pagerank: 0.00010478458
Overall Rank: 1,497 | 89.94%
DOI: 10.1145/304182.304201

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_sigmod99,
        title = {{An Efficient Bitmap Encoding Scheme for Selection Queries}},
        author = {Chan, Chee-Yong and Ioannidis, Yannis E.},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304201},
        url = {https://dl.acm.org/doi/10.1145/304182.304201},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 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
2,422	Parallel Data Analysis Directly on Scientific File Formats	2014	SIGMOD	8.4891004e-05
2,583	Fauce: Fast and Accurate Deep Ensembles with Uncertainty for Cardinality Estimation	2021	VLDB	8.2589758e-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
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,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
6,949	Supporting Ranking and Clustering as Generalized Order-By and Group-By	2007	SIGMOD	5.6365631e-05
7,481	CUBIT: Concurrent Updatable Bitmap Indexing	2025	VLDB	5.5128501e-05
8,500	Tree-Encoded Bitmaps	2020	SIGMOD	5.3296886e-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
12,780	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,780	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
2	6,715	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
3	2,201	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD
4	2,819	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB
5	9,941	Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads	2015	VLDB
6	4,748	Query Optimization for Selections using Bitmaps	1999	SIGMOD
7	1,930	Optimizing Queries On Compressed Bitmaps	2000	VLDB
8	5,600	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB
9	1,896	Performance Measurements of Compressed Bitmap Indices	1999	VLDB
10	773	Bitmap Index Design and Evaluation	1998	SIGMOD