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