10.1. Example of Dynamization

We consider the balanced kd-tree introduced in Section 2.4. For a static set of n points, a balanced kd-tree can be easily built by allocating space for a binary tree with 2 ^k leaves , where 2 ^k ˆ 1 < n ‰ 2 ^k . For example, in Figure 10.1, a balanced kd-tree for a set of 11 points is given. The balanced kd-tree supports efficient range queries for rectangular ranges Q .

Figure 10.1: A single static kd-tree.

We apply a general dynamization technique. That is, we implement the dynamic insert and delete operations of the given data structure without any knowledge of its internal representation, thus avoiding complicated special rebalancing operations. Additionally, the cost of query operations should not be affected significantly. The main idea is that we transform the given problem adequately and use efficient algorithms for the full static structure.

10.1.1. Amortizing Kd-Tree Insert Operations Over Time

First, we will discuss the generic dynamization of insert operations and will try to demonstrate that spreading work over time is a good paradigm. Assume that a new point l = (5.5, 8.5) has to be inserted into the kd-tree of Figure 10.2. We can simply insert l by following the path to the corresponding rectangular region of k . The region is split accordingly and a new node is allocated and appended to the tree; see Figure 10.3. After some of these simple insertions, the tree is no longer balanced, but it is almost balanced. For a while, such simple insertions will not charge the query operations and insert operations significantly.

Figure 10.2: A set of static kd-trees .

Figure 10.3: Inserting a single object into a static kd-tree.

On the other hand, many simple insertions may unbalance the tree significantly. In this case, insert and query operations will require more effort. Therefore, after a while, we should reorganize and rebalance the tree, if we still want to perform efficient insert operations and search queries. We apply an amortized cost model. The reorganization is costly but does not happen very often. We distribute the cost over the sequence of all operations that happens between two reorganizations. The amortized cost model is formally explained in Section 10.2.

Amortizing the cost over a sequence of operations is most promising if the cost for the rebalance operations is small. Since we are restricted to the use of the static construction algorithm of the data structure, we try to avoid reconstruction of the whole data structure. Accordingly, we transform the static structure into a set of balanced static structures and apply occasional reconstructions only to subsets of these structures. For example, in Figure 10.1, a balanced kd-tree for a set of 11 points is given, whereas in Figure 10.2, we consider a set of different static balanced kd-trees for the same set of points.

A simple insert operation may affect only small subsets. For example, if the new point l = (5.5, 8.5) has to be inserted into the set of kd-trees, we would like to insert l into one of the smaller structures.

In the next section, we will specify the decomposition more precisely.

10.1.2. A Binary Decomposition of Static Kd-Trees

Let us assume that we start with a fixed set of points. We need a general rule for subdividing a single static kd-tree into a set of static structures. Many ideas for such decomposition were presented in the beginning of the 1980s. For example, Maurer and Ottmann [Maurer and Ottmann 79] introduced an equal block method, which spread n objects over k structures V ₁ , V ₂ , , V _k with V _j ‰ . Thus, every V _j has some room for simple insertions. This means that, in general, a simple weak insertion technique has to be implemented.

We will present an efficient decomposition that goes back to [Bentley 79]. As you will see, weak insertions are not necessary. The main idea is that we use the binary representation of the number of points. For example, the binary representation of 11 is given by 1011, which represents a linear combination

and results in the corresponding three substructures V = 1, V ₁ = 2, and V ₃ = 8; see Figure 10.2. In general, for n points in the plane and the binary representation

there is always a unique binary decomposition W _n , given as a set of kd-trees { V _i : a _i = 1}. Every V _i contains exactly 2 ⁱ objects, and every object is contained in uniquely one V _i .

As previously mentioned, we would like to insert new elements in smaller structures. The main advantage is that, due to the binary decomposition, the kd-tree V _i with 2 ⁱ elements remains valid until the number of objects of the lower-order structures V , V ₁ , V ₂ , , V _i _ˆ1 will exactly sum up to 2 ⁱ ˆ 1 elements and an additional element p has to be inserted; i.e., there is room for 2 ⁱ ˆ 1 elements below V _i . If the insertion of p happens, we have to construct V _i ₊ ₁ out of V , V ₁ , V ₂ , , V _i _ˆ ₁ and p . For clarification , let us further assume that with respect to the binary decomposition, the structures V , V ₁ , V ₂ , , V _i _ˆ ₁ and V _i ₊ ₁ are empty. Thus, we can insert elements without affecting V _i .

For example, if we insert l = (5.5, 8.5), the number of elements below V ₂ rise to V ₁ + V + 1 = 2 ² (see Figure 10.4), and we reconstruct V ₁ , V , and l to V ₂ (see Figure 10.5). Note that the binary representation of the current number of elements 12 = 1 2 ³ + 1 2 ² + 0 2 ¹ + 0 2 exactly represents the distribution of the points in the kd-tree V ₂ and V ₃ .

Figure 10.4: A change in the binary decomposition from W ₁₁ to W ₁₂ .

