Mapping Function

 As mentioned above, the mapping function plays a major role in this access method. It determines the branches you have to traverse, for searching or insertions. In our system, the mapping function is denoted in terms of several parameters and these parameters are stored in the root and the expanded buckets of the structure.

Our system allows the use any function for mapping n-dimensional points onto linear space, but it should provide a uniform linearization for the data set given. To provide a uniform distribution of points among the buckets, we redefine the mapping function according to the distribution of the objects. This is done by analysing the distribution of objects and then changing the parameters of the mapping function accordingly. Figure 3 illustrates how the mapping function is dynamically changed to absorb the skewed-ness in the data distribution.

  

Figure 3: Dynamic adoption of the mapping function.

In the case of spatial data, the class of mapping functions depends on X or Y or both. We have tested the performance of our system with spatial data and 2-dimensional mapping functions and performance results are given in Section 5.

However, in real life, we can not expect uniformly distributed objects, we usually end up with highly skewed data, instead. In such cases, we use the knowledge of a domain expert to devise a mapping function which maintains the uniformity. The uniformity is achieved by repeatedly tuning the mapping function. We still investigate the behaviour of different mapping functions under different application domains and the cost of tuning algorithms.