Very large multidimensional arrays are commonly used in data intensive scientific computations as well ason-line analytical processing applications referred to as MOLAP. The storage organization of such arrays on disks is done by partitioning the large global array into fixed size sub-arrays called chunks or tiles that form the units of data transfer between disk and memory. Typical queries involve the retrieval of sub-arrays in a manner that access all chunks that overlap the query results. An important metric of the storage efficiency is the expected number of chunks retrieved over all such queries. The question that immediately arises is "what shapes of array chunks give theminimum expected number of chunks over a query workload?" The problem of optimal chunking was first introduced by Sarawagi and Stonebraker [11] who gave an approximate solution. In this paper we develop exact mathematical models of the problem and provide exact solutions using steepest descent and geometric programming methods. Experimental results, using synthetic and real life workloads, show that our solutions are consistently within than 2.0% of the true number of chunks retrieved for any number of dimensions. In contrast, the approximate solution of [11] can deviate considerably from the true result with increasing number of dimensions and also may lead suboptimal chunk shapes.

In his paper “Should the two-headed disk be greedy? — Yes, it should” Hofri defined a “greedy policy” as follows. Assuming that the range of disk addresses is [0,1], a request at location x is served by the closest arm while the other arm jockeys to a new position, z, where z = (13)x or z = 23 + x3 depending on whether x is larger or smaller than 12. Hofri proved that this policy minimizes the expected seek distance for uniform request probabilities and conjectured that it stochastically dominates every other policy. Stochastic dominance is of practical importance in this context as it guarantees that a policy that optimizes expected seek distance also guarantees optimal seek time. The main result of this paper is a proof of Hofri's conjecture. The paper contains two proofs, the first establishes the conjecture, and the second shows that if the seek distance is stochastically minimized under a repositioning policy, then the policy must be Hofri's greedy policy and the request distribution must be uniform.

Optimal arrangements of cartridges and file partitioning schemes are examined in carousel type mass storage systems using Markov decision theory. It is shown that the Organ-Pipe Arrangement is optimal under different storage configurations for both the anticipatory as well as the non-anticipatory versions of the problem. When requests arrive as per an arbitrary renewal process this arrangement is also shown to minimize the mean queueing delay and the time spent in the system by the requests.