Database Reference
In-Depth Information
X
q3
X
B
Y
A
q1
C
A
Y
q2
q4
C
B
Scenario 1
Scenario 2
X
X
X
X
A
Y
Y
B
A
Y
A
A
B
Y
C
C
B
Z
Z
C
B
F
F
C
Figure 11.14
Binary Tree.
planes. Figure 11.14 shows an example tree for three ellipsoids
A
,
B
, and
C
and two cutting planes
X
and
Y
.
For now let us focus on the tree in the top part of Figure 11.14 and describe
the operations supported by the index.
Retrieve
There are two possible traversals in the index that result in a successful
retrieve.
Primary Retrieve.
The first, called a Primary Retrieve, is illustrated
with query point
q
2
. The retrieve starts at the root, checking on which side
of hyperplane
X
the query point lies. The search continues recursively with
the corresponding subtree, the left one in the example. When a leaf node is
reached, the ellipsoid in the leaf is checked for the containment of the query
point. In the example,
A
contains
q
2
, therefore, we have a successful Primary
Retrieve.
Secondary Retrieve.
Since the Binary Tree only indexes centers, ellip-
soids can straddle cutting planes; for example,
A
covers volume on both sides
of cutting plane
X
. If ellipsoids are straddling planes, then the Primary Re-
trieve can result in a false negative. For example,
q
3
lies to the right of
X
and so the Primary Retrieve fails even though there exists an ellipsoid
A
