next up previous
Next: Conclusions Up: PERFORMANCE EVALUATION Previous: Exist

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:

Figure: Averaged results for a select query where 2 features were queried, image size 512$\times$512, 64 features.
\begin{figure}
\psfull\centerline {\psfig{file=sel5_2q.eps,width=8cm,height=5.5cm}}\end{figure}

Figure: Averaged results for a select query where 5 features were queried, image size 512$\times$512, 64 features.
\begin{figure}
\psfull\centerline {\psfig{file=sel5_5q.eps,width=8cm,height=5.5cm}}\end{figure}

Figure: Averaged results for a select query where 10 features were queried, image size 512$\times$512, 64 features.
\begin{figure}
\psfull\centerline {\psfig{file=sel5_10q.eps,width=8cm,height=5.5cm}}\end{figure}

Figure: Select query for a varying number of queried features, image size 512$\times$512, window size 30$\times$30.
\begin{figure}
\psfull\centerline {\psfig{file=selft5a.eps,width=8cm,height=5.5cm}}\end{figure}


next up previous
Next: Conclusions Up: PERFORMANCE EVALUATION Previous: Exist
Eleni Tousidou
2000-01-03