Consensus answers for queries over probabilistic databases

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.

REFERENCES

• 1: Nir Ailon, Aggregation of partial rankings, p-ratings and top-m lists, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.415-424, January 07-09, 2007, New Orleans, Louisiana
• 2: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: Ranking and clustering, Journal of the ACM (JACM), v.55 n.5, p.1-27, October 2008 [doi>10.1145/1411509.1411513]
• 3: Periklis Andritsos , Ariel Fuxman , Renee J. Miller, Clean Answers over Dirty Databases: A Probabilistic Approach, Proceedings of the 22nd International Conference on Data Engineering, p.30, April 03-07, 2006 [doi>10.1109/ICDE.2006.35]
• 4: Lyublena Antova , Christoph Koch , Dan Olteanu, From complete to incomplete information and back, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247559]
• 5: D. Barbará , H. Garcia-Molina , D. Porter, The Management of Probabilistic Data, IEEE Transactions on Knowledge and Data Engineering, v.4 n.5, p.487-502, October 1992 [doi>10.1109/69.166990]
• 6: George Beskales , Mohamed A. Soliman , Ihab F. IIyas, Efficient search for the top-k probable nearest neighbors in uncertain databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453895]
• 7: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluating probabilistic queries over imprecise data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872823]
• 8: Graham Cormode , Feifei Li , Ke Yi, Semantics of Ranking Queries for Probabilistic Data and Expected Ranks, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.305-316, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.75]
• 9: Graham Cormode , Andrew McGregor, Approximation algorithms for clustering uncertain data, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376944]
• 10: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, Proceedings of the Thirtieth international conference on Very large data bases, p.864-875, August 31-September 03, 2004, Toronto, Canada
• 11: Nilesh Dalvi , Dan Suciu, Management of probabilistic data: foundations and challenges, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-12, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265531]
• 12: Amol Deshpande , Carlos Guestrin , Samuel R. Madden , Joseph M. Hellerstein , Wei Hong, Model-driven data acquisition in sensor networks, Proceedings of the Thirtieth international conference on Very large data bases, p.588-599, August 31-September 03, 2004, Toronto, Canada
• 13: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 14: C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation revistied. In Manuscript, 2001.
• 15: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing Top k Lists, SIAM Journal on Discrete Mathematics, v.17 n.1, p.134-160, January 2004 [doi>10.1137/S0895480102412856]
• 16: Norbert Fuhr , Thomas Rölleke, A probabilistic relational algebra for the integration of information retrieval and database systems, ACM Transactions on Information Systems (TOIS), v.15 n.1, p.32-66, Jan. 1997 [doi>10.1145/239041.239045]
• 17: Minos Garofalakis and Dan Suciu, editors. IEEE Data Engineering Bulletin Special Issue on Probabilistic Data Management. March 2006.
• 18: Todd J. Green , Grigoris Karvounarakis , Val Tannen, Provenance semirings, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265535]
• 19: Todd Green and Val Tannen. Models for incomplete and probabilistic information. In EDBT, 2006.
• 20: Rahul Gupta , Sunita Sarawagi, Creating probabilistic databases from information extraction models, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 21: Ming Hua , Jian Pei , Wenjie Zhang , Xuemin Lin, Efficiently Answering Probabilistic Threshold Top-k Queries on Uncertain Data, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1403-1405, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497570]
• 22: Ming Hua , Jian Pei , Wenjie Zhang , Xuemin Lin, Ranking queries on uncertain data: a probabilistic threshold approach, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376685]
• 23: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 24: T. S. Jayram , Andrew McGregor , S. Muthukrishnan , Erik Vee, Estimating statistical aggregates on probabilistic data streams, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265565]
• 25: J.C. Borda. Mémoire sur les élections au scrutin. Histoire de l'Acad'emie Royale des Sciences, 1781.
• 26: J.G. Kemeny. Mathematics without numbers. Daedalus, 88:571--591, 1959.
• 27: J. Hodge and R.E. Klima. The mathematics of voting and elections: a hands-on approach. AMS, 2000.
• 28: Laks V. S. Lakshmanan , Nicola Leone , Robert Ross , V. S. Subrahmanian, ProbView: a flexible probabilistic database system, ACM Transactions on Database Systems (TODS), v.22 n.3, p.419-469, Sept. 1997 [doi>10.1145/261124.261131]
• 29: Jian Li, Barna Saha, and Amol Deshpande. Ranking and clustering in probabilistic databases. http://www.cs.umd.edu/~lijian/paper/clusterrank_tr.pdf, 2008. Unpublished manuscript.
• 30: Silvio Micali , Vijay V. Vazirani, An O(v|v| c |E|) algoithm for finding maximum matching in general graphs, Proceedings of the 21st Annual Symposium on Foundations of Computer Science, p.17-27, October 13-15, 1980
• 31: M.J. Condorcet. Éssai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. 1785.
• 32: Christopher Re, Nilesh Dalvi, and Dan Suciu. Efficient top-k query evaluation on probabilistic data. In ICDE, 2007.
• 33: Christopher Ré , Dan Suciu, Materialized views in probabilistic databases: for information exchange and query optimization, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 34: Anish Das Sarma , Omar Benjelloun , Alon Halevy , Jennifer Widom, Working Models for Uncertain Data, Proceedings of the 22nd International Conference on Data Engineering, p.7, April 03-07, 2006 [doi>10.1109/ICDE.2006.174]
• 35: Prithviraj Sen and Amol Deshpande. Representing and querying correlated tuples in probabilistic databases. In ICDE, 2007.
• 36: Prithviraj Sen , Amol Deshpande , Lise Getoor, Exploiting shared correlations in probabilistic databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453944]
• 37: M. Soliman, I. Ilyas, and K. C. Chang. Top-k query processing in uncertain databases. In ICDE, 2007.
• 38: Christopher Réand Dan Suciu. Efficient evaluation of having queries on a probabilistic database. In DBPL, 2007.
• 39: Daisy Zhe Wang, Eirinaios Michelakis, Minos Garofalakis, and Joseph M. Hellerstein. BayesStore: Managing large, uncertain data repositories with probabilistic graphical models. In VLDB, Auckland, New Zealand, 2008.
• 40: Ke Yi , Feifei Li , George Kollios , Divesh Srivastava, Efficient Processing of Top-k Queries in Uncertain Databases, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1406-1408, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497571]
• 41: Y. Wakabayashi. The complexity of computing medians of relations. In Resenhas, volume 3(3), pages 323--349, 1998.
• 42: Xi Zhang and Jan Chomicki. On the semantics and evaluation of top-k queries in probabilistic databases. In DBRank, 2008.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Theory

Keywords:
consensus answers, probabilistic and/xor tree, probabilistic databases, query processing, rank aggregation