Ladex: A New Index Mechanism
in Spatial Object Database System
Xiao Weiqi
Feng Yucai
Department of Computer Science, Huazhong University
of Science & Technology ; Wuhan ,Hubei Province ,People's Republic of China-
Post code; 430074
Fax; 4-86 27 7801738
Commission ll, Intercommission Working Group Il /IV
KEY WORDS Spatial, Object, Database, Spatial Object, Database System ,
Spatial Index.
ABSTRACT
We propose a new index mechanism called Ladex( Lattice index) that supports all kinds of spatial object
retrieval efficiently. Ladex organizes spatial objects with respect to their position and extension in the data
space, it is an innovative spatial index structure that can be utilized in rapidly retrieving objects in a region
with arbitrary shape or on certain location. In a sense, Ladex outperforms R-tree and its variants, it has a
lot of extra advantages of which the other index structures lack. Ladex is a promising index structure for
the future. In this paper, the structure of Ladex is described in detail. The search insertion, deletion and
modification algorithms of Ladex are presented, some implementation issues are also discussed in detail.
Finally, the performance analyses and experimental results of Ladex are provided.
] Introduction
Modern database management systems have been
widely used in many applications, including: Geo-
graphic Information System (GIS) [Monehouse,
1992; Medeiros, 1994 ]; Cartography [ White,
1981 ]; Computer-Aided Design (CAD) [ Ouster-
hout, 1984 ]; City planning [ Monehouse, 1992;
Medeitos,1994]; Real estate managing [Medeiros,
1994], etc. In the aforementioned applications ,
there exist a large quantity of graphic/image enti-
ties,each of them has its own geometric form and
size, that is to say, every one of them has position
and extension in data space. In this paper,we call
these entities spatial objects. A lot of spatial
queries may arise in the above applications. The
best way improving spatial search /retrieval speed
is to construct an efficient index mechanism suit-
able for spatial operations. In the past decade sev-
eral spatial access approaches have been proposed.
A resent survey can be found in[Lu, 1993]. Quad-
tree[Aref,1991], Grid-file[Hinrichs ,1983] and R-
tree [Guttman, 1984] are typical spatial index
structures. The structure of quad-tree is simple, it
lacks flexibility in partition operation on itself
[Aref, 1991 ], however it suits the needs of de-
scribing the single object/s extension in space,
though it does not support the search of objects in
a specific area. The Grid-file structure is originally
established for point query [Hinrichs, 1983]. R-
tree [Guttman, 1984] and its variants (R *-tree
[Faloutsos , 1987 ], R *-tree [Bechmann , 1990] and
930
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
Hilbert R-tree [ Ibrahim, 1994] , etc. ) support
spatial range query, they are based on multidimen-
sional non-linear index techniques. However, R-
tree-based index mechanisms have a lot of draw-
backs. First,as the structure of R-tree-based index
modified dynamically, the performance would de-
crease significantly, and reorganization of the in-
dex structure is indispensable. Second, R-tree-
based index structures do not adapt to irregular
range query. Another disadvantage is that they
support no control of query precision level.
The main idea in this paper is to present an innova-
tive index method called Ladex (stands for lattice
index) , which supports spatial query efficiently,
especially irregular range query at various preci-
sion levels. The remainder of the paper is orga-
nized as follows. Section 2 gives the structure of
Ladex. Section 3 describes fundamental operations
and algorithms for Ladex. Section 4 presents per-
formance analyses and experimental results. Sec-
tion 5 discusses the advantages of Ladex in detail.
Section 6 gives the conclusions and directions for
future research.
2 Structure of Ladex
2. 1 Basic Concepts
Ahead of description of the structure of Ladex,
some prerequisite concepts should be introduced.
* Spatial Index (SpIdx):This is a carefully man-
aged data structure with the position and extension
features of spatial obje ts,and with object identi-
fiers and information used to locate the underlying
of
ob.
de»
rep
spe
the
poi
tyr
Po
the
(st
spe
sea
giv
it
Sp
SU]
sec
ma
eac
res
sio
the
blc
pai
lev
lev
Fig
Su
tor
ref
lat
Li
is |
wh
rel
Doi
gio
tur
bu
fol
(b
but
(2:
set
km
(3
the
Ip,
Th
