Proceedings

Synthesizing Union Tables from the Web

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 2677-2682.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

Several recent works have focused on harvesting HTML tables from the Web and recovering their semantics. As a result, hundreds of millions of high quality structured data tables can now be explored by the users. In this paper, we argue that those efforts only scratch the surface of the true value of structured data on the Web, and study the challenging problem of synthesizing tables from the Web, i.e., producing never-before-seen tables from raw tables on the Web. Table synthesis offers an important semantic advantage: when a set of related tables are combined into a single union table, powerful mechanisms, such as temporal or geographical comparison and visualization, can be employed to understand and mine the underlying data holistically. We focus on one fundamental task of table synthesis, namely, table stitching. Within a given site, many tables with identical schemas can be scattered across many pages. The task of table stitching involves combining such tables into a single meaningful union table and identifying extra attributes and values for its rows so that rows from different original tables can be distinguished. Specifically, we first define the notion of stitchable tables and identify collections of tables that can be stitched. Second, we design an effective algorithm for extracting hidden attributes that are essential for the stitching process and for aligning values of those attributes across tables to synthesize new columns. We also assign meaningful names to these synthesized columns. Experiments on real world tables demonstrate the effectiveness of our approach.

  1. [Barzilay and Lee, 2002] R. Barzilay and L. Lee. Boot- strapping lexical choice via multiple-sequence alignment. In Proceedings of the ACL-02 conference on Empiri- cal methods in natural language processing-Volume 10, pages 164-171. Association for Computational Linguis- tics, 2002.
  2. [Barzilay and Lee, 2003] R. Barzilay and L. Lee. Learning to paraphrase: An unsupervised approach using multiple- sequence alignment. In Proceedings of the 2003 Con- ference of the North American Chapter of the Associa- tion for Computational Linguistics on Human Language Technology-Volume 1, pages 16-23. Association for Com- putational Linguistics, 2003.
  3. [Bergroth et al., 2000] L. Bergroth, H. Hakonen, and T. Raita. A survey of longest common subsequence algo- rithms. In String Processing and Information Retrieval, 2000. SPIRE 2000. Proceedings. Seventh International Symposium on, pages 39-48. IEEE, 2000.
  4. [Cafarella et al., 2008a] M.J. Cafarella, A. Halevy, D.Z. Wang, E. Wu, and Y. Zhang. Webtables: exploring the power of tables on the web. Proceedings of the VLDB En- dowment, 1(1):538-549, 2008.
  5. [Cafarella et al., 2008b] M.J. Cafarella, A.Y. Halevy, Y. Zhang, D.Z. Wang, and E. Wu. Uncovering the relational web. WebDB, 2008.
  6. [Cafarella et al., 2009] M.J. Cafarella, A. Halevy, and N. Khoussainova. Data integration for the relational web. Proceedings of the VLDB Endowment, 2(1):1090-1101, 2009.
  7. [Crescenzi and Mecca, 2004] Valter Crescenzi and Giansal- vatore Mecca. Automatic information extraction from large websites. Journal of the ACM (JACM), 51(5):731- 779, 2004.
  8. [Das Sarma et al., 2012] A. Das Sarma, L. Fang, N. Gupta, A. Halevy, H. Lee, F. Wu, R. Xin, and C. Yu. Finding re- lated tables. In Proceedings of the 2012 international con- ference on Management of Data, pages 817-828. ACM, 2012.
  9. [Elmeleegy et al., 2009] H. Elmeleegy, J. Madhavan, and A. Halevy. Harvesting relational tables from lists on the web. Proceedings of the VLDB Endowment, 2(1):1078- 1089, 2009.
  10. [Gatterbauer and Bohunsky, 2006] W. Gatterbauer and P. Bohunsky. Table extraction using spatial reasoning on the css2 visual box model. In PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, volume 21, page 1313. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2006.
  11. [Gupta and Sarawagi, 2011] Rahul Gupta and Sunita Sarawagi. Joint training for open-domain extraction on the web: Exploiting overlap when supervision is limited. In WSDM, 2011.
  12. [Gusfield, 1997] D. Gusfield. Algorithms on strings, trees and sequences: computer science and computational biol- ogy. Cambridge University Press, 1997.
  13. [Lafferty et al., 2001] J. Lafferty, A. McCallum, and F.C.N. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. 2001.
  14. [Limaye et al., 2010] G. Limaye, S. Sarawagi, and S. Chakrabarti. Annotating and searching web ta- bles using entities, types and relationships. Proceedings of the VLDB Endowment, 3(1-2):1338-1347, 2010.
  15. [Milne and Witten, 2008] D. Milne and I.H. Witten. Learn- ing to link with wikipedia. In Proceedings of the 17th ACM conference on Information and knowledge management, pages 509-518. ACM, 2008.
  16. [Pasca and Van Durme, 2008] M. Pasca and B. Van Durme. Weakly-supervised acquisition of open-domain classes and class attributes from web documents and query logs. In Proceedings of the 46th Annual Meeting of the Associ- ation for Computational Linguistics (ACL-08), pages 19- 27, 2008.
  17. [Pimplikar and Sarawagi, 2012] Rakesh Pimplikar and Sunita Sarawagi. Answering table queries on the web using column keywords. In Proc. of the 38th Int'l Conference on Very Large Databases (VLDB), 2012.
  18. [Ratinov et al., 2011] L. Ratinov, D. Roth, D. Downey, and M. Anderson. Local and global algorithms for disam- biguation to wikipedia. In Proceedings of the Annual Meeting of the Association of Computational Linguistics (ACL), 2011.
  19. [Venetis et al., 2011] P. Venetis, A. Halevy, J. Madhavan, M. Pas ¸ca, W. Shen, F. Wu, G. Miao, and C. Wu. Recov- ering semantics of tables on the web. Proceedings of the VLDB Endowment, 4(9):528-538, 2011.
  20. [Wang and Jiang, 1994] L. Wang and T. Jiang. On the com- plexity of multiple sequence alignment. Journal of com- putational biology, 1(4):337-348, 1994.
  21. [Wang et al., 2012] Jingjing Wang, Haixun Wang, Zhongyuan Wang, and Kenny Qili Zhu. Understanding tables on the web. In ER, pages 141-155, 2012.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards