{"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":1781251731564,"version":"3.54.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>Markov Logic Networks (MLNs) have emerged as a powerful framework that combines statistical and logical reasoning; they have been applied to many data intensive problems including information extraction, entity resolution, and text mining. Current implementations of MLNs do not scale to large real-world data sets, which is preventing their widespread adoption. We present Tuffy that achieves scalability via three novel contributions: (1) a bottom-up approach to grounding that allows us to leverage the full power of the relational optimizer, (2) a novel hybrid architecture that allows us to perform AI-style local search efficiently using an RDBMS, and (3) a theoretical insight that shows when one can (exponentially) improve the efficiency of stochastic local search. We leverage (3) to build novel partitioning, loading, and parallel algorithms. We show that our approach outperforms state-of-the-art implementations in both quality and speed on several publicly available datasets.<\/jats:p>","DOI":"10.14778\/1978665.1978669","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"373-384","source":"Crossref","is-referenced-by-count":138,"title":["Tuffy"],"prefix":"10.14778","volume":"4","author":[{"given":"Feng","family":"Niu","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christopher","family":"R\u00e9","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"AnHai","family":"Doan","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jude","family":"Shavlik","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497507"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0080-z"},{"key":"e_1_2_1_3_1","volume-title":"Parallel and Distributed Computation: Numerical Methods","author":"Bertsekas D. P.","year":"1989","unstructured":"D. P. Bertsekas and J. N. Tsitsiklis . Parallel and Distributed Computation: Numerical Methods . Prentice-Hall , 1989 . D. P. Bertsekas and J. N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, 1989."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316764"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142483"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855041"},{"key":"e_1_2_1_7_1","unstructured":"P. Domingos et al. http:\/\/alchemy.cs.washington.edu\/.  P. Domingos et al. http:\/\/alchemy.cs.washington.edu\/."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90060-U"},{"key":"e_1_2_1_9_1","unstructured":"W. Feller. An Introduction to Probability Theory and its Applications. Vol. I. John Wiley &amp;amp; Sons 1950.  W. Feller. An Introduction to Probability Theory and its Applications. Vol. I . John Wiley &amp;amp; Sons 1950."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376686"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497525"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.748202"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/035\/15"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.59"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009953814988"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978669"},{"key":"e_1_2_1_17_1","volume-title":"Networks of Plausible Inference","author":"Pearl J.","year":"1988","unstructured":"J. Pearl . Probabilistic Reasoning in Intelligent Systems : Networks of Plausible Inference . 1988 . J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. 1988."},{"key":"e_1_2_1_18_1","first-page":"913","volume-title":"AAAI","author":"Poon H.","year":"2007","unstructured":"H. Poon and P. Domingos . Joint inference in information extraction . In AAAI , pages 913 -- 918 , 2007 . H. Poon and P. Domingos. Joint inference in information extraction. In AAAI, pages 913--918, 2007."},{"key":"e_1_2_1_19_1","first-page":"886","volume-title":"ICDE","author":"C.","year":"2007","unstructured":"C. R&amp;#233;, N. N. Dalvi , and D. Suciu . Efficient top-k query evaluation on probabilistic data . In ICDE , pages 886 -- 895 , 2007 . C. R&amp;#233;, N. N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In ICDE, pages 886--895, 2007."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376688"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-5833-1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1596324.1596357"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0153-2"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827593255135"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.65"},{"key":"e_1_2_1_26_1","unstructured":"V. Vazirani. Approximation Algorithms. Springer Verlag 2001.   V. Vazirani. Approximation Algorithms . Springer Verlag 2001."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453896"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888900006147"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367583"},{"key":"e_1_2_1_30_1","first-page":"2","volume-title":"UAI","author":"Allen D.","year":"2003","unstructured":"D. Allen and A. Darwiche . New advances in inference by recursive conditioning . In UAI , pages 2 -- 10 , 2003 . D. Allen and A. Darwiche. New advances in inference by recursive conditioning. In UAI, pages 2--10, 2003."},{"key":"e_1_2_1_31_1","first-page":"369","volume-title":"NIPS","author":"Duchi J.","year":"2007","unstructured":"J. Duchi , D. Tarlow , G. Elidan , and D. Koller . Using combinatorial optimization within max-product belief propagation . In NIPS , pages 369 -- 376 , 2007 . J. Duchi, D. Tarlow, G. Elidan, and D. Koller. Using combinatorial optimization within max-product belief propagation. In NIPS, pages 369--376, 2007."},{"key":"e_1_2_1_32_1","first-page":"1300","volume-title":"IJCAI","author":"Friedman N.","year":"1999","unstructured":"N. Friedman , L. Getoor , D. Koller , and A. Pfeffer . Learning probabilistic relational models . In IJCAI , pages 1300 -- 1309 , 1999 . N. Friedman, L. Getoor, D. Koller, and A. Pfeffer. Learning probabilistic relational models. In IJCAI, pages 1300--1309, 1999."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273538"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/035\/15"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273575"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1893538.1893549"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/648232.752991"},{"key":"e_1_2_1_38_1","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 , 2006 . H. Poon and P. Domingos. Sound and efficient inference with probabilistic and deterministic dependencies. In AAAI, 2006."},{"key":"e_1_2_1_39_1","first-page":"1075","volume-title":"AAAI","author":"Poon H.","year":"2008","unstructured":"H. Poon , P. Domingos , and M. Sumner . A general method for reducing the complexity of relational inference and its application to MCMC . In AAAI , pages 1075 -- 1080 , 2008 . H. Poon, P. Domingos, and M. Sumner. A general method for reducing the complexity of relational inference and its application to MCMC. In AAAI, pages 1075--1080, 2008."},{"key":"e_1_2_1_40_1","first-page":"1951","volume-title":"IJCAI","author":"Shavlik J.","year":"2009","unstructured":"J. Shavlik and S. Natarajan . Speeding up inference in Markov logic networks by preprocessing to reduce the size of the resulting grounded network . In IJCAI , pages 1951 -- 1956 , 2009 . J. Shavlik and S. Natarajan. Speeding up inference in Markov logic networks by preprocessing to reduce the size of the resulting grounded network. In IJCAI, pages 1951--1956, 2009."},{"key":"e_1_2_1_41_1","first-page":"488","volume-title":"AAAI","author":"Singla P.","year":"2006","unstructured":"P. Singla and P. Domingos . Memory-efficient inference in relational domains . In AAAI , pages 488 -- 493 , 2006 . P. Singla and P. Domingos. Memory-efficient inference in relational domains. In AAAI, pages 488--493, 2006."},{"key":"e_1_2_1_42_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_43_1","first-page":"485","volume-title":"UAI","author":"Taskar B.","year":"2002","unstructured":"B. Taskar , P. Abbeel , and D. Koller . Discriminative probabilistic models for relational data . In UAI , pages 485 -- 492 , 2002 . B. Taskar, P. Abbeel, and D. Koller. Discriminative probabilistic models for relational data. In UAI, pages 485--492, 2002."},{"key":"e_1_2_1_44_1","volume-title":"AAAI","author":"Wei W.","year":"2004","unstructured":"W. Wei , J. Erenrich , and B. Selman . Towards efficient sampling: Exploiting random walk strategies . In AAAI , 2004 . W. Wei, J. Erenrich, and B. Selman. Towards efficient sampling: Exploiting random walk strategies. In AAAI, 2004."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1978665.1978669","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:19:00Z","timestamp":1672222740000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1978665.1978669"}},"subtitle":["scaling up statistical inference in Markov logic networks using an RDBMS"],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":44,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.14778\/1978665.1978669"],"URL":"https:\/\/doi.org\/10.14778\/1978665.1978669","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,3]]}}}