Nouveaux modèles d'index bitmap compressés à 64 bits
Abstract
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.