Conclusions and future work

 We have proposed a new indexing structure for spatial data and devised related algorithms. It has been implemented and its performance was tested with synthetic data. The data we used, were drawn from uniform distributions. However, we need to carry out more experiments with data from non-uniform distributions. We know that, this structure will not behave well in its worst case, i.e. when data are extremely skewed. In such a situation, all the points are mapped to a single bucket and in subsequent lateral expansions, they are mapped again into single buckets. Then the resultant structure will be a sequential bucket structure where the order of the search algorithm reduced to O(n). This is not an acceptable value for very large databases. But, data from the real world do not fall into either extremes (they are neither exactly uniform nor extremely skewed). Under these circumstances, we can discard the worst case performance of this structure, since the probability of occurring the worst case from real world data is ridiculously small. The next experiment will be based on real world data.

The performance of the linearization structure entirely depends on the decision metric used. The behaviour of the decision metric need to be investigated to find a class of decision metrics yielding optimum performance.

The motivation behind this access method is its applicability into higher dimensional feature vectors. The next goal of this project is to devise an n-dimensional access structure. The experimental setup has to be generalized to handle high dimensional vectors as objects.