Abstract
Concentric Hyperspaces and Disk Allocation for Fast Parallel Range Searching
by: Hakan Ferhatosmanoglu, Divyakanth Agrawal, and Amr El Abbadi
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.
Keywords:
Multi-dimensional databases, data partitioning, parallel I/O,declustering
Date:
January 1999
Document: 1999-03
