BayesStore: managing large, uncertain data repositories with probabilistic graphical models

ABSTRACT

Several real-world applications need to effectively manage and reason about large amounts of data that are inherently uncertain. For instance, pervasive computing applications must constantly reason about volumes of noisy sensory readings for a variety of reasons, including motion prediction and human behavior modeling. Such probabilistic data analyses require sophisticated machine-learning tools that can effectively model the complex spatio/temporal correlation patterns present in uncertain sensory data. Unfortunately, to date, most existing approaches to probabilistic database systems have relied on somewhat simplistic models of uncertainty that can be easily mapped onto existing relational architectures: Probabilistic information is typically associated with individual data tuples, with only limited or no support for effectively capturing and reasoning about complex data correlations. In this paper, we introduce BayesStore, a novel probabilistic data management architecture built on the principle of handling statistical models and probabilistic inference tools as first-class citizens of the database system. Adopting a machine-learning view, BAYESSTORE employs concise statistical relational models to effectively encode the correlation patterns between uncertain data, and promotes probabilistic inference and statistical model manipulation as part of the standard DBMS operator repertoire to support efficient and sound query processing. We present BAYESSTORE's uncertainty model based on a novel, first-order statistical model, and we redefine traditional query processing operators, to manipulate the data and the probabilistic models of the database in an efficient manner. Finally, we validate our approach, by demonstrating the value of exploiting data correlations during query processing, and by evaluating a number of optimizations which significantly accelerate query processing.

REFERENCES

• 1: L. Antova, T. Jansen, C. Koch, and D. Olteanu. Fast and simple relational processing of uncertain data. In ICDE, 2008.
• 2: L. Antova, D. Olteanu, and S. Scherzinger. 10(10⁶) worlds and beyond: Efficient representation and processing of incomplete information. In ICDE, 2007.
• 3: 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]
• 4: 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
• 5: Roger Cavallo , Michael Pittarelli, The Theory of Probabilistic Databases, Proceedings of the 13th International Conference on Very Large Data Bases, p.71-81, September 01-04, 1987
• 6: Robert G. Cowell , Steffen L. Lauritzen , A. Philip David , David J. Spiegelhalter , V. Nair , J. Lawless , M. Jordan, Probabilistic Networks and Expert Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 7: 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
• 8: Amol Deshpande , Samuel Madden, MauveDB: supporting model-based user views in database systems, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142483]
• 9: 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
• 10: 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]
• 11: 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
• 12: 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]
• 13: M. I. Jordan. Graphical models. Statistical Science (Special Issue on Bayesian Statistics), 19:140--155, 2004.
• 14: E. Michelakis, D. Z. Wang, M. Garofalakis, and J. M. Hellerstein. Granularity conscious modeling for probabilistic databases. In DUNE, 2007.
• 15: Avrom Jacob Pfeffer , Daphne Koller, Probabilistic reasoning for complex systems, Stanford University, Stanford, CA, 2000
• 16: D. Poole. First-order Probabilistic Inference. In IJCAI, 2003.
• 17: P. Sen and A. Deshpande. Representing and Querying Correlated Tuples in Probabilistic Databases. In ICDE, 2007.
• 18: P. Sen, A. Deshpande, and L. Getoor. Representing tuple and attribute uncertainty in probabilistic databases. In DUNE, 2007.
• 19: B. Taskar, P. Abbeel, and D. Koller. Discriminative probabilistic models for relational data. In UAI, 2002.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data warehouse and repository

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
      H.2.8 Database applications
          Subjects: Statistical databases
  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)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning

General Terms:
Design, Management, Performance