{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T06:12:52Z","timestamp":1747807972645},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>Recently, there has been increasing interest in extending relational query processing to include data obtained from unstructured sources. A common approach is to use stand-alone Information Extraction (IE) techniques to identify and label entities within blocks of text; the resulting entities are then imported into a standard database and processed using relational queries. This two-part approach, however, suffers from two main drawbacks. First, IE is inherently probabilistic, but traditional query processing does not properly handle probabilistic data, resulting in reduced answer quality. Second, performance inefficiencies arise due to the separation of IE from query processing. In this paper, we address these two problems by building on an in-database implementation of a leading IE model---Conditional Random Fields using the Viterbi inference algorithm. We develop two different query approaches on top of this implementation. The first uses deterministic queries over maximum-likelihood extractions, with optimizations to push the relational operators into the Viterbi algorithm. The second extends the Viterbi algorithm to produce a set of possible extraction \"worlds\", from which we compute top-<jats:italic>k<\/jats:italic>probabilistic query answers. We describe these approaches and explore the trade-offs of efficiency and effectiveness between them using two datasets.<\/jats:p>","DOI":"10.14778\/1920841.1920974","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1057-1067","source":"Crossref","is-referenced-by-count":12,"title":["Querying probabilistic information extraction"],"prefix":"10.14778","volume":"3","author":[{"given":"Daisy Zhe","family":"Wang","sequence":"first","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael J.","family":"Franklin","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minos","family":"Garofalakis","sequence":"additional","affiliation":[{"name":"Technical University of Crete"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph M.","family":"Hellerstein","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497502"},{"key":"e_1_2_1_2_1","unstructured":"W. Shen A. Doan J. Naughton and R. Ramakrishnan \"Declarative Information Extraction Using Datalog with Embedded Extraction Predicates \" in VLDB 2007. W. Shen A. Doan J. Naughton and R. Ramakrishnan \"Declarative Information Extraction Using Datalog with Embedded Extraction Predicates \" in VLDB 2007."},{"key":"e_1_2_1_3_1","unstructured":"A. Doan R. Ramakrishnan F. Chen P. DeRose Y. Lee R. McCann M. Sayyadian and W. Shen \"Community information management \" 2006. A. Doan R. Ramakrishnan F. Chen P. DeRose Y. Lee R. McCann M. Sayyadian and W. Shen \"Community information management \" 2006."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"N. Dalvi and D. Suciu \"Efficient Query Evaluation on Probabilistic Databases \" in VLDB 2004. N. Dalvi and D. Suciu \"Efficient Query Evaluation on Probabilistic Databases \" in VLDB 2004.","DOI":"10.1016\/B978-012088469-8.50076-0"},{"key":"e_1_2_1_5_1","unstructured":"O. Benjelloun A. Sarma A. Halevy and J. Widom \"ULDB: Databases with Uncertainty and Lineage \" in VLDB 2006. O. Benjelloun A. Sarma A. Halevy and J. Widom \"ULDB: Databases with Uncertainty and Lineage \" in VLDB 2006."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142483"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"P. Sen and A. Deshpande \"Representing and Querying Correlated Tuples in Probabilistic Databases \" in ICDE 2007. P. Sen and A. Deshpande \"Representing and Querying Correlated Tuples in Probabilistic Databases \" in ICDE 2007.","DOI":"10.1109\/ICDMW.2007.11"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497507"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"D. Wang E. Michelakis M. Garofalakis and J. Hellerstein \"BayesStore: Managing Large Uncertain Data Repositories with Probabilistic Graphical Models \" in VLDB 2008. D. Wang E. Michelakis M. Garofalakis and J. Hellerstein \"BayesStore: Managing Large Uncertain Data Repositories with Probabilistic Graphical Models \" in VLDB 2008.","DOI":"10.14778\/1453856.1453896"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"D. Wang E. Michelakis M. Franklin M. Garofalakis and J. Hellerstein \"Probabilistic Declarative Information Extraction \" in ICDE 2010. D. Wang E. Michelakis M. Franklin M. Garofalakis and J. Hellerstein \"Probabilistic Declarative Information Extraction \" in ICDE 2010.","DOI":"10.1109\/ICDE.2010.5447844"},{"key":"e_1_2_1_11_1","unstructured":"R. Gupta and S. Sarawagi \"Creating Probabilistic Databases from Information Extraction Models \" in VLDB 2006. R. Gupta and S. Sarawagi \"Creating Probabilistic Databases from Information Extraction Models \" in VLDB 2006."},{"key":"e_1_2_1_12_1","unstructured":"T. Kristjansson A. Culotta P. Viola and A. McCallum \"Interactive Information Extraction with Constrained Conditional Random Fields \" in AAAI'04 2004. T. Kristjansson A. Culotta P. Viola and A. McCallum \"Interactive Information Extraction with Constrained Conditional Random Fields \" in AAAI'04 2004."},{"key":"e_1_2_1_13_1","unstructured":"\"Enron email dataset http:\/\/www.cs.cmu.edu\/enron\/.\" \"Enron email dataset http:\/\/www.cs.cmu.edu\/enron\/.\""},{"key":"e_1_2_1_14_1","unstructured":"J. Lafferty A. McCallum and F. Pereira \"Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data \" in ICML 2001. J. Lafferty A. McCallum and F. Pereira \"Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data \" in ICML 2001."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"C. Sutton and A. McCallum \"Introduction to Conditional Random Fields for Relational Learning \" in Introduction to Statistical Relational Learning 2008. C. Sutton and A. McCallum \"Introduction to Conditional Random Fields for Relational Learning \" in Introduction to Statistical Relational Learning 2008.","DOI":"10.7551\/mitpress\/7432.003.0006"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"G. D. Forney \"The Viterbi Algorithm \" IEEE 1973. G. D. Forney \"The Viterbi Algorithm \" IEEE 1973.","DOI":"10.1109\/PROC.1973.9030"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"L. Huang and D. Chiang \"Better k-best Parsing \" in IWPT 2005. L. Huang and D. Chiang \"Better k-best Parsing \" in IWPT 2005.","DOI":"10.3115\/1654494.1654500"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007593"},{"key":"e_1_2_1_19_1","unstructured":"\"Contact record extraction data http:\/\/www2.selu.edu\/academics\/faculty\/aculotta\/data\/contact.html.\" \"Contact record extraction data http:\/\/www2.selu.edu\/academics\/faculty\/aculotta\/data\/contact.html.\""},{"key":"e_1_2_1_20_1","unstructured":"\"Dblp dataset http:\/\/kdl.cs.umass.edu\/data\/dblp\/dblp-info.html.\" \"Dblp dataset http:\/\/kdl.cs.umass.edu\/data\/dblp\/dblp-info.html.\""},{"key":"e_1_2_1_21_1","unstructured":"E. Agichtein and S. Sarawagi \"Scalable Information Extraction and Integration \" in KDD 2006. E. Agichtein and S. Sarawagi \"Scalable Information Extraction and Integration \" in KDD 2006."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142595"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559858"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376718"},{"key":"e_1_2_1_25_1","unstructured":"M. Skounakis M. Craven and S. Ray \"Hierarchical Hidden Markov Models for Information Extraction \" in Proc. of IJCAI 2003. M. Skounakis M. Craven and S. Ray \"Hierarchical Hidden Markov Models for Information Extraction \" in Proc. of IJCAI 2003."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.3115\/1220575.1220611"},{"key":"e_1_2_1_27_1","unstructured":"H. Poon and P. Domingos \"Joint Inference in Information Extraction \" in Proc. of AAAI 2007. H. Poon and P. Domingos \"Joint Inference in Information Extraction \" in Proc. of AAAI 2007."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1920841.1920974","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T14:41:02Z","timestamp":1689345662000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1920841.1920974"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":27,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.14778\/1920841.1920974"],"URL":"https:\/\/doi.org\/10.14778\/1920841.1920974","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}