Database Reference
In-Depth Information
model (Section 11.4.2.2). The streaming nature of the application introduces
a new storage and retrieval, and hence indexing, problem in the algorithm.
This section then discusses the indexing problem in detail: its challenges and
solutions that have been proposed (Sections 11.4.2.3 and 11.4.2.4).
11.4.2.1
Local Models
Local models are used in many applications to approximate complex high-
dimensional functions. Given a function
f
:
R
m
R
n
a local model defines
a set of high-dimensional regions in the function domain:
→
=
{
R
1
...
R
n
|
R
i
⊆
R
f
R
i
:
R
i
→
R
m
R
n
; such that
}
. Each region
R
i
is associated with a function
∀
x
∈
f
R
i
(
R
i
:
||
x
)
−
f
(
x
)
|| ≤
, where
is a specified error tolerance in the model
and
is an error metric such as the Euclidean distance. Using a local model
to evaluate
f
at some point
x
in the function domain first involves finding a
region
R
||
f
R
(
∈
R
that contains
x
and then evaluating
x
)
as an approximation
to
f
(
x
)
.
11.4.2.2
The ISAT Algorithm
Main algorithm:
ISAT is an online algorithm for function approximation.
Its pseudocode is shown in Figure 11.12. The algorithm takes as input a query
point
x
at which the function value must be computed and a search structure
I
that stores the regions in
.
I
is empty when the simulation starts. The
algorithm first tries to compute the function value at
x
using the local model it
has built so far (Lines 2 and 3). If that fails, the algorithm computes
f
R
(
x
)
using
the expensive model (Line 5) and uses
f
to update existing or add new
regions in the current local model (Line 6). The algorithm is online because
it does not have access to all query points when it builds the model.
Model updating:
ISAT updates the local model using the strategy out-
lined in Figure 11.13. In general it is di
cult to exactly define a region
R
and an associated
f
R
, such that
f
R
approximates
f
in all parts of
R
. ISAT
uses a two-step process to “discover” regions. It initially starts with a region
that is very small and conservative but where it is known that a particular
(
x
)
f
R
ISAT Algorithm
1:
Require:
Query Point
x
, index structure
I
f
R
2:
if
∃
R
,
∈
I
such that
x
∈
R
f
3:
Compute
y
=
(
x
)
4:
else
5:
Compute
y
=
f
(
x
)
6:
Update(
I
,
x
,
f
(
x
)
)
7:
end if
8:
return y
Figure 11.12
ISAT algorithm.
