Fully Dynamic Data Structure for Top-k Queries on Uncertain Data

Details Fully Dynamic Data Structure for Top-k Queries on Uncertain Data Fully Dynamic Data Structure for Top-k Queries on Uncertain Data

2010-07-29

arxiv.org/abs/1007.5110v1

Computer Science

Databases

Scientific paper

Top-$k$ queries allow end-users to focus on the most important (top-$k$) answers amongst those which satisfy the query. In traditional databases, a user defined score function assigns a score value to each tuple and a top-$k$ query returns $k$ tuples with the highest score. In uncertain database, top-$k$ answer depends not only on the scores but also on the membership probabilities of tuples. Several top-$k$ definitions covering different aspects of score-probability interplay have been proposed in recent past~\cite{R10,R4,R2,R8}. Most of the existing work in this research field is focused on developing efficient algorithms for answering top-$k$ queries on static uncertain data. Any change (insertion, deletion of a tuple or change in membership probability, score of a tuple) in underlying data forces re-computation of query answers. Such re-computations are not practical considering the dynamic nature of data in many applications. In this paper, we propose a fully dynamic data structure that uses ranking function $PRF^e(\alpha)$ proposed by Li et al.~\cite{R8} under the generally adopted model of $x$-relations~\cite{R11}. $PRF^e$ can effectively approximate various other top-$k$ definitions on uncertain data based on the value of parameter $\alpha$. An $x$-relation consists of a number of $x$-tuples, where $x$-tuple is a set of mutually exclusive tuples (up to a constant number) called alternatives. Each $x$-tuple in a relation randomly instantiates into one tuple from its alternatives. For an uncertain relation with $N$ tuples, our structure can answer top-$k$ queries in $O(k\log N)$ time, handles an update in $O(\log N)$ time and takes $O(N)$ space. Finally, we evaluate practical efficiency of our structure on both synthetic and real data.

Affiliated with

Also associated with

No associations

Rating

Fully Dynamic Data Structure for Top-k Queries on Uncertain Data 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 Fully Dynamic Data Structure for Top-k Queries on Uncertain Data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fully Dynamic Data Structure for Top-k Queries on Uncertain Data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-450582