Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes

Details Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes

2008-08-15

arxiv.org/abs/0808.2083v3

Computer Science

Databases

To appear in proceedings of DOLAP 2008

Scientific paper

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%.

Affiliated with

Also associated with

No associations

Rating

Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-650587