Database Reference
In-Depth Information
Algorithm 7.2
Answering PT-
k
queries on probabilistic linkages.
Input:
A PME-graph
G
containing components
G
1
,···,
G
m
andaPT-
k
query
Q
Output:
Answer to
Q
Method:
1: sort all vertices satisfying the query predicate in the ranking order;
{
*let
S
=
v
1
,···,
v
n
be the vertices in the ranking order
}
2:
for
i
=
2to
n
do
3:
for
j
=
1to
m
do
4:
if
G
j
does not contain
v
i
−
1
or
v
i
then
5:
f
j
(
x
)=
Pr
(
G
j
(
v
i
−
1
)
,
x
)
;
6:
else if
G
j
contains
v
i
−
1
then
7:
apply Equation 7.6 to compute
f
j
(
x
)=
Pr
(
G
j
(
v
i
−
1
)
,
x
)
;
8:
else
9:
apply Theorem 7.4 to compute
f
j
(
x
)=
Pr
(
G
j
(
v
i
−
1
)
,
x
|
v
i
)
;
10:
end if
11:
Pr
(
G
(
v
)
,
x
|
v
i
)=
f
(
x
)=
f
1
(
x
)
∗···∗
f
m
(
x
)
;
k
−
1
Pr
k
12:
(
v
i
)=
Pr
(
v
i
) ∑
0
Pr
(
G
(
v
)
,
x
|
v
i
)
;
i
=
13:
end for
14:
end for
Case 3: only
v
i
+
1
is in
G
j
.
G
2
in Figure 7.7 illustrates this case. When scanning
v
i
, we computed the sub-
graph probability for
Pr
(
G
j
(
v
i
)
,
x
)
. Then, when processing
v
i
+
1
, we have to com-
pute
Pr
(
G
j
(
v
i
+
1
)
,
x
|
v
i
+
1
)
. Again, according to Corollary 7.3,
G
j
(
v
i
)
is a subgraph of
G
j
(
v
i
+
1
)
. Thus,
Pr
(
G
j
(
v
i
+
1
)
,
x
|
v
i
+
1
)
can be computed based on
Pr
(
G
j
(
v
i
)
,
x
)
using
Theorem 7.4.
Case 4: both
v
i
and
v
i
+
1
are in
G
j
.
The situation is similar to Case 3. Subgraph probability
Pr
(
G
j
(
v
i
+
1
)
,
x
|
v
i
+
1
)
can be
computed based on
Pr
using Theorem 7.4.
Generally, we scan each vertex
v
i
in the ranked list and compute the subgraph
probabilities of
G
(
G
j
(
v
i
)
,
x
|
v
i
)
in each component
G
j
. If a component does not contain
v
i
or
v
i
−
1
, then the subgraph probabilities of
v
i
and
v
i
−
1
are the same. Otherwise, we apply
Equation 7.7 or Theorem 7.4 to compute the subgraph probabilities, which avoids
computing subgraph probabilities from scratch. Algorithm 7.2 shows the complete
routine.
(
v
i
)
7.5.3 Pruning Techniques
From Corollary 7.3, for any two vertices
v
i
f
v
j
, the dominant subgraph
G
(
v
i
)
is a
subgraph of
G
(
v
j
)
. Therefore, we have
