Tri de la table de faits et compression des index bitmaps avec alignement sur les mots
| dc.creator | Aouiche, Kamel | |
| dc.creator | Lemire, Daniel | |
| dc.creator | Kaser, Owen | |
| dc.date | 2008-05-21 | |
| dc.date | 2008-08-15 | |
| dc.date.accessioned | 2026-07-07T09:56:36Z | |
| dc.date.available | 2026-07-07T09:56:36Z | |
| dc.description | Bitmap indexes are frequently used to index multidimensional data. They rely mostly on sequential input/output. Bitmaps can be compressed to reduce input/output costs and minimize CPU usage. The most efficient compression techniques are based on run-length encoding (RLE), such as Word-Aligned Hybrid (WAH) compression. This type of compression accelerates logical operations (AND, OR) over the bitmaps. However, run-length encoding is sensitive to the order of the facts. Thus, we propose to sort the fact tables. We review lexicographic, Gray-code, and block-wise sorting. We found that a lexicographic sort improves compression--sometimes generating indexes twice as small--and make indexes several times faster. While sorting takes time, this is partially offset by the fact that it is faster to index a sorted table. Column order is significant: it is generally preferable to put the columns having more distinct values at the beginning. A block-wise sort is much less efficient than a full sort. Moreover, we found that Gray-code sorting is not better than lexicographic sorting when using word-aligned compression. | |
| dc.description | to appear at BDA'08 | |
| dc.identifier | https://arxiv.org/abs/0805.3339 | |
| dc.identifier | http://arxiv.org/abs/0805.3339 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/167034 | |
| dc.subject | Databases | |
| dc.title | Tri de la table de faits et compression des index bitmaps avec alignement sur les mots | |
| dc.type | text |