Database Reference
In-Depth Information
SERIES
AVERAGE
[1 8]
5
+
[1 8]
-0.25
RELEVANT
RANGES
-
+
[5 8]
[1 4]
2.25
-0.25
+
-
+
-
1
-0.5
-1
0.5
[1 2]
[3 4]
[5 6]
[7 8]
RELEVANT RANGES
+
+
-
+
-
-
+
-
8
6
2
3
4
6
6
5
ORIGINAL SERIES VALUES RECONSTRUCTED FROM TREE PATH
Figure 6.2.
The Error Tree from the Wavelet Decomposition
series has been replicated just below the error-tree in
Figure 6.2
, and it
can be reconstructed by adding or subtracting the values in the nodes
along the path leading to that value. We note that each coecient in a
node should be added, if we use the left branch below it to reach to the
series values. Otherwise, it should be subtracted. This natural decom-
position means that an entire contiguous range along the series can be
reconstructed by using only the portion of the error-tree which is rele-
vant to it. Furthermore, we only need to retain those coecients whose
values are significantly large, and therefore affect the values of the un-
derlying series. In general, we would like to minimize the reconstruction
error by retaining only a fixed number of coecients, as defined by the
space constraints. While wavelet decomposition is easy to perform for
multi-dimensional data sets, it is much more challenging for the case of
data streams. This is because data streams impose a one-pass constraint
on the wavelet construction process. A variety of one-pass algorithms
for wavelet construction are discussed in [41].
Histograms:
The technique of histogram construction is closely related
to that of wavelets. In histograms the data is binned into a number of
intervals along an attribute. For any given query, the counts from the
bins can be utilized for query resolution. A simple representation of the
histogram method would simply partition the data into equi-depth or
equi-width intervals. The main inaccuracy with the use of histograms
