R-tree-based data migration and self-tuning strategies in shared-nothing spatial databases

ABSTRACT

In order to provide fast and timely answers to queries in the context of spatial databases and GIS, we present our solution for effective data migration and tuning strategies in shared-nothing parallel spatial databases. Our purpose is to improve the performance of the indexes. Our approach has the following features. First, our scheme is self-tuning, dynamic as well as query-centric and it can adapt to dynamically changing user access patterns. Second, a global distributed R-tree-based indexing method is employed to facilitate effective data migration. Third, unlike traditional partitioning strategies where each processing element (PE) contains data from a single region of space, we allow each PE to store data from multiple and disjoint regions. This minimizes overlap in regions as well as coverage.We implemented the proposed scheme and conducted an extensive performance study on Fujitsu's AP3000 machine with 32 workstations using real datasets. Our experimental results show that our load-balancing strategy can distribute the load effectively across the PEs in the system, thereby reducing response times of incoming queries.

REFERENCES

• 1: Thomas E. Anderson , David E. Culler , David A. Patterson , and the NOW team, A Case for NOW (Networks of Workstations), IEEE Micro, v.15 n.1, p.54-64, February 1995 [doi>10.1109/40.342018]
• 2: 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
• 3: Ibrahim Kamel , Christos Faloutsos, Parallel R-trees, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.195-204, June 02-05, 1992, San Diego, California, United States
• 4: Mong Li Lee , Masaru Kitsuregawa , Beng Chin Ooi , Kian-Lee Tan , Anirban Mondal, Towards self-tuning data placement in parallel database systems, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.225-236, May 15-18, 2000, Dallas, Texas, United States
• 5: A. Mondal, B.C. Ooi, K.L. Tan, M. Kitsuregawa, and M.L. Lee. Query-centric load-balancing using r-trees in shared-nothing spatial databases. Unpublished manuscript, Available from the AUTHORs, 2001.
• 6: Chendong Zou , Betty Salzberg, On-line reorganization of sparsely-populated B+-trees, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.115-124, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Design, Management, Performance, Theory