Otoo, Ekow J.
osti: 927033
Seshadri, Sridhar
Programming
99
doi: 10.2172/927033
Chunking of Large Multidimensional Arrays
Processing
Storage Multi-Dimensional Arrays Algorithm Array Chunking
Multi-Dimensional Arrays Algorithm Array Chunking
Metrics
2007-02-28
Rotem, Doron
ark: ark:/67531/metadc896932
rep-no: LBNL--63230
Exact Solutions
Mathematical Models
Data intensive scientific computations as well on-lineanalytical processing applications as are done on very large datasetsthat are modeled as k-dimensional arrays. The storage organization ofsuch arrays on disks is done by partitioning the large global array intofixed size hyper-rectangular sub-arrays called chunks or tiles that formthe units of data transfer between disk and memory. Typical queriesinvolve the retrieval of sub-arrays in a manner that accesses all chunksthat overlap the query results. An important metric of the storageefficiency is the expected number of chunks retrieved over all suchqueries. The question that immediately arises is "what shapes of arraychunks give the minimum expected number of chunks over a query workload?"In this paper we develop two probabilistic mathematical models of theproblem and provide exact solutions using steepest descent and geometricprogramming methods. Experimental results, using synthetic workloads onreal life data sets, show that our chunking is much more efficient thanthe existing approximate solutions.
grantno: DE-AC02-05CH11231
Efficiency
Lawrence Berkeley National Laboratory
United States. Department of Energy. Office of Advanced Scientific Computing Research.