ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 35/3 - 2016  - pp.335-355  - doi:10.3166/tsi.35.335-355
TITRE
Vers de meilleures performances avec des Roaring bitmaps

TITLE
Better bitmap performance with Roaring bitmaps

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. 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 et Concise 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’à 1 100 fois pour les intersections).


ABSTRACT
Bitmap indexes are frequently used in data warehouses and search engines. Their effectiveness at exploiting bit-level parallelism and fast bitwise operations significantly speed up search queries. However, on high cardinality attributes, they consume a large amount of space. Hence, many bitmap compression techniques have been introduced that provide efficient space representations with better search times compared to other indexing schemes such as B-trees. In this work, we introduce a new bitmap compression scheme, called Roaring bitmap, and compare it to two well-known bitmap encoding techniques: WAH and Concise. Synthetic and real data experiments have shown that our index requires ≈ 25 % of the space needed by WAH and ≈ 50 % of Concise’s space, while performing bitwise operations many times faster.


AUTEUR(S)
Samy Chambi , Daniel LEMIRE, Robert GODIN

Reçu le 1 décembre 2014.    Accepté le 17 avril 2016.

MOTS-CLÉS
index bitmap, compression, performances.

KEYWORDS
index bitmap, compression, performances.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (381 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier