Hybrid Linear Quadtree

Another approach has been proposed in [11], where apart from the quadtree leaves, internal nodes are also registered in the B$^+$tree. However, internal nodes are heterogeneous blocks since they contain more than one feature. Internal nodes are coded with a locational key, whereas to represent the feature information each quadtree node will accommodate a bitstring of size equal to the number of features existing in the thematic map. A specific bit of the bitstring is set to 1, if and only if the respective feature exists in the represented quadrant.

Evidently, this approach has a storage overhead due to the storage of the internal nodes and the corresponding bitstring. In [11] it is explained that this overhead is not significant since the number of internal nodes are not larger than the 1/3 of the number of leaves and, consequently, the asymptotic space occupancy will remain the same. Also, since computer systems are based on a 32-bit architecture, space can always be saved for at least 16 features, which is a reasonable number of features.

Applying the method of HL-trees on the thematic layer of Figure , the following list of nodes, either internal or external, will be created and stored in the B$^+$tree leaves. As can be seen, each locational key is accompanied by a bitstring of size four, since four are the features existing in the represented thematic map. Nodes accompanied by a bitstring that has only one bit set to 1 are homogeneous quadtree leaves covered by the respective feature. For example, the locational code 110 that corresponds to an internal node is related to bitmap 1101, since all features exist in the represented quadrant apart from the feature with id=2.

 

(000,1111), (100,1111), (110,1101), (111,0100), (112,0001),

(113,1000), (114,0100), (120,0100), (130,1010), (131,1000),

(132,0010), (133,0010), (134,1000), (140,0100), (200,1100),

(210,1000), (220,0100), (230,0100), (240,1000), (300,1011),

(310,0010), (320,1000), (330,0010), (340,0001), (400,1000)