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

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

File(s) available for this item:

PDF - Roaring64bits.pdf
Content : Submitted Version
License : Creative Commons Attribution.

Download

Item Type:	Papers in Conference Proceedings
Refereed:	Yes
Status:	Published
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 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.
Depositor:	Lemire, Daniel
Owner / Manager:	Daniel Lemire
Deposited:	27 Apr 2016 19:18
Last Modified:	27 Apr 2016 19:18

Actions (login required)

RÉVISER