RNTI

MODULAD
Nouveaux modèles d'index bitmap compressés à 64 bits
In EDA 2016, vol. RNTI-B-12, pp.1-16
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 résident en 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 introduites à ce jour, telles que : Roaring bitmap, WAH ou Concise, ne supportent que des bitmaps d'au plus 232  4 milliards d'entrées et sont souvent impraticables sur de telles masses de données. Ce travail propose trois nouveaux modèles d'index bitmap compressés supportant jusqu'à 264 entrées. Des expériences comparant les performances des nouveaux modèles avec celles de la solution OpenBitSet utilisée par le moteur de recherche Apache Lucene, ainsi que d'autres collections Java ont montré que les approches proposées ont permis de calculer des opérations logiques jusqu'à  6 millions de fois et jusqu'à  soixante-trois milles fois plus vite qu'OpenBitSet et les structures Java, respectivement, tout en consommant beaucoup moins d'espace mémoire.