ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Performance Measurements of Compressed Bitmap Indices.

Theodore Johnson: Performance Measurements of Compressed Bitmap Indices. VLDB 1999: 278-289
@inproceedings{DBLP:conf/vldb/Johnson99,
  author    = {Theodore Johnson},
  editor    = {Malcolm P. Atkinson and
               Maria E. Orlowska and
               Patrick Valduriez and
               Stanley B. Zdonik and
               Michael L. Brodie},
  title     = {Performance Measurements of Compressed Bitmap Indices},
  booktitle = {VLDB'99, Proceedings of 25th International Conference on Very
               Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,
               UK},
  publisher = {Morgan Kaufmann},
  year      = {1999},
  isbn      = {1-55860-615-7},
  pages     = {278-289},
  ee        = {db/conf/vldb/Johnson99.html},
  crossref  = {DBLP:conf/vldb/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Bitmap indices are commonly used by DBMS's to accelerate decision support queries. A bitmap index is a collection of bitmaps in which each bit is mapped to a record ID (RID). A bit in a bitmap is set if the corresponding RID has property P (i.e., the RID represents a customer that lives in New York), and is reset otherwise. A significant advance of bitmap indices is that complex logical selection operations can be perfromed very quickly, by performing bit-wise AND, OR, and NOT operations. Bitmap are also compact representations of densely popolated sets. By using bitmap compression techniques, they are also compact representations of sparsely populated sets.

In spite of the great interest in bitmap indices, little has been published about the comparative performance of bitmap compression algorithms (i.e., compression ratios and times for Boolean operations) in a DBMS environment. We have implemented the three main bitmap compression techniques (LZ compression, variable bit-length codes, and variable byte-length codes) and built a generic bitmap index from them. We have tested each of these compression techniques (and their variants) for their compression ratio on a wide variety of synthetic and actual bitmap indices. Because bitmap indices are valuable for complex selection conditions, we evaluate four methods for performing a Boolean operation between compressed bitmaps, including methods that use compressed or partially uncompressed bitmaps directly.

Our results show that the best bitmap index compression technique and the best Boolean operation algorithms strongly depend on the bitmaps being compressed or operated on and the operations being performed. These results are a step towards understanding the space-time tradeoff in adaptive compressed bitmap indices, developing a bitmap index design methodology for compressed bitmaps, and optimizing Boolean expression evaluation on compressed bitmaps.

Copyright © 1999 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

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

Printed Edition

Malcolm P. Atkinson, Maria E. Orlowska, Patrick Valduriez, Stanley B. Zdonik, Michael L. Brodie (Eds.): VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK. Morgan Kaufmann 1999, ISBN 1-55860-615-7
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
...
[2]
...
[3]
Chee Yong Chan, Yannis E. Ioannidis: Bitmap Index Design and Evaluation. SIGMOD Conference 1998: 355-366 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
...
[6]
Jean-Loup Gailly, Mark Adler: Zlib Home Page (old location: http://quest.jpl.nasa.gov/zlib). http://www.cdrom.com/pub/infozip/zlib/ CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Alistair Moffat, Justin Zobel: Parameterised Compression for Sparse Bitmaps. SIGIR 1992: 274-285 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]
...
[12]
...
[13]
Ming-Chuan Wu, Alejandro P. Buchmann: Encoded Bitmap Indexing for Data Warehouses. ICDE 1998: 220-230 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:08 2010 by Michael Ley (ley@uni-trier.de)