Patent Document ID: 20090006049
Application ID: 12209071
Patent Flag: 0

Claim One:
1. A computer program product having a plurality of executable instruction codes, for determining an expansion of storage resulting from a candidate clustering scheme for data, the steps performed by the executable instruction codes comprising: modeling an anticipated space waste to result from two or more multidimensional candidate clustering schemes, each multidimensional candidate clustering scheme defined by two or more clustering keys and configured to group data into a plurality of logical cells such that logically related data is stored in close proximity on a physical storage medium to reduce data access times, each unique logical cell defined by a unique combination of two or more clustering key values, each of the two or more clustering keys defining a dimension in the multidimensional candidate clustering scheme, each unique logical cell corresponding to one or more physical storage blocks in the physical storage medium, wherein the physical storage blocks have a block size, wherein each unique cell comprises a partially filled storage block from the data, wherein defining the anticipated space waste comprises calculating the anticipated space waste as a proportion of the block size, wherein modeling the anticipated space waste comprises: determining a cardinality of unique cells to be created in accordance with the multidimensional candidate clustering scheme; defining the anticipated space waste in proportion to the cardinality of unique cells; wherein the anticipated space waste is determined in accordance with a following equation: 
 W=n cell *P % *β, where W is the anticipated space waste (W), n cell is a cardinality of unique clusters, P % is an estimated proportion of each partially filled block that is waste space, and β is the block size, and a second set of instruction codes for defining the expansion of data storage in proportion to the anticipated space waste, and defining expansion of data storage in proportion to the anticipated space waste for each candidate clustering scheme; and selecting one or more candidate clustering schemes that result in a least amount of expansion of storage.