Equivalent Disk Allocations

Periodic Disk Allocations with Best Additive Error and Threshold

   Efficient retrieval of a range query is challening. Multi-disk architectures offer the opportunity to exploit I/O parallelism during retrieval. A common approach for efficient parallel I/O is partitioning the data space into disjoint regions, and allocating the data to multiple disks. When users issue a query, data falling into disjoint partitions is retrieved in parallel from multiple disks. This technique is referred to as declustering and can be summarized as a good way of distributing data to multiple I/O devices.

   Additive error of a range query is the difference between optimal and actual retrieval cost. Additive error of a declustering scheme is the maximum additive error over all the queries. Threshold of a declustering scheme is k if all spatial range queries with at most k buckets can be retrieved optimally. It is desirable to find declustering schemes with low additive error and high threshold. Periodic disk allocations yield good results, however; the number of periodic disk allocations is large and finding the ones with the best additive error and threshold is not easy.

   Here, we share our recent research findings by providing periodic disk allocations giving the best additive error and threshold for 2, 3 and 4 dimensional databases.

Format of the Files

  • The first column is N, the number of disks in the system.
  • The second column is the best additive error or threshold for N number of disks specified in the first column.
  • The third column is the allocation that yields the best additive error or threshold.
  • We use the notation (a1 , a2 , . . . , ad ) for the d-dimensional disk allocation (a1∗i1 + a2∗i2 + . . . + ad∗id mod N).

Results

Dimentionality
 Additive Error
 Threshold
2 Dimensions
 txt
 txt
3 Dimensions
 txt
 txt
4 Dimensions
 txt
 txt

Contact

You can send an e-mail to this address for any questions.