{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T22:29:22Z","timestamp":1778106562297,"version":"3.51.4"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>\n            We present the design of a structured search engine which returns a multi-column table in response to a query consisting of keywords describing each of its columns. We answer such queries by exploiting the millions of tables on the Web because these are much richer sources of structured knowledge than free-format text. However, a corpus of tables harvested from arbitrary HTML web pages presents huge challenges of diversity and redundancy not seen in centrally edited knowledge bases. We concentrate on one concrete task in this paper. Given a set of Web tables\n            <jats:italic>T<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,...,\n            <jats:italic>T<\/jats:italic>\n            <jats:sub>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sub>\n            , and a query\n            <jats:italic>Q<\/jats:italic>\n            with\n            <jats:italic>q<\/jats:italic>\n            sets of keywords\n            <jats:italic>Q<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,...,\n            <jats:italic>Q<\/jats:italic>\n            <jats:sub>\n              <jats:italic>q<\/jats:italic>\n            <\/jats:sub>\n            , decide for each\n            <jats:italic>T<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            if it is relevant to\n            <jats:italic>Q<\/jats:italic>\n            and if so, identify the mapping between the columns of\n            <jats:italic>T<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            and query columns. We represent this task as a graphical model that jointly maps all tables by incorporating diverse sources of clues spanning matches in different parts of the table, corpus-wide co-occurrence statistics, and content overlap across table columns. We define a novel query segmentation model for matching keywords to table columns, and a robust mechanism of exploiting content overlap across table columns. We design efficient inference algorithms based on bipartite matching and constrained graph cuts to solve the joint labeling task. Experiments on a workload of 59 queries over a 25 million web table corpus shows significant boost in accuracy over baseline IR methods.\n          <\/jats:p>","DOI":"10.14778\/2336664.2336665","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"908-919","source":"Crossref","is-referenced-by-count":86,"title":["Answering table queries on the web using column keywords"],"prefix":"10.14778","volume":"5","author":[{"given":"Rakesh","family":"Pimplikar","sequence":"first","affiliation":[{"name":"IBM Research, New Delhi, India"}]},{"given":"Sunita","family":"Sarawagi","sequence":"additional","affiliation":[{"name":"IIT Bombay, Mumbai, India"}]}],"member":"320","published-online":{"date-parts":[[2012,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.969114"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687750"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453916"},{"key":"e_1_2_1_4_1","volume-title":"WebDB","author":"Cafarella M. J.","year":"2008","unstructured":"M. J. Cafarella , A. Y. Halevy , Y. Zhang , D. Z. Wang , and E. Wu . Uncovering the relational web . In WebDB , 2008 . M. J. Cafarella, A. Y. Halevy, Y. Zhang, D. Z. Wang, and E. Wu. Uncovering the relational web. In WebDB, 2008."},{"issue":"1","key":"e_1_2_1_5_1","first-page":"3","article-title":"Enhancing search with structure","volume":"33","author":"Chakrabarti S.","year":"2010","unstructured":"S. Chakrabarti , S. Sarawagi , and S. Sudarshan . Enhancing search with structure . IEEE Data Eng. Bull. , 33 ( 1 ): 3 -- 24 , 2010 . S. Chakrabarti, S. Sarawagi, and S. Sudarshan. Enhancing search with structure. IEEE Data Eng. Bull., 33(1): 3--24, 2010.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_6_1","first-page":"109","volume-title":"SODA","author":"Chekuri C.","year":"2001","unstructured":"C. Chekuri , S. Khanna , J. S. Naor , and L. Zosin . Approximation algorithms for the metric labeling problem via a new linear programming formulation . In SODA , pages 109 -- 118 , 2001 . C. Chekuri, S. Khanna, J. S. Naor, and L. Zosin. Approximation algorithms for the metric labeling problem via a new linear programming formulation. In SODA, pages 109--118, 2001."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935904"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1090488.1090497"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687661"},{"key":"e_1_2_1_10_1","volume-title":"Probabilistic graphical models: principles and techniques","author":"Koller D.","year":"2009","unstructured":"D. Koller and N. Friedman . Probabilistic graphical models: principles and techniques . MIT Press , 2009 . D. Koller and N. Friedman. Probabilistic graphical models: principles and techniques. MIT Press, 2009."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.200"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1699571.1699635"},{"key":"e_1_2_1_13_1","first-page":"247","volume-title":"Combinatorial optimization: algorithms and complexity","author":"Papadimitriou C.","year":"1982","unstructured":"C. Papadimitriou and K. Steiglitz . Combinatorial optimization: algorithms and complexity , chapter 11, pages 247 -- 254 . Prentice Hall , 1982 . C. Papadimitriou and K. Steiglitz. Combinatorial optimization: algorithms and complexity, chapter 11, pages 247--254. Prentice Hall, 1982."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/860435.860479"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807214"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780100057"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807251"},{"key":"e_1_2_1_18_1","first-page":"503","volume-title":"UAI","author":"Sontag D.","year":"2008","unstructured":"D. Sontag , T. Meltzer , A. Globerson , T. Jaakkola , and Y. Weiss . Tightening LP relaxations for MAP using message passing . In UAI , pages 503 -- 510 , 2008 . D. Sontag, T. Meltzer, A. Globerson, T. Jaakkola, and Y. Weiss. Tightening LP relaxations for MAP using message passing. In UAI, pages 503--510, 2008."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11744047_2"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1699571.1699595"},{"issue":"1","key":"e_1_2_1_21_1","first-page":"67","article-title":"Keyword search in relational databases: A survey","volume":"33","author":"Yu J. X.","year":"2010","unstructured":"J. X. Yu , L. Qin , and L. Chang . Keyword search in relational databases: A survey . IEEE Data Eng. Bull , 33 ( 1 ): 67 -- 78 , 2010 . J. X. Yu, L. Qin, and L. Chang. Keyword search in relational databases: A survey. IEEE Data Eng. Bull, 33(1): 67--78, 2010.","journal-title":"IEEE Data Eng. Bull"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2336664.2336665","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:45:02Z","timestamp":1672224302000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2336664.2336665"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":21,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.14778\/2336664.2336665"],"URL":"https:\/\/doi.org\/10.14778\/2336664.2336665","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,6]]}}}