Select

Regarding the select query, in the first set of experiments for each queried window the blocks, where the queried features were found, were searched. The results can be seen in Figures , and . As observed before, the methods where the new bitstring is embedded always perform much better than the respective ones without the bitstring since we can avoid to visit tree branches where the queried features do not exist.

More specifically, in Figures , and where we search for 2, 5 and 10 features respectively, it can be observed that the IL-trees seem to have a good performance in comparison to the other methods. However, their performance is not stable since it will always depend on the number of queried features (as demonstarted in Figure where all features are queried). The explanation is that the IL-trees' performance is tightly connected to the number of features queried, as well as to their occurrence frequency. More specifically, sparse features with low occurrence will create very small trees, possibly of even one node only, while the tree of a more frequent feature will be bigger and will affect the method's performance substantially. In general, the IL-trees seem to work very well for a few features only, which are rarely met in the thematic map.

In the previous graphs, it is shown that with an increasing number of queried features, the performance of the IL-trees becomes worse and this tendency is apparent in the second set of experiments. In this second set of experiments, the methods' performance was tested for two fixed window sizes, where the number of the queried features was increasing.

As can be seen in Figure , the performance of the IL-trees decreases progressively with the number of queried features resulting in a quite bad performance when a large number of features is queried, whereas on the contrary the BHL- and BSL-tree show a comparatively stable behavior. As expected, on one hand SL- and BSL-trees, and on the other hand HL- and BHL-trees behave similarly when a large number of features is queried and that is why the graphs of the BSL- and BHL-tree only are shown.

As a conclusion, the previous experiments show that the technique of posting feature information by means of a bitstring to upper levels of a linear-type quadtree results in superior performance for:

• large thematic maps because they produce a greater number of locational keys and, therefore, the height of the B$^+$tree will be bigger. Thus, filtering based on queried features can be applied at higher tree levels and, thus, traversing some B$^+$tree branches can be avoided,
• the exist query because at a very early stage the bitstring helps responding to the user query,
• thematic maps with concentrated features, such as typical GIS raster images. Otherwise the features will be spread to various locations leading to non-homogeneous leaf nodes, as far as the features are concerned, and consequently to bitstrings with many positions set to 1 that allow no filtering.

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

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

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

Figure: Select query for a varying number of queried features, image size 512$\times$512, window size 30$\times$30.