Jigsaw: Efficient Optimization Over Uncertain Enterprise Data

Probabilistic databases, in particular ones that allow users to externally define models or probability distributions – so called VG-Functions – are an ideal tool for constructing, simulating and analyzing hypothetical business scenarios. Enterprises often use such tools with parameterized models and need to explore a large parameter space in order to discover parameter values that optimize for a given goal. Parameter space is usually very large, making such exploration extremely expensive. We present Jigsaw, a probabilistic database-based simulation framework that addresses this performance problem. In Jigsaw, users define what-if style scenarios as parameterized probabilistic database queries and identify parameter values that achieve desired properties. Jigsaw uses a novel “fingerprinting” technique that efficiently identifies correlations between a query’s output distribution for different parameter values. Using fingerprints, Jigsaw is able to reuse work performed for different parameter values, and obtain speedups of as much as 2 orders of magnitude for several real business scenarios.

Presented at:
2011 ACM SIGMOD Conference, Athens, Greece, June 12-16, 2011

 Record created 2011-05-23, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)