%0 Conference Paper %B Proceedings of the 2010 international conference on Management of data %D 2010 %T Lineage processing over correlated probabilistic databases %A Kanagal,Bhargav %A Deshpande, Amol %K conjunctive queries %K Indexing %K junction trees %K lineage %K Probabilistic databases %X In this paper, we address the problem of scalably evaluating conjunctive queries over correlated probabilistic databases containing tuple or attribute uncertainties. Like previous work, we adopt a two-phase approach where we first compute lineages of the output tuples, and then compute the probabilities of the lineage formulas. However unlike previous work, we allow for arbitrary and complex correlations to be present in the data, captured via a forest of junction trees. We observe that evaluating even read-once (tree structured) lineages (e.g., those generated by hierarchical conjunctive queries), polynomially computable over tuple independent probabilistic databases, is #P-complete for lightly correlated probabilistic databases like Markov sequences. We characterize the complexity of exact computation of the probability of the lineage formula on a correlated database using a parameter called lwidth (analogous to the notion of treewidth). For lineages that result in low lwidth, we compute exact probabilities using a novel message passing algorithm, and for lineages that induce large lwidths, we develop approximate Monte Carlo algorithms to estimate the result probabilities. We scale our algorithms to very large correlated probabilistic databases using the previously proposed INDSEP data structure. To mitigate the complexity of lineage evaluation, we develop optimization techniques to process a batch of lineages by sharing computation across formulas, and to exploit any independence relationships that may exist in the data. Our experimental study illustrates the benefits of using our algorithms for processing lineage formulas over correlated probabilistic databases. %B Proceedings of the 2010 international conference on Management of data %S SIGMOD '10 %I ACM %C New York, NY, USA %P 675 - 686 %8 2010/// %@ 978-1-4503-0032-2 %G eng %U http://doi.acm.org/10.1145/1807167.1807241 %R 10.1145/1807167.1807241 %0 Conference Paper %B Proceedings of the 35th SIGMOD international conference on Management of data %D 2009 %T Indexing correlated probabilistic databases %A Kanagal,Bhargav %A Deshpande, Amol %K caching %K Indexing %K inference queries %K junction trees %K Probabilistic databases %X With large amounts of correlated probabilistic data being generated in a wide range of application domains including sensor networks, information extraction, event detection etc., effectively managing and querying them has become an important research direction. While there is an exhaustive body of literature on querying independent probabilistic data, supporting efficient queries over large-scale, correlated databases remains a challenge. In this paper, we develop efficient data structures and indexes for supporting inference and decision support queries over such databases. Our proposed hierarchical data structure is suitable both for in-memory and disk-resident databases. We represent the correlations in the probabilistic database using a junction tree over the tuple-existence or attribute-value random variables, and use tree partitioning techniques to build an index structure over it. We show how to efficiently answer inference and aggregation queries using such an index, resulting in orders of magnitude performance benefits in most cases. In addition, we develop novel algorithms for efficiently keeping the index structure up-to-date as changes (inserts, updates) are made to the probabilistic database. We present a comprehensive experimental study illustrating the benefits of our approach to query processing in probabilistic databases. %B Proceedings of the 35th SIGMOD international conference on Management of data %S SIGMOD '09 %I ACM %C New York, NY, USA %P 455 - 468 %8 2009/// %@ 978-1-60558-551-2 %G eng %U http://doi.acm.org/10.1145/1559845.1559894 %R 10.1145/1559845.1559894