Répertoire de publications
de recherche en accès libre

Compressed bitmap indexes: beyond unions and intersections [r-libre/261]

Kaser, Owen et Lemire, Daniel (2016). Compressed bitmap indexes: beyond unions and intersections. Software: Practice and Experience, 46 (2). https://doi.org/10.1002/spe.2289

Fichier(s) associé(s) à ce document :
[img]  PDF - symmetricbitmap.pdf
Contenu du fichier : Manuscrit accepté (révisé après évaluation)
Licence : Creative Commons CC BY.
Catégorie de document : Articles de revues
Évaluation par un comité de lecture : Oui
Étape de publication : Publié
Résumé : Compressed bitmap indexes are used to speed up simple aggregate queries in databases. Indeed, set operations like intersections, unions and complements can be represented as logical operations (AND,OR,NOT) that are ideally suited for bitmaps. However, it is less obvious how to apply bitmaps to more advanced queries. For example, we might seek products in a store that meet some, but maybe not all, criteria. Such threshold queries generalize intersections and unions; they are often used in information-retrieval and data-mining applications. We introduce new algorithms that are sometimes three orders of magnitude faster than a naive approach. Our work shows that bitmap indexes are more broadly applicable than is commonly believed.
Adresse de la version officielle : http://onlinelibrary.wiley.com/doi/10.1002/spe.228...
Déposant: Lemire, Daniel
Responsable : Daniel Lemire
Dépôt : 05 sept. 2014 13:00
Dernière modification : 20 mars 2016 19:13

Actions (connexion requise)