Database Reference
In-Depth Information
Effect 3:
Misses caused by decreasing Ellr will grow and add other
ellipsoids. These grows and adds make regions cover new parts of the
domain and also change the overall structure of the index. Both of these
affect the probability of retrieves for future queries. This is a more subtle
effect unique to this problem.
Tuning Grows and Adds.
Just like the Retrieve, the Grow and Add op-
erations can be controlled by the number of ellipsoids examined for growing,
denoted as Ellg. Since an Add is performed only if a Grow fails, this parame-
ter controls both the operations. Ellg provides a knob for controlling several
effects.
Effect 4:
The first part of the grow process involves traversing the index
to find ellipsoids that can be grown. Decreasing Ellg reduces the time
spent in the traversal.
Effect 5:
Decreasing Ellg decreases the the number of ellipsoids exam-
ined for the grow and hence the number of ellipsoids actually grown.
This results in the following effects.
-
Effect 5a:
Reducing the number of ellipsoids grown reduces index
update costs, which can be significant in high-dimensional indexes.
-
Effect 5b:
Growing a large number of ellipsoids on each Grow op-
eration covers more parts of the function domain, thereby improving
the probability of future retrieves.
-
Effect 5c:
Growing a large number of ellipsoids on each Grow re-
sults in significant overlap among ellipsoids. Overlap among objects
being indexed reduces search eciency in many high-dimensional
indexes.
Effect 6:
Decreasing Ellg increases the number of Add operations. Cre-
ating a new region is more expensive than growing an existing region
since it involves initializing the function
f
R
in the new region.
In summary, the two tuning parameters have many different effects on index
performance and the cost of the simulation. What makes the problem inter-
esting is that these effects often move in opposite directions. Moreover, tuning
affects indexes differently and to varying degrees, which makes it necessary to
analyze each index individually.
11.4.2.4
An Example: A Binary Tree Index
The previous section presented a qualitative discussion of the effects that
tuning Ellr and Ellg can have on index performance and simulation cost. This
section makes these effects more concrete using an example index structure,
the Binary Tree. This tree indexes only the centers of the ellipsoids (not the
actual ellipsoid) by recursively partitioning the space with cutting planes.
Leaf nodes of the tree contain ellipsoids, and nonleaf nodes represent cutting
