Database Reference
In-Depth Information
Evaluating probabilistic ranking queries
Problem transformation
Computing the number of successes in Poisson Trials
Exact statistical solution
Approximate statistical solution
Poisson binomial recurrence
A sampling algorithm
A Poisson approximation based algorithm
1) cannot handle generation rules
2) inefficient
Handling rules: rule−tuple compression
Improve efficiency: reordering and pruning techniques
An efficient and scalable exact algorithm
Fig. 5.14
The query evaluation algorithms for probabilistic ranking queries.
index on-the-fly to answer a query, in most cases it is still substantially faster than
the query evaluation methods without indices.
Last, we test the scalability of the
PRist+
construction method and the query
evaluation methods with respect to the number of tuples and the number of tuples in
rules, respectively. Figure 5.13 shows that the methods are scalable and much more
efficient than query answering without index.
5.7 Summary
In this chapter, we developed three methods, as shown in Figure 5.14, for answering
probabilistic ranking queries defined in Section 2.2.2.
•
We adopted the Poisson binomial recurrence [103] to compute the rank-
k
prob-
abilities for independent tuples. Since the Poisson binomial recurrence cannot
handle the tuples involved in generation rules, we developed a rule-tuple com-
pression technique to transform the tuples in generation rules into a set of in-
dependent rule-tuples, so that the Poisson binomial recurrence can be applied.
Moreover, to improve the efficiency, we devised two reordering techniques that
reuse the computation. Last, we proposed several effective pruning techniques
that reduce the number of tuples that we need to consider.
•
We developed a sampling method to approximate the rank-
k
probabilities of tu-
ples and compute the approximate answers to probabilistic ranking queries.
