Database Reference
In-Depth Information
(0.8,1.0]
b5
(0.8,1.0]
b5
L5:
2 (t4)
L5:
2 (t4)
4 (t1)
4 (t2)
4 (t3)
4 (t1,t2,t3)
U4:
L4:
3 (t4)
U4:
L4:
3 (t4)
2 (t3)
4 (t1)
2 (t4)
4 (t2)
4 (t1)
4 (t3)
4 (t2)
(0.6,0.8]
(0.6,0.8]
b4
b4
2 (t3,t4)
4 (t1,t2)
U3:
L3:
3 (t3,t4)
U3:
L3:
U2:
L2:
U1:
3 (t3)
0 (t1)
3 (t4)
1 (t3)
4 (t1)
1 (t4)
4 (t2)
4 (t2)
(0.4,0.6]
(0.4,0.6]
b3
b3
0 (t1)
1 (t3,t4)
4 (t2)
2 (t3,t4)
U2:
L2:
1 (t1)
1 (t1)
0 (t1)
1 (t1)
2 (t3)
0 (t3)
1 (t3)
2 (t4)
1 (t2)
2 (t2)
4 (t2)
1 (t4)
2 (t4)
(0.2,0.4]
(0.2,0.4]
b2
b2
0 (t1,t3)
1 (t2,t4)
U1:
1 (t1,t3)
2 (t2,t4)
(0,0.2]
b1
(0,0.2]
b1
(a) The
PRist
index.
(b) The compressed
PRist
index.
Fig. 5.3
A
PRist
index for the uncertain tuples in Table 2.2.
, we maintain two lists associated with
the interval. The L-list stores a lower bound for each tuple, and the U-list stores
an upper bound for each tuple. Therefore, for t
4
, lower bound
0
is inserted into the
L-list of
To store the bounds in interval
(
0
,
0
.
2
]
.
The lower and upper bounds of ranks for other prob-intervals can be computed
in the same way. Finally, the entry of t
4
in a
PRist
is shown in Figure 5.2(b).
(
0
,
0
.
2
]
, and upper bound
2
is inserted into the U-list of
(
0
,
0
.
2
]
>
Formally, given a set of uncertain tuples
T
and a
granularity parameter h
0, a
i
−
1
i
h
PRist
index for
T
contains a set of
prob-intervals
{
b
1
,...,
b
h
}
, where
b
i
=(
,
]
h
(1
≤
h
).
Each prob-interval
b
i
(
i
≤
2
≤
i
≤
h
−
1
)
is associated with two lists: a
U
-list and an
L
-list.
An entry in the
U
-list of
b
i
corresponds to a tuple
t
and consists of two items:
tuple id
t
and an
upper rank
of
t
in
b
i
, denoted by
t
.
U
i
, such that one of the following
holds: (1)
Pr
t
.
U
i
i
h
and
Pr
t
.
U
i
−
1
i
h
when
Pr
m
i
(
t
)
>
≤
(
t
)
>
h
; or (2)
t
.
U
i
=
m
when
Pr
m
i
T
has an entry in the
U
-list. All entries in the
U
-list are
sorted in ascending order of the upper ranks.
An entry in the
L
-list of
b
i
corresponds to a tuple
t
and consists of two items:
tuple id
t
and a
lower rank
of
t
in
b
i
, denoted by
t
(
t
)
≤
h
. Each tuple
t
∈
.
L
i
, such that one of the following
holds: (1)
Pr
t
.
L
i
i
−
1
h
and
Pr
t
.
L
i
+
1
i
−
1
h
when
Pr
m
i
−
1
h
(
t
)
≤
(
t
)
>
(
t
)
>
;or(2)
t
.
L
i
=
m
when
Pr
m
i
−
1
h
. Each tuple
t
T
has an entry in the
L
-list. All entries in the
L
-list are sorted in ascending order of the lower ranks.
Prob-interval
b
1
is associated with only a
U
-list but no
L
-list. Prob-interval
b
h
is associated with only an
L
-list but no
U
-list. For any tuple
t
(
t
)
≤
∈
∈
T
,
t
.
L
1
=
0 and
t
m
. The reason is that the lower ranks for entries in
b
1
are always 0 and the
upper ranks for entries in
b
h
are always
m
. Those two lists can be omitted.
.
U
h
=
Example 5.5 (
PRist
). For tuples t
1
,···,
t
4
in Table 2.2, whose top-k probabilities are
plotted in Figure 2.5, the
PRist
index is shown in Figure 5.3(a).
