Online Algorithm for Approximate Quantile Queries on Sliding Windows
| Autor: | Chun-Nam Yu, Ruichuan Chen, Alessandra Sala, Michael S. Crouch |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
060201 languages & linguistics
Computer science business.industry Real-time computing Volume (computing) Cloud computing 06 humanities and the arts 02 engineering and technology Tracking (particle physics) Task (computing) Sliding window protocol 0602 languages and literature 0202 electrical engineering electronic engineering information engineering Application specific 020201 artificial intelligence & image processing Online algorithm business Quantile |
| Zdroj: | Experimental Algorithms ISBN: 9783319388502 SEA |
| Popis: | Estimating statistical information about the most recent parts of a stream is an important problem in network and cloud monitoring. Modern cloud infrastructures generate in high volume and high velocity various measurements on CPU, memory and storage utilization, and also different types of application specific metrics. Tracking the quantiles of these measurements in a fast and space-efficient manner is an essential task in monitoring the health of the overall system. There are space-efficient algorithms for estimating approximate quantiles under the "sliding window" model of streams. However, they are slow in query time, which makes them less desirable for monitoring applications. In this paper we extend the popular Greenwald-Khanna algorithm for approximating quantiles in the unbounded stream model into the sliding window model, getting improved runtime guarantees over the existing algorithm for this problem. These improvements are confirmed by experiment. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|