Exist

As far as the exist query is concerned, the performance difference of each examined method can be seen clearly. For each queried window, the existence of a number of features was searched. More specifically, the focus was in finding out whether at least one of the queried features existed inside the queried window. As soon as one of them was met, processing stopped.

In Figures , , the results, when 2, 5 and 10 features are queried respectively, are illustrated. A first observation is that the methods using the bitstring always perform better than their counterparts which do not use a bitstring. In addition, the BHL-tree outperforms all methods for more than 2 features. This is explained by considering two facts:

• the HL-tree stores locational keys for internal quadtree nodes as well. As explained in Section 3.2.2, this can lead to less disk accesses since very soon it can be identified whether the region that it is looked for is homogeneous or not, and which features it contains.
• at upper levels, the use of the bitstring can help skipping those tree portions that do not contain any of the queried features.

The bad performance of the SL-tree is explained by the fact that the specific quadblocks of which, the region that is searched is comprised, have to be found out in order to check the contained features. As far as the IL-trees are concerned, all the feature-indices have to be processed always without knowing whether the specific feature is contained inside the queried window or not. In addition, the order of accessing the independent indices is random and there is no means to bypass non useful indices. Figure depicts how the IL-trees' behavior worsens with respect to the number of features.

Figure: Averaged results for an exist query where 2 features were queried, image size 512$\times$512, 64 features.

Figure: Averaged results for an exist query where 5 features were queried, image size 512$\times$512, 64 features.

Figure: Averaged results for an exist query where 10 features were queried, image size 512$\times$512, 64 features.

Figure: Averaged results for an exist query for a varying number of queried features, image size 512$\times$512, 64 features, query window 30$\times$30.