URI | http://purl.tuc.gr/dl/dias/494394BF-9D81-47F8-AF0F-EAA0B9094476 | - |
Αναγνωριστικό | http://dimacs.rutgers.edu/~graham/pubs/papers/cdquant.pdf | - |
Γλώσσα | en | - |
Μέγεθος | 12 pages | en |
Τίτλος | Holistic aggregates in a networked world: distributed tracking of approximate quantiles | en |
Δημιουργός | Cormode, Graham, 1977- | en |
Δημιουργός | Muthukrishnan, S | en |
Δημιουργός | Garofalakis Minos | en |
Δημιουργός | Γαροφαλακης Μινως | el |
Δημιουργός | Rastogi Rajeev | en |
Εκδότης | Association for Computing Machinery | en |
Περίληψη | 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 Paper | en |
Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
Ημερομηνία | 2015-12-01 | - |
Ημερομηνία Δημοσίευσης | 2005 | - |
Θεματική Κατηγορία | Database management | en |
Βιβλιογραφική Αναφορά | 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 |