Next: Algorithm Description Up: PROPOSED METHOD Previous: PROPOSED METHOD

## Description of the New Method

Here, the pointerless representation of the new method will be described since the pointer-based one can be developed in a similar way. The Linear quadtree uses the Btree as a storage medium for the locational keys of the thematic map, and as an efficient structure for the fast retrieval of the represented information. The proposed method is based on a restructuring of the Btree nodes.

Evidently, the original Btree traversal is based on the locational code, which is the Btree key. To be able to efficiently perform window queries that search for certain features inside a given window, it is important to know whether the Btree sub-structure that is about to be traversed contains at least one of the desired features. In case it does not, this sub-structure can be skipped resulting in fewer disk accesses. Since this traversal has to be additionally constrained with the feature information, a bitstring representing the kind of needed information will be stored in the upper levels of the Btree.

In the following it will be made obvious that the proposed method of posting to the parent node a second-order bitstring can be applied to the SL-tree and the HL-tree as well. The structures derived by such a use of the bitstring are named BSL-tree and BHL-tree, respectively. According to the new proposal each entry in the Btree leaves will consist of:

• a locational key of the represented quadrant,
• a value field containing the color of the specific quadrant or (when applied to the HL-tree) a bitstring of size equal to the number of features. This bitstring is encoded so that the -th bit is set to 1, if and only if the feature with id= exists in the respective quadrant.
However, according to the new method, a second-order bitstring is introduced in the entries of the internal nodes. More specifically, the bitstrings (or value fields) of the entries of a specific Btree leaf are superimposed (OR-ed), thus forming a new second-order bitstring which represents the feature information of the respective leaf in a condensed/abstract way. In essence, for each leaf a new bitstring is encoded so that the -th bit is set to 1, if and only if the feature with id= exists in the entries of the specific leaf. Then, this second-order bitstring is posted to the parent node of the leaf. The idea of producing second-order bitstrings can be generalized for all Btree levels. Thus finally, each entry in the internal nodes will be accompanied by this second order bitstring which will have 1s only at positions where the respective features exist in the corresponding Btree sub-structure.

The layout of internal and leaf nodes is illustrated in the upper and lower part of Figure , respectively. Basically, leaves comprise of pairs (locational key, value field or bitstring), whereas internal nodes comprise of triplets (tree pointer, locational key, bitstring), where is the tree fanout. The size of a tree pointer is 4 bytes (32 bits). The value field of the leaves is used in the case of the BSL-tree since only the color of the homogeneous quadrant needs to be stored. The bitstring is used in the case of the BHL-tree since, in case of a heterogeneous quadrant, it might be needed to store more than one feature.

Regarding the internal nodes of the tree, since their average space requirements would be about 30 or 40 MB, it can be safely assumed that they can be easily accommodated in the main memory of modern computers. On the other hand, for images of size 10241024 or 20482048 pixels, the quadtree depth is 10 or 11 levels and the length of the locational key is 24 or 26 bits, respectively. Assuming that the locational key is represented by an integer, in the case of the BSL-tree, as far as the leaves are concerned, the remaining one or two bytes can be used in order to store the color.

As stated in the previous, this is the reason for ignoring the space occupied by the value field when calculating the introduced storage overhead in the case of the BSL-tree. Also, there is no change in the case of the BHL-tree since the leaves of the original HL-tree already contained those bitstrings.

As expected, the Btree root and some entries at the level below the root will probably contain bitstrings with many positions set to 1 since the respective subtrees will contain almost all features. More specifically, in the case of widely spread features, the number of bitstring positions set to 1 will be large, resulting in visiting all queried maximal blocks inside the query window. It should be noticed though, that for such thematic maps, whatever the method used, they will result in a great number of disk accesses since the queried features will be spread in almost all Btree leaves. On the other hand, if the queried maps contain features which are concentrated in specific areas, this would result in only a few positions set to 1 in the Btree leaves, allowing to avoid visiting some irrelevant tree branches. Figure illustrates an example of a BHL-tree, where =3 and =3.

Next: Algorithm Description Up: PROPOSED METHOD Previous: PROPOSED METHOD
Eleni Tousidou
2000-01-03