ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Bitmap Index Design and Evaluation.

Chee Yong Chan, Yannis E. Ioannidis: Bitmap Index Design and Evaluation. SIGMOD Conference 1998: 355-366
@inproceedings{DBLP:conf/sigmod/ChanI98,
  author    = {Chee Yong Chan and
               Yannis E. Ioannidis},
  editor    = {Laura M. Haas and
               Ashutosh Tiwary},
  title     = {Bitmap Index Design and Evaluation},
  booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
               on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-995-5},
  pages     = {355-366},
  ee        = {http://doi.acm.org/10.1145/276304.276336, db/conf/sigmod/ChanI98.html},
  crossref  = {DBLP:conf/sigmod/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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.

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ... Online Version (ACM WWW Account required): Full Text in PDF Format

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Laura M. Haas, Ashutosh Tiwary (Eds.): SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2-4, 1998, Seattle, Washington, USA. ACM Press 1998, ISBN 0-89791-995-5 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 27(2), June 1998
Contents

Online Edition: ACM SIGMOD

[Abstract]
[Full Text (Postscript)]

References

[1]
...
[2]
...
[3]
Surajit Chaudhuri, Umeshwar Dayal: An Overview of Data Warehousing and OLAP Technology. SIGMOD Record 26(1): 65-74(1997) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
...
[6]
Clark D. French: ``One Size Fits All'' Database Architectures Do Not Work for DDS. SIGMOD Conference 1995: 449-450 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Patrick E. O'Neil: Model 204 Architecture and Performance. HPTS 1987: 40-59 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Patrick E. O'Neil, Goetz Graefe: Multi-Table Joins Through Bitmapped Join Indices. SIGMOD Record 24(3): 8-11(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Patrick E. O'Neil, Dallan Quass: Improved Query Performance with Variant Indexes. SIGMOD Conference 1997: 38-49 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Thin-Fong Tsuei, Allan Packer, Keng-Tai Ko: Database Buffer Size Investigation for OLTP Workloads (Experience Paper). SIGMOD Conference 1997: 112-122 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
...
[13]
Harry K. T. Wong, Jianzhong Li, Frank Olken, Doron Rotem, Linda Wong: Bit Transposition for Very Large Scientific and Statistical Databases. Algorithmica 1(3): 289-309(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Harry K. T. Wong, Hsiu-Fen Liu, Frank Olken, Doron Rotem, Linda Wong: Bit Transposed Files. VLDB 1985: 448-457 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:21:34 2010 by Michael Ley (ley@uni-trier.de)