Indexing correlated probabilistic databases

ABSTRACT

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.

REFERENCES

• 1: Periklis Andritsos , Ariel Fuxman , Renee J. Miller, Clean Answers over Dirty Databases: A Probabilistic Approach, Proceedings of the 22nd International Conference on Data Engineering, p.30, April 03-07, 2006 [doi>10.1109/ICDE.2006.35]
• 2: Lyublena Antova , Thomas Jansen , Christoph Koch , Dan Olteanu, Fast and Simple Relational Processing of Uncertain Data, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.983-992, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497507]
• 3: Lyublena Antova , Christoph Koch , Dan Olteanu, From complete to incomplete information and back, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247559]
• 4: A. Berry, P. Heggernes, and Y. Villanger. A vertex incremental approach for maintaining chordality. Discrete Mathematics, 2006.
• 5: Héctor Corrada Bravo , Raghu Ramakrishnan, Optimizing mpf queries: decision support and probabilistic inference, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247558]
• 6: Reynold Cheng , Yuni Xia , Sunil Prabhakar , Rahul Shah , Jeffrey Scott Vitter, Efficient indexing methods for probabilistic threshold queries over uncertain data, Proceedings of the Thirtieth international conference on Very large data bases, p.876-887, August 31-September 03, 2004, Toronto, Canada
• 7: A. Choi and A. Darwiche. Focusing generalizations of belief propagation on targeted queries. In AAAI, 2008.
• 8: 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
• 9: Nilesh Dalvi , Dan Suciu, Management of probabilistic data: foundations and challenges, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-12, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265531]
• 10: 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
• 11: Adnan Darwiche , Mark Hopkins, Using Recursive Decomposition to Construct Elimination Orders, Jointrees, and Dtrees, Proceedings of the 6th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, p.180-191, September 19-21, 2001
• 12: R. Dechter. Constraint Networks (Survey). John Wiley&Sons, 1992
• 13: A. Deshpande, L. Getoor, and P. Sen. Graphical Models for Uncertain Data. Managing and Mining Uncertain Data. Charu Aggarwal ed., Springer, 2009.
• 14: A. Deshpande, C. Guestrin, and S. Madden. Using probabilistic models for data management in acquisitional environments. In CIDR, 2005.
• 15: Xin Dong , Alon Y. Halevy , Cong Yu, Data integration with uncertainty, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 16: J. Finn and J. Frank. Optimal junction trees. In UAI, 1994.
• 17: 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
• 18: C. Huang and A. Darwiche. Inference in belief networks: A procedural guide. Int. J. Approx. Reasoning, 1996.
• 19: 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]
• 20: T. S. Jayram, R. Krishnamurthy, S. Raghavan, S. Vaithyanathan, and H. Zhu. Avatar information extraction system. IEEE Data Eng. Bull., 29(1), 2006.
• 21: Bhargav Kanagal , Amol Deshpande, Online Filtering, Smoothing and Probabilistic Modeling of Streaming data, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1160-1169, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497525]
• 22: Bhargav Kanagal , Amol Deshpande, Ef?cient Query Evaluation over Temporally Correlated Probabilistic Streams, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.1315-1318, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.229]
• 23: Christoph Koch , Dan Olteanu, Conditioning probabilistic databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453894]
• 24: S. Kundu and J. Misra. A linear tree partitioning algorithm. SIAM J. Comput., 1977.
• 25: Laks V. S. Lakshmanan , Nicola Leone , Robert Ross , V. S. Subrahmanian, ProbView: a flexible probabilistic database system, ACM Transactions on Database Systems (TODS), v.22 n.3, p.419-469, Sept. 1997 [doi>10.1145/261124.261131]
• 26: Julie Letchner , Christopher Re , Magdalena Balazinska , Matthai Philipose, Access Methods for Markovian Streams, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.246-257, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.21]
• 27: R. Mateescu and R. Dechter. And/or cutset conditioning. In IJCAI, 2005.
• 28: D. Patterson, L. Liao, D. Fox, and H. Kautz. Inferring high level behavior from low level sensors. In UBICOMP, 2003.
• 29: Christopher Ré , Julie Letchner , Magdalena Balazinksa , Dan Suciu, Event queries on correlated probabilistic streams, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376688]
• 30: P. Sen and A. Deshpande. Representing and querying correlated tuples in probabilistic databases. In ICDE, 2007.
• 31: Prithviraj Sen , Amol Deshpande , Lise Getoor, Exploiting shared correlations in probabilistic databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453944]
• 32: S. Singh, C. Mayfield, S. Prabhakar, R. Shah, and S. E. Hambrusch. Indexing uncertain categorical data. In ICDE, 2007.
• 33: Yufei Tao , Reynold Cheng , Xiaokui Xiao , Wang Kay Ngai , Ben Kao , Sunil Prabhakar, Indexing multi-dimensional uncertain data with arbitrary probability density functions, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 34: Daisy Zhe Wang , Eirinaios Michelakis , Minos Garofalakis , Joseph M. Hellerstein, BayesStore: managing large, uncertain data repositories with probabilistic graphical models, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453896]
• 35: J. Widom. Trio: A system for integrated management of data, accuracy, and lineage. In CIDR, 2005.
• 36: J. S. Yedidia, W. T. Freeman, and Y. Weiss. Generalized belief propagation. In NIPS, 2000.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Design, Management, Performance

Keywords:
caching, indexing, inference queries, junction trees, probabilistic databases