Fast Probabilistic Ranking under x-Relation Model

Details Fast Probabilistic Ranking under x-Relation Model Fast Probabilistic Ranking under x-Relation Model

2009-06-26

arxiv.org/abs/0906.4927v1

Computer Science

Databases

Scientific paper

The probabilistic top-k queries based on the interplay of score and probability, under the possible worlds semantic, become an important research issue that considers both score and uncertainty on the same basis. In the literature, many different probabilistic top-k queries are proposed. Almost all of them need to compute the probability of a tuple t_i to be ranked at the j-th position across the entire set of possible worlds. The cost of such computing is the dominant cost and is known as O(kn^2), where n is the size of dataset. In this paper, we propose a new novel algorithm that computes such probability in O(kn).

Affiliated with

Also associated with

No associations

Rating

Fast Probabilistic Ranking under x-Relation Model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Probabilistic Ranking under x-Relation Model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Probabilistic Ranking under x-Relation Model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-670983