Database Reference
In-Depth Information
G
]
F
[
C
D
E
B
0
1
2
3
4
5
6
7
8
9
10
11
Q1
Figure 6.4
A collection of X-axis parallel line segments.
geometric objects such as points, lines, and polyhedra in computational ge-
ometry, graphics, multimedia, and spatial databases. Other applications that
have seen considerable research in multidimensional data structures include
data mining of scientific databases and geographic information systems. Ob-
jects characterized by
k
-dimensional feature vectors are typically represented
either by their spatial extents in the appropriate metric space or mapped as
points in
k
-dimensional metric space that defines an appropriate metric mea-
sure of relationship between any two points.
15
,
33
,
74
,
79
Depending on the types
of queries on the objects, different data structures that recognize the spatial
extents of the objects can be utilized. A more general approach, however, is
still by mapping of these objects as points, and then partitioning either the
points or the embedding space. To illustrate these general approaches of rep-
resenting objects that can be characterized by feature vectors, we consider the
representation of line segments as in Figure 6.4 that are subjected to stabbing
line and intersection queries.
Two well-known memory resident data structures for representing such
line segments for ecient processing of the stabbing line queries are the
in-
terval tree
and
segment tree
.
74
,
79
They also have corresponding disk based
counterparts.
96
Since each line segment is characterized by a vector
of
its left and right x-values, these can be mapped as points in two-dimensional
space as shown in Figure 6.5. The stabbing line query
Q
1
lx
,
rx
=
4
.
5 translates
rx
12
E
10
G
B
8
D
6
F
A
C
4
2
lx
2
4
6
8
10
12
Figure 6.5
Shaded region representing a stabbing query.
