2010/07/29 by Patil, Manish, Shah, Rahul, Thankachan, Sharma V.
#Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1007.5110
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~\citeR10,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 PRFe(α) proposed by Li et al.~\citeR8 under the generally adopted model of x-relations~\citeR11. PRFe can effectively approximate various other top-k definitions on uncertain data based on the value of parameter α. 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(klog 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.