004 
thod 
The 
|uire 
ding 
tree. 
r the 
the 
ng a 
f an 
. the 
ig of 
erlap 
index 
d the 
[ data 
patial 
sional 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004 
  
points. They support the efficient processing of basic spatial 
queries. Such spatial queries are: 
e spatial selection queries like the point query and the 
window query, 
e the computation of & nearest neighbors (nearest neighbor 
query, see e.g. (Hjaltason & Samet, 1999)), and 
e the spatial join (see e.g. (Brinkhoff et al., 1993)). 
Index structures typically preserve the ordering of data locally. 
In the case of spatial access methods, spatially close objects are 
stored with high probability in the same database block. This is 
essential for processing spatial queries because one query 
accesses typically many spatially neighbored objects and 
because reading a database block from secondary storage is a 
very costly (ie. slow) operation in comparison to other 
computer operations. Storing near objects in the same block 
reduces the number of block accesses and increases the 
probability to find the block in the cache of the database system 
or of the operating system. 
Other techniques try to store blocks, which are described by 
spatially close block regions, physically close on the secondary 
storage (“global order"). The objective is to reduce the cost of 
sets of blocks required by one spatial query. The presented 
spatial access methods do not preserve the global order. This 
would require the usage of additional techniques like the 
approaches proposed by (Hutflesz et al, 1988) or by 
(Brinkhoff, 2001). 
3. USAGE FOR DATA FROM LASERSCANNING 
3.1 Preparation 
For investigating the spatial access methods presented in the 
sections 2.3 and 2.4 for data produced by laserscanning, some 
preparations had been necessary: 
* Modula-2 implementations of the BANG file and the buddy 
tree, both implemented for old Motorola processors, were 
adapted to current Intel processors. A unified API was 
designed and implemented. 
Besides the well-known R*-/ree — a very efficient variant of 
the R-tree (Beckmann et al., 1990) — the new Revised R*- 
tree. (RR*-tree) of Beckmann & Seeger (2004) was 
implemented in Java. 
The two Modula-2 implementations and the Java 
implementation of the R-tree variants were integrated under 
a unified Java user interface. 
e 
  
Figure 7. Illustration of the test data. 
101 
The data structures were tested by a cloud of points that 
originates from the measurement of the façade of a building. 
The data set consists of about 3.66 million points. It is 
illustrated in Figure 7. 
3.2 Investigation 
The following experiments were performed on a Pentium IV- 
PC with 2 GHz and 256 MB main memory. 
The aspect investigated first was the construction of the spatial 
access methods. The points were inserted into the index 
structures in the order they have been measured. The observed 
storage overhead is — independently of the data structure — 
about 68%. The reasons are the storage requirements for the 
directory and — more significant — empty space in the data 
nodes. The empty space is due to fact that all investigated 
spatial access methods are dynamic index structures allowing 
insertions and deletions without worsening their performance. 
The empty space can be reduced by using special bulk-loading 
algorithms. 
The insert throughput is depicted in Figure 8. The performance 
of most the spatial access methods is rather high. One exception 
can be observed: the R*-tree achieved only a third of the 
throughput compared to the other trees. 
  
9000 
8000 
7000 
6000 
5000 
4000 
3000 
2000 
1000 
throughput (points/sec.) 
  
BANG file Buddy tree R*-tree RR*-tree 
  
  
  
Figure 8. Throughput of the insertion of points. 
All spatial access methods showed an excellent performance for 
extracting data points queried by small query cuboids. The 
access to the data does not require a long loading phase. The 
queried points were accessed by few block accesses. 
Many applications require extracting an overview about the 
distribution and/or location of the points. One example is a 
rough visualization which is often sufficient for getting an 
impression of the data. A reasonable approach for such 
requirements is to stop the traversal of the spatial access method 
as soon as the size of a block region falls under a given 
threshold. Such an approach reduces the number of block 
accesses significantly. However, the tests have shown that the 
query time was not reduced significantly. The reason is that the 
investigated spatial access methods preserve only the local 
order. In consequence, block accesses on the secondary storage 
had often led to a seek operation on disk. Therefore, the 
standard access methods were compared to globally re-ordered 
variants. In the globally re-ordered variants, the blocks were 
sequentially arranged on secondary storage according to a depth 
first traversal through the respective tree. Figure 9 shows the 
results of this comparison. The query time of the standard 
version is set to 100% for each spatial access method. We can 
passes soi x 
E as 
temm 
| 
i