Object-relational management of complex geographical objects

ABSTRACT

Modern database applications including computer-aided design, multimedia information systems, medical imaging, molecular biology, or geographical information systems impose new requirements on the effective and efficient management of spatial data. Particular problems arise from the need of high resolutions for large spatial objects and from the design goal to use general purpose database management systems in order to guarantee industrial-strength. In the past two decades, various stand-alone spatial index structures have been proposed but their integration into fully-fledged database systems is problematic. Most of these approaches are based on the decomposition of spatial objects leading to replicating index structures. In contrast to common black-and-white decompositions which suffer from the lack of intermediate solutions, we introduce gray intervals which are stored in a spatial index. Additionally, we store the exact information of these gray intervals in a compressed way. These gray intervals are created by using a cost-based decompositioning algorithm which takes the access probability and the decompression cost of them into account. Furthermore, we exploit statistical information of the database objects to find a cost-optimal decomposition of the query objects. The experimental evaluation on the SEQUOIA benchmark test points out that our new concept outperforms the Relational Interval Tree by more than one order of magnitude with respect to overall query response time.

REFERENCES

• 1: G. Slivinskas, Developing a DataBlade for a New Index, Proceedings of the 15th International Conference on Data Engineering, p.314, March 23-26, 1999
• 2: Weidong Chen , Jyh-Herng Chow , You-Chin Fuh , Jean Grandbois , Michelle Jou , Nelson Mendonça Mattos , Brian T. Tran , Yun Wang, High Level Indexing of User-Defined Types, Proceedings of the 25th International Conference on Very Large Data Bases, p.554-564, September 07-10, 1999
• 3: Deutsch P.: RFC1951, DEFLATE Compressed Data Format Specification. http://rfc.net/rfc1951.html, 1996. Int. Conf. on Data Engineering (ICDE), 91--100, 2000.
• 4: Johann-Christoph Freytag , M. Flasza , M. Stillger, Implementing Geospatial Operations in an Object-Relational Database System, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.209, July 26-28, 2000 [doi>10.1109/SSDM.2000.869789]
• 5: Christos Faloutsos , H. v. Jagadish , Yannis Manolopoulos, Analysis of the n-Dimensional Quadtree Decomposition for Arbitrary Hyperrectangles, IEEE Transactions on Knowledge and Data Engineering, v.9 n.3, p.373-383, May 1997 [doi>10.1109/69.599927]
• 6: Volker Gaede, Optimal Redundancy in Spatial Database Systems, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.96-116, August 06-09, 1995
• 7: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 8: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 9: Hirvola H.: HA archiver source code, http://sunsite.unc.edu/pub/Linux/utils/compress/ha0999plinux.tar.gz, 1995.
• 10: IBM Corp.: IBM DB2 Universal Database Application Development Guide, Version 6. Armonk, NY, 1999.
• 11: Informix Software, Inc.: DataBlade Developers Kit User's Guide, Version 3.4. Menlo Park, CA, 1998.
• 12: Hans-Peter Kriegel , Peter Kunath , Martin Pfeifle , Matthias Renz, Acceleration of relational index structures based on statistics, Proceedings of the 15th international conference on Scientific and statistical database management, p.258-261, July 09-11, 2003, Cambridge, MA [doi>10.1109/SSDM.2003.1214992]
• 13: Hans-Peter Kriegel , Martin Pfeifle , Marco Pötke , Thomas Seidl, A Cost Model for Interval Intersection Queries on RI-Trees, Proceedings of the 14th International Conference on Scientific and Statistical Database Management, p.131-141, July 24-26, 2002 [doi>10.1109/SSDM.2002.1029713]
• 14: Hans-Peter Kriegel , Marco Pötke , Thomas Seidl, Managing Intervals Efficiently in Object-Relational Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.407-418, September 10-14, 2000
• 15: Hans-Peter Kriegel , Marco Pötke , Thomas Seidl, Interval Sequences: An Object-Relational Approach to Manage Spatial Data, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.481-501, July 12-15, 2001
• 16: Lempel A., Ziv J.: A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory, Vol. IT-23, No. 3, 337--343, 1977.
• 17: Bongki Moon , H. V. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the clustering properties of Hilbert space-filling curve, University of Maryland at College Park, College Park, MD, 1996
• 18: Yannis Manolopoulos , Yannis Theodoridis , Vassilis J. Tsotras, Advanced database indexing, Kluwer Academic Publishers, Norwell, MA, 2000
• 19: Oracle Corp.: Oracle8i Data Cartridge Developer's Guide, Release 2 (8.1.6). Redwood Shores, CA, 1999.
• 20: J. A. Orenstein, Redundancy in spatial databases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.295-305, June 1989, Portland, Oregon, United States
• 21: Mark A. Roth , Scott J. Van Horn, Database compression, ACM SIGMOD Record, v.22 n.3, p.31-39, Sept. 1993 [doi>10.1145/163090.163096]
• 22: K. V. Ravi Kanth , Siva Ravada , Jayant Sharma , Jay Banerjee, Indexing medium-dimensionality data in Oracle, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.521-522, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 23: Michael Stonebraker , Jim Frew , Kenn Gardels , Jeff Meredith, The SEQUOIA 2000 storage benchmark, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.2-11, May 25-28, 1993, Washington, D.C., United States
• 24: Extensible Indexing: a Framework for Integrating Domain-Specific Indexing Schemes into Oracle8i, Proceedings of the 16th International Conference on Data Engineering, p.91, February 28-March 03, 2000
• 25: Steinmetz R., Nahrstedt K.: Multimedia Fundamentals, Volume 1: Media Coding and Content Processing, Second Edition. Prentice Hall, 110--119, 2002.
• 26: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Management, Performance

Keywords:
data management, object decomposition, object-relational database, spatial