Scaling the Construction of Wavelet Synopses for Maximum Error Metrics
- 27 August 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 31 (9) , 1794-1808
Abstract
Modern analytics involve computations over enormous numbers of data records. The volume of data and the stringent response-time requirements place increasing emphasis on the efficiency of approximate query processing. A major challenge over the past years has been the construction of synopses that provide a deterministic quality guarantee, often expressed in terms of a maximum error metric. By approximating sharp discontinuities, wavelet decomposition has proved to be a very effective tool for data reduction. However, existing wavelet thresholding schemes that minimize maximum error metrics are constrained with impractical complexities for large datasets. Furthermore, they cannot efficiently handle the multi-dimensional version of the problem. In order to provide a practical solution, we develop parallel algorithms that take advantage of key-properties of the wavelet decomposition and allocate tasks to multiple workers. To that end, we present (i) a general framework for the parallelization of existing dynamic programming algorithms, (ii) a parallel version of one such DP algorithm, and (iii) two highly efficient distributed greedy algorithms that can deal with data of arbitrary dimensionality. Our extensive experiments on both real and synthetic datasets over Hadoop show that the proposed algorithms achieve linear scalability and superior running-time performance compared to their centralized counterparts.Keywords
This publication has 26 references indexed in Scilit:
- Synopses for Massive Data: Samples, Histograms, Wavelets, SketchesFoundations and Trends® in Databases, 2011
- On Multidimensional Wavelet Synopses for Maximum Error BoundsLecture Notes in Computer Science, 2009
- Hierarchical synopses with optimal error guaranteesACM Transactions on Database Systems, 2008
- Wavelet synopses for general error metricsACM Transactions on Database Systems, 2005
- One-pass wavelet decompositions of data streamsIEEE Transactions on Knowledge and Data Engineering, 2003
- A survey on wavelet applications in data miningACM SIGKDD Explorations Newsletter, 2002
- Join synopses for approximate query answeringACM SIGMOD Record, 1999
- Approximate computation of multidimensional aggregates of sparse data using waveletsACM SIGMOD Record, 1999
- Wavelet-based histograms for selectivity estimationACM SIGMOD Record, 1998
- New sampling-based summary statistics for improving approximate query answersACM SIGMOD Record, 1998