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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Multi-query optimization for sketch-based estimation

Dobra Alin , Garofalakis Minos, Gehrke Johannes, Rastogi Rajeev

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/D90992AF-1B30-4B4C-B517-2FF9075D0ED5-
Αναγνωριστικόhttp://www.sciencedirect.com/science/article/pii/S0306437908000598-
Αναγνωριστικόhttps://doi.org/doi:10.1016/j.is.2008.06.002-
Γλώσσαen-
Μέγεθος22 pagesen
ΤίτλοςMulti-query optimization for sketch-based estimationen
ΔημιουργόςDobra Alin en
ΔημιουργόςGarofalakis Minosen
ΔημιουργόςΓαροφαλακης Μινωςel
ΔημιουργόςGehrke Johannesen
ΔημιουργόςRastogi Rajeeven
ΕκδότηςElsevieren
ΠερίληψηRandomized techniques, based on computing small “sketch” synopses for each stream, have recently been shown to be a very effective tool for approximating the result of a single SQL query over streaming data tuples. In this paper, we investigate the problems arising when data-stream sketches are used to process multiple such queries concurrently. We demonstrate that, in the presence of multiple query expressions, intelligently sharing sketches among concurrent query evaluations can result in substantial improvements in the utilization of the available sketching space and the quality of the resulting approximation error guarantees. We provide necessary and sufficient conditions for multi-query sketch sharing that guarantee the correctness of the result-estimation process. We also investigate the difficult optimization problem of determining sketch-sharing configurations that are optimal (e.g., under a certain error metric for a given amount of space). We prove that optimal sketch sharing typically gives rise to NP-hard questions, and we propose novel heuristic algorithms for finding good sketch-sharing configurations in practice. Results from our experimental study with queries from the TPC-H benchmark verify the effectiveness of our approach, clearly demonstrating the benefits of our sketch-sharing methodology.en
ΤύποςPeer-Reviewed Journal Publicationen
ΤύποςΔημοσίευση σε Περιοδικό με Κριτέςel
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-10-29-
Ημερομηνία Δημοσίευσης2009-
Θεματική ΚατηγορίαData streamingen
Θεματική ΚατηγορίαSketchesen
Θεματική ΚατηγορίαApproximate query processingen
Θεματική Κατηγορία Multi-query optimizationen
Βιβλιογραφική ΑναφοράA. Dobra, M. Garofalakis, J. Gehrke and R. Rastogi, "Multi-query optimization for sketch-based estimation", Inform. Syst., vol. 34, no. 2, pp. 209-230, Apr. 2009. doi:10.1016/j.is.2008.06.002en

Υπηρεσίες

Στατιστικά