RH: An improved AMH aggregate query method

摘要

As data stream grows exponentially, the aggregate query technique is widely used since it can rapidly obtain the summary information. Typical approximate aggregate query methods, like sliding-window, random sampling, wavelet, sketch index structure, histogram, etc., all evaluate the quality of the algorithms by the average size of query errors and ignore the maximum relative error, which determines the availability of the methods. Regarding this issue, this paper proposes the Reasonable Histogram (RH) method to improve the classic aggregate query method AMH. Based on the analysis of AMH errors' mathematical characteristics, we build an aggregate query mathematical model based on the Kalman filter, using the optimal estimate of the buckets' average frequency to calculate the aggregate values of the anomalous points, so as to restrain the maximum relative error.