Wavelet decomposition algorithm for uncertain data streams

Recently, data mining over uncertain data streams has attracted a lot of attentions because of the widely existed imprecise data generated from a variety of streaming applications. Many applications have endless uncertain data streams which have a huge amount of data so that it is infeasible to reserve all data in memory to be visited. Therefore, we need a new technology to effectively compress uncertain data streams. Among different data compression technology, the Haar wavelet decomposition is the most popular one, but the traditional wavelet decomposition is no longer applicable on uncertain data streams. Although a significant amount of previous research explore various data reduction techniques on data streams, data reduction techniques on uncertain data streams have seldom been investigated. In this paper, we try to resolve the problem of the wavelet decomposition over uncertain data streams and propose U-HWT(Uncertain Haar Wavelet Transform), a new algorithm for compressing the uncertain data streams. U-HWT uses discrete Haar wavelet transform and emphasis on the impact of the tuple uncertainty on the decomposition. Experimental results show that U-HWT can effectively compress the uncertain data streams.