Faculty Advisor
Sawin, Jason
Area of Study
Science and Mathematics
Publication Date
Summer 2011
Abstract
A bitmap index is a type of database index in which querying is implemented using logical operations (AND, OR, XOR) at the CPU level. To accelerate these operations, we compress the bitmaps using run-length encoding (RLE). To improve RLE, and thus improve the efficiency of the compression, we can reorder the rows of the bitmap to maximize the run lengths in the columns. Finding the perfect row-reordering is NP-hard, so approximations must be used. A commonly-used approximation for row-reordering is lexicographically sorting the bitmap. Unfortunately, bitmap indices are often to large to fit entirely into memory, so a full sort is often unfeasible. A partition-sorting scheme is investigated in which a bitmap index is split into several partitions which are then sorted individually. This partitioned-sorting scheme achieves compression efficiency approaching a full sort, with enormous savings in CPU time.
Recommended Citation
Brooks, Kyle, "Partitioned Compression of Bitmap Indices" (2011). Summer Research. 129.
https://soundideas.pugetsound.edu/summer_research/129
Rights
Publisher
University of Puget Sound