Volume 2 Number 8 (Oct. 2007)
Home > Archive > 2007 > Volume 2 Number 8 (Oct. 2007) >
JCP 2007 Vol.2(8): 64-76 ISSN: 1796-203X
doi: 10.4304/jcp.2.8.64-76

Dynamic Nonuniform Data Approximation in Databases with Haar Wavelet

Su Chen1, Antonio Nucci2
1Dept. of Computer Science, Rutgers University, Piscataway, NJ, USA
2Narus Inc., Mountain View, CA, USA

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

[PDF]

Cite: Su Chen, Antonio Nucci, "Dynamic Nonuniform Data Approximation in Databases with Haar Wavelet," Journal of Computers vol. 2, no. 8, pp. 64-76, 2007.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>