{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T08:08:51Z","timestamp":1781251731868,"version":"3.54.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,3]]},"abstract":"<jats:p>Increasingly large Knowledge Bases are being created, by crawling the Web or other corpora of documents, and by extracting facts and relations using machine learning techniques. To manage the uncertainty in the data, these KBs rely on probabilistic engines based on Markov Logic Networks (MLN), for which probabilistic inference remains a major challenge. Today's state of the art systems use variants of MCMC, which have no theoretical error guarantees, and, as we show, suffer from poor performance in practice.<\/jats:p>\n          <jats:p>In this paper we describe SlimShot (Scalable Lifted Inference and Monte Carlo Sampling Hybrid Optimization Technique), a probabilistic inference engine for knowledge bases. SlimShot converts the MLN to a tuple-independent probabilistic database, then uses a simple Monte Carlo-based inference, with three key enhancements: (1) it combines sampling with safe query evaluation, (2) it estimates a conditional probability by jointly computing the numerator and denominator, and (3) it adjusts the proposal distribution based on the sample cardinality. In combination, these three techniques allow us to give formal error guarantees, and we demonstrate empirically that SlimShot outperforms to-day's state of the art probabilistic inference engines used in knowledge bases.<\/jats:p>","DOI":"10.14778\/2904483.2904487","type":"journal-article","created":{"date-parts":[[2016,4,12]],"date-time":"2016-04-12T12:24:41Z","timestamp":1460463881000},"page":"552-563","source":"Crossref","is-referenced-by-count":12,"title":["SlimShot"],"prefix":"10.14778","volume":"9","author":[{"given":"Eric","family":"Gribkoff","sequence":"first","affiliation":[{"name":"University of Washington"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"VLDB J.","author":"Abiteboul S.","year":"2008","unstructured":"S. Abiteboul , O. Benjelloun , and T. Milo . The active XML project . VLDB J. , 2008 . S. Abiteboul, O. Benjelloun, and T. Milo. The active XML project. VLDB J., 2008."},{"key":"e_1_2_1_2_1","unstructured":"http:\/\/alchemy.cs.washington.edu\/.  http:\/\/alchemy.cs.washington.edu\/."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76298-0_52"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066277"},{"key":"e_1_2_1_5_1","volume-title":"IJCAI. Citeseer","author":"Braz R.","year":"2005","unstructured":"R. Braz , E. Amir , and D. Roth . Lifted first-order probabilistic inference . In IJCAI. Citeseer , 2005 . R. Braz, E. Amir, and D. Roth. Lifted first-order probabilistic inference. In IJCAI. Citeseer, 2005."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2898607.2898816"},{"key":"e_1_2_1_7_1","first-page":"1722","volume-title":"AAAI","author":"Chakraborty S.","year":"2014","unstructured":"S. Chakraborty , D. Fremont , K. Meel , S. Seshia , and M. Vardi . Distribution-aware sampling and weighted model counting for SAT . In AAAI , pages 1722 -- 1730 , 2014 . S. Chakraborty, D. Fremont, K. Meel, S. Seshia, and M. Vardi. Distribution-aware sampling and weighted model counting for SAT. In AAAI, pages 1722--1730, 2014."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610516"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492471"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1534901"},{"key":"e_1_2_1_11_1","volume-title":"IJCAI","author":"Darwiche A.","year":"2011","unstructured":"A. Darwiche . SDD : A new canonical representation of propositional knowledge bases . In IJCAI , 2011 . A. Darwiche. SDD: A new canonical representation of propositional knowledge bases. In IJCAI, 2011."},{"key":"e_1_2_1_12_1","volume-title":"KR","author":"den Broeck G. V.","year":"2014","unstructured":"G. V. den Broeck , W. Meert , and A. Darwiche . Skolemization for weighted first-order model counting . In KR , 2014 . G. V. den Broeck, W. Meert, and A. Darwiche. Skolemization for weighted first-order model counting. In KR, 2014."},{"key":"e_1_2_1_13_1","first-page":"2178","volume-title":"IJCAI","author":"den Broeck G. V.","year":"2011","unstructured":"G. V. den Broeck , N. Taghipour , W. Meert , J. Davis , and L. D. Raedt . Lifted probabilistic inference by first-order knowledge compilation . In IJCAI , pages 2178 -- 2185 , 2011 . G. V. den Broeck, N. Taghipour, W. Meert, J. Davis, and L. D. Raedt. Lifted probabilistic inference by first-order knowledge compilation. In IJCAI, pages 2178--2185, 2011."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-01549-6","volume-title":"Markov Logic: An Interface Layer for Artificial Intelligence","author":"Domingos P. M.","year":"2009","unstructured":"P. M. Domingos and D. Lowd . Markov Logic: An Interface Layer for Artificial Intelligence . Morgan & Claypool Publishers , 2009 . P. M. Domingos and D. Lowd. Markov Logic: An Interface Layer for Artificial Intelligence. Morgan & Claypool Publishers, 2009."},{"key":"e_1_2_1_15_1","first-page":"334","volume-title":"ICML","author":"Ermon S.","year":"2013","unstructured":"S. Ermon , C. Gomes , A. Sabharwal , and B. Selman . Taming the curse of dimensionality: Discrete integration by hashing and optimization . In ICML , pages 334 -- 342 , 2013 . S. Ermon, C. Gomes, A. Sabharwal, and B. Selman. Taming the curse of dimensionality: Discrete integration by hashing and optimization. In ICML, pages 334--342, 2013."},{"key":"e_1_2_1_16_1","first-page":"1535","volume-title":"EMNLP","author":"Fader A.","year":"2011","unstructured":"A. Fader , S. Soderland , and O. Etzioni . Identifying relations for open information extraction . In EMNLP , pages 1535 -- 1545 , 2011 . A. Fader, S. Soderland, and O. Etzioni. Identifying relations for open information extraction. In EMNLP, pages 1535--1545, 2011."},{"key":"e_1_2_1_17_1","unstructured":"https:\/\/www.freebase.com\/.  https:\/\/www.freebase.com\/."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2532641"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735494"},{"key":"e_1_2_1_20_1","volume-title":"UAI","author":"Gribkoff E.","year":"2014","unstructured":"E. Gribkoff , G. Van den Broeck, and D. Suciu. Understanding the complexity of lifted inference and asymmetric weighted model counting . In UAI , 2014 . E. Gribkoff, G. Van den Broeck, and D. Suciu. Understanding the complexity of lifted inference and asymmetric weighted model counting. In UAI, 2014."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.06.001"},{"key":"e_1_2_1_22_1","first-page":"72","article-title":"Constructive proofs of concentration bounds","volume":"17","author":"Impagliazzo R.","year":"2010","unstructured":"R. Impagliazzo and V. Kabanets . Constructive proofs of concentration bounds . ECCC , 17 : 72 , 2010 . R. Impagliazzo and V. Kabanets. Constructive proofs of concentration bounds. ECCC, 17:72, 2010.","journal-title":"ECCC"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350236"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.35"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1795555"},{"key":"e_1_2_1_27_1","first-page":"109","volume-title":"ACL","author":"Li Y.","year":"2011","unstructured":"Y. Li , F. Reiss , and L. Chiticariu . Systemt: A declarative information extraction system . In ACL , pages 109 -- 114 , 2011 . Y. Li, F. Reiss, and L. Chiticariu. Systemt: A declarative information extraction system. In ACL, pages 109--114, 2011."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978669"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.123"},{"key":"e_1_2_1_30_1","first-page":"985","volume-title":"IJCAI","volume":"3","author":"Poole D.","year":"2003","unstructured":"D. Poole . First-order probabilistic inference . In IJCAI , volume 3 , pages 985 -- 991 . Citeseer , 2003 . D. Poole. First-order probabilistic inference. In IJCAI, volume 3, pages 985--991. Citeseer, 2003."},{"key":"e_1_2_1_31_1","first-page":"458","volume-title":"AAAI","author":"Poon H.","year":"2006","unstructured":"H. Poon and P. Domingos . Sound and efficient inference with probabilistic and deterministic dependencies . In AAAI , pages 458 -- 463 , 2006 . H. Poon and P. Domingos. Sound and efficient inference with probabilistic and deterministic dependencies. In AAAI, pages 458--463, 2006."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00092-1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"e_1_2_1_34_1","unstructured":"http:\/\/reasoning.cs.ucla.edu\/sdd\/.  http:\/\/reasoning.cs.ucla.edu\/sdd\/."},{"key":"e_1_2_1_35_1","volume-title":"VLDB","author":"Shen W.","year":"2007","unstructured":"W. Shen , A. Doan , J. F. Naughton , and R. Ramakrishnan . Declarative information extraction using datalog with embedded extraction predicates . In VLDB , 2007 . W. Shen, A. Doan, J. F. Naughton, and R. Ramakrishnan. Declarative information extraction using datalog with embedded extraction predicates. In VLDB, 2007."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809991"},{"key":"e_1_2_1_37_1","volume-title":"Official Google Blog","author":"Singhal A.","year":"2012","unstructured":"A. Singhal . Introducing the knowledge graph: things, not strings . Official Google Blog , May , 2012 . A. Singhal. Introducing the knowledge graph: things, not strings. Official Google Blog, May, 2012."},{"key":"e_1_2_1_38_1","first-page":"1094","volume-title":"AAAI","author":"Singla P.","year":"2008","unstructured":"P. Singla and P. Domingos . Lifted first-order belief propagation . In AAAI , pages 1094 -- 1099 , 2008 . P. Singla and P. Domingos. Lifted first-order belief propagation. In AAAI, pages 1094--1099, 2008."},{"key":"e_1_2_1_39_1","volume-title":"Probabilistic Databases. Synthesis Lectures on Data Management","author":"Suciu D.","year":"2011","unstructured":"D. Suciu , D. Olteanu , C. R\u00e9 , and C. Koch . Probabilistic Databases. Synthesis Lectures on Data Management . Morgan & Claypool Publishers , 2011 . D. Suciu, D. Olteanu, C. R\u00e9, and C. Koch. Probabilistic Databases. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011."},{"key":"e_1_2_1_40_1","volume-title":"IAAI","author":"Wei W.","year":"2004","unstructured":"W. Wei , J. Erenrich , and B. Selman . Towards efficient sampling: Exploiting random walk strategies . In IAAI , 2004 . W. Wei, J. Erenrich, and B. Selman. Towards efficient sampling: Exploiting random walk strategies. In IAAI, 2004."},{"key":"e_1_2_1_41_1","unstructured":"http:\/\/www.cs.rice.edu\/CS\/Verification\/Projects\/WeightGen\/.  http:\/\/www.cs.rice.edu\/CS\/Verification\/Projects\/WeightGen\/."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213891"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463680"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463702"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2904483.2904487","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:49:46Z","timestamp":1672224586000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2904483.2904487"}},"subtitle":["in-database probabilistic inference for knowledge bases"],"short-title":[],"issued":{"date-parts":[[2016,3]]},"references-count":44,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2016,3]]}},"alternative-id":["10.14778\/2904483.2904487"],"URL":"https:\/\/doi.org\/10.14778\/2904483.2904487","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,3]]}}}