Appendix A: Illustration of Lateral and Longitudinal Expansion.

The following sequence of the diagrams illustrate how does this linearization structure grow in vertical and horizontal directions under lateral and longitudinal expansions, respectively.

Figure 8 illustrates a one level structure with one mapping function and 4 buckets. It is still unexpanded. The structure remains in this form, till one of the buckets overflows.

  

Figure 8: Before any expansion.

Let us assume, bucket B₁ overflows, after several insertions. Then, a lateral expansion is applied to bucket B₁. A new mapping function is created and stored in bucket B₁. Data objects are re-mapped to new buckets B₁₀ .. B₁₃. This results in a vertical growth of the structure. Figure 9 illustrates the structure after the lateral expansion.

  

Figure 9: After applying Lateral Expansion to B₁.

We may apply a number of such lateral expansions due to subsequent overflow situations. This may occur at the lop level (eg. bucket B₁) or on another level (eg. bucket B₁₂) as illustrated in Figure 10.

  

Figure 10: After applying several Lateral Expansions.

After a number of such lateral expansions, the decision metric forces the system to do a local reorganization by applying a longitudinal expansion. As a result of the longitudinal expansion, buckets B₀ ..B₃ and their child buckets are replaced with a new bucket sequence B₀ .. B₁₁. The old mapping function, Hⁿ_i is now replaced with a new mapping function, Hⁿ_j. The length of the bucket sequence is decided by the decision metric. Such a longitudinal expansion forces the structure to grow horizontally, reducing the length of search paths. Figure 11 illustrates the structure after the longitudinal expansion.

  

Figure 11: After applying Longitudinal Expansion.