Database Reference
In-Depth Information
and V each EKMR(4) is compressed then a pointer
array with size d n × d n-1 × …× d n-5 is used to link
the arrays R, CK, and V in each EKMR(4).
In the following example, L represents the
uncompressed form of a database, where 0's are
the constant to be suppressed and the V's are the
unsuppressed values. H represents the header
database/file which contains the number of data
or constants where odd position represents the
data and even position represents constants. The
physical, compressed form of the data is repre-
sented by P.
L:V 1 V2 0 0 0 0 0 0 0 0 0 V 3 V 4 V 5 V 6 V 7 0 0
V 8 V 9 V 10 0 0 0
H: 2, 9, 7, 11, 10, 14
P: V 1 V 2 V 3 V 4 V 5 V 6 V 7 V 8 V 9 V 1O
header compression
The header compression method (Eggers &
Shohani, 1980) is used to suppress sequences
of missing data codes, called constants , in lin-
earized arrays by counts. This method makes
use of a header that is a vector of counts. The
odd-positioned counts are for the unsuppressed
sequences, and the even positioned counts are for
suppressed sequences. Each count contains the
cumulative number of values of one type at the
point at which a series of that type switches to a
series of the other. The counts reflect accumulation
from the beginning of the linearized array to the
switch points. In addition to the header file, the
output of the compression method consists of a
file of compressed data items, called the physical
file . The original linearized array, which is not
stored, is called the logical file .
BAP compression
The BAP compression method (Li et al; 1987)
consists of three parts: Bit Vector (BV), Address
Vector (AV), Physical Vector (PV) and therefore
called BAP compression method.
Let DB={x 1 ,x 2 ,...,x n ) be a logical database and
c be the constants. The physical vector PV is the
vector of non-constants in DB, that is,
Figure 6. The ECRS compressing scheme for a three dimensional sparse array based on EKMR(3)
0 5 1 0 0 0 3 0
2 0 0 9 0 5 0 6
4 0 3 0 0 7 0 2
3 0 0 2 0 0 0 1
(a) The original EKMR
1
R
4
8
12
15
0 1 2 3 4 5 6 7 8 9 10 11 12 13
CK
1
2
6
0
3
5
6
0
2
5
7
0
3
7
V
5
1
3
2
9
5
6
4
3
7
2
3
2
1
(b) The compressed EKMR
Search WWH ::




Custom Search