| 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 <em>O</em>(1) using prefix sum aggregates but prefix sum update costs are proportional to the size of the data cube <em>O</em>(<em>n</em><em><SUP><FONT SIZE="-1">d</FONT></SUP></em>). Using the Relative Prefix Sum (RPS) method, the update costs can be reduced to the root of the size of the data cube <em>O</em>(<em>n</em><em><SUP><FONT SIZE="-1">d/2</FONT></SUP></em>). We present a new family of base b wavelet algorithms further reducing the update costs to <em>O</em>(<em>n</em><em><SUP><FONT SIZE="-1">d/b</FONT></SUP></em>) for b as large as we want while preserving constant-time queries. We also show that this approach leads to <em>O</em>(log<em><SUP><FONT SIZE="-1">d</FONT></SUP></em> <em>n</em>) query and update methods twice as fast as Haarbased methods. Moreover, since these new methods are pyramidal, they provide incrementally improving estimates. |
|---|
