ina.
spatial object
n in the data
ts in a region
ants, it hasa
structure for
deletion and
sed in detail.
2. ) support
| multidimen-
However, R-
lot of draw-
>-based index
ce would de-
on of the in-
ond, R-tree-
to irregular
is that they
level.
nt an innova-
ds for lattice
y efficiently,
arious preci-
aper is orga-
structure of
al operations
presents per-
results. Sec-
lex in detail.
lirections for
e of Ladex,
introduced.
refully man-
nd extension
)bject identi-
e underlying
objects in database.
* Spatial Search /Query/Retrieval: This is a kind
of operation on spatial database, which return the
objects that satisfy a given query condition QC.
Usually,this operation is supported by Spatial In-
dex ( Spldx) . A Spatial search operation can be
represent as OP (DB,QC,Spldx) , where DB is a
spatial object database.
* Point Search: This type of operation is to search
the objects that locate at or are near to a given
point in a specific data space[Ibrahim , 1994]. This
type of operation is expressed by PointQ (DB,
PointC ,SpIdx).
+ Line Search: This type of operation is to search
the objects that locate at or are near to a given line
(such as straight line, polyline or even curve) in a
specific data space. This can be described as LineQ
(DB, LineC, Spldx).
* Region Search: This type of operation is to
search the objects that fall into or intersect with a
given area in a specific data space[Ibrahim , 1994],
it can be denoted as RegionQ (DB, RegionC,
SpIdx).
2. 2 Description of Ladex
The Ladex index mechanism we present here can
support point search, line search and region
search. The main idea for Ladex is to partition a
map into a lot of small blocks with equivalent size
each small block can be used as a bucket ,and every
object on a certain small block is stored in the cor-
responding bucket. In order to reach higher preci-
sion, each small block could be subdivided furs
ther, this procedure could proceed until the small
block can not be partitioned any more. Different
partition levels correspond to different precision
levels. First level small block corresponds to first
level precision,and second to second, and so on.
Figure 1 is a map of MxN first level small blocks.
Suppose the origin of the coordinates is at the bot-
tom-left corner, a first level small block could be
represented as Block[k,j];0<k<N,0<j<M. A
lattice of MxN first level blocks on a map has
MxN buckets, the i-th bucket is represented as BK
[i],the relationship between a bucket and a block
is described as:
BK [i J«>Block[i div M ,i mod M ]
where 0<i(MxN, ’'+' is a symbol of one to one
relationship. Figure 2 demonstrates the case that a
noint-shaped object ,a line-shaped object and a re-
gion-shaped object take spaces on a lattice struc-
ture. Suppose the set of geographic objects in
bucket BK[i] is S BK[i]( 0<i<MxN). Ladex has
following characteristics :
(1) For any point-shaped object P Obj,,if it is in
bucket BK[i]. then we have P Obj, €S BK[i];
(2) For any line-shaped object L Obj,, suppose the
set of buckets occupied by L Obj, is (ki, kr...
Km) »if V i€ kj ko. - 1km}s then we have L Obj,
€S BK [i];
(3) For any region-shaped object R Obj,, suppose
the set of buckets overlapped by R Obj, is (ri,
fos scola uf V iC (fistosveeo Iu ı then we lave
R Obj, € S BK[i].
The data structure of Ladex is composed of an ar-
931
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
ray of buckets and their corresponding linked
nodes, this has been shown in figure 3.
In general, blocks can be subdivided at different
levels, in our inplementation, Ladex supports
three levels of subdivision which corresponds to
three levels of precision. At the second level,any
first level block Block [i,j] (0<<i<M ,0< j<<N)can
be subdivided into M,xN, sub-blocks: Block, [ is,
jo J (0<{i,<M,;0< j,<<N,), where ‘2’ denotes sec-
ond level subdivision. At the third level, every
second level block
0 M—1
Figure 1;The lattice on a map
N-—À
0 M—1
Figure 2: The position and extension of
objects on a lattice
Block zip » ja | (0<lip,<<M,, 0<{j,<<N,), can be subdi-
vided into M3;xN, points, further partition is for-
bidden. In consideration of efficiency , second and
third level blocks should not be organized as buck-
et structures. The spatial information of an object
in a second or third level block can be expressed by
a feature information field in a node of Ladex
structure. Following is the discussion of represen-
tation of feature information field.
A point-shaped object at the second level must be
on a second level small block which has a relative
block number within its first level block,so the
relative block number can be used as feature infor-
mation; and at the third level, that is the same
case. Therefore, the feature information of a
point-shaped object can be represented as "Second
Jevel block number-- Third level block number".
As for line-shaped objects , the feature information
is more complicated than that of point-shaped ob-
jects. Suppose a line-shaped object pass through m
second level blocks (in a first level block of number
i),the blocks are in the set {L,,Lz». - - ,Lm} repre-
sented by Set?. For V j€Setj?, Setj! represents the
set of third level blocks that the object overlaps in
the j-th second level t ock. Hence, in the i-th
bucket the feature information of a line-shaped ob-
ject Obj, can be expressed by {L,. Set{, L;. Seti;
**,Lm. Seti), the above set is represent as Ob-
ix INFO, including feature information of Obj, in