Figure 10.5: After insertion of l, we build V ₂ from V ₁ , V , and l.

According to the amortization idea just presented, a reconstruction operation for V _i occurs if exactly 2 ⁱ insert operations are done. Additionally, the number of objects for constructing V _i ₊₁ from V , V ₁ , V ₂ , , V _i _ˆ1 , V _i is also in O (2 ⁱ ). Thus, we can amortize the reconstruction cost for V _i ₊ ₁ by O (2 ⁱ ) insert operations. We divide the cost for building V _i ₊ ₁ by 2 ⁱ ; for details see Section 10.3.1. The binary decomposition goes back to [Bentley 79] and is denoted also as the logarithmic method .

In principle, we will never insert an object directly into one of the substructures V _j . Let us assume that an element p is inserted. If V is free, there is nothing to do; the element itself represents V . Otherwise, V and p may be combinend to V ₂ . If V ₂ is not free, we may combine V and p and V ₂ to V ₃ , and so on. Technically, there are only reconstructions and no insertions at all.

10.1.3. Query Operations in the Binary Representation of Kd-Trees

We still have to guarantee that the binary decomposition of a kd-tree supports efficient data queries. We require that the query is decomposable . That is, the set of answers resulting from the queries to any kd-tree in the set of kd-trees can be used for constructing the answer to the single static tree.

Fortunately, the requirement holds for many range query data structures and also for general search query data structures. For example, in Figure 10.6, a rectangular range query is answered by the union of rectangular range queries. With respect to the binary decomposition, we have to combine the answer of O (log n ) substructures. Therefore, the running time of the query will rise within a factor of O (log n ).

Figure 10.6: A kd-tree query is decomposable.

10.1.4. Generic Delete Operations for a Kd-Tree by the Half- Size Rule

Reconstruction and rebalancing in a full dynamic kd-tree may also be required because of delete operations. For a generic implementation of delete operations, we follow a similar idea as presented in the previous section. We discuss the following idea, which goes back to [van Leeuwen and Maurer 80]. For a while, we perform simple delete operationsthat is, we do not delete an element physically; we only mark an element as deleted. This weak delete operation is denoted as WeakDelete, and for a while, the number of dead elements in the tree will not affect the efficiency of query operations or new delete operations. See Figure 10.7 for the application of a sequence of WeakDelete operations.

Figure 10.7: A set of objects are weakly deleted from the static kd-tree.

We want to rebuild the data structure if the actual number of objects and the total number of objects (the actual number plus the number of weakly deleted objects) differ too much. As a good rule of thumb, the set of actual numbers should be at least as big as the set of weakly deleted objects. Therefore, we reconstruct the static data structure if the number of weakly deleted objects equals or exceeds the number of real objects. This method can be denoted as the half-size rule . Obviously, a query operation can easily filter out the needed objects.

We can spread the cost for the reconstruction of V by 1/2 V WeakDelete operations. Additionally, we have to account for the WeakDelete operation itself; see Section 10.3.2 for details.

Up to now, we have considered insert and delete operations independently. Obviously, a sequence of operations will contain both insert and delete operations (and query operations also). In this case, the idea of using a binary decomposition for handling insertions and applying the half-size rule for a set of WeakDelete operations must interact. [Overmars and van Leeuwen 81c] showed that for a special class of decomposable search queries, one can handle delete operations directly within the binary decomposition.

10.1.5. Half-Size Rule and Binary Decomposition of a Kd-Tree

Finally, we should be able to combine the methods of the preceding sections. Performing a WeakDelete operation of an element p in a single kd-tree is not difficult. The weakly deleted object has to be find and marked .

In the binary decomposition, we first have to find the corresponding structure V _j with p ˆˆ V _j . This search problem is solved with a standard one-dimensional balanced search tree; see Figure 2.7. Every object is represented by a unique ID, so that we can compare two objects efficiently . Every element in the search tree has a pointer to its current substructure . For example, let us assume that the elements in Figure 10.8 can be identified by ID( a ) = 1, ID( b ) = 2 , , ID( k ) = 11. The corresponding balanced binary search tree is shown in Figure 10.9. For every ID, there is a pointer to the corresponding substructure. In the substructure, the element is weakly deleted. We assume that the one-dimensional search tree is fully dynamized. This assumption is justified because a dynamic binary search tree does already belong to standard libraries. Finding the adequate substructure needs additional O (log n ) time for n elements.

Figure 10.8: Some WeakDelete operations in the binary decomposition of a static kd-tree.

Figure 10.9: The balanced binary search tree for 11 elements. The entries have a pointer to the corresponding substructure.

So far, we have specified how a WeakDelete operation can be done efficiently. Now, we apply the half-size rule for the whole structure. If the number of weakly deleted objects equal the number of real objects, we will reconstruct the binary representation. We can spread the cost for the reconstruction of the whole V by 1/2 V WeakDelete operations and account also for the WeakDelete operation itself. The use of the binary tree gives a summand of O (log n ); see Section 10.3.3 for details.