Performances of Multi-Level and Multi-Component Compressed BitmapIndices

Wu, Kesheng ; Stockinger, Kurt ; Shoshani, Arie

Lawrence Berkeley National Laboratory

关键词: 99;    Compression;    Validation Compressed Bitmap Index Multi-Component Index Multi-Level Indexbitmap Index Performance;    Performance;    Compressed Bitmap Index Multi-Component Index Multi-Level Indexbitmap Index Performance;   

DOI  :  10.2172/920347
RP-ID  :  LBNL--60891
RP-ID  :  DE-AC02-05CH11231
RP-ID  :  920347

美国|英语

来源: UNT Digital Library

【 摘 要 】

This paper presents a systematic study of two large subsetsof bitmap indexing methods that use multi-component and multi-levelencodings. Earlier studies on bitmap indexes are either empirical or foruncompressed versions only. Since most of bitmap indexes in use arecompressed, we set out to study the performance characteristics of thesecompressed indexes. To make the analyses manageable, we choose to use aparticularly simple, but efficient, compression method called theWord-Aligned Hybrid (WAH) code. Using this compression method, a numberof bitmap indexes are shown to be optimal because their worst-case timecomplexities for answering a query is a linear function of the number ofhits. Since compressed bitmap indexes behave drastically different fromuncompressed ones, our analyses also lead to a number of new methods thatare much more efficient than commonly used ones. As a validation for theanalyses, we implement a number of the best methods and measure theirperformance against well-known indexes. The fastest new methods arepredicted and observed to be 5 to 10 times faster than well-knownindexing methods.