Equivalent Disk Allocations
- 16 June 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 23 (3) , 538-546
Abstract
Declustering techniques reduce query response times through parallel I/O by distributing data among multiple devices. Except for a few cases, it is not possible to find declustering schemes that are optimal for all spatial range queries. As a result of this, most of the research on declustering have focused on finding schemes with low worst case additive error. Number-theoretic declustering techniques provide low additive error and high threshold. In this paper, we investigate equivalent disk allocations and focus on number-theoretic declustering. Most of the number-theoretic disk allocations are equivalent and provide the same additive error and threshold. Investigation of equivalent allocations simplifies schemes to find allocations with desirable properties. By keeping one of the equivalent disk allocations, we can reduce the complexity of searching for good disk allocations under various criteria such as additive error and threshold. Using proposed scheme, we were able to collect the most extensive experimental results on additive error and threshold in 2, 3, and 4 dimensions.Keywords
This publication has 35 references indexed in Scilit:
- Threshold-based declusteringInformation Sciences, 2007
- Iterative-improvement-based declustering heuristics for multi-disk databasesInformation Systems, 2005
- Optimal parallel I/O using replication2003
- Cyclic allocation of two-dimensional data2002
- A Hypergraph Based Approach to Declustering ProblemsDistributed and Parallel Databases, 2001
- (Almost) optimal parallel block access to range queries2000
- LEDA: a platform for combinatorial and geometric computingCommunications of the ACM, 1995
- Latin squares for parallel array accessIEEE Transactions on Parallel and Distributed Systems, 1993
- The R*-tree: an efficient and robust access method for points and rectangles1990
- Optimal file distribution for partial match retrieval1988