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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Approximate query processing using wavelets

Chakrabarti Kaushik, Garofalakis Minos, Rastogi Rajeev, Shim Kyuseok

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/845EC50A-7796-4CC5-BFD5-8DA24931F688-
Αναγνωριστικόhttp://link.springer.com/article/10.1007%2Fs007780100049-
Αναγνωριστικόhttps://doi.org/10.1007/s007780100049-
Γλώσσαen-
Μέγεθος25 pagesen
ΤίτλοςApproximate query processing using waveletsen
ΔημιουργόςChakrabarti Kaushiken
ΔημιουργόςGarofalakis Minosen
ΔημιουργόςΓαροφαλακης Μινωςel
ΔημιουργόςRastogi Rajeeven
ΔημιουργόςShim Kyuseoken
ΕκδότηςSpringer Verlagen
ΠερίληψηApproximate query processing has emerged as a cost-effective approach for dealing with the huge data volumes and stringent response-time requirements of today's decision support systems (DSS). Most work in this area, however, has so far been limited in its query processing scope, typically focusing on specific forms of aggregate queries. Furthermore, conventional approaches based on sampling or histograms appear to be inherently limited when it comes to approximating the results of complex queries over high-dimensional DSS data sets. In this paper, we propose the use of multi-dimensional wavelets as an effective tool for general-purpose approximate query processing in modern, high-dimensional applications. Our approach is based on building wavelet-coefficient synopses of the data and using these synopses to provide approximate answers to queries. We develop novel query processing algorithms that operate directly on the wavelet-coefficient synopses of relational tables, allowing us to process arbitrarily complex queries entirely in the wavelet-coefficient domain. This guarantees extremely fast response times since our approximate query execution engine can do the bulk of its processing over compact sets of wavelet coefficients, essentially postponing the expansion into relational tuples until the end-result of the query. We also propose a novel wavelet decomposition algorithm that can build these synopses in an I/O-efficient manner. Finally, we conduct an extensive experimental study with synthetic as well as real-life data sets to determine the effectiveness of our wavelet-based approach compared to sampling and histograms. Our results demonstrate that our techniques: (1) provide approximate answers of better quality than either sampling or histograms; (2) offer query execution-time speedups of more than two orders of magnitude; and (3) guarantee extremely fast synopsis construction times that scale linearly with the size of the data.en
ΤύποςPeer-Reviewed Journal Publicationen
ΤύποςΔημοσίευση σε Περιοδικό με Κριτέςel
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-10-29-
Ημερομηνία Δημοσίευσης2001-
Θεματική ΚατηγορίαQuery processingen
Θεματική Κατηγορία Data synopsesen
Θεματική ΚατηγορίαApproximate query answersen
Θεματική ΚατηγορίαWavelet decompositionen
Βιβλιογραφική ΑναφοράK. Chakrabarti, M. Garofalakis, R. Rastogi and K. Shim, "Approximate query processing using wavelets", VLDB J., vol. 10, no. 2-3, pp. 199-223, Sep. 2001. doi:10.1007/s007780100049en

Υπηρεσίες

Στατιστικά