Roaring bitmap : nouveau modèle de compression bitmap [r-libre/929]

Chambi, Samy; Lemire, Daniel et Godin, Robert (2014). Roaring bitmap : nouveau modèle de compression bitmap. Dans Actes des 10e journées francophones sur les Entrepôts de Données et l'Analyse en Ligne.

Fichier(s) associé(s) à ce document :

PDF - ArticleEDA.pdf
Contenu du fichier : Manuscrit soumis (avant évaluation)
Licence : Creative Commons CC BY.

Télécharger

Catégorie de document :	Communications dans des actes de congrès/colloques
Évaluation par un comité de lecture :	Oui
Étape de publication :	Publié
Résumé :	Les index bitmap sont très utilisés dans les entrepôts de données et moteurs de recherche. Leur capacité à exécuter efficacement des opérations binaires entre bitmaps améliore significativement les temps de réponse des requêtes. Cependant, sur des attributs de hautes cardinalités, ils consomment un espace mémoire important. Ainsi, plusieurs techniques de compression bitmap ont été introduites pour réduire l'espace mémoire occupé par ces index, et accélérer leurs temps de traitement. Ce papier introduit un nouveau modèle de compression bitmap, appelé Roaring bitmap. Une comparaison expérimentale, sur des données réelles et synthétiques, avec deux autres solutions de compression bitmap connues dans la littérature : WAH (Word Aligned Hybrid compression scheme) et Concise (Compressed "n" Composable integer Set), a montré que Roaring bitmap n'utilise que 25% d'espace mémoire comparé à WAH et 50% par rapport à Concise, tout en accélérant significativement les temps de calcul des opérations logiques entre bitmaps (jusqu'à 1100 fois pour les intersections).
Déposant:	Lemire, Daniel
Responsable :	Daniel Lemire
Dépôt :	29 avr. 2016 13:24
Dernière modification :	29 avr. 2016 13:24

Actions (connexion requise)

RÉVISER