Abstract
The design of external index structures for one- and multidimensional extended objects is a long and well studied subject in basic database research. Today, more and more commercial applications rely on spatial datatypes and require a robust and seamless integration of appropriate access methods into reliable database servers. This paper proposes an efficient, dynamic and scalable approach to manage one-dimensional interval sequences within off-the-shelf object-relational database systems. The presented technique perfectly fits to the concept of space-filling curves and, thus, generalizes to spatially extended objects in multidimensional data spaces. Based on the Relational Interval Tree, the method is easily embedded in modern extensible indexing frameworks and significantly outmatches Linear Quadtrees and Relational R-trees with respect to usability, concurrency, and performance. As demonstrated by our experimental evaluation on an Oracle server with real GIS and CAD data, the competing methods are outperformed by factors of up to 4.6 (Linear Quadtree) and 58.3 (Relational R-tree) for query response time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berchtold S., Böhm C, Kriegel H.-R, Michel U.: Implementation of Multidimensional Index Structures for Knowledge Discovery in Relational Databases. Proc. 1st DaWaK, LNCS 1676, 261–270, 1999.
Böhm C, Klump G., Kriegel H.-R: XZ-Ordering: A Space-Filling Curve for Objects with Spatial Extension. Proc. 6th SSD, LNCS 1651, 75–90, 1999.
Berchtold S., Kriegel H.-R, Pötke M.: Database Support for Concurrent Digital Mock-Up. Proc. IFIP Int. Conf. PROLAMAT, 499–509, 1998.
Beckmann N., Kriegel H.-R, Schneider R., Seeger B.: TheR *-tree: An Efficient and Robust Access Method for Points and Rectangles. Proc. ACM SIGMOD, 322–331, 1990.
Bliujute R., Saltenis S., Slivinskas G., Jensen C.S.: Developing a DataBlade for a New Index. Proc. IEEE 15th ICDE, 314–323, 1999.
Chen W., Chow J.-H., Fuh Y.-C, Grandbois J., Jou M., Mattos N., Tran B., Wang Y.: High Level Indexing of User-Defined Types. Proc. 25th VLD), 554–564, 1999.
Edelsbrunner H.: Dynamic Rectangle Intersection Searching Inst. for Information Processing Report 47, Technical University of Graz, Austria, 1980.
Edelsbrunner H., Overmars M. H.: Batched Dynamic Solutions to Decomposable Searching Problems. Journal of Algorithms, 6(4), 515–542, 1985.
Eisenberg A., Melton J.: SQL.-1999, formerly known as SQL3. ACM SIGMOD Record, 28(1): 131–138, 1999.
Egenhofer M., Sharma J.: Topological Relations Between Regions in R 2 and Z2. Proc. 3rd SSD, LNCS 692, 316–336, 1993.
Freytag J.-C, Flasza M., Stillger M.: Implementing Geospatial Operations in an Object-Relational Database System. Proc. 12th SSDBM, 2000.
Faloutsos C, Jagadish H. V., Manolopoulos Y.: Analysis of the n-Dimensional Quadtree Decomposition for Arbitrary Hyperrectangles. IEEE TKDE 9(3): 373–383, 1997.
Faloutsos C, Roseman S.: Fractals for Secondary Key Retrieval. Proc. ACM PODS, 247–252, 1989.
Faloutsos C, Rong Y.: DOT: A Spatial Access Method Using Fractals. Proc. IEEE 7th ICDE, 152–159, 1991.
Gaede V.: Optimal Redundancy in Spatial Database Systems. Proc. 4th SSD, LNCS 951, 96–116, 1995.
Gaede V., Günther O.: Multidimensional Access Methods. ACM Computing Surveys 30(2):170–231, 1998.
Glinther O.: The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases. Proc. IEEE 5th ICDE, 598–605, 1989.
Guttman A.: R-trees: A Dynamic Index Structure for Spatial Searching. Proc. ACM SIGMOD, 47–57, 1984.
Hellerstein J. M., Naughton J. F., Pfeffer A.: Generalized Search Trees for Database Systems. Proc. 21st VLDB, 562–573, 1995.
IBM Corp.: IBM DB2 Spatial Extender Administration Guide and Reference, 2.1.1. Armonk, NY, 1998.
IBM Corp.: IBMDB2 Universal Database Application Development Guide, Vs. 6. Armonk, NY, 1999.
Informix Software, Inc.: DataBlade Developers Kit User’s Guide. Menlo Park, CA, 1998.
Jagadish H. V.: Linear Clustering of Objects with Multiple Attributes. Proc. ACM SIGMOD, 332–342, 1990.
Kornacker M., Banks D.: High-Concurrency Locking in R-Trees. Proc. 21st VLDB, 134–145, 1995.
Kamel I., Faloutsos C: Hubert R-tree: An Improved R-tree Using Fractals. Proc. ACM SIGMOD, 500–509, 1994.
Kriegel H.-P, Horn H., Schiwietz M.: The Performance of Object Decomposition Techniques for Spatial Query Processing. Proc. 2nd SSD, LNCS 525, 257–276, 1991.
Kriegel H.-P, Müller A., Pötke M., Seidl T.: Spatial Data Managementfor Computer Aided Design. Proc. ACM SIGMOD, 2001.
Kornacker M.: High-Performance Extensible Indexing. Proc. 25th VLDB, 699–708, 1999.
Kriegel H.-P, Pötke M., Seidl T.: Managing Intervals Efficiently in Object-Relational Databases. Proc. 26th VLDB, 407–418, 2000.
Moon B., Jagadish H. V, Faloutsos C, Saltz J. H.: Analysis of the Clustering Properties of Hilbert Space-filling Curve. Techn. Report CS-TR-3611, University of Maryland, 1996.
Medeiros C.B., Pires F.: Databases for GIS. ACM SIGMOD Record, 23(1): 107–115, 1994.
McNeely W. A., Puterbaugh K. D., Troy J. J.: Six Degree-of-Freedom Haptic Rendering Using Voxel Sampling. Proc. ACM SIGGRAPH, 401–408, 1999.
Manolopoulos Y, Theodoridis Y, Tsotras V. J.: Advanced Database Indexing. Boston, MA: Kluwer, 2000.
Nascimento M. A., Dunham M. H.: Using Two B+-Trees to Efficiently Process Inclusion Spatial Queries. Proc. 5th Int. Workshop on Advances in Geographic Information Systems (GIS), 5–8, 1997.
Orenstein J. A., Manola F. A.: PROBE Spatial Data Modeling and Query Processing in an Image Database Application. IEEE Trans, on Software Engineering, 14(5): 611–629, 1988.
Oracle Corp.: Oracle8i Data Cartridge Developer’s Guide, 8.1.6. Redwood City, CA, 1999.
Oracle Corp.: Oracle Spatial User’s Guide and Reference, 8.1.6. Redwood City, CA, 1999.
Orenstein J. A.: Redundancy in Spatial Databases. Proc. ACM SIGMOD, 294–305, 1989.
Preparata F. P., Shamos M. I.: Computational Geometry: An Introduction. Springer, 1993.
Ramaswamy S.: Efficient Indexing for Constraint and Temporal Databases. Proc. 6th ICDT, LNCS 1186, 419–413, 1997.
Ravi Kanth K. V., Ravada S., Sharma J., Banerjee J.: Indexing Medium-dimensionality Data in Oracle. Proc. ACM SIGMOD, 521–522, 1999.
Ravada S., Sharma J.: Oracle8i Spatial: Experiences with Extensible Databases. Proc. 6th SSD, LNCS 1651, 355–359, 1999.
Samet H.: Applications of Spatial Data Structures. Addison-Wesley, Reading, Mass, 1990.
Stonebraker M., Frew J., Gardels K., Meredith J.: The SEQUOIA 2000 Storage Benchmark. Proc. ACM SIGMOD, 2–11, 1993.
Schiwietz M., Kriegel H.-P.: Query Processing of Spatial Objects: Complexity versus Redundancy. Proc. 3rd SSD, LNCS 692, 377–396, 1993.
Srinivasan J., Murthy R., Sundara S., Agarwal N., DeFazio S.: Extensible Indexing: A Framework for Integrating Domain-Specific Indexing Schemes into Oracle8i. Proc. IEEE 16th ICDE, 91–100, 2000.
Sellis T., Roussopoulos N., Faloutsos C: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. Proc. 13th VLDB, 507–518, 1987.
Stonebraker M.: Inclusion of New Types in Relational Data Base Systems. Proc. IEEE 2nd ICDE, 262–269, 1986.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kriegel, HP., Pötke, M., Seidl, T. (2001). Interval Sequences: An Object-Relational Approach to Manage Spatial Data. In: Jensen, C.S., Schneider, M., Seeger, B., Tsotras, V.J. (eds) Advances in Spatial and Temporal Databases. SSTD 2001. Lecture Notes in Computer Science, vol 2121. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47724-1_25
Download citation
DOI: https://doi.org/10.1007/3-540-47724-1_25
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42301-0
Online ISBN: 978-3-540-47724-2
eBook Packages: Springer Book Archive