Information Technology Reference
In-Depth Information
N
∑
bp
×
mod,
ND
j
j
j
=
1
where each
p
j
and
ND
are relatively prime and
j
= 1 to
N
. To consider an
N
-attribute multiple-ary file, an efficient allocation method proposed by Chen
et al. [11] was defined as follows. Each bucket
B
= [
b
1
,
b
2
, …,
b
N
] is assigned to
a disk unit
=
( )
+
( )
++
( )
(
)
DM
()
Bhbhb
…
h
b
mod
ND
,
11
22
NN
where
h
i
is a hash function. It is shown to be strictly optimal for all possible
partial match queries when the number of disks is greater than 3. Let us
consider an example. Let
F
be a 3-attribute 3-ary file and
ND
= 14. Table 10.3
gives the hash function. The distribution for assigning all buckets to ND
disks is shown in Table 10.4. Having explained the background, we now out-
line the principle of the proposed method.
TaBLe 10.3
Hash Function for a 3-Attribute File Defined
b
0
1
2
h1(b)
0
1
2
h2(b)
0
3
6
h3(b)
0
4
9
Source:
Chen, C. Y., Lin, H. F., Chang, C. C., and
Lee, R. C. T.
IEEE Transactions on Knowledge
and Data Engineering,
9, 148-60, 1997.
TaBLe 10.4
Distribution for Assigning all Buckets to
ND
Disks
Bucket
Assigned Disk
Bucket
Assigned Disk
Bucket
Assigned Disk
[0, 0, 0]
0
[1, 0, 0]
1
[2, 0, 0]
2
[0, 0, 1]
4
[1, 0, 1]
5
[2, 0, 1]
6
[0, 0, 2]
9
[1, 0, 2]
10
[2, 0, 2]
11
[0, 1, 0]
3
[1, 1, 0]
4
[2, 1, 0]
5
[0, 1, 1]
7
[1, 1, 1]
8
[2, 1, 1]
9
[0, 1, 2]
12
[1, 1, 2]
13
[2, 1, 2]
0
[0, 2, 0]
6
[1, 2, 0]
7
[2, 2, 0]
8
[0, 2, 1]
10
[1, 2, 1]
11
[2, 2, 1]
12
[0, 2, 2]
1
[1, 2, 2]
2
[2, 2, 2]
3
