Compression Schemes of High Dimensional Data for MOLAP - Evolving Application Domains of Data Warehousing and Mining - page 69

Figure 3. The CRS compressing scheme for sparse multidimensional array

base of these arrays is 0. Array VL stores the val-
ues of nonzero array elements. Array RO stores
information of nonzero array elements of each row
(columns for CCS). If the number of rows is k for
the array then RO contains k+1 elements. RO[0]
contains 1, RO[1] contains the summation of the
number non zero elements in row 0 of the array
and R[0]. In general, RO[i] contains the number of
nonzero elements in (i-1)th row of the array plus
the contents of RO[i-1]. The number of non zero
array elements in the ith row can be obtained by
subtracting the value of RO[i] from RO[i+1]. Ar-
ray CO stores the column (rows for CCS) indices
of nonzero array elements of each row (columns
for CCS). Figure 3 shows an example of CRS
scheme for a two dimensional array.
In Figure 3, the number of nonzero element
of row 1 can be found by RO[2]-RO[1] = 3. The
column indices of the nonzero array elements of
row 1 are stored in CO[RO[1]-1], CO[RO[1]],
and CO[RO[1]+1] i.e CO[2], CO[3], and CO[4],
since there are 3 nonzero array elements exist in
row 1. Finally the values of the nonzero array

elements of row 1 can be found in VL[2], VL[3],
and VL[4]. Based on this scheme, a sparse array of
dimension 3 can be compressed adding one more
one dimensional integer array JO which stores
the third dimension indices of the nonzero array
elements of each row. For higher dimensional
sparse arrays more one dimensional integer ar-
rays are needed.

ekMr Based compression

A basic array representation scheme named Ex-
tended Karnaugh Map Representation (EKMR)
is proposed by Chun et al; 2002, 2003. In this
scheme, an n-dimensional array is represented
by a set of 2 dimensional arrays.
A more concrete example based on the row-
major data layout is given in Figure 5. In Figure
5(a), a three dimensional array based on the
TMA(3) with a size of 3×4×5 is shown in a 2D
view as three 4×5 two-dimensional arrays. Its
corresponding EKMR(3) with a size of 4×15 is
given in Figure 5(b).

Figure 4. 3-input K-map and its corresponding EKMR(3)