Report ID
1999-03
Report Authors
Hakan Ferhatosmanoglu, Divyakanth Agrawal, and Amr El Abbadi
Report Date
Abstract
Data partitioning and declustering have been extensively used in the past toparallelize I/O for range queries. Numerous declustering and disk allocationtechniques have been proposed in the literature. However, most of thesetechniques were primarily designed for two-dimensional data and for balancedpartitioning of the data space. As databases increasingly integrate multimediainformation in the form of image, video, and audio data, it is necessary toextend the declustering techniques for multidimensional data. In this paper,we first establish that traditional declustering techniques do not scale forhigh-dimensional data. We then propose several new partitioning schemes basedon concentric hyperspaces. We then develop disk allocation methods for each ofthe proposed schemes. We conclude with an evaluation of range queries based onthese schemes and show that partitioning based on concentric hyperspaces has asignificant advantage over balanced partitioning approach for parallel I/O.
Document
1999-03.ps218.3 KB