A fast algorithm for range sum queries over data stream

Range sum queries are fundamental part of modern data analysis application. But traditional query algorithms can not be applied on data stream, which is an unbounded sequence of data elements generated at a rapid rate. In this paper, we propose a novel approach for computing range sum from data streams based on wavelet sliding window model. The basic idea is to divide sliding window into equally-sized batch windows and represent the data elements within a batch window using wavelet coefficients, then store these coefficients in a WaveletWindow structure. As a result, range sum queries toward data streams can be converted to compute range sum over such wavelet coefficients. This algorithm takes advantage of the merit of wavelet decomposition for range sum query and achieves superior runtime performance. The extensive experiments verified the effectiveness of our algorithm.