| Résumé | L'exploration de données et applications connexes utilisent souvent de nombreuses interrogations sommatives sur un ensemble de données. Il est donc important que ces interrogations puissent être correctement mises à l'échelle. Une interrogation sommative sur un ensemble dans un cube de données avec une aggrégation par somme au préfixe nécessite un temps <em>O</em>(1), mais les coûts (en temps) de mise à jour nécessités par la sommation en préfixe sont proportionnels à la taille du cube de données <em>O</em>(<em>n</em><em><SUP><FONT SIZE="-1">d</FONT></SUP></em>). Le recours à la méthode de sommation relative en préfixe (RPS) permet de réduire les coûts à la racine carrée de la taille du cube de données <em>O</em>(<em>n</em><em><SUP><FONT SIZE="-1">d/2</FONT></SUP></em>). Nous présentons une nouvelle famille d'algorithmes d'ondelettes à base b qui réduisent encore les coûts de mise à jour, jusqu'à <em>O</em>(<em>n</em><em><SUP><FONT SIZE="-1">d/b</FONT></SUP></em>), pour une valeur de b aussi élevée que voulue, tout en préservant les interrogations à temps constant. Nous montrons également que cette approche donne <em>O</em>(log<em><SUP><FONT SIZE="-1">d</FONT></SUP></em> <em>n</em>) méthodes de recherche et de mise à jour deux fois plus rapides que les méthodes reposant sur les ondelettes de Haar. De plus, puisque ces nouvelles méthodes sont pyramidales, elles peuvent donner des estimations s'améliorant progressivement. |
|---|
