ISSN : 1796-203X
Volume : 2    Issue : 8    Date : October 2007

Dynamic Nonuniform Data Approximation in Databases with Haar Wavelet
Su Chen and Antonio Nucci
Page(s): 64-76
Full Text:
PDF (536 KB)

Data synopsis is a lossy compressed representation of data stored into databases that helps the
query optimizer to speed up the query process, e.g. time to retrieve the data from the database. An
efficient data synopsis must provide accurate information about the distribution of data to the query
optimizer at any point in time. Due to the fact that some data will be queried more often than others,
a good data synopsis should consider the use of nonuniform accuracy, e.g. provide better
approximation of data that are queried the most. Although, the generation of data synopsis is a
critical step to achieve a good approximation of the initial data representation, data synopsis must
be updated over time when dealing with time varying data. In this paper, we introduce new Haar
wavelet synopses for nonuniform accuracy and time-varying data that can be generated in linear
time and space, and updated in sublinear time. We further introduce two linear algorithms, called
2-step and M-Step for the Point-wise approximation problem that clearly outperforms previous
algorithms known in literature, and two new algorithm called, DataMapping and WeightMapping for
the Range-sum approximation problem that, to the best of our knowledge, represent a key research
milestone as being the first linear algorithm for arbitrary weights. For both scenarios, we focus not
only on the generation of the data synopsis but also on their updates over time. The efficiency of our
new data synopses is validated against other linear methods by using both synthetic and real data

Index Terms
Dynamic data synopsis, query optimization, nonuniform lossy compression, point-wise and
range-sum approximation, linear complexity