Top-kqueries on uncertain data

摘要: Uncertain data arises in a number of domains, including integration and sensor networks. Top-k queries that rank results according to some user-defined score are an important tool for exploring large uncertain sets. As several recent papers have observed, the semantics top-k on can be ambiguous due tradeoffs between reporting high-scoring tuples with high probability being resulting set. In this paper, we demonstrate need present distribution vectors allow user choose along score-probability dimensions. One option would display complete all potential tuple vectors, but set is too compute. Instead, propose provide typical effectively sample distribution. We efficient algorithms compute these vectors. also extend scenario ties, which not dealt previous work area. Our includes systematic empirical study both real dataset synthetic datasets.