Histogram-aware sorting for enhanced word-aligned compression in bitmap indexes

ABSTRACT

Bitmap indexes must be compressed to reduce input/output costs and minimize CPU usage. To accelerate logical operations (AND, OR, XOR) over bitmaps, we use techniques based on run-length encoding (RLE), such as Word-Aligned Hybrid (WAH) compression. These techniques are sensitive to the order of the rows: a simple lexicographical sort can divide the index size by 9 and make indexes several times faster. We investigate reordering heuristics based on computed attribute-value histograms. Simply permuting the columns of the table based on these histograms can increase the sorting efficiency by 40%.

REFERENCES

• 1: G. Antoshenkov, Byte-aligned bitmap compression, Proceedings of the Conference on Data Compression, p.476, March 28-30, 1995
• 2: K. Aouiche, D. Lemire, and O. Kaser. Tri de la table de faits et compression des index bitmaps avec alignement sur les mots. available from http://arxiv.org/abs/0805.3339.
• 3: L. Bellatreche, R. Missaoui, H. Necir, and H. Drias. Selection and pruning algorithms for bitmap index selection problem using data mining. LNCS, 4654:221, 2007.
• 4: G. Canahuate, H. Ferhatosmanoglu, and A. Pinar. Improving bitmap index compression by data reorganization. http://hpcrd.lbl.gov/~apinar/papers/TKDE06.pdf (checked 2008-05-30), 2006.
• 5: 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
• 6: 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
• 7: Ravi Darira , Karen C. Davis , Jennifer Grommon-Litton, Heuristic design of property maps, Proceedings of the 9th ACM international workshop on Data warehousing and OLAP, November 10-10, 2006, Arlington, Virginia, USA [doi>10.1145/1183512.1183529]
• 8: K. Davis and A. Gupta. Data Warehouses and OLAP: Concepts, Architectures, and Solutions, chapter Indexing in Data Warehouses. IRM Press, 2007.
• 9: S. Hettich and S. D. Bay. The UCI KDD archive. http://kdd.ics.uci.edu (checked 2008-04-28), 2000.
• 10: M. Hirabayashi. QDBM: Quick database manager. http://qdbm.sourceforge.net/ (checked 2008-02-22), 2006.
• 11: O. Kaser, S. Keith, and D. Lemire. The LitOLAP project: Data warehousing with literature. In CaSTA'06, 2006.
• 12: 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]
• 13: Netflix, Inc. Nexflix prize. http://www.netflixprize.com (checked 2008-04-28), 2007.
• 14: Ali Pinar , Tao Tao , Hakan Ferhatosmanoglu, Compressing Bitmap Indices by Data Reorganization, Proceedings of the 21st International Conference on Data Engineering, p.310-321, April 05-08, 2005 [doi>10.1109/ICDE.2005.35]
• 15: M. F. Porter, An algorithm for suffix stripping, Readings in information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 16: Project Gutenberg Literary Archive Foundation. Project Gutenberg. http://www.gutenberg.org/ (checked 2007-05-30), 2007.
• 17: Doron Rotem , Kurt Stockinger , Kesheng Wu, Minimizing I/O Costs of Multi-Dimensional Queries with Bitmap Indices, Proceedings of the 18th International Conference on Scientific and Statistical Database Management, p.33-44, July 03-05, 2006 [doi>10.1109/SSDBM.2006.33]
• 18: Y. Sharma and N. Goyal. An efficient multi-component indexing embedded bitmap compression for data reorganization. Information Technology Journal, 7(1):160--164, 2008.
• 19: 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]
• 20: K. Stockinger, K. Wu, and A. Shoshani. Evaluation strategies for bitmap indices with binning. In DEXA 2004, 2004.
• 21: TPC. DBGEN 2.4.0. http://www.tpc.org/tpch/ (checked 2007-12-4), 2006.
• 22: Peter D. Turney , Michael L. Littman, Corpus-based Learning of Analogies and Semantic Relations, Machine Learning, v.60 n.1-3, p.251-278, September 2005 [doi>10.1007/s10994-005-0913-1]
• 23: Harry K. T. Wong , Hsiu-Fen Liu , Frank Olken , Doron Rotem , Linda Wong, Bit transposed files, Proceedings of the 11th international conference on Very Large Data Bases, p.448-457, August 21-23, 1985, Stockholm, Sweden
• 24: 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]
• 25: Kesheng Wu , Ekow J. Otoo , Arie Shoshani, Optimizing bitmap indices with efficient compression, ACM Transactions on Database Systems (TODS), v.31 n.1, p.1-38, March 2006 [doi>10.1145/1132863.1132864]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Experimentation, Performance

Keywords:
bitmap index, compression, data warehouse, gray codes, indexing