Exploiting shared correlations in probabilistic databases

ABSTRACT

There has been a recent surge in work in probabilistic databases, propelled in large part by the huge increase in noisy data sources --- from sensor data, experimental data, data from uncurated sources, and many others. There is a growing need for database management systems that can efficiently represent and query such data. In this work, we show how data characteristics can be leveraged to make the query evaluation process more efficient. In particular, we exploit what we refer to as shared correlations where the same uncertainties and correlations occur repeatedly in the data. Shared correlations occur mainly due to two reasons: (1) Uncertainty and correlations usually come from general statistics and rarely vary on a tuple-to-tuple basis; (2) The query evaluation procedure itself tends to re-introduce the same correlations. Prior work has shown that the query evaluation problem on probabilistic databases is equivalent to a probabilistic inference problem on an appropriately constructed probabilistic graphical model (PGM). We leverage this by introducing a new data structure, called the random variable elimination graph (rv-elim graph) that can be built from the PGM obtained from query evaluation. We develop techniques based on bisimulation that can be used to compress the rv-elim graph exploiting the presence of shared correlations in the PGM, the compressed rv-elim graph can then be used to run inference. We validate our methods by evaluating them empirically and show that even with a few shared correlations significant speed-ups are possible.

REFERENCES

• 1: 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]
• 2: Stefan Arnborg, Efficient algorithms for combinatorial problems on graphs with bounded, decomposability—a survey, BIT, v.25 n.1, p.2-23, 1985
• 3: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 4: Héctor Corrada Bravo , Raghu Ramakrishnan, Optimizing mpf queries: decision support and probabilistic inference, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247558]
• 5: 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]
• 6: 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
• 7: A. Das Sarma, M. Theobald, and J. Widom. Exploiting lineage for confidence computation in uncertain and probabilistic databases. In ICDE, 2008.
• 8: R. de Salvo Braz, E. Amir, and D. Roth. Lifted first-order probabilistic inference. In International Joint Conference on Artificial Inteligence, 2005.
• 9: 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
• 10: Agostino Dovier , Carla Piazza , Alberto Policriti, A Fast Bisimulation Algorithm, Proceedings of the 13th International Conference on Computer Aided Verification, p.79-90, July 18-22, 2001
• 11: Nir Friedman , Lise Getoor , Daphne Koller , Avi Pfeffer, Learning Probabilistic Relational Models, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1300-1309, July 31-August 06, 1999
• 12: 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]
• 13: L. Getoor, N. Friedman, D. Koller, and B. Taskar. Learning probabilistic models with link uncertainty. Journal of Machine Learning Research, 2002.
• 14: Lise Getoor , Ben Taskar, Introduction to Statistical Relational Learning (Adaptive Computation and Machine Learning), The MIT Press, 2007
• 15: 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
• 16: C. Huang and A. Darwiche. Inference in belief networks: A procedural guide. International Journal of Approximate Reasoning, 1994.
• 17: Paris C. Kanellakis , Scott A. Smolka, CCS expressions, finite state processes, and three problems of equivalence, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.228-240, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806724]
• 18: U. Kjaerulff. Triangulation of graphs - algorithms giving small total state space. Technical report, University of Aalborg, Denmark, 1990.
• 19: Robert Paige , Robert E. Tarjan, Three partition refinement algorithms, SIAM Journal on Computing, v.16 n.6, p.973-989, December 1, 1987 [doi>10.1137/0216062]
• 20: D. Poole. First-order probabilistic inference. In International Joint Conference on Artificial Inteligence, 2003.
• 21: C. Re, N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In ICDE, 2007.
• 22: 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
• 23: Irina Rish , Rina Dechter, Efficient reasoning in graphical models, University of California, Irvine, 1999
• 24: P. Sen and A. Deshpande. Representing and querying correlated tuples in probabilistic databases. In ICDE, 2007.
• 25: S. Singh, C. Mayfield, S. Prabhakar, S. Hambrusch, and R. Shah. Indexing uncertain categorical data. In ICDE, 2007.
• 26: S. Singh, C. Mayfield, R. Shah, S. Prabhakar, S. Hambrusch, J. Neville, and R. Cheng. Database support for probabilistic attributes and tuples. In ICDE, 2008.
• 27: N. L. Zhang and D. Poole. A simple approach to bayesian network computations. In Canadian Conference on AI, 1994.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Statistical databases

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
      H.2.m Miscellaneous
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Management, Performance