Database Reference
In-Depth Information
100
140
Naive
Det
Sam-Q
Sam
Det-Q
120
80
Precision(Sam)
Precision(Det-Q)
Precision(Sam-Q)
Recall(Sam)
Recall(Det-Q)
Recall(Sam)
100
80
60
60
40
40
20
0
20
10
20
30
40
50
10
20
30
40
50
Variance
Variance
(a) Runtime vs. Variance.
(b) Quality vs. Variance.
Fig. 6.6
Efficiency and approximation quality on data sets under the Gamma distribution.
400
250
Naive
Det
Sam-Q
Sam
Det-Q
Naive
Det
Sam-Q
Sam
Det-Q
350
200
300
250
150
200
100
150
100
50
50
0
0
100
200
300
400
500
200
400
600
800
1000
Number of uncertain streams
Width of window
(a) Number of streams.
(b) Window width.
10
10
Naive
Det
Sam
Sam-Q
Det-Q
Naive
Det
Sam
Sam-Q
Det-Q
8
8
6
6
4
4
2
2
0
0
100
200
300
400
500
200
400
600
800
1000
Number of uncertain streams
Width of window
(c) Number of streams.
(d) Window width.
Fig. 6.7
Scalability.
tion 6.1.2, we also plot the runtime of the method (
Naive
) discussed in Section 6.1.1,
which does not explore the sharing between sliding windows. We evaluate the prob-
abilistic top-
k
queries in 5 consecutive sliding windows. In the first sliding window,
the runtime of the “Naıve” algorithm and the “Det” algorithm is the same. But in
the next 4 sliding windows, the “Naive” algorithm recomputes the top-
k
probabil-
ities without using the results in the previous sliding windows. But the “Det” al-
gorithm adopts the incremental window maintenance techniques, and thus requires
very little computation. Therefore, by average, the runtime of the “Naive” algorithm
is approximately 5 times greater than the runtime of the “Det” algorithm. Among
all methods, the sampling method and the algorithm using quantiles have much less
runtime than the deterministic methods.
