A SURVEY OF MODEL-BASED SENSOR DATA ACQUISITION AND MANAGEMENT - Managing and Mining Sensor Data - page 42

segment with the most suitable model. They propose a greedy approach
in which they employ multiple models for each segment of the data
stream and store the model that achieves the highest compression ratio
for the segment. They experimentally proved that their multi-model
approximation approach always produces fewer or equal data segments
than those of the best individual model. Their approach could also be
used to exploit spatial correlations among different attributes from the
same location, e.g., humidity and temperature from the same stationary
sensor.
5.6 Orthogonal Transformations
The main application of the orthogonal transformation approaches
has been in dimensionality reduction, since reducing the dimensional-
ity improves performance of indexing techniques for similarity search
in large collections of data streams. Typically, sequences of fixed length
are mapped to points in an N -dimensional Euclidean space; then, multi-
dimensional access methods, such as R-tree family, can be used for fast
access of those points. Since, sequences are usually long, a straightfor-
ward application of the above approach, which does not use dimension-
ality reduction, suffers from performance degradation due to the curse
of dimensionality [56].
The process of dimensionality reduction can be described as follows.
The original data stream or signal is a finite sequence of real values or co-
ecients, recorded over time. This signal is transformed (using a specific
transformation function) into a signal in a transformed space. To achieve
dimensionality reduction, a subset of the coe cients of the orthogonal
transformation are selected as features. These features form a feature
space, which is simply a projection of the transformed space. The basic
idea is to approximate the original data stream with a few coecients of
the orthogonal transformation; thus reducing the dimensionality of the
data stream.
5.6.1 Discrete Fourier Transform (DFT). The Fourier trans-
form is the most popular orthogonal transformation. It is based on the
simple observation that every signal can be represented by a superposi-
tion of sine and cosine functions. The discrete Fourier transform (DFT)
and discrete cosine transform (DCT) are ecient forms of the Fourier
transform often used in applications. The DFT is the most popular
orthogonal transformation and was first used in [1, 22]. The Discrete
Fourier Transform of a time sequence x = x 0 ,...,x N− 1 is a sequence