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 d...
Exponential Histogram (EH. Modeling Another important data structure, which is an effective method for estimating statistics on sliding windows, is the exponential histograms (EHs). The EH is used for the counting problem, i.e. the problem of determining, with a bound on the relative error, the number of 1s in the last N units of time. The exponential histogram data structure is a histogram, where the buckets that record older data are exponentially wider than the buckets that record more recent data. When, a query takes place, i.e. to find the number of 1s that are seen in the last n units of time, we simply iterate over the buckets starting with the bucket containing the most recently recorded 1 till we find the bucket that covers the time we are interested in. Then we return the probabilistic distance of that bucket from the current timestamp. Streaming processing and sliding-window domain is an important application domain and there are various hardware-based works that accelerate such workloads. Xxxxxx et al. [56] analyzed the sliding-window applications domain when executing on FPGAs, GPUs, and multicores. For each device, they presented optimization strategies and analyzed the cases, where each device was most effective. The results showed that FPGAs can achieve speedup of up to 11x and 57x compared to GPUs and multicores, respectively, while also using orders of magnitude less energy. Qian et al. in [57] presented an novel algorithm named M3Join, which was implemented on an FPGA platform. The system needs only one scan over the data streams since different join queries share the intermediate results. The experimental results show that the hardware can accelerate join processing vastly. This section presents the analysis of the input and the output of the proposed EH data structure. Also, we describe the data sets that were used the validation of our implemented system. Next, the algorithmic analysis of the EH method is presented. Lastly, we present the EH data structures and their basic operations.
