Abstract
The transformation technique is one of the earliest approaches for storing a set of bounding boxes of arbitrary geometric objects such that insertion, deletion and proximity queries can be carried out with reasonable performance. The basic idea is to transform the bounding boxes into points in higher dimensional space in order to apply data structures for points which are better understood and easier to handle. Even though the basic concept of the transformation idea at first glance seems fascinatingly simple and elegant, the majority of the data structure community regard this technique as less appropriate because some of its properties are considered harmful.
Main contribution of this paper is to shed some new light on the transformation technique in a sense that some of these properties can be proven to be harmless while the harmful ones can be overcome by new methods. Furthermore, we demonstrate that new kinds of transformations which take other than pure location parameters into account, provide the transformation technique with new quality.
This work has been supported by the European Community, ESPRIT Project No. 6881 (AMUSING).
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
Freeston, M.W.: The BANG file: a new kind of grid file. In: Proc. ACM SIGMOD Int. Conf. on the Management of Data, pp. 260–169, San Francisco 1987.
Günther, O. (ed.): Efficient structures for geometric data management, volume 337 of Lecture Notes in Computer Science. Springer Verlag, Berlin 1988.
Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Proc. ACM SIGMOD Int. Conf. on Management of Data, pp. 47–57, Boston 1984.
Henrich, A., Six, H.-W.: How to split buckets in spatial data structures. In: Gambosi, G., Scholl, M., Six, H.-W. (eds.): Geographic Database Management Systems, pp. 212–244, Capri (Italy), May 1991. Esprit Basic Research Series DG XIII, Springer-Verlag.
Henrich, A., Six, H.-W., Widmayer, P.: The LSD-tree: spatial access to multidimensional point-and non-point objects. In: 15th Int. Conf. on VLDB, pp. 45–53, Amsterdam 1989.
Hutflesz, A., Six, H.-W., Widmayer, P.: The R-file: an efficient access structure for proximity queries. In: Proc. 6th Int. Conf. on Data Engineering, pp. 372–379, Los Angeles 1990.
Kriegel, H.-P., Seeger, B.: Multidimensional order preserving linear hashing with partial expansions. In: Proc. Int. Conf. on Database Theory, pp. 203–220, Rome 1986.
Krishnamurthy, R., Whang, K.-Y.: Multilevel grid files. Research report, IBM Yorktown Heights (1985).
Meyer, B.: Eiffel: The Language. Prentice Hall (1991).
Nievergelt, J., Hinterberger, H., Sevcik, K.C.: The grid file: an adaptable, symmetric multikey file structure. ACM Transactions on Database Systems, 9(1):38–71 (1984).
Ohler, T.: The multi class grid file: an access structure for multi class range queries. In: Proc. 5th Int. Symp. on Spatial Data Handling, pp. 260–271, Charleston 1992.
Pagel, B.-U., Six, H.-W., Toben, H., Widmayer, P.: Towards an analysis of range query performance in spatial data structures. In: Proc. ACM 12th Symposium on Principles of Database Systems (PODS), Washington D.C., May 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pagel, BU., Six, HW., Toben, H. (1993). The transformation technique for spatial objects revisited. In: Abel, D., Chin Ooi, B. (eds) Advances in Spatial Databases. SSD 1993. Lecture Notes in Computer Science, vol 692. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56869-7_5
Download citation
DOI: https://doi.org/10.1007/3-540-56869-7_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56869-8
Online ISBN: 978-3-540-47765-5
eBook Packages: Springer Book Archive