FAST APPROXIMATE WAVELET TRACKING ON STREAMS

The first fast solution to the problem of tracking wavelet representations of one-dimensional and multi-dimensional data streams based on a stream synopsis, the Group-Count Sketch (GCS) is provided. By imposing a hierarchical structure of groups over the data and applying the GCS, our algorithms can quickly recover the most important wavelet coefficients with guaranteed accuracy. A tradeoff between query time and update time is established, by varying the hierarchical structure of groups, allowing the right balance to be found for specific data streams. Experimental analysis confirmed this tradeoff, and showed that all the methods significantly outperformed previously known methods in terms of both update time and query time, while maintaining a high level of accuracy.