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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Probabilistic wavelet synopses

Garofalakis Minos, Gibbons Phillip B.

Απλή Εγγραφή

URIhttp://purl.tuc.gr/dl/dias/66BAE10D-5BA3-4877-8F8B-4977FC4F9A2C-
Αναγνωριστικόhttp://dl.acm.org/citation.cfm?id=974753&dl=ACM&coll=DL&CFID=723856831&CFTOKEN=21128548-
Αναγνωριστικόhttps://doi.org/10.1145/974750.974753-
Γλώσσαen-
Μέγεθος47 pagesen
ΤίτλοςProbabilistic wavelet synopsesen
ΔημιουργόςGarofalakis Minosen
ΔημιουργόςΓαροφαλακης Μινωςel
ΔημιουργόςGibbons Phillip B.en
ΕκδότηςAssociation for Computing Machineryen
ΠερίληψηRecent work has demonstrated the effectiveness of the wavelet decomposition in reducing large amounts of data to compact sets of wavelet coefficients (termed "wavelet synopses") that can be used to provide fast and reasonably accurate approximate query answers. A major shortcoming of these existing wavelet techniques is that the quality of the approximate answers they provide varies widely, even for identical queries on nearly identical values in distinct parts of the data. As a result, users have no way of knowing whether a particular approximate answer is highly-accurate or off by many orders of magnitude. In this article, we introduce Probabilistic Wavelet Synopses, the first wavelet-based data reduction technique optimized for guaranteed accuracy of individual approximate answers. Whereas previous approaches rely on deterministic thresholding for selecting the wavelet coefficients to include in the synopsis, our technique is based on a novel, probabilistic thresholding scheme that assigns each coefficient a probability of being included based on its importance to the reconstruction of individual data values, and then flips coins to select the synopsis. We show how our scheme avoids the above pitfalls of deterministic thresholding, providing unbiased, highly accurate answers for individual data values in a data vector. We propose several novel optimization algorithms for tuning our probabilistic thresholding scheme to minimize desired error metrics. Experimental results on real-world and synthetic data sets evaluate these algorithms, and demonstrate the effectiveness of our probabilistic wavelet synopses in providing fast, highly accurate answers with improved quality guarantees.en
ΤύποςPeer-Reviewed Journal Publicationen
ΤύποςΔημοσίευση σε Περιοδικό με Κριτέςel
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-10-29-
Ημερομηνία Δημοσίευσης2004-
Θεματική ΚατηγορίαWaveletsen
Βιβλιογραφική ΑναφοράM. Garofalakis and P. B. Gibbons, "Probabilistic wavelet synopses", ACM Trans. Dat. Syst., vol. 29, no. 1, pp. 43-90, Mar. 2004. doi:10.1145/974750.974753en

Υπηρεσίες

Στατιστικά

 

Copyright © DIAS 2013