Open access research
publication repository
publication repository
Lemire, Daniel (2002). WaveletBased Relative Prefix Sum Methods for Range Sum Queries in Data Cubes. In Stewart, Darlene A., & Johnson, J. Howard (Ed.), Proceedings of the 2002 Conference of the Center for Advanced Studies on Collaborative Research (CASCON '02) (p. 6). Riverton, NJ, USA : IBM.
File(s) available for this item:PDF  multihaar_final.pdf 

Item Type:  Papers in Conference Proceedings 

Refereed:  Yes 
Status:  Published 
Abstract:  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 constanttime queries. We also show that this approach leads to O(log^d n) query and update methods twice as fast as Haarbased methods. Moreover, since these new methods are pyramidal, they provide incrementally improving estimates. 
Additional Information:  Prix du meilleur papier 
Official URL:  http://dl.acm.org/citation.cfm?id=782121&CFID=5134... 
Depositor:  Lemire, Daniel 
Owner / Manager:  Daniel Lemire 
Deposited:  16 Jul 2007 
Last Modified:  16 Jul 2015 00:47 
RÉVISER 