Wavelet-Based Relative Prefix Sum Methods for Range Sum Queries in Data Cubes

Lemire, Daniel (2002). « Wavelet-Based Relative Prefix Sum Methods for Range Sum Queries in Data Cubes », dans CASCON 2002 (12th IBM Centers for Advanced Studies Annual International Conference, Toronto, 2002) Toronto, pp. 1-10.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (101kB)

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.

Type:	Communication, article de congrès ou colloque
Informations complémentaires:	Prix du meilleur papier
Mots-clés ou Sujets:	OLAP, Data Warehousing, Data Mining, Range Sums
Unité d'appartenance:	Télé-université > UER Science et Technologie
Déposé par:	Daniel Lemire
Date de dépôt:	16 juill. 2007
Dernière modification:	01 nov. 2014 02:03
Adresse URL :	http://archipel.uqam.ca/id/eprint/348

Versions disponibles de ce document

• Wavelet-Based Relative Prefix Sum Methods for Range Sum Queries in Data Cubes. (déposé le 23 juill. 2007)
  • Wavelet-Based Relative Prefix Sum Methods for Range Sum Queries in Data Cubes. (déposé le 16 juill. 2007) [Actuellement Affiché]

Modifier les métadonnées (propriétaire du document)

Statistiques