EDBT/ICDT 2009 Joint Conference

Electronic Conference Proceedings

• Welcome
• Full Program
• ICDT Sessions
• ICDT Papers
• EDBT Sessions
  • Invited Talks
  • Research Track
    • System Architectures
    • Spatio-Temporal
    • Database Summarization
    • Query Processing
    • XML, XPath, XQuery
    • Graph Techniques
    • Privacy & Security
    • Data Models
    • Stream Processing
    • XML, XPath, XQuery
    • Database Summarization
    • Query Processing
    • Top-K Techniques
    • Graph Techniques
    • Data Mining
    • Heterogeneous & Distributed
    • System Architectures
    • Privacy & Security
    • Uncertainty
    • Workflow Techniques
    • Multi-Dimensional
    • Caching Techniques
    • Information Retrieval
    • Query Processing
    • Top-K Techniques
    • Potpourri
    • Provenance
    • Spatio-Temporal
    • Skylines
    • Transaction Processing
  • Industrial Track
  • Demo Track
  • Tutorials
• EDBT Papers
• Author Index
• Workshops

Secondary Bitmap Indexes with Vertical and Horizontal Partitioning

Authors

• Guadalupe Canahuate (Ohio State University, USA)
• Tan Apaydin (Ohio State University, USA)
• Ahmet Sacan (Ohio State University, USA)
• Hakan Ferhatosmanoglu (Ohio State University, USA)

Abstract

Traditional bitmap indexes are utilized as a special type of primary or clustered indexes where the queries are answered by performing fast logical operations supported by hardware. Answers are mapped to the physical data by using the row id of each tuple. Bitmaps represent the i-th tuple in the original table with the i-th bit position of the index. Run-length compression is used to reduce the size of the bitmaps and it has been shown that ordered data is significantly better compressed. However, for large-scale and dynamic datasets it is infeasible to keep the data always sorted. Partitioning can be used to keep the data in smaller and manageable chunks, where a different bitmap index is built for each chunk. We propose a novel bitmap index design with partitioning which serves as basis for non-clustered bitmap indexes. Individual bitmaps are not stored, only an Existence Bitmap (EB) for the existing ranks of the full table is maintained. This approach improves update performance of sorted bitmaps and does not require maintaining a heap as the underlying table, nor the same ordering for all the partitions. A one dimensional index is used over the ranks to map the bits in the EB to the physical order of the data, which allows queries to run even faster. The proposed approach, called ranked Non-Clustered Bitmaps (rNCB), is compared against traditional bitmaps using FastBit and shows significant performance gains.

Session

EDBT Research Session 17: System Architectures (Thursday, March 26, 09:00—10:30)