Continuously maintaining approximate quantile summaries over large uncertain datasets

Quantile summarization is a useful tool for management of massive datasets in the rapidly growing number of applications, and its importance is further enhanced with uncertainty in the data being explored. In this paper, we focus on the problem of computing approximate quantile summaries over large uncertain datasets. On the basis of GK [14] algorithm, we propose a novel online algorithm namely uGK. Using only little space, the proposed uGK algorithm maintains a small set of tuples, each of which contains a point value and the “count” of uncertain elements that are not larger than this value, and supports any quantile query within a given error. Experimental evaluation on both synthetic and real-life datasets illustrates the effectiveness of our uGK algorithm.