Concentric hyperspaces and disk allocation for fast parallel range searching
Authors:
- D. AgrawalDAD. Agrawal
- A. El AbbadiAAA. El Abbadi
- 1 January 1999
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 608-615
Abstract
Data partitioning and declustering have been extensively used in the past to parallelize I/O for range queries. Numerous declustering and disk allocation techniques have been proposed in the literature. However most of these techniques were primarily designed for two-dimensional data and for balanced partitioning of the data space. As databases increasingly integrate multimedia information in the form of image, video, and audio data, it is necessary to extend the declustering techniques for multidimensional data. We first establish that traditional declustering techniques do not scale for high-dimensional data. We then propose several new partitioning schemes based on concentric hyperspaces. We then develop disk allocation methods for each of the proposed schemes. We conclude with an evaluation of range queries based on these schemes and show that partitioning based on concentric hyperspaces has a significant advantage over a balanced partitioning approach for parallel I/O.Keywords
This publication has 7 references indexed in Scilit:
- Concentric hyperspaces and disk allocation for fast parallel range searching1999
- The pyramid-technique1998
- Efficient disk allocation for fast similarity searching1998
- A cost model for nearest neighbor search in high-dimensional data space1997
- Fast parallel similarity search in multimedia databases1997
- Optimal file distribution for partial match retrieval1988
- Disk allocation for Cartesian product files on multiple-disk systemsACM Transactions on Database Systems, 1982