The DOI matches its Crossref record; 4 of the 4 references it cites were found in a registry or an index.
Bitmap index design and evaluation
Abstract
Bitmap indexing has been touted as a promising approach for processing complex adhoc queries in read-mostly environments, like those of decision support systems. Nevertheless, only few possible bitmap schemes have been proposed in the past and very little is known about the space-time tradeoff that they offer. In this paper, we present a general framework to study the design space of bitmap indexes for selection queries and examine the disk-space and time characteristics that the various alternative index choices offer. In particular, we draw a parallel between bitmap indexing and number representation in different number systems, and define a space of two orthogonal dimensions that captures a wide array of bitmap indexes, both old and new. Within that space, we identify (analytically or experimentally) the following interesting points: (1) the time-optimal bitmap index; (2) the space-optimal bitmap index; (3) the bitmap index with the optimal space-time tradeoff (knee); and (4) the time-optimal bitmap index under a given disk-space constraint. Finally, we examine the impact of bitmap compression and bitmap buffering on the space-time tradeoffs among those indexes. As part of this work, we also describe a bitmap-index-based evaluation algorithm for selection queries that represents an improvement over earlier proposals. We believe that this study offers a useful first set of guidelines for physical database design using bitmap indexes.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An overview of data warehousing and OLAP technology
Chaudhuri, S., & Dayal, U. (1997) · ACM SIGMOD Record · doi:10.1145/248603.248616 · Cited by 2,424
Query evaluation techniques for large databases
Graefe, G. (1993) · ACM Computing Surveys · doi:10.1145/152610.152611 · Cited by 1,262
Improved query performance with variant indexes
O'Neil, P. E., & Quass, D. (1997) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/253260.253268 · Cited by 488
Database buffer size investigation for OLTP workloads
Tsuei, T.-F., Packer, A. N., & Ko, K.-T. (1997) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/253260.253279 · Cited by 28
Cited by
An overview of the HDF5 technology suite and its applications
Folk, M., Heber, G., Koziol, Q., Pourmal, E., & Robinson, D. (2011) · Proceedings of the EDBT/ICDT 2011 Workshop on Array Databases · doi:10.1145/1966895.1966900 · Cited by 507
Ambit: in-memory accelerator for bulk bitwise operations using commodity DRAM technology
Seshadri, V., Lee, D., Mullins, T., Hassan, H., Boroumand, A., Kim, J., Kozuch, M. A., Mutlu, O., Gibbons, P. B., & Mowry, T. C. (2017) · Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture · doi:10.1145/3123939.3124544 · Cited by 434
Processing data where it makes sense: Enabling in-memory computation
Mutlu, O., Ghose, S., Gómez-Luna, J., & Ausavarungnirun, R. (2019) · Microprocessors and Microsystems · doi:10.1016/j.micpro.2019.01.009 · Cited by 300
The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds
Ferragina, P., & Vinciguerra, G. (2020) · Proceedings of the VLDB Endowment · doi:10.14778/3389133.3389135 · Cited by 274
Buddy-RAM: Improving the Performance and Efficiency of Bulk Bitwise Operations Using DRAM
Seshadri, V., Lee, D., Mullins, T., Hassan, H., Boroumand, A., Kim, J., Kozuch, M. A., Mutlu, O., Gibbons, P. B., & Mowry, T. C. (2016) · arXiv · doi:10.48550/arxiv.1611.09988 · Cited by 54
Metadata
- Authors
- Chan, C.-Y., & Ioannidis, Y. E.
- Venue
- Proceedings of the 1998 ACM SIGMOD international conference on Management of data
- Publisher
- ACM
- Published
- 1998-06
- Pages
- 355-366
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W1982945449
- Cited by
- 360
- References
- 4
- FWCI
- 14.28
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Bitmap index design and evaluation. https://app.cochat.ai/papers/10.1145/276304.276336
- The paper
- Chan, C.-Y., & Ioannidis, Y. E. (1998). Bitmap index design and evaluation. Proceedings of the 1998 ACM SIGMOD international conference on Management of data. https://doi.org/10.1145/276304.276336
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.