A Theoretical and Empirical Evaluation of a Novel Spatial Data Indexing Structure

In this paper, we present a theoretical and empirical evaluation of the performance of the Multi Layer Quadtree (MLQ), a spatial join structure used for indexing spatial data. The Multi Layer Quadtree is based on the PM1-Quadtree. It permits the representation of multi-layers in a single structure rather than a structure for each layer. The theoretical evaluation of the MLQ is intended to compute the storage required by the structure in a worst case scenario to show that the structure would be accommodated in a reasonable memory without degrading the system performance. The empirical evaluation is based on real data as well as synthetic data to show the flexibility of the structure and the response attained by adopting such a structure. The application of the selection, insertion, and deletion operations using the MLQ is also presented. We consider point and range queries over two-dimensional data such as lines, poly-lines and regions data.