Optimizing bitmap indices with efficient compression

ABSTRACT

Bitmap indices are efficient for answering queries on low-cardinality attributes. In this article, we present a new compression scheme called Word-Aligned Hybrid (WAH) code that makes compressed bitmap indices efficient even for high-cardinality attributes. We further prove that the new compressed bitmap index, like the best variants of the B-tree index, is optimal for one-dimensional range queries. More specifically, the time required to answer a one-dimensional range query is a linear function of the number of hits. This strongly supports the well-known observation that compressed bitmap indices are efficient for multidimensional range queries because results of one-dimensional range queries computed with bitmap indices can be easily combined to answer multidimensional range queries. Our timing measurements on range queries not only confirm the linear relationship between the query response time and the number of hits, but also demonstrate that WAH compressed indices answer queries faster than the commonly used indices including projection indices, B-tree indices, and other compressed bitmap indices.

REFERENCES

• 1: Sihem Amer-Yahia , Theodore Johnson, Optimizing Queries on Compressed Bitmaps, Proceedings of the 26th International Conference on Very Large Data Bases, p.329-338, September 10-14, 2000
• 2: Antoshenkov, G. 1994. Byte-aligned bitmap compression. Tech. rep. Oracle Corp., Redwood Shores, CA. U.S. Patent number 5,363,098.
• 3: Gennady Antoshenkov , Mohamed Ziauddin, Query processing and optimization in Oracle Rdb, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.229-237, December 1996 [doi>10.1007/s007780050026]
• 4: Chee-Yong Chan , Yannis E. Ioannidis, Bitmap index design and evaluation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.355-366, June 01-04, 1998, Seattle, Washington, United States
• 5: Chee-Yong Chan , Yannis E. Ioannidis, An efficient bitmap encoding scheme for selection queries, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.215-226, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 6: Surajit Chaudhuri , Umeshwar Dayal, An overview of data warehousing and OLAP technology, ACM SIGMOD Record, v.26 n.1, p.65-74, March 1997 [doi>10.1145/248603.248616]
• 7: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 8: Czech, Z. J. and Majewski, B. S. 1993. A linear time algorithm for finding minimal perfect hash functions. Comput. J. 36, 6 (Dec.), 579--587.
• 9: Edward A. Fox , Qi Fan Chen , Amjad M. Daoud , Lenwood S. Heath, Order-preserving minimal perfect hash functions and information retrieval, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.281-308, July 1991 [doi>10.1145/125187.125200]
• 10: Furuse, K., Asada, K., and Iizawa, A. 1995. Implementation and performance evaluation of compressed bit-sliced signature files. In Information Systems and Data Management, 6th International Conference, CISMOD'95, Bombay, India, November 15--17, 1995, Proceedings, S. Bhalla, Ed. Lecture Notes in Computer Science, vol. 1006. Springer, Berlin, Germany, 164--177.
• 11: Gailly, J. and Adler, M. 1998. zlib 1.1.3 manual. Source code available online at http://-www.info-zip.org/pub/-infozip/zlib.
• 12: Yoshiharu Ishikawa , Hiroyuki Kitagawa , Nobuo Ohbo, Evaluation of signature files as set access facilities in OODBs, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.247-256, May 25-28, 1993, Washington, D.C., United States
• 13: Theodore Johnson, Performance Measurements of Compressed Bitmap Indices, Proceedings of the 25th International Conference on Very Large Data Bases, p.278-289, September 07-10, 1999
• 14: Jürgens, M. and Lenz, H.-J. 1999. Tree based indexes vs. bitmap indexes---a performance study. In Proceedings of the International Workshop on Design and Management of Data Warehouses, DMDW'99, Heidelberg, Germany, June 14-15, 1999, S. Gatziu, M. A. Jeusfeld, M. Staudt, and Y. Vassiliou, Eds.
• 15: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 16: Nick Koudas, Space efficient bitmap indexing, Proceedings of the ninth international conference on Information and knowledge management, p.194-201, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354819]
• 17: Dik Lun Lee , Young Man Kim , Gaurav Patel, Efficient Signature File Methods for Text Retrieval, IEEE Transactions on Knowledge and Data Engineering, v.7 n.3, p.423-435, June 1995 [doi>10.1109/69.390248]
• 18: Alistair Moffat , Justin Zobel, Parameterised compression for sparse bitmaps, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.274-285, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133210]
• 19: Patrick E. O'Neil, Model 204 Architecture and Performance, Proceedings of the 2nd International Workshop on High Performance Transaction Systems, p.40-59, September 28-30, 1987
• 20: Patrick O'Neil , Elizabeth O'Neil, Database--Principles, Programming and Performance, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 21: Patrick O'Neil , Dallan Quass, Improved query performance with variant indexes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.38-49, May 11-15, 1997, Tucson, Arizona, United States
• 22: Patrick O'Neil , Goetz Graefe, Multi-table joins through bitmapped join indices, ACM SIGMOD Record, v.24 n.3, p.8-11, Sept. 1995 [doi>10.1145/211990.212001]
• 23: A. Shoshani , L. M. Bernardo , H. Nordberg , D. Rotem , A. Sim, Multidimensional Indexing and Query Coordination for Tertiary Storage Management, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.214, July 28-30, 1999 [doi>10.1109/SSDM.1999.787637]
• 24: Kurt Stockinger , Dirk Düllmann , Wolfgang Hoschek , Erich Schikuta, Improving the Performance of High-Energy Physics Analysis through Bitmap Indices, Proceedings of the 11th International Conference on Database and Expert Systems Applications, p.835-845, September 04-08, 2000
• 25: Kurt Stockinger , Kesheng Wu , Arie Shoshani, Strategies for processing ad hoc queries on large data warehouses, Proceedings of the 5th ACM international workshop on Data Warehousing and OLAP, p.72-79, November 08-08, 2002, McLean, Virginia, USA [doi>10.1145/583890.583901]
• 26: Wong, H. K. T., Liu, H.-F., Olken, F., Rotem, D., and Wong, L. 1985. Bit transposed files. In Proceedings of VLDB 85 (Stockholm, Sweden). 448--457.
• 27: Wu, K.-L. and Yu, P. 1996. Range-based bitmap indexing for high cardinality attributes with skew. Tech. rep. RC 20449. IBM Watson Research Division, Yorktown Heights, NY.
• 28: Ming-Chuan Wu , Alejandro P. Buchmann, Encoded Bitmap Indexing for Data Warehouses, Proceedings of the Fourteenth International Conference on Data Engineering, p.220-230, February 23-27, 1998
• 29: Kesheng Wu , Wendy Koegler , Jacqueline Chen , Arie Shoshani, Using bitmap index for interactive exploration of large datasets, Proceedings of the 15th international conference on Scientific and statistical database management, p.65-74, July 09-11, 2003, Cambridge, MA [doi>10.1109/SSDM.2003.1214955]
• 30: Kesheng Wu , Ekow J. Otoo , Arie Shoshani, A performance comparison of bitmap indexes, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502689]
• 31: Kesheng Wu , Ekow J. Otoo , Arie Shoshani, Compressing Bitmap Indexes for Faster Search Operations, Proceedings of the 14th International Conference on Scientific and Statistical Database Management, p.99-108, July 24-26, 2002 [doi>10.1109/SSDM.2002.1029710]
• 32: Wu, K., Otoo, E. J., and Shoshani, A. 2004. On the performance of bitmap indices for high-cardinality attributes. In Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, Canada, August 31-September 3, 2004, M. A. Nascimento, M. T. Özsu, D. Kossmann, R. J. Miller, J. A. Blakeley, and K. B. Schiefer, Eds. Morgan Kaufmann, San Francisco, CA, 24--35.
• 33: Wu, K., Otoo, E. J., Shoshani, A., and Nordberg, H. 2001b. Notes on design and implementation of compressed bit vectors. Tech. rep. LBNL/PUB-3161. Lawrence Berkeley National Laboratory, Berkeley, CA.
• 34: Ziv, J. and Lempel, A. 1977. A universal algorithm for sequential data compression. IEEE Trans. Inform. Theor. 23, 3, 337--343.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Performance

Keywords:
Compression, bitmap index, query processing