Top- @math queries allow end-users to focus on the most important (top- @math ) 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- @math query returns @math tuples with the highest score. In uncertain database, top- @math answer depends not only on the scores but also on the membership probabilities of tuples. Several top- @math definitions covering different aspects of score-probability interplay have been proposed in recent past R10,R4,R2,R8 . Most of the existing work in this research field is focused on developing efficient algorithms for answering top- @math 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 @math proposed by R8 under the generally adopted model of @math -relations R11 . @math can effectively approximate various other top- @math definitions on uncertain data based on the value of parameter @math . An @math -relation consists of a number of @math -tuples, where @math -tuple is a set of mutually exclusive tuples (up to a constant number) called alternatives. Each @math -tuple in a relation randomly instantiates into one tuple from its alternatives. For an uncertain relation with @math tuples, our structure can answer top- @math queries in @math time, handles an update in @math time and takes @math space. Finally, we evaluate practical efficiency of our structure on both synthetic and real data.
Efforts have been made in recent times to extend the semantics of top- @math '' to uncertain databases. @cite_5 defined the problem of ranking over uncertain databases. They proposed two ranking functions, namely U-Top @math and U- @math Ranks , and proposed algorithms for each of them. Improved algorithms for the same ranking functions were presented later by @cite_15 . @cite_1 proposed another top- @math definition PT- @math () and proposed efficient solutions. @cite_0 defined number of key properties satisfied by top- @math " over deterministic data including exact- @math , containment, unique-rank, value-invariance, and stability . With each of the existing top- @math definition lacking one or more of these properties, Cormode at al. @cite_0 proposed yet another ranking function expected-rank . As the list of top- @math definitions continued to grow, @cite_9 argued that a single specific ranking function may not be appropriate to rank different uncertain databases and empirically illustrated the diverse, conflicting nature of parameterized ranking functions that generalize or can approximate many know ranking functions.
@cite_9 @cite_1 @cite_0 @cite_5 @cite_15
2041763948 2140237757 2138271690 2125402103
Uncertain data is inherent in a few important applications such as environmental surveillance and mobile object tracking. Top-k queries (also known as ranking queries) are often natural and useful in analyzing uncertain data in those applications. In this paper, we study the problem of answering probabilistic threshold top-k queries on uncertain data, which computes uncertain records taking a probability of at least p to be in the top-k list where p is a user specified probability threshold. We present an efficient exact algorithm, a fast sampling algorithm, and a Poisson approximation based algorithm. An empirical study using real and synthetic data sets verifies the effectiveness of probabilistic threshold top-k queries and the efficiency of our methods. When dealing with massive quantities of data, top-k queries are a powerful technique for returning only the k most relevant tuples for inspection, based on a scoring function. The problem of efficiently answering such ranking queries has been studied and analyzed extensively within traditional database settings. The importance of the top-k is perhaps even greater in probabilistic databases, where a relation can encode exponentially many possible worlds. There have been several recent attempts to propose definitions and algorithms for ranking queries over probabilistic data. However, these all lack many of the intuitive properties of a top-k over deterministic data. Specifically, we define a number of fundamental properties, including exact-k, containment, unique-rank, value-invariance, and stability, which are all satisfied by ranking queries on certain data. We argue that all these conditions should also be fulfilled by any reasonable definition for ranking uncertain data. Unfortunately, none of the existing definitions is able to achieve this. To remedy this shortcoming, this work proposes an intuitive new approach of expected rank. This uses the well-founded notion of the expected rank of each tuple across all possible worlds as the basis of the ranking. We are able to prove that, in contrast to all existing approaches, the expected rank satisfies all the required properties for a ranking query. We provide efficient solutions to compute this ranking across the major models of uncertain data, such as attribute-level and tuple-level uncertainty. For an uncertain relation of N tuples, the processing cost is O(N logN)—no worse than simply sorting the relation. In settings where there is a high cost for generating each tuple in turn, we provide pruning techniques based on probabilistic tail bounds that can terminate the search early and guarantee that the top-k has been found. Finally, a comprehensive experimental study confirms the effectiveness of our approach. Top-k processing in uncertain databases is semantically and computationally different from traditional top-k processing. The interplay between score and uncertainty makes traditional techniques inapplicable. We introduce new probabilistic formulations for top-k queries. Our formulations are based on "marriage" of traditional top-k semantics and possible worlds semantics. In the light of these formulations, we construct a framework that encapsulates a state space model and efficient query processing techniques to tackle the challenges of uncertain data settings. We prove that our techniques are optimal in terms of the number of accessed tuples and materialized search states. Our experiments show the efficiency of our techniques under different data distributions with orders of magnitude improvement over naive materialization of possible worlds. This work introduces novel polynomial-time algorithms for processing top-k queries in uncertain databases, under the generally adopted model of x-relations. An x-relation consists of a number of x-tuples, and each x-tuple randomly instantiates into one tuple from one or more alternatives. Our results significantly improve the best known algorithms for top-k query processing in uncertain databases, in terms of both running time and memory usage. Focusing on the single-alternative case, the new algorithms are orders of magnitude faster.