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
3027
Venue
SIGMOD
Year
1998
Pagerank
0.00014532778
Overall Rank
1,035 | 92.81%
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
857 The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds 2020 VLDB 0.00015882892
1,312 Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes 2016 SIGMOD 0.00012652548
1,375 FITing-Tree: A Data-aware Index Structure 2019 SIGMOD 0.00012303141
1,704 An Efficient Bitmap Encoding Scheme for Selection Queries 1999 SIGMOD 0.000108332
2,757 Parallel Data Analysis Directly on Scientific File Formats 2014 SIGMOD 8.1679384e-05
2,862 An Experimental Study of Bitmap Compression vs. Inverted List Compression 2017 SIGMOD 7.9898539e-05
2,986 On the Performance of Bitmap Indices for High Cardinality Attributes 2004 VLDB 7.778912e-05
3,157 High-Dimensional OLAP: A Minimal Cubing Approach 2004 VLDB 7.4656511e-05
3,571 Lightning Fast and Space Efficient Inequality Joins 2015 VLDB 6.9580858e-05
3,856 Bit-Sliced Index Arithmetic 2001 SIGMOD 6.6942616e-05
4,528 Query Optimization for Selections using Bitmaps 1999 SIGMOD 6.1083382e-05
4,681 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.0034918e-05
4,711 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 5.9790683e-05
5,119 Design Tradeoffs of Data Access Methods 2016 SIGMOD 5.6807904e-05
5,194 Bitvector-aware Query Optimization for Decision Support Queries 2020 SIGMOD 5.6368209e-05
5,322 Generalized Hash Teams for Join and Group-by 1999 VLDB 5.5701077e-05
5,346 UpBit: Scalable In-Memory Updatable Bitmap Indexing 2016 SIGMOD 5.5561846e-05
5,596 Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps 2006 VLDB 5.4181535e-05
5,749 BinDex: A Two-Layered Index for Fast and Robust Scans 2020 SIGMOD 5.3418923e-05
6,199 Supporting RFID-based Item Tracking Applications in Oracle DBMS Using a Bitmap Datatype 2005 VLDB 5.1605194e-05
7,045 Processing Star Queries on Hierarchically-Clustered Fact Tables 2002 VLDB 4.8528709e-05
7,831 CUBIT: Concurrent Updatable Bitmap Indexing 2025 VLDB 4.6387445e-05
8,430 Tree-Encoded Bitmaps 2020 SIGMOD 4.5154973e-05
8,447 Cabin: a Compressed Adaptive Binned Scan Index 2024 SIGMOD 4.5102052e-05
8,785 Bringing Cloud-Native Storage to SAP IQ 2021 SIGMOD 4.4522556e-05
9,031 Extending SQL to Return a Subdatabase 2025 SIGMOD 4.4039656e-05
10,105 RABIT: Efficient Range Queries with Bitmap Indexing 2026 SIGMOD 4.1945683e-05
10,106 Regular Expression Indexing for Log Analysis 2026 SIGMOD 4.1945683e-05
10,179 LiveBin: A Localized and Version-Aware Binned Scan Index 2026 SIGMOD 4.1945683e-05
12,295 Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes 2009 PODS 4.1945683e-05
12,674 A Data Warehousing Architecture for Enabling Service Provisioning Process 2001 VLDB 4.1945683e-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.00045447517
457 "One Size Fits All" Database Architectures Do Not Work For DSS 1995 SIGMOD 0.00022713791
832 Bit Transposed Files 1985 VLDB 0.00016152615
3,595 Database Buffer Size Investigation for OLTP Workloads 1997 SIGMOD 6.9373987e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,488 On the Analysis of Indexing Schemes 1997 PODS 0.00011699446
2,862 An Experimental Study of Bitmap Compression vs. Inverted List Compression 2017 SIGMOD 7.9898539e-05
5,682 Optimal Indexing Using Near-Minimal Space [Extended Abstract] 2003 PODS 5.372736e-05
9,633 Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads 2015 VLDB 4.3131863e-05
2,986 On the Performance of Bitmap Indices for High Cardinality Attributes 2004 VLDB 7.778912e-05
5,596 Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps 2006 VLDB 5.4181535e-05
4,528 Query Optimization for Selections using Bitmaps 1999 SIGMOD 6.1083382e-05
2,061 Optimizing Queries On Compressed Bitmaps 2000 VLDB 9.6529345e-05
1,951 Performance Measurements of Compressed Bitmap Indices 1999 VLDB 9.9685919e-05
1,704 An Efficient Bitmap Encoding Scheme for Selection Queries 1999 SIGMOD 0.000108332