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

50 %
50 %
Information about Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap...
Technology

Published on November 11, 2008

Author: lemire

Source: slideshare.net

Description

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

Add a comment

Related presentations

Related pages

Histogram-Aware Sorting for Enhanced Word-Aligned ...

Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes Owen Kaser Dept. of CSAS University of New Brunswick 100 Tucker Park Road
Read more

Histogram-Aware Sorting for Enhanced Word-Aligned ...

Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes Owen Kaser1, Daniel Lemire2, Kamel Aouiche2 1- University of New Brunswick ...
Read more

Title: Histogram-Aware Sorting for Enhanced Word-Aligned ...

... Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes. ... as Word-Aligned Hybrid (WAH) compression. ... sorting ...
Read more

Histogram-Aware Sorting for Enhanced Word-Aligned ...

Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes [r-libre/223]
Read more

Aouiche, Histogram-aware sorting for enhanced word-aligned ...

... {Kaser08aouiche,histogram-aware ... {Aouiche, Histogram-aware sorting for enhanced word-aligned compression} ... Bitmap indexes must be ...
Read more

Histogram-Aware Sorting for Enhanced Word-Aligned ...

Title: Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes: Authors: Kaser, Owen; Lemire, Daniel; Aouiche, Kamel: Publication:
Read more

Histogram-aware sorting for enhanced word-aligned ...

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

Aouiche, Histogram-aware sorting for enhanced word-aligned ...

... Pradeep Teregowda): Bitmap indexes ... Histogram-aware sorting for enhanced word-aligned compression ... Histogram-aware sorting for enhanced ...
Read more

Performance evaluation of word-aligned compression methods ...

... Histogram-aware sorting for enhanced word-aligned compression in ... Performance evaluation of word-aligned compression methods for bitmap indices
Read more