Nouveaux modèles d’index bitmap compressés à 64 bits [r-libre/930]

Chambi, Samy; Lemire, Daniel et Godin, Robert (2016). Nouveaux modèles d’index bitmap compressés à 64 bits. Dans Actes des 12es journées francophones sur les Entrepôts de Données et l'Analyse en Ligne.

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

PDF - Roaring64bits.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 pour accélérer les requêtes d'interrogation. Leurs principaux avantages sont leur forme compacte et leur capacité à tirer profit du traitement parallèle de bits dans les CPU (bit-level parallelism). Dans l'ère actuelle du Big Data, les collections de données deviennent de plus en plus volumineuses. Les librairies d'index bitmap compressés disponibles à ce jour dans la littérature, telles que : Roaring bitmap, WAH ou Concise, ne supportent qu'au plus 4 milliards d'entrées et sont très souvent impraticables dans de tels contextes. Après avoir constaté ce besoin tant dans le milieu industriel que scientifique, nous proposons trois nouveaux modèles d'index bitmap compressés, basés sur le format de notre précédente contribution Roaring bitmap et qui supportent jusqu'à 2^64 entrées. Des expériences sur des données synthétiques ont été mises en oeuvre pour comparer les performances des trois nouvelles propositions avec la solution du moteur de recherche Apache Lucene : OpenBitSet, et d'autres collections Java. Les résultats ont montré que les trois nouvelles techniques ont été près de 300 millions de fois et 1800fois moins volumineuses en consommation mémoire qu'OpenBitSet et les collections Java, respectivement. Aussi, les trois nouveaux modèles ont calculé des opérations logiques, jusqu'à 6 millions de fois et jusqu'à 63 milles fois plus vite qu'OpenBitSet et les structures Java, respectivement.
Déposant:	Lemire, Daniel
Responsable :	Daniel Lemire
Dépôt :	27 avr. 2016 19:18
Dernière modification :	27 avr. 2016 19:18

Actions (connexion requise)

RÉVISER