Name
Abstract | ||
|---|---|---|
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 row-reordering heuristics. Simply permuting the columns of the table can increase the sorting efficiency by 40%. Secondary contributions include efficient algorithms to construct and aggregate bitmaps. The effect of word length is also reviewed by constructing 16-bit, 32-bit and 64-bit indexes. Using 64-bit CPUs, we find that 64-bit indexes are slightly faster than 32-bit indexes despite being nearly twice as large. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.datak.2009.08.006 | data and knowledge engineering |
Keywords | DocType | Volume |
bitmap index,indexing,64-bit cpus,efficient algorithm,32-bit index,multidimensional databases,logical operation,cpu usage,index size,gray codes,64-bit index,aggregate bitmaps,compression,word-aligned hybrid,gray code,run length encoding,input output,indexation,multidimensional database | Journal | 69 |
Issue | ISSN | Citations |
1 | Data & Knowledge Engineering, Volume 69, Issue 1, 2010, Pages 3-28 | 52 |
PageRank | References | Authors |
1.60 | 30 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Lemire | 1 | 821 | 52.14 |
| Owen Kaser | 2 | 325 | 24.02 |
| Kamel Aouiche | 3 | 233 | 13.32 |