Database Reference
In-Depth Information
7.5 Exact Query Answering Algorithms
In this section, we first develop an exact query evaluation algorithm based on the
subgraph probability calculation technique discussed in Section 7.3. Then, we dis-
cuss how to improve the efficiency of the algorithm.
7.5.1 An Exact Algorithm
With the subgraph probability computation technique discussed in Section 7.3, we
can answer a probabilistic threshold top-
k
query on a set of probabilistic linkages as
follows.
First, we build the corresponding PME-graph
G
and sort all vertices satisfying
the query predicate
P
in the ranking order according to the scoring function
f
. Let
S
=
v
1
,···,
v
n
be the list of vertices in the ranking order. We then scan the vertices
one by one.
For each vertex
v
i
, we derive the dominant subgraph
G
(
v
i
)
of
v
i
. The subgraph
probability of
G
can be computed using the method discussed in Section 7.4.
The top-
k
probability of
v
i
can be calculated using Equation 7.6.
(
v
i
)
7.5.2 Reusing Intermediate Results
Can we reuse the intermediate results to reduce the computational cost? Once the
subgraph probability of a vertex is calculated, the intermediate results can be reused
to compute the subgraph probability of the next vertex in the ranked list.
Example 7.6 (Reusing intermediate results). Consider the PME-graph G in Fig-
ure 7.7(a) that contains three connected components G
1
,G
2
and G
3
. Suppose the
list of vertices v
1
v
10
are sorted in the ranking order.
To compute the top-k probability of v
5
, we first construct the dominant subgraph
,···,
G
(
v
5
)
, which contains the grey vertices in Figure 7.7(a).
To compute the top-k probability of v
6
, we construct the dominant subgraph
G
(
v
6
)
as shown in Figure 7.7(b).
Interestingly, by comparing G
, we can find the following.
First, in component G
1
, the dominant graph of v
5
and v
6
are the same. Therefore,
(
v
5
)
and G
(
v
6
)
Pr
(
.
Moreover, in component G
2
, the subgraph probability of G
2
(
G
1
(
v
6
)
,
x
)=
Pr
(
G
1
(
v
5
)
,
x
)
v
5
)
is Pr
(
G
2
(
v
5
)
,
x
)=
Pr
(
{
v
2
},
x
)
. Since v
6
∈
G
2
, we have to compute the conditional subgraph probability
of G
2
(
v
6
)
,Pr
(
G
2
(
v
6
)
,
x
|
v
6
)=
Pr
(
{
v
2
},
x
|
v
6
)
. Since Pr
(
{
v
2
},
x
)
has been computed
when scanning v
5
, we can compute Pr
(
{
v
2
},
x
|
v
6
)
based on Pr
(
{
v
2
},
x
)
using The-
orem 7.4.
