------------------------------------------------------------------------------ ****************************************************************************** ------------------------------------------------------------------------------ B O S T O N U N I V E R S I T Y Computer Science Department C O L L O Q U I U M Wednesday, April 9, 1997 3:00 pm (Coffee served at 2:30 pm, Room MCS 137) Room MCS 135 ------------------------------------------------------------------------------ ****************************************************************************** ------------------------------------------------------------------------------ Data Placement for High Performance Spatial Databases Bongki Moon Department of Computer Science University of Maryland at College Park http://www.cs.umd.edu/users/bkmoon Data clustering and declustering play a role in achieving high performance for large-scale scientific and spatio-temporal databases. The main challenge for efficiently handling such databases is to minimize response time for multidimensional range queries. For clustering, we have focused on the Hilbert space-filling curve, which provides a locality-preserving mapping from a multidimensional space into a linear space. We present the clustering property of the Hilbert curve in simple closed-form formulas. The second part of this research deals with the problem of declustering Cartesian product files across multiple disks. Using the response time of hypercubic range queries as a metric, we have derived formulas which state the limited scalability and the optimal conditions of two popular declustering methods. Lastly, we present a new data placement algorithm based on binary search trees and the Hilbert curve. This algorithm aims at spatial datasets that are incremental and non-uniformly distributed. We have compared it with graph-theoretic approaches, and evaluated its effectiveness with real-world datasets such as AVHRR satellite imagery on a shared-nothing architecture. Host: Prof. Steve Homer ------------------------------------------------------------------------------ For colloquium info, including directions, see http://www.cs.bu.edu/colloquium For more information contact Prof. David Yates ------------------------------------------------------------------------------