Database Reference
In-Depth Information
containing it. To overcome this problem the Binary Tree performs a more
expensive Secondary Retrieve if the Primary fails. The main idea of the Sec-
ondary Retrieve is to explore the “neighborhood” around the query point by
examining nearby subtrees. In the case of
q
3
, the failed Primary Retrieve
ended in leaf
B
. Nearby subtrees are explored by moving up a level in the tree
and exploring the other side of the cutting plane. Specifically,
C
is examined
first (after moving up to
Y
,
C
is in the unexplored subtree). Then the search
would continue with
A
(now moving up another level to
X
and accessing the
whole left subtree). This process continues until a containing ellipsoid is found,
or Ellr ellipsoids have been examined unsuccessfully.
Update
Scenario 1 (Grow) and Scenario 2 (Add) of Figure 11.14 illustrate the update
operations on the index.
Grow.
The search for growable ellipsoids proceeds in exactly the same way
as a Secondary Retrieve, starting where the failed Primary Retrieve ended.
Assume that in the example in Figure 11.14, ellipsoid
B
can be grown to
include
q
4
, but
C
and
A
cannot. After the retrieve failed, the Grow operation
first attempts to grow
C
. Then it continues to examine
B
, then
A
(unless
Ellg
3).
B
is grown to include
q
4
, as shown on the bottom left (Scenario 1).
Growing of
B
made it straddle hyperplane
Y
. Hence, for any future query point
near
q
4
and “below”
Y
, a Secondary Retrieve is necessary to find containing
ellipsoid
B
, which is “above”
Y
.
Add.
The alternative to growing
B
is illustrated on the bottom right part
of Figure 11.14 (Scenario 2). Assume Ellg
<
1; that is, after examining
C
, the
Grow search ends unsuccessfully. Now we add a new ellipsoid
F
with center
q
4
to the index. This is done by replacing leaf
C
with an inner node
Z
, which
stores the hyperplane that best separates
C
and
F
. The Add step requires the
expensive computation of
f
, but it will enable future query points near
q
4
to
be found by a Primary Retrieve.
Tuning parameter Ellg affects the Binary Tree in its choice of scenario 2
over 1. This choice, that is, performing an Add instead of a Grow operation,
reduces false positives for future queries but adds extra cost for the current
query. Experiments on real simulation workloads have shown that this tradeoff
has a profound influence on the overall simulation cost.
30
=
11.4.3 Deployment Examples
The ISAT Algorithm and its optimizations have primarily been applied to
combustion simulation workloads. However, the ideas are applicable to any
simulation setting where repeated evaluations in a fixed domain of a function
that is locally smooth and expensive to compute are required. Preliminary
results of applying the techniques to real simulations suggest that a significant
reduction in overall simulation time, one or more orders of magnitude, can be
achieved by careful index tuning.
