Exponential Histogram (EH Clause Samples

Exponential Histogram (EH. The QualiMaster project focuses on processing of streams that come from different and distributed data sources. In addition, the goal of the QualiMaster is the efficient processing of huge amounts of data over time-based sliding windows. Exponential histograms (EHs) [17] guarantee complex query answering over distributed data streams in the sliding-window model. The use of EHs in the QualiMaster project would offer fast answering queries over distributed streams and efficient storage of the statistics over sliding windows. Exponential histograms [17] are a deterministic structure, proposed to address the basic counting problem, i.e., for counting the number of true bits in the last N stream arrivals. They belong to the family of methods that break the sliding window range into smaller windows, called buckets or basic windows, to enable efficient maintenance of the statistics. Each bucket contains the aggregate statistics, i.e., number of arrivals and bucket bounds, for the corresponding sub-range. Buckets that no longer overlap with the sliding window are expired and discarded from the structure. To compute an aggregate over the whole (or a part of) sliding window, the statistics from all buckets overlapping with the query range are aggregated. For example, for basic counting, aggregation is a summation of the number of true bits in the buckets. A possible estimation error can be introduced due to the oldest bucket inside the query range, which usually has only a partial overlap with the query. Therefore, the maximum possible estimation error is bounded by the size of the last bucket. To reduce the space requirements, exponential histograms maintain buckets of exponentially increasing sizes. Bucket boundaries are chosen such that the ratio of the size of each bucket b with the sum of the sizes of all buckets more recent than b is upper bounded. In particular, the following invariant (1) is maintained for all buckets j: /(( + )) ≤ () where e denotes the maximum acceptable relative error and Cj denotes the size of bucket j (number of true bits arrived in the bucket range), with bucket 1 being the most recent bucket. Queries are answered by summing the sizes of all buckets that fully overlap the query range, and half of the size of the oldest bucket, if it partially overlaps the query. The estimation error is solely contained in the oldest bucket, and is therefore bounded by this invariant, resulting to a maximum relative error of e. The EHs access each data ...