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

  1. (PDF, 297 KB)
AuthorSearch for:
ConferenceProceedings of CASCON 2002, October 2002., Toronto, Ontario, Canada
AbstractData 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.
Publication date
AffiliationNRC Institute for Information Technology; National Research Council Canada
Peer reviewedNo
NRC number44967
NPARC number5764065
Export citationExport as RIS
Report a correctionReport a correction
Record identifier45b8af0a-ca7b-416d-ab76-fa0306a8af30
Record created2009-03-29
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)