JOURNAL OF COMPUTERS (JCP)

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)

**Abstract**

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

sets.

**Index Terms**

Dynamic data synopsis, query optimization, nonuniform lossy compression, point-wise and

range-sum approximation, linear complexity

ISSN : 1796-203X

Volume : 2 Issue : 8 Date : October 2007

Page(s): 64-76

Full Text: PDF (536 KB)

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

sets.

range-sum approximation, linear complexity