10.2. Model of the Dynamization

In this section, we will formalize the presented ideas in a very general setting. Thus, we need a data structure description independent from a special problem. We use the notion of an abstract (geometric) data type. An abstract data type Static is defined by the following:

a set of objects,
a set of operations for the given objects, and
a semantical interpretation of the operations.

The abstract data type will not specify how the given objects are represented internally or how the operations have to be implemented. In turn , the description is independent from a specific programming language. For example, the standard description of a Stack with the well-known operations Pop, Push, Top, and New over a set of objects X is an abstract data type.

Let us assume that Static is a static abstract (geometric) data type. We want to define the generic dynamization by a module that imports a set of operations from Static and exports a set of new dynamic operations. As shown in the kd-tree example in the preceding section, we need a method to build a single static structure for a set of input objects. Additionally, we have to be able to collect all elements from a static structure in order to construct a single static data structure from the input of a set of static structures; see Figure 10.10. This also means that we need a method for deleting a given static structure. Furthermore, since we have a geometric data structure, we can assume that there is a query operation on the set of stored geometric objects D in Static. That is, for a query object q , the answer is a subset of D. Note that the answer might be empty.

Figure 10.10: Dynamization in a generic sense. (Redrawn and adapted courtesy of Rolf Klein.)

Altogether, we can assume that the following operations are given.

V := D . Build:	Build the structure V of type Static with all data objects in the set D.
A := V . Query( q ):	Return the answer A (objects of D) to a query to V with query object q .
C := V . Collect:	Collect all data objects of V in C (objects of D represented in V ).
V . Destroy:	Delete the complete data structure V from storage.

The dynamization module should export a dynamic abstract (geometric) data type DYNAMIC with the same set of operations. Since we export a dynamic data structure, additional operations for insert and delete are made available.

W := D . BUILD:	Build the structure W of type DYNAMIC with data objects of the set D.
A := W . QUERY( q ):	Return the answer A (objects of D) to a query to W with query object q .
C := W . COLLECT:	Collect all data objects of W in C (objects of D represented in W ).
W . DESTROY:	Delete the complete data structure W from storage.
W . INSERT(d):	Insert object d into W .
W . DELETE(d):	Delete d from W .

Note that the new operations DELETE and INSERT are necessary, since we have a dynamic data type now.

Additionally, we introduce some cost functions for the operations of the abstract dynamic and the abstract static data type. For example, let b _V ( n ) denote the time function for the operation V := D . BUILD of the data type Static with D = n . The notions are fully presented in Figure 10.10. The cost functions depend on the implementation of the data type Static. The cost function of DYNAMIC will depend on the cost functions of Static together with the efficiency of the general dynamization.

In order to guarantee some bounds for the corresponding cost functions of DYNAMIC, the cost functions of Static have to behave well and run within certain bounds. Additionally, for the proofs of the time bounds, we need some kind of monotonic behavior of the cost functions. The functions should not oscillate. Altogether, we define the following simple requirements to the static data structure and its cost functions.

The operations Query and Destroy become more time-consuming if the object set grows. This means that the functions q _V ( n ) and y _V ( n ) are non- decreasing in n . Example functions: 1, log n , , n , n log n , n ² , 2 ⁿ .
The Build operation and the needed space for n objects lies in ( n ). This means that the functions b _V ( n ) and s _V ( n ) are at least linear in n . Example functions: n , n log n , n ² , 2 ⁿ .
All operations do not change their behavior significantly if the set of object grows only by a constant factor. This means that all functions f ˆˆ {q _V , b _V , c _V , s _V , y _V } are somehow smooth. That is, there is a constant K , so that f ( cn ) ‰ K f ( n ) for a constant c > 1. Example functions: 1, , n , n ² , and also log n with n > 1, as well as the products of these functions, but not 2 ⁿ !
Collecting all elements needs at most twice the rebuilding time. This means that we require c _V ( n ) ‰ 2 b _V ( n ).
Moreover, we assume that the Query operation is decomposable; i.e., for a decomposition V = V ₁ ˆ V ₂ ˆ ˆ V _j of the data set V , the results of the single operations V _i . Query( q ) lead to the solution of V . Query(d). This holds for many kinds of search queries.

We consider an amortized cost model. Let Work be an arbitrary operation with cost function h. For a sequence of t different operations, let Work be applied k times. That is, among the t operations there are only k Work operations. If

holds for a cost function h , we say that the operation Work is performed in amortized time h ( t ).

Note that this is not an expected value and that h is a function of t , i.e., the length of the operation sequence. The current data set may have a number of elements n ‰ t . The worst-case cost of all operations should be given by functions in n .