LogoTeluq
English
Logo
Répertoire de publications
de recherche en accès libre

Wavelet-Based Relative Prefix Sum Methods for Range Sum Queries in Data Cubes [r-libre/216]

Lemire, Daniel (2002). Wavelet-Based Relative Prefix Sum Methods for Range Sum Queries in Data Cubes. Dans Stewart, Darlene A. et Johnson, J. Howard (dir.), Proceedings of the 2002 Conference of the Center for Advanced Studies on Collaborative Research (CASCON '02) (p. 6). Riverton, NJ, USA : IBM.

Fichier(s) associé(s) à ce document :
[img]  PDF - multihaar_final.pdf  
Catégorie de document : Communications dans des actes de congrès/colloques
Évaluation par un comité de lecture : Oui
Étape de publication : Publié
Résumé : Data mining and related applications often rely on extensive range sum queries and thus, it is important for these queries to scale well. Range sum queries in data cubes can be achieved in time O(1) using prefix sum aggregates, but prefix sum update costs are proportional to the size of the data cube O(n^d). Using the Relative Prefix Sum (RPS) method, the update costs can be reduced to the root of the size of the data cube (O(n^(d/2)). We present a new family of base b wavelet algorithms further reducing the update costs to O(n^(d/beta)) for beta as large as we want, while preserving constant-time queries. We also show that this approach leads to O(log^d n) query and update methods twice as fast as Haar-based methods. Moreover, since these new methods are pyramidal, they provide incrementally improving estimates.
Informations complémentaires : Prix du meilleur papier
Adresse de la version officielle : http://dl.acm.org/citation.cfm?id=782121&CFID=5134...
Déposant: Lemire, Daniel
Responsable : Daniel Lemire
Dépôt : 16 juill. 2007
Dernière modification : 16 juill. 2015 00:47

Actions (connexion requise)

RÉVISER RÉVISER