Database Reference
In-Depth Information
nesic function specifies, for every point in the data series, the
maximum
allowable error for the approximation, which is useful when the applica-
tion requires quality guarantees for the approximation of the data series.
When we use absolute amnesic functions, we allow the approximation
to use as much memory as necessary in order to meet the error bounds.
More formally, we define the following two problems in the context of
landmark windows
.The
landmark window
is the window that contains
all the values of the data series (from a given time point) up to now.
Problem 2.3 (Land. Win. with Relative Amnesic (URA))
Given a memory budget
M
and a relative amnesic function
RA
(
x
)
,con-
struct an amnesic approximation using memory at most
M
that mini-
mizes the approximation error of the data points inside the window.
Problem 2.4 (Land. Win. with Absolute Amnesic (UAA))
Given an absolute amnesic function
AA
(
x
)
, construct an amnesic ap-
proximation that minimizes the required memory
M
.
Note that in the
URA
and
UAA
problems, the optimization objective
is different. In the
URA
problem we seek to minimize the approximation
error given the memory space used by the data series approximation,
while in the
UAA
problem we want to minimize the space used in the
approximation given the maximum error allowed.
Following the definition of the problems for the landmark window, we
now define the corresponding problems for the case where we consider
the sliding window model.
Problem 2.5 (Sliding window with Relative Amnesic (SRA))
Given a sliding window
W
, a memory budget
M
, and a relative amnesic
function
RA
(
x
)
, construct an amnesic approximation using memory
M
that minimizes the approximation error of the data series within the
sliding window.
Problem 2.6 (Sliding window with Absolute Amnesic (SAA))
Given a sliding window
W
, and an absolute amnesic function
AA
(
x
)
,
construct an amnesic approximation that minimizes the required memory
M
.
2.3.1 Proposed Techniques.
Bulut and Singh propose the
use of wavelets to represent data streams, which are biased towards the
more recent values [16], and describe an ecient, online method for
incrementally maintaining this representation. The bias to the most
recent values can be seen as a special case of an amnesic function, whose
