Database Paper Browser

Back to papers

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
3028
Venue
SIGMOD
Year
1998
Pagerank
0.0001453376
Overall Rank
1,033 | 92.83%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank Citing Paper Year Venue Pagerank
844 The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds 2020 VLDB 0.00015964123
1,300 Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes 2016 SIGMOD 0.00012711153
1,365 FITing-Tree: A Data-aware Index Structure 2019 SIGMOD 0.00012379754
1,701 An Efficient Bitmap Encoding Scheme for Selection Queries 1999 SIGMOD 0.00010828605
2,764 Parallel Data Analysis Directly on Scientific File Formats 2014 SIGMOD 8.1607305e-05
2,821 An Experimental Study of Bitmap Compression vs. Inverted List Compression 2017 SIGMOD 8.0639288e-05
2,984 On the Performance of Bitmap Indices for High Cardinality Attributes 2004 VLDB 7.7768363e-05
3,162 High-Dimensional OLAP: A Minimal Cubing Approach 2004 VLDB 7.4622284e-05
3,575 Lightning Fast and Space Efficient Inequality Joins 2015 VLDB 6.9509846e-05
3,858 Bit-Sliced Index Arithmetic 2001 SIGMOD 6.6893766e-05
4,532 Query Optimization for Selections using Bitmaps 1999 SIGMOD 6.1027943e-05
4,679 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 5.9978792e-05
4,718 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 5.9664602e-05
5,118 Design Tradeoffs of Data Access Methods 2016 SIGMOD 5.6781464e-05
5,195 Bitvector-aware Query Optimization for Decision Support Queries 2020 SIGMOD 5.6314278e-05
5,329 Generalized Hash Teams for Join and Group-by 1999 VLDB 5.5652298e-05
5,341 UpBit: Scalable In-Memory Updatable Bitmap Indexing 2016 SIGMOD 5.5592799e-05
5,605 Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps 2006 VLDB 5.413565e-05
5,762 BinDex: A Two-Layered Index for Fast and Robust Scans 2020 SIGMOD 5.3367636e-05
6,233 Supporting RFID-based Item Tracking Applications in Oracle DBMS Using a Bitmap Datatype 2005 VLDB 5.1390355e-05
7,042 Processing Star Queries on Hierarchically-Clustered Fact Tables 2002 VLDB 4.8483133e-05
7,837 CUBIT: Concurrent Updatable Bitmap Indexing 2025 VLDB 4.6342964e-05
8,424 Tree-Encoded Bitmaps 2020 SIGMOD 4.5111681e-05
8,439 Cabin: a Compressed Adaptive Binned Scan Index 2024 SIGMOD 4.5058812e-05
8,781 Bringing Cloud-Native Storage to SAP IQ 2021 SIGMOD 4.4479873e-05
9,034 Extending SQL to Return a Subdatabase 2025 SIGMOD 4.3997447e-05
10,105 RABIT: Efficient Range Queries with Bitmap Indexing 2026 SIGMOD 4.1905499e-05
10,106 Regular Expression Indexing for Log Analysis 2026 SIGMOD 4.1905499e-05
10,179 LiveBin: A Localized and Version-Aware Binned Scan Index 2026 SIGMOD 4.1905499e-05
12,303 Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes 2009 PODS 4.1905499e-05
12,683 A Data Warehousing Architecture for Enabling Service Provisioning Process 2001 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

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
121 Improved Query Performance with Variant Indexes 1997 SIGMOD 0.00045429472
456 "One Size Fits All" Database Architectures Do Not Work For DSS 1995 SIGMOD 0.00022703892
828 Bit Transposed Files 1985 VLDB 0.00016141484
3,601 Database Buffer Size Investigation for OLTP Workloads 1997 SIGMOD 6.9285208e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,485 On the Analysis of Indexing Schemes 1997 PODS 0.00011698762
2,821 An Experimental Study of Bitmap Compression vs. Inverted List Compression 2017 SIGMOD 8.0639288e-05
5,695 Optimal Indexing Using Near-Minimal Space [Extended Abstract] 2003 PODS 5.3675705e-05
9,633 Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads 2015 VLDB 4.309053e-05
2,984 On the Performance of Bitmap Indices for High Cardinality Attributes 2004 VLDB 7.7768363e-05
5,605 Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps 2006 VLDB 5.413565e-05
4,532 Query Optimization for Selections using Bitmaps 1999 SIGMOD 6.1027943e-05
2,065 Optimizing Queries On Compressed Bitmaps 2000 VLDB 9.6467359e-05
1,955 Performance Measurements of Compressed Bitmap Indices 1999 VLDB 9.9641178e-05
1,701 An Efficient Bitmap Encoding Scheme for Selection Queries 1999 SIGMOD 0.00010828605