The time consumed in step LR1 is evidently not 
great than LT. Let T, be the time needed for a 
comparison related to precision control. In fact, in 
application, the average number of objects a buck- 
et holds is not great than 10,so,from step LR5,the 
time spent here is not more than 10 T... Let the el- 
ement number of B Set ( Obj,) at. step LRI be m 
initially. the time for this algorithm can be evalu- 
ated as follow; LRT —LT --m * l0* T,—n*PT 
+ 10m * T. If the query precision is at first level, 
then T,,— 0, in this situation, the time complexity 
is only O( n) . Obviously, mxczM xN ,usually , m « 
«n and T, «PT , so the time complexity of this 
algorithm is O (n). 
Space Complexity: From figure 3, we can see that 
Ladex must keep a table with MxN buckets and 
many a lot of lists that vary in length. Hence, 
Ladex structure needs a lot of storage space. How- 
ever ,because only the object identifier and its fea- 
ture information are stored in the structure, the 
storage needed by Ladex is significantly less then 
that occupied by the large scale database itself. In 
a sense, the storage overhead of Ladex can be ig- 
nored in most applications. 
4. 2 Experimental Results 
Ladex is established on Map Databse Management 
System MDB funded by Chinese Electronic Indus- 
try Ministry. In MDB, users can define, store, ac- 
cess and edit conventional data and complex spatial 
data in a uniform format. Conventional data and 
complex spatial data are tightly coupled at physical 
level. We integrate Ladex with B"-tree (An im- 
proved Bt-tree) in MDB, and the goal of quick 
spatial retrieval is achieved successfully. The fol- 
lowing is the performance evaluation approach. 
The resolution of the tested maps is 10240x10240 
in pixel. In fact, in many applications ‚a data space 
with resolution of 10240x10240 in pixel has less 
then 10000 objects. We designed a tool automati- 
cally generate 100 maps with 100 geographic ob- 
jects, 100 maps with 1000, 100 maps with 5000 
and 100 maps with 5000 geographic objects respec- 
tively. Each map has different number of point- 
shaped objects (such as bridges and towers), dif- 
ferent number of line-shaped objects (railways, 
roads and so on) and different number of region- 
shaped objects (such as plant fields and residential 
areas). Every spatial object contain multiple con- 
ventional attributes (such as order number , longi- 
tude latitude , etc. ), the average is about 12. The 
Evaluation indices are as follows (excluding the 
drawing time) : 
(1) Tqi: Average time retrieving all objects in a 
whole map. 
(2) Tqz: Average time retrieving all objects in a 
region with arbitrary shape that takes one quarter 
of a map in size. 
(3) Tq: Average time retrieving one object in a 
map. 
(4) Te: Average time creating Ladex for a whole 
map. 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
(b) Tp: Average time deleting Ladex for a com- 
plete map. 
(6) Tp;: Average time deleting index information 
of all objects in a region with arbitrary shape that 
occupy a quarter of a map in size. 
(7) Tp: Average time deleting one object's index 
information in Ladex. 
Table 1 shows the experimental results at the 2nd 
precision level in a CompaQ 486/33 personal com- 
puter. From the results, we can see that most of 
the performance indices are ideal, especially the 
performance for search operation. This implies 
that Ladex meets the needs of quick interactive 
spatial query. 
5 Advantages of Ladex 
Ladex is a new spatial index mechanism quite dif- 
ferent from R'*-tree. it has the following advan- 
tages: | 
(1) The number of buckets is fixed ,the structure 
is simple and operation algorithms are efficient ; 
(2) Can manage spatial objects with irregular 
shape; 
(3) Support various query types,and the query 
range can be non-rectangle in shape. For instance, 
retrieval of all towns with 15 kilometers along a 
road (see figure 5) and search of all plant areas be- 
tween 200 and 250 meters of altitude (refer to fig- 
ure 6). 
  
100 1000 5000 10000 
Operations | Jndices objects | objects | objects | objects 
  
To: 0. 80 2. 52 5. 40 9.20 
  
Search To2 0. 42 1-21 2. 50 4.70 
  
T os 0. 10 0. 13 0. 14 0. 18 
  
Insertion Tc 5.23 58.67 | 311. 38 | 595. 40 
  
Tpi 0. 46 1. 07 1. 52 1.95 
  
Deletion Tp 2.28 3.435 5. 44 7.29 
  
  
  
  
  
  
  
  
T» ] 0.12 [0:14 5010 10.19 
  
Table 1: Performance Indices (in second) 
     
—— 20m 
  
Figure 5: a line query Figure 6: a region query 
  
  
  
  
  
  
  
  
   
  
  
   
    
   
   
  
   
  
  
  
   
  
   
  
   
   
   
   
   
   
   
   
   
   
  
  
  
  
  
   
   
  
  
   
  
  
  
  
  
   
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
    
   
st