Database Reference
In-Depth Information
8
d
0.4
7
e
6
0.2
b
a
5
4
0
c
def
cb
3
-0.2
2
f
T(o,black)=L(o|black)
T(o,white)=L(o|white)
DT(o,white,black)
1
-0.4
0
0
1
2
3
4
5
6
7
8
X
Location of data point
(a) A set of points.
(b) Typicality.
Fig. 2.1
The simple typicality and discriminative typicality curves of a set of points.
the probability density around each observed sample. More details will be discussed
in Chapter 4.
Hereafter, unless specified otherwise, the simple typicality measure refers to the
estimator
T
A
i
1
,···,
A
i
l
(
o
,
O
)
. Moreover, for the sake of simplicity, when
A
i
1
,···,
A
i
l
are
clear from context,
T
A
i
1
,···,
A
i
l
(
,
)
and
L
A
i
1
,···,
A
i
l
(
|
)
(
,
)
o
O
o
O
are abbreviated to
T
o
O
and
L
, respectively.
Given an uncertain object
O
on attributes
A
i
1
,···,
(
o
|
O
)
A
i
l
of interest, a predicate
P
and a positive integer
k
,a
top-
k
simple typicality query
returns, from the set of
instances in
O
satisfying predicate
P
, the
k
instances having the largest simple typi-
cality values that are computed on attributes
A
i
1
,...,
A
i
l
.
Example 2.5 (Top-k simple typicality queries). Consider the set of points belong to
an uncertain object in Figure 2.1(a). A top-
3
simple typicality query on attribute X
with predicate COLOR
white returns the
3
white points having the largest simple
typicality values computed on attribute X.
Figure 2.1(b) projects the points in T to attribute X. The likelihood function of
the white points and that of the black points on attribute X are labeled as L
=
(
|
)
o
white
and L
in the figure, respectively, while we will discuss how to compute the
likelihood values in Chapter 4. Points a, b and c have the highest likelihood values
among all white points, and thus should be returned as the answer to the query.
(
o
|
black
)
2.2.1.2 Discriminative Typicality
Given two uncertain objects O and S, which instance is the most typical in O but not
in S?
We use the discriminative typicality to answer such a question. By intuition,
an instance
o
O
is typical and discriminative in
O
if the difference between its
typicality in
O
and that in
S
is large.
∈
Definition 2.6 (Discriminative typicality).
Given two uncertain objects
O
and
S
on attributes
A
1
,···,
be the
n
-dimensional
random vectors generating the instances in
O
and
S
, respectively, the
discriminative
A
n
(
O
is the
target object
), let
U
and
V
