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

Figure 5. (a) A three dimensional TMA (b) The
corresponding EKMR

The idea of the EKMR scheme is based on
the Karnaugh map (K-map). Consider a 3 input
K-map and its corresponding EKMR(3) in Figure
4. Let A[k][i][j] denote a three-dimensional array
based on Traditional Multidimensional Array
TMA(3) with a size of 3×4×5. The corresponding
EKMR(3) of array A[3][4][5] is shown in Figure
4(b). The analogy between the EKMR(3) and the
3-input Karnaugh map is that the index variables
i, j, and k correspond to the variables X, Y, and Z,
respectively. According to the 3-input Karnaugh
map, a three dimensional array based on the
TMA(3) can be presented by a two-dimensional
array based on the EKMR(3). The EKMR(3) is
represented by a two-dimensional array with the
size of 4×(3 × 5). Here, index variable i is used to
indicate the row direction and the index variable
j is used to indicate the column direction. The
index variable i is the same for both EKMR and
TMA representations and the index variable j of
EKMR is a combination of the index variables j
and k of TMA (See Figure 5). The basic difference
between TMA(3) and the EKMR(3) is the place-
ment of elements along the direction indexed by
k. The relative position makes the fundamental
difference when using EKMR as array represen-
tations. The EKMR(4) can be obtained in the
similar way. The EKMR(4) is also represented
in by two dimensional array. The EKMR(n) for n
dimensional array is represented by d n × d n-1 ×…×
d n-5 EKMR(4) and a one dimensional array that
links all the EKMR(4) where d i ( 5£ i n ) is
the length of the corresponding dimension. For
example a 2×3×4×2×3×5 six dimensional array
can be represented by six EKMR(4) each of size
12×10.

dimensional sparse array based on the EKMR
scheme. It can be implemented in two ways:
EKMR Compressed Row Storage (ECRS) and
EKMR Compressed Column Storage (ECCS).
[REMOVED SHAPE FIELD]
The ECRS (or ECCS) scheme compresses all
the nonzero array elements along rows (columns
for ECCS). Array V stores the values of non zero
array elements.Array R stores information of non-
zero array elements of each row. R[i] contains the
number of nonzero elements in (i-1)th row of the
array plus the contents of RO[i-1] and the contents
of R[0] is 1. The number of non zero array elements
in the ith row can be obtained by subtracting the
value of R[i] from R[i+1]. Array CK stores the
column (rows for ECCS) indices of nonzero array
elements of each row (columns for ECCS). Figure
6 shows an example of ECRS scheme for a 4×8
sparse array based on EKMR(3). The compressed
elements of the array can be accessed as described
in CRS scheme in this chapter.
The EKMR(4) can also be compressed using
the one dimensional arrays R, CK, and V as dis-
cussed above. Since EKMR(n) can be represented
by d n × d n-1 × …× d n-5 EKMR(4) ( d i ( 5£ i n ) is
the length of the corresponding dimension), the
higher dimensional (more than 4) data sets can be
generalized as follows: Using the arrays R, CK

Compressing the Sparse Array

The EKMR array can then be compressed using
the CRS or CCS schemes described before in this
chapter. The scheme uses one one-dimensional
floating point array V and two one-dimensional
integer arrays R and CK to compress a multi-