@conference {13360,
	title = {Consensus answers for queries over probabilistic databases},
	booktitle = {Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems},
	series = {PODS {\textquoteright}09},
	year = {2009},
	month = {2009///},
	pages = {259 - 268},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {We address the problem of finding a "best" deterministic query answer to a query over a probabilistic database. For this purpose, we propose the notion of a consensus world (or a consensus answer) which is a deterministic world (answer) that minimizes the expected distance to the possible worlds (answers). This problem can be seen as a generalization of the well-studied inconsistent information aggregation problems (e.g. rank aggregation) to probabilistic databases. We consider this problem for various types of queries including SPJ queries, Top-k ranking queries, group-by aggregate queries, and clustering. For different distance metrics, we obtain polynomial time optimal or approximation algorithms for computing the consensus answers (or prove NP-hardness). Most of our results are for a general probabilistic database model, called and/xor tree model, which significantly generalizes previous probabilistic database models like x-tuples and block-independent disjoint models, and is of independent interest.},
	keywords = {consensus answers, probabilistic and/xor tree, Probabilistic databases, Query processing, rank aggregation},
	isbn = {978-1-60558-553-6},
	doi = {10.1145/1559795.1559835},
	url = {http://doi.acm.org/10.1145/1559795.1559835},
	author = {Li,Jian and Deshpande, Amol}
}
