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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Holistic aggregates in a networked world: distributed tracking of approximate quantiles

Cormode, Graham, 1977-, Muthukrishnan, S, Garofalakis Minos, Rastogi Rajeev

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/494394BF-9D81-47F8-AF0F-EAA0B9094476-
Αναγνωριστικόhttp://dimacs.rutgers.edu/~graham/pubs/papers/cdquant.pdf-
Γλώσσαen-
Μέγεθος12 pagesen
ΤίτλοςHolistic aggregates in a networked world: distributed tracking of approximate quantilesen
ΔημιουργόςCormode, Graham, 1977-en
ΔημιουργόςMuthukrishnan, Sen
ΔημιουργόςGarofalakis Minosen
ΔημιουργόςΓαροφαλακης Μινωςel
ΔημιουργόςRastogi Rajeeven
ΕκδότηςAssociation for Computing Machineryen
ΠερίληψηWhile traditional database systems optimize for performance on one-shot queries, emerging large-scale monitoring applications require continuous tracking of complex aggregates and data-distribution summaries over collections of physically-distributed streams. Thus, effective solutions have to be simultaneously space efficient (at each remote site), communication efficient (across the underlying communication network), and provide continuous, guaranteedquality estimates. In this paper, we propose novel algorithmic solutions for the problem of continuously tracking complex holistic aggregates in such a distributed-streams setting — our primary focus is on approximate quantile summaries, but our approach is more broadly applicable and can handle other holistic-aggregate functions (e.g., “heavy-hitters” queries). We present the first known distributed-tracking schemes for maintaining accurate quantile estimates with provable approximation guarantees, while simultaneously optimizing the storage space at each remote site as well as the communication cost across the network. In a nutshell, our algorithms employ a combination of local tracking at remote sites and simple prediction models for local site behavior in order to produce highly communication- and space-efficient solutions. We perform extensive experiments with real and synthetic data to explore the various tradeoffs and understand the role of prediction models in our schemes. The results clearly validate our approach, revealing significant savings over naive solutions as well as our analytical worst-case guarantees.en
ΤύποςΠλήρης Δημοσίευση σε Συνέδριοel
ΤύποςConference Full Paperen
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-12-01-
Ημερομηνία Δημοσίευσης2005-
Θεματική ΚατηγορίαDatabase managementen
Βιβλιογραφική ΑναφοράG. Cormode, M. Garofalakis, S. Muthukrishnan and R. Rastogi, "Holistic aggregates in a networked world: distributed tracking of approximate quantiles", in ACM SIGMOD International Conference on Management of Data, June 2005, pp. 25-36. en

Υπηρεσίες

Στατιστικά