You are using an outdated browser that does not fully support the intranda viewer.
As a result, some pages may not be displayed correctly.

We recommend you use one of the following browsers:

Full text

International cooperation and technology transfer
Mussio, Luigi

h of left of each
have M.LON<
I be the L nodes
insertion follows
‘vhich the points
e points of our
tance, the one
'able 1. In this
field the GPS
an attribute of
is empty: this
Level 2
that this node
de if we must
n between the
Id (2) must be
the tree, the
Ids: 2.LON is
i is connected
t 3, we begin
}.LON<1 .LON,
r ith the L field,
it 4 we have:
le comparison
In this case,
done between
ecord child is
the region is
nt 1 divides it
ide X = 12°20'
like discriminating; point 2 divides the right surface (B) into
two more regions: northern (C) and southern (D) with
respect to cp = 43°60'; point 3 divides the left region into
two subregions northern and southern (F) of (p = 42°50';
finally the point 4 divides the D surface into two parts
corresponding to East (G) and West (H) of X = 16°10'.
When we perform a query on the database, the structure
allows to access only the points of the subregion of
interest, avoiding of take into account the whole interval
((p,Jt), as it happened in the first example (Fig. 2).
This type of structure can be used also for data with more
than two dimensions; in this case the tree is named k-D-
tree, where k is the number of dimensions of the data.
The structure of the record changes and instead of the
LAT and LON fields there is a matrix with k columns (Fig.
Fig. 5- Example of a 2-D-tree space partition
typedef struct
information_type INFO;
real VAL[k];
node L;
node R;
} node;
Fig. 6 - Structure of a k-D-tree record
2.2 Point quadtree
This type of structure may be used for represent the
points only in two spatial dimensions. Each node divides
the region in four quadrants: NW (north - west), NE (north
- east), SW (south - west), SE (south - east). The
structure of a point quadtree record is given in Fig. 7,
where the INFO fields, LAT and LON have the same
meaning we have already seen for the 2-D-tree. The fields
NW, SW, NE and SE point to four children records.
[typedef struct]
} node;
Fig. 7 - Structure of a point-quadtree record.
Given a node N the branch in which we insert a new M
point depends on its coordinates; respectively it is
• NE , if M.LAT> N.LAT and M.LON> N.LON ;
• NW, if M.LAT> N.LAT and M.LON< N.LON;
• SE, if M.LAT< N.LAT and M.LON> N.LON;
• SW, if M.LAT< N.LAT and M.LON< N.LON.
Regarding to the insertion, we have that (considering
Table 1) the record corresponding to point 1 is the root of
the tree (Fig. 8). For the insertion of point 2, we have that
2. LAT<1.LAT and 2.LON>1.LON: the child is connected
with the field SE.. For the insertion of point 3,
3. LAT<1.LAT and 3.LON<1.LON: the child is connected
with the field SW. Finally for the insertion of point 4, as
first step we observe that 4.LAT<1.LAT and
4. LON>1.LON and the corresponding node is SE.
Because this node has already a child (point 2) and we
have that 4.LAT<2.LAT and 4.LON>2.LON, the record
corresponding to point 4 is connected with the SE field of
point 2.
Fig. 8 - Example of point- quadtree structure
Each insertion divides the region into four subregions (Fig.
9): point 1 divides it into four zones (A, B, C, D) using the
longitude 12°20' and the latitude 44°50' like discriminating;
point 2 divides the D region into four more regions (E, F,
G, H); point 3 divides the C region into (I, L, M, N); point 4
divides the H region into the four (O, P, Q, R).
With respect to the 2-D-tree each node divides the current
region in four parts instead of two; this allows to have
trees with less levels and, as a consequence, a faster
access to the data. But, at the same time we have a more
complex structure with four pointers instead of the two we
have in the previous case.