Home // DBKDA 2011, The Third International Conference on Advances in Databases, Knowledge, and Data Applications // View article

A Concept for a Compression Scheme of Medium-Sparse Bitmaps

Authors:
Andreas Schmidt
Mirko Beine

Keywords: Compressed bitmaps,WAH algorithm, RLE, CPU-memory-gap

Abstract:
In this paper, we present an extension of the WAH algorithm, which is currently considered one of the fastest and most CPU-efficient bitmap compression algorithm available. The algorithm is based on run length encoding (RLE) and its encoding/decoding units are chuncs of the processor's word size. The fact that the algorithm works on a blocking factor, which is a multiple of the CPU word size, makes the algorithm extremely fast, but also leads to a bad compression ratio in the case of medium-sparse bitmaps (1% - 10%), which is what we are mainly interested in. A recent extension of the WAH algorithm is the PLWAH algorithm, which has a better compression ratio by piggybacking trailing words, which look "similar" to the previous fill-block. The interesting point here is that the algorithm also is described to be faster than the original WAH version under most circumstances, even though the compression algorithm is more complex. Therefore, the concept of the PLWAH algorithm was extended to allow socalled "polluted blocks" to appear not only at the end of a fillblock, but also multiple times inside, leading to much longer fill lengths and, as a consequence, to a smaller memory footprint, which again is expected to reduce the overall processing time of the algorithm when performing operations on compressed bitmaps.

Pages: 192 to 195

Copyright: Copyright (c) IARIA, 2011

Publication date: January 23, 2011

Published in: conference

ISSN: 2308-4332

ISBN: 978-1-61208-115-1

Location: St. Maarten, The Netherlands Antilles

Dates: from January 23, 2011 to January 28, 2011