The Wavelet Digest Homepage
Return to the homepage
Search the complete Wavelet Digest database
Help about the Wavelet Digest mailing list
About the Wavelet Digest
The Digest The Community
 Latest Issue  Back Issues  Events  Gallery
The Wavelet Digest
   -> Volume 11, Issue 1


Preprint: Wavelet-Based Relative Prefix Sum Methods for Range Sum Queries in Data Cubes
 
images/spacer.gifimages/spacer.gif Reply into Digest
Previous :: Next  
Author Message
Daniel Lemire (lemire@ondelette.com)
Guest





PostPosted: Thu Aug 15, 2002 11:24 am    
Subject: Preprint: Wavelet-Based Relative Prefix Sum Methods for Range Sum Queries in Data Cubes
Reply with quote

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

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/B) for B 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.


Keywords
B-adic wavelets, multidimensional databases, knowledge discovery.


Reference
Daniel Lemire, Wavelet-Based Relative Prefix Sum Methods for Range Sum Queries
in Data Cubes. Proceedings of CASCON 2002, Toronto, Canada, October 2002.

URL
http://www.ondelette.com/lemire/abstracts/CASCON2002.html
All times are GMT + 1 Hour
Page 1 of 1

 
Jump to: 
 


disclaimer - webmaster@wavelet.org
Powered by phpBB

This page was created in 0.225960 seconds : 18 queries executed : GZIP compression disabled