Chambi, Samy
(2017).
« Les index bitmap compressés » Thèse.
Montréal (Québec, Canada), Université du Québec à Montréal, Doctorat en informatique.
Fichier(s) associé(s) à ce document :
Résumé
Les index bitmap sont très utilisés dans les moteurs de recherche et les bases de données pour accélérer les opérations de recherche. Leurs principaux avantages sont leur forme compacte et leur capacité à tirer profit du traitement parallèle de bits dans les CPU (bit-level parallelism). Lorsque employés sur des attributs de faibles cardinalités, l'efficacité des index bitmaps en matière d'occupation d'espace mémoire et de temps de traitements comparé aux autres types d'index classiques, tels que l'arbre-B, est largement reconnue dans la littérature. Cependant, plus la cardinalité d'un attribut s'élève plus la taille et les temps de traitements de son index bitmap augmentent jusqu'à consommer plus d'espaces mémoires que les données indexées et d'importants temps de calculs. Afin de maintenir l'efficacité de ces solutions d'indexation dans ces conditions- là, plusieurs chercheurs ont proposé des travaux dans le but de réduire la taille et améliorer les temps de traitement de bitmaps indexant des attributs de larges cardinalités. Les solutions proposées dans la littérature adressant cette problématique se divisent en trois catégories : le paquetage des bitmaps, l'encodage des bitmaps et la compression des bitmaps. Les contributions proposées dans cette thèse se classent parmi la troisième catégorie. Après avoir constaté que la plupart des techniques de compression de bitmaps introduites ces 15 dernières années se basent sur le modèle de la solution WAH, qui combine une compression par plages de valeurs avec une représentation bitmap sous forme de chaînes de bits alignées par mots CPU, cette thèse propose la technique Roaring bitmap, qui adopte un nouveau modèle pour compresser les bitmaps. Cette méthode discrétise l'espace des entiers représentés par un bitmap en des partitions de taille fixe, puis applique sur chacune une forme de compression appropriée selon la densité du groupe d'entiers. Des expériences ont été conduites pour comparer les performances temps-espace du nouveau modèle avec ceux de deux autres solutions de compression bitmap parmi les plus connues dans la littérature : WAH et Concise. Les résultats ont montré que, sur des faibles densités, la nouvelle méthode ne consomme que ≈ 50% de l'espace mémoire occupé par Concise et ≈ 25% de celui de WAH. Aussi, Roaring bitmap a pu accélérer les temps de calcul d'opérations logiques par rapport aux deux autres techniques sur tous les tests effectués, en étant de 4 à 5 fois plus performant sur des données synthétiques, et jusqu'à 1100 fois plus rapide sur des données réelles. La librairie de Roaring bitmap et celles des autres solutions adoptant le modèle WAH qui sont disponibles au grand public ne supportent que des bitmaps d'au plus 232 (≈ 4 milliards) entrées. Avec l'avènement du Big Data, le besoin d'indexer de très larges collections de données sur lesquelles de telles librairies se révèlent impraticables est souvent rencontré. Les ingénieurs du moteur de recherche Apache Lucene ont rencontré ce problème, et ont introduit la solution OpenBitSet, qui peut allouer des bitmaps avec jusqu'à 64 x 232 – 1 entrées. Cependant, cette solution reste simple et n'applique aucune forme de compression sur les bitmaps. La présente thèse propose trois nouveaux modèles de compression bitmap basés sur le format de Roaring bitmap et qui peuvent indexer jusqu'à 264 entrées. Des expériences sur des données synthétiques comparant les performances des trois nouveaux modèles avec la solution d'Apache Lucene, OpenBitSet, et d'autres collections Java du paquetage Java.Util : ArrayList, LinkedList, HashSet et TreeSet, ont montré qu'OpenBitSet et les collections Java consomment, respectivement, jusqu'à ≈ 300 millions de fois et ≈ 1800 fois plus d'espaces mémoire comparés aux trois nouveaux modèles. Ces derniers ont également calculé des intersections entre deux ensembles d'entiers, ≈ 6 millions de fois, ≈ 63 milles fois et ≈ 6 fois plus rapidement par rapport à OpenBitSet, aux deux collections ArrayList et LinkedList, et aux deux structures HashSet et TreeSet, respectivement. En évaluant les temps pour calculer l'union de deux ensembles d'entiers, les nouvelles méthodes ont été jusqu'à ≈ 3 millions de fois plus performantes qu'OpenBitSet. Aussi, cette dernière structure de données a été jusqu'à ≈ 14 millions de fois plus lente pour insérer un entier généré aléatoirement que les trois solutions proposées. Afin de valider le format de la solution Roaring bitmap dans un SGBD réel, cette technique d'indexation a été intégrée au moteur OLAP Druid. Ce système se base essentiellement sur des index bitmap compressés avec la technique Concise pour accélérer les temps de réponse de requêtes OLAP effectuant des analyses détaillées sur les données (drill-down). Des expériences sur des données réelles ont été réalisées pour évaluer les performances de Roaring bitmap et de Concise au sein du SGBD Druid. Les résultats ont montré que Roaring bitmap a amélioré de ≈ 2 fois les temps de réponse de requêtes d'agrégations et près de 5 fois le temps de traitements de requêtes de recherche comparé à la solution Concise.
______________________________________________________________________________
MOTS-CLÉS DE L’AUTEUR : index bitmap, compression, performances, opérations logiques, structures de données.
| Type: |
Thèse ou essai doctoral accepté
|
| Informations complémentaires: |
La thèse a été numérisée telle que transmise par l'auteur. |
|
Directeur de thèse: |
Lemire, Daniel |
| Mots-clés ou Sujets: |
Données matricielles -- Index / Données -- Compression / Structures de données |
| Unité d'appartenance: |
Faculté des sciences > Département d'informatique |
| Déposé par: |
Service des bibliothèques
|
| Date de dépôt: |
30 janv. 2017 18:59 |
| Dernière modification: |
30 janv. 2017 18:59 |
| Adresse URL : |
http://archipel.uqam.ca/id/eprint/9303 |
RECHERCHER
PARCOURIR
LIBRE ACCÈS
