next up previous
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 B$^+$tree 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 B$^+$tree nodes.

Evidently, the original B$^+$tree traversal is based on the locational code, which is the B$^+$tree 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 B$^+$tree 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 B$^+$tree.

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 B$^+$tree leaves will consist of:

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 B$^+$tree 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 $i$-th bit is set to 1, if and only if the feature with id=$i$ 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 B$^+$tree 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 B$^+$tree sub-structure.

Figure: Layout of internal and leaf nodes.
\begin{figure}
\centerline {\psfig{file=fig3.eps,width=7cm,height=1.5cm}}\end{figure}

The layout of internal and leaf nodes is illustrated in the upper and lower part of Figure [*], respectively. Basically, leaves comprise of $m$ pairs (locational key, value field or bitstring), whereas internal nodes comprise of $l$ triplets (tree pointer, locational key, bitstring), where $l$ 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 1024$\times$1024 or 2048$\times$2048 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.

Figure: Branch of the B$^+$tree.
\begin{figure}
\centerline {\psfig{file=fig4.eps,width=8cm,height=3.5cm}}\end{figure}

As expected, the B$^+$tree 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 B$^+$tree 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 B$^+$tree leaves, allowing to avoid visiting some irrelevant tree branches. Figure [*] illustrates an example of a BHL-tree, where $m$=3 and $l$=3.


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