Scalable Probabilistic Databases with Factor Graphs and MCMC

Details Scalable Probabilistic Databases with Factor Graphs and MCMC Scalable Probabilistic Databases with Factor Graphs and MCMC

2010-05-11

arxiv.org/abs/1005.1934v1

Computer Science

Databases

Submitted to VLDB 2010

Scientific paper

Probabilistic databases play a crucial role in the management and understanding of uncertain data. However, incorporating probabilities into the semantics of incomplete databases has posed many challenges, forcing systems to sacrifice modeling power, scalability, or restrict the class of relational algebra formula under which they are closed. We propose an alternative approach where the underlying relational database always represents a single world, and an external factor graph encodes a distribution over possible worlds; Markov chain Monte Carlo (MCMC) inference is then used to recover this uncertainty to a desired level of fidelity. Our approach allows the efficient evaluation of arbitrary queries over probabilistic databases with arbitrary dependencies expressed by graphical models with structure that changes during inference. MCMC sampling provides efficiency by hypothesizing {\em modifications} to possible worlds rather than generating entire worlds from scratch. Queries are then run over the portions of the world that change, avoiding the onerous cost of running full queries over each sampled world. A significant innovation of this work is the connection between MCMC sampling and materialized view maintenance techniques: we find empirically that using view maintenance techniques is several orders of magnitude faster than naively querying each sampled world. We also demonstrate our system's ability to answer relational queries with aggregation, and demonstrate additional scalability through the use of parallelization.

Affiliated with

Also associated with

No associations

Rating

Scalable Probabilistic Databases with Factor Graphs and MCMC does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Scalable Probabilistic Databases with Factor Graphs and MCMC, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable Probabilistic Databases with Factor Graphs and MCMC will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-498374