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

Reordering Columns for Smaller Indexes [r-libre/231]

Lemire, Daniel et Kaser, Owen (2011). Reordering Columns for Smaller Indexes. Information Sciences, 181 (12), 2550–2570. https://doi.org/10.1016/j.ins.2011.02.002

Fichier(s) associé(s) à ce document :
[img]  PDF - 0909.1346v8.pdf  
Catégorie de document : Articles de revues
Évaluation par un comité de lecture : Oui
Étape de publication : Publié
Résumé : Column-oriented indexes-such as projection or bitmap indexes-are compressed by run-length encoding to reduce storage and increase speed. Sorting the tables improves compression. On realistic data sets, permuting the columns in the right order before sorting can reduce the number of runs by a factor of two or more. Unfortunately, determining the best column order is NP-hard. For many cases, we prove that the number of runs in table columns is minimized if we sort columns by increasing cardinality. Experimentally, sorting based on Hilbert space-filling curves is poor at minimizing the number of runs.
Adresse de la version officielle : http://www.sciencedirect.com/science/article/pii/S...
Déposant: Lemire, Daniel
Responsable : Daniel Lemire
Dépôt : 12 sept. 2014 19:25
Dernière modification : 16 juill. 2015 00:46

Actions (connexion requise)