International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004 
observe a performance improvement of factors between 6 
and 10. 
  
  
100 
D standard version 
B globally re-ordered 
  
query time (in %) 
Qn 
eo 
  
  
  
  
  
  
  
  
  
  
BANG file Buddy tree R*-tree RR*-tree 
  
  
  
Figure 8. Comparison of query time. 
4 CONCLUSIONS 
In this paper, we discussed the usage of spatial access methods, 
which have been originally developed for organizing spatial 
data in spatial database systems and GIS, for the persistent 
storage of point clouds produced by laserscanning. As potential 
data structures, the BANG file and the buddy tree as 
representatives of hash trees and the R*-tree and the RR*-tree 
as R-trees have been selected, implemented and experimentally 
investigated using real laserscanner data. The first results show 
that both types of index structures have the potential for 
organizing point clouds originating from laserscanning. 
Two important tasks for future work can be identified: 1. The 
definition of typical query profiles. Such profiles would allow a 
more detailed investigation and comparison of index structures. 
2. The order preserving properties and spatial hierarchies of 
spatial access methods may be used for analysing the clouds of 
points measured by laserscanners. Especially the extraction and 
approximation of surfaces and edges (e.g. like in (Niemeier & 
Kern, 2001)) should be considered. 
5. REFERENCES 
Beckmann, N., H.-P. Kriegel, R. Schneider & B. Seeger, 1990. 
The R*-tree: An Efficient and Robust Access Method for Points 
and Rectangles. In: Proceedings ACM SIGMOD International 
Conference on Management of Data, Atlantic City, NJ, pp. 
322-331. 
Beckmann, N. & B. Seeger, 2004. Ready for System 
Integration: A Revised R*-tree with Improved Insertion and 
Search Performance. Technical Report of the University of 
Marburg. 
Brinkhoff, T., 2001. Using a Cluster Manager in a Spatial 
Database System. In: Proceedings 9th ACM International 
Symposium on Advances in Geographic Information Systems 
(ACM-GIS), Atlanta, GA, pp. 136-141. 
Brinkhoff, T., H.-P. Kriegel & B. Seeger, 1993. Efficient 
Processing of Spatial Joins Using R-trees. Proceedings ACM 
SIGMOD International Conference on Management of Data, 
Washington, DC, pp. 237-246. 
Freeston, M., 1987. The BANG file: A new kind of grid file. In: 
Proceedings ACM SIGMOD International Conference on 
Management of Data, San Francisco, CA, pp. 260-269. 
Guttman, A., 1984. R-trees: A Dynamic Index Structure for 
Spatial Searching. In: Proceedings  ACM | SIGMOD 
International Conference on Management of Data, Boston, pp. 
47-57. 
Hjaltason, G.R. & H. Samet, 1999. Distance Browsing in 
Spatial Databases. ACM Transactions on Database Systems, 
(24)2, pp. 265-318. 
Hutflesz, A., H.-W. Six & P. Widmayer, 1988. Globally Order 
Preserving Multidimensional Linear Hashing. In: Proceedings 
4th International Conference on Data Engineering, Los 
Angeles, CA, pp. 572-579. 
Niemeier, W. & F. Kern, 2001. Anwendungspotentiale von 
scannenden Messverfahren. In: U. Weferling et al. (eds..): Von 
Handaufmafl bis High Tech, Verlag Philipp von Zabern, pp. 
134-140. 
Nievergelt, J., H. Hinterberger & K.C. Sevcik, 1984. The Grid 
File: An Adaptable, Symmetric Multikey File Structure. ACM 
Transactions on Database Systems, (9)1, pp. 38-71. 
Rigaux, P., M. Scholl & A. Voisard, 2002. Spatial Databases 
With Application To GIS. Morgan Kaufmann Publishers, San 
Francisco. . 
Schwermann, R. & C. Effkemann, 2002. Kombiniertes 
Monoplotting in Laserscanner- und Bilddaten mit PHIDIAS. In: 
Luhmann T. (ed), Photogrammetrie und Laserscanning, 
Anwendung für As-Built-Dokumentation und Facility 
Management. Herbert Wichmann Verlag. pp. 57-70. 
Seeger, B., 1989. Entwurf und Implementierung 
mehrdimensionaler | Zugriffsstrukturen. Dissertation of the 
University of Bremen. 
Seeger, B. & H.-P. Kriegel, 1990. The Buddy Tree: An 
Efficient and Robust Access Method for Spatial Databases. In: 
Proceedings 16th International Conference on Very Large Data 
Bases, Brisbane, Australia, pp. 590-601. 
RI 
The 
GIS. 
softy 
pape 
inclu 
conc 
Buil 
reali 
four 
that 
impl 
Mod 
Buil 
Sinc« 
the | 
the | 
esser 
scien 
hum: 
devel 
abstr 
grapl 
impo 
map 
has 1 
proje 
dime 
infor 
genet 
thus 
certai 
is po: 
mean 
dimei 
softw 
3D at 
The x 
mode 
unnec 
the r 
doma 
descri 
in the