Scalable Probabilistic Databases with Factor Graphs and MCMC.

Michael L. Wick, Andrew McCallum, Gerome Miklau

TL;DR

This paper introduces a novel framework for building and querying probabilistic databases (PDBs) that can handle complex dependencies and large datasets. By combining factor graphs for representing uncertainty with Markov Chain Monte Carlo (MCMC) sampling for efficient inference, they enable scalable query evaluation on uncertain data, overcoming limitations of previous approaches.

What Problem Does This Paper Address?

Managing and querying uncertain data is a growing challenge in many applications, from sensor networks to information extraction. Traditional relational databases struggle to represent this uncertainty effectively. Existing probabilistic database systems often face a trade-off: they can either be highly expressive but computationally intractable for queries, or they sacrifice modeling power for efficiency. This paper tackles the problem of building PDBs that are both expressive enough to model complex dependencies and scalable enough to handle large, real-world datasets, particularly for arbitrary relational queries.

Methods

The core innovation lies in the combination of two key techniques:

  • Factor Graphs: The authors represent the probabilistic relationships within the database using factor graphs. These are a flexible graphical model that can represent any exponential family probability distribution, acting as a unified framework for Bayesian networks and Markov random fields. This allows for rich modeling of dependencies between uncertain data elements.
  • Markov Chain Monte Carlo (MCMC) Sampling with View Maintenance: Instead of trying to compute exact probabilities (which is often #P-hard), the system uses MCMC sampling to generate approximate answers. Crucially, they employ a view maintenance technique to efficiently update query results as the MCMC sampler transitions between states (possible worlds). This avoids re-running the entire query on each sampled world, significantly speeding up evaluation. The MCMC sampler proposes local changes to the database's state, and the view maintenance approach efficiently calculates how these changes affect the query answer.

Datasets

The paper evaluates their approach on a real-world information extraction problem: named entity recognition (NER) using a large corpus of ten million New York Times articles. They also mention using this data for entity resolution. No new benchmarks were introduced; instead, they used existing datasets to demonstrate their system's capabilities.

Key Insights and Ideas

  • Factor Graphs as a Unified Representation: Using factor graphs provides a powerful and flexible way to model complex dependencies in uncertain data, bridging the gap between expressive graphical models and database systems.
  • MCMC + View Maintenance is a Game Changer: The most significant insight is the synergy between MCMC sampling and materialized view maintenance. This combination allows for efficient query evaluation over uncertain data by incrementally updating results, rather than recomputing them from scratch for each sample. This is a key enabler for scalability.
  • Query Agnosticism: The sampling approach makes their system query-agnostic. They don't need to develop specialized algorithms for each type of relational algebra operator (including aggregates), which is a major advantage over traditional PDBs.
  • Any-Time Algorithm: The MCMC approach naturally lends itself to an "any-time" algorithm. Users can stop the process at any point and get an approximate answer, with accuracy improving over time.

Key Results

  • Dramatic Speedup: The materialized MCMC sampler achieved significant speedups, reducing query evaluation time by several orders of magnitude compared to a naive MCMC approach. For a 10-million tuple dataset, the naive approach was estimated to take 227 hours, while their system completed in under two-and-a-half hours.
  • Scalability: The system demonstrated scalability to large datasets (up to 10 million tuples) and complex models (skip-chain CRFs) where exact inference is intractable.
  • Accurate Aggregates: The system successfully handled aggregate queries, showing rapid convergence to accurate results.
  • Parallelization Benefits: Parallelizing MCMC chains provided further improvements, achieving near-linear speedups and even super-linear gains in fidelity due to increased sample independence.

Limitations and Future Work

  • Jump Function Design: The authors acknowledge that designing effective "jump functions" (the proposal distribution in MCMC) that target specific queries is an area for future work. This could further improve efficiency.
  • DBMS Integration: While they use a DBMS for storing the database, the interaction between in-memory MCMC and disk-based DBMS operations could be further optimized.
  • Learning Parameters: The paper mentions that parameters can be learned automatically, but the focus is on query evaluation. Further work could explore more sophisticated parameter learning techniques within their framework.
  • Optimizing Thinning: The choice of "thinning" (skipping samples to improve independence) is noted as an open problem, suggesting potential for adaptive strategies.

Summary updated

Abstract

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.
BibTeX
@article{wick2010scalable,
  author = {Michael L. Wick and Andrew McCallum and Gerome Miklau},
  title = {{Scalable Probabilistic Databases with Factor Graphs and MCMC.}},
  journal = {PVLDB2010},
  year = {2010},
  url = {https://openreview.net/forum?id=slUsxSzV40},
}
Figure