Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

A fast approximation scheme for probabilistic wavelet synopses

Deligiannakis Antonios, Garofalakis Minos, Roussopoulos Nick

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/09F0998A-1CC4-4760-9DDC-0E190E255C7D-
Αναγνωριστικόhttps://pdfs.semanticscholar.org/78fa/613beaeebbe5bff344905e49e989be595b21.pdf-
Γλώσσαen-
Μέγεθος10 pagesen
ΤίτλοςA fast approximation scheme for probabilistic wavelet synopsesen
ΔημιουργόςDeligiannakis Antoniosen
ΔημιουργόςΔεληγιαννακης Αντωνιοςel
ΔημιουργόςGarofalakis Minosen
ΔημιουργόςΓαροφαλακης Μινωςel
ΔημιουργόςRoussopoulos Nicken
ΠερίληψηSeveral studies have demonstrated the effectiveness of Haar wavelets in reducing large amounts of data down to compact wavelet synopses that can be used to obtain fast, accurate approximate query answers. While Haar wavelets were originally designed for minimizing the overall root-mean-squared (i.e., ✂✁ - norm) error in the data approximation, the recently-proposed idea of probabilistic wavelet synopses also enables their use in minimizing other error metrics, such as the relative error in individual data-value reconstruction, which is arguably the most important for approximate query processing. Known construction algorithms for probabilistic wavelet synopses employ probabilistic schemes for coefficient thresholding that are based on optimal DynamicProgramming (DP) formulations over the error-tree structure for Haar coefficients. Unfortunately, these (exact) schemes can scale quite poorly for large data-domain and synopsis sizes. To address this shortcoming, in this paper, we introduce a novel, fast approximation scheme for building probabilistic wavelet synopses over large data sets. Our algorithm’s running time is near-linear in the size of the data-domain (even for very large synopsis sizes) and proportional to ✄✆☎✞✝, where ✝ is the desired approximation guarantee. The key technical idea in our approximation scheme is to make exact DP formulations for probabilistic thresholding much “sparser”, while ensuring a maximum relative degradation of ✝ on the quality of the approximate synopsis, i.e., the desired approximation error metric. Extensive experimental results over synthetic and real-life data clearly demonstrate the benefits of our proposed techniques.en
ΤύποςΠλήρης Δημοσίευση σε Συνέδριοel
ΤύποςConference Full Paperen
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-12-01-
Ημερομηνία Δημοσίευσης2005-
Θεματική ΚατηγορίαDatabasesen
Βιβλιογραφική ΑναφοράA. Deligiannakis, M. Garofalakis and N. Roussopoulos, "A fast approximation scheme for probabilistic wavelet synopses," in 17th International Scientific and Statistical Database Management Conference, June 2005, pp. 243-252. en

Υπηρεσίες

Στατιστικά