Abstract
Efficient access methods, such as indices, are indispensable for the quick answer to database queries. In spatial databases the selection of an appropriate access method is particularly critical since different types of queries pose distinct requirements and no known data structure outperforms all others for all types of queries. Thus, spatial access methods must be designed for excelling in a particular kind of inquiry while performing reasonably in the other ones. This article describes the Fieldtree, a data structure that provides one of such access methods. The Fieldtree has been designed for GIS and similar applications, where range queries are predominant and spatial nesting and overlaping of objects are common. Besides their hierarchical organization of space, Fieldtrees are characterized by three other features:(i) they subdivide space regularly, (ii) spatial objects are never fragmented, and (iii) semantic information can be used to assign the location of a certain object in the tree. Besides describing the Fieldtree this work presents analytical results on several implementations of those variants, and compares them to published results on the Rtree and the R +tree.
This research was partially funded by grants from NSF under No. IST 86-09123 and Digital Equipment Corporation (Principal Investigator: Andrew U. Frank). The support from NSF for the NCGIA under grant number SES 88-10917 is gratefully acknowledged.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Abel and J. Smith. A Data Structure and Query Algorithm Based on a Linear Key for a Database of Areal Entities. The Australian Computer Journal, 16(4), November 1984.
J. Banerjee et al. Clustering a DAG for CAD Databases. IEEE Transactions on Software Engineering, 14(11), November 1988.
R. Barrera and A. Frank. Analysis and Comparison of the Performance of the Fieldtree. Technical Report, Department of Surveying Engineering, University of Maine, Orono, ME, March 1989.
P. Burt et al. Segmentation and Estimation of Image Region Properties through Cooperative Hierarchical Computation. IEEE Transactions on Systems, Man, and Cybernetics, 11(12), December 1981.
M. Egenhofer. A Spatial SQL Dialect. Technical Report, Department of Surveying Engineering, University of Maine, Orono, ME, September 1988. submitted for publication.
M. Egenhofer and A. Frank. Towards a Spatial Query Language: User Interface Considerations. In: D. DeWitt and F. Bancilhon, editors, 14th International Conference on Very Large Data Bases, Los Angeles, CA, August 1988.
Faloutsos et al. Analysis of Object-Oriented Spatial Access Methods. In: Proceedings of SIGMOD Conference, May 1987.
A. Frank. PANDA—A Pascal Network Database System. In: G.W. Gorsline, editor, Proceedings of the Fifth Symposium on Small Systems, Colorado Springs, CO, 1982.
A. Frank. Problems of Realizing LIS: Storage Methods for Space Related Data: The Field Tree. Technical Report 71, Institut for Geodesy and Photogrammetry, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, 1983.
O. Günther. The Cell Tree: An Object-Oriented Index Structure for Geometric Databases. In: Proceedings IEEE Fifth International Conference on Data Engineering, Los Angeles, CA, February 1989.
A. Guttman. R-Trees: A Dynamic Index Structure for Spatial Searching. In: Proceedings of the Annual Meeting ACM SIGMOD, Boston, MA, 1984.
K. Hinrichs. The GRid File System: Implementation and Case Studies of Applications (in German). PhD thesis, Swiss Federal Institute of Technology, Zurich, Switzerland, 1985.
M. Kitsuregawa et al. Join Strategies on KD-tree Indexed Relations. In: Proceedings Fifth International Conference on Data Engineering, Los Angeles, CA, February 1989.
J. Nievergelt et al. The GRID FILE: An Adaptable, Symmetric Multi-Key File Structure. ACM Transactions on Database Systems, 9(1), March 1984.
J. Orenstein. Spatial Query Processing in an Object-Oriented Database System. ACM-SIGMOD, International Conference on Management of Data, 15(2), 1986.
J. Orenstein. Redundancy in Spatial Databases. ACM-SIGMOD, International Conference on Management of Data, 1989.
H. Samet. The Quadtree and Related Hierarchical Data Structures. ACM Computing Surveys, 16(2), June 1984.
T. Sellis et al. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In: P. Stocker and W. Kent, editors, 13th VLDB conference, Brighton, England, September 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Frank, A.U., Barrera, R. (1990). The fieldtree: A data structure for geographic information systems. In: Buchmann, A.P., Günther, O., Smith, T.R., Wang, YF. (eds) Design and Implementation of Large Spatial Databases. SSD 1989. Lecture Notes in Computer Science, vol 409. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52208-5_20
Download citation
DOI: https://doi.org/10.1007/3-540-52208-5_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-52208-9
Online ISBN: 978-3-540-46924-7
eBook Packages: Springer Book Archive