Query Optimization for Selections using Bitmaps

Summary: Bitmap-based query optimization for selections in data warehouses; handles continuous and discrete predicates. Static optimization: optimal bitmap design and tree reduction; dynamic optimization via inclusion-exclusion for bit-sliced/encoded indexes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3164
Venue: SIGMOD
Year: 1999
Pagerank: 6.5834278e-05
Overall Rank: 4,656 | 68.06%
DOI: 10.1145/304182.304202

Incoming Non-self Citations Over Time

Authors

1. Ming-Chuan Wu (Technical University of Darmstadt)

BibTeX Citation

@inproceedings{wu_sigmod99,
        title = {{Query Optimization for Selections using Bitmaps}},
        author = {Wu, Ming-Chuan},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304202},
        url = {https://dl.acm.org/doi/10.1145/304182.304202},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,597	Bit-Sliced Index Arithmetic	2001	SIGMOD	7.2721197e-05
5,472	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB	6.2058219e-05
7,162	Processing Star Queries on Hierarchically-Clustered Fact Tables	2002	VLDB	5.6851725e-05
8,121	NetCube: A Scalable Tool for Fast Data Mining and Compression	2001	VLDB	5.4834308e-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
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00083340894
104	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033932213
794	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00013969303

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,612	Index Intersection for High-Dimensional Range Queries	2026	VLDB
2	4,849	Bitvector-aware Query Optimization for Decision Support Queries	2020	SIGMOD
3	2,773	On the Performance of Bitmap Indices for High Cardinality Attributes	2004	VLDB
4	5,472	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB
5	9,765	Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads	2015	VLDB
6	1,053	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD
7	1,867	Performance Measurements of Compressed Bitmap Indices	1999	VLDB
8	1,464	An Efficient Bitmap Encoding Scheme for Selection Queries	1999	SIGMOD
9	1,894	Optimizing Queries On Compressed Bitmaps	2000	VLDB
10	794	Bitmap Index Design and Evaluation	1998	SIGMOD