PERFORMANCE EVALUATION

Detailed experiments were performed to compare the SL-tree, the HL-tree and the IL-trees against the new proposed technique applied to both the SL-tree (BSL-tree) and on the HL-tree (BHL-tree). All kinds of queries were tested, however the results of the report query were only used to show the drawbacks of the IL-trees, as it will be shortly explained in the following section. The exist and selection query were considered as the most important ones, since they can extensively show how the bitstring can accelerate processing in queries involving features. The selection of the queried features was based on their frequencies. Suppose that $i$ features are to be selected out of $j$ ones. First, the features were sorted according to decreasing frequency and, then, the 1st, the $\lfloor \frac{j}{i} \rfloor$-th, $\lfloor \frac{2j}{i} \rfloor$-th, ..., $\lfloor \frac{(i-1)j}{i} \rfloor$-th feature was selected. For instance, if $i$=4 and $j$=64, then the 1st, the 16th, the 32nd and the 48th feature should be selected.

All structures were implemented in C++ programming language under Windows NT and the experiments run on a Pentium II workstation. For a thematic map of size 256$\times$256, 512$\times$512 or 1024$\times$1024 pixels, the B$^+$tree that will be created will have a height of at most 4 levels. The window queries of size 25$\times$25, 50$\times$50 and 100$\times$100 pixels were executed on 256$\times$256 and 512$\times$512 images containing 8, 16 and 64 features. The page size used was 1K for smaller maps and 2K for larger maps leading to a fanout of 84 and 169 entries, respectively. The number of maximal blocks created for each thematic map ranges approximately from 40,000 to 240,000. The first group of thematic layers (i.e. 256$\times$256 images) was downloaded from the GRASS site, a public domain GIS system, while the second group of maps (i.e. 512$\times$512 maps) were meteorological satellite views of Europe and Asian regions from Meteosat Imagery site. The measurements were based on the number of disk accesses where only the accessed leaves were counted. For each thematic map, 50 queries were performed for four different window sizes and the results were averaged. Due to space limitations, the results for the 512$\times$512 images only are shown since the conclusions are similar for all cases.