Databases Reference
In-Depth Information
3.3 Proposed Rule Ordering Mechanism
In Sect. 2.3.2 five existing rule ordering strategies were presented. Each is
separated into both rule weighting and rule re-ordering stages. From the pre-
vious section, a list of CARs
R
⊂R
has been generated that only consists
of the “best
k
” rules for each class
c
i
∈
. A rule re-ordering
strategy is then required in the process of rule ordering. The rule re-ordering
mechanism proposed herein contains three steps as follows:
C
, identified in
R
1.
R
is ordered using the well-established CSA ordering strategy.
2. The original
R
,as
R
+
R
is linked at back of
R
.
3. Reassign:
R←
(
R
+
R
).
3.4 Deterministic Selectors
We say that a set
P
hits a set
Q
on element
q
,if
P
∩
Q
=
{
q
}
, and a family
F
of sets hits a set
Q
on element
q
,if
P
∩
Q
=
{
q
}
for at least one
P
∈F
.
De Bonis et al. [19] introduced a definition of a family of subsets of set [
N
]
≡
{
which hits each subset of [
N
] of size at most
k
on at
least
m
distinct elements, where
N,k
and
m
are parameters,
N
0
,
1
,
···
,N
−
2
,N
−
1
}
≥
k
≥
m
≥
1.
They proved the existence of such a family of size
O
((
k
2
/
(
k
m
+ 1)) log
N
).
For convenience of our presentation, we prefer the following slight modification
of this definition, obtained by using the parameter
r
=
k
−
m
instead of the
parameter
m
. For integers
N
and
k
,andarealnumber
r
such that
N
−
≥
k
≥
r
≥
0, a family
F
of subsets of [
N
]isa(
N,k,r
)-selector, if for any subset
Q
⊂
[
N
]ofsizeatmost
k
, the number of all elements
q
of
Q
such that
F
does
not hit
Q
on
q
is at most
r.
That is,
|{
q
∈
Q
:
∀
P
∈F
,P
∩
Q
=
{
q
}}| ≤
r
.
In terms of this definition, De Bonis et al. [19] showed the existence of a
(
N,k,r
)-selector of size
T
(
N,k,r
)=
O
((
k
2
/
(
r
+1)) log
N
)
.
In particular, there
exists a (
N,k,
0)-selector of size
O
(
k
2
log
N
) such a “strong” selector hits each
set
Q
⊂
[
N
] of size at most
k
on each of its elements.
3.5 Proposed Randomised Selectors
A randomised
k
-selector
F
is a family of subsets of set [
N
]
≡{
0
,
1
,...,N
−
2
,
N
−
1
}
which hits each element
q
of the subset
Q
⊂
[
N
] of size at most
k
with a high probability.
Theorem 1.
There exists a randomised k-selector
F
of size O
(
k
)
such that
F
hits each set Q
⊂
[
N
]
of size at most k on each of its elements with a constant
probability p
≥
1
/
8
.
