Toward best-effort information extraction

ABSTRACT

Current approaches to develop information extraction (IE) programs have largely focused on producing precise IE results. As such, they suffer from three major limitations. First, it is often difficult to execute partially specified IE programs and obtain meaningful results, thereby producing a long "debug loop". Second, it often takes a long time before we can obtain the first meaningful result (by finishing and running a precise IE program), thereby rendering these approaches impractical for time-sensitive IE applications. Finally, by trying to write precise IE programs we may also waste a significant amount of effort, because an approximate result -- one that can be produced quickly -- may already be satisfactory in many IE settings.

To address these limitations, we propose iFlex, an IE approach that relaxes the precise IE requirement to enable best-effort IE. In iFlex, a developer U uses a declarative language to quickly write an initial approximate IE program P with a possible-worlds semantics. Then iFlex evaluates P using an approximate query processor to quickly extract an approximate result. Next, U examines the result, and further refines P if necessary, to obtain increasingly more precise results. To refine P, U can enlist a next-effort assistant, which suggests refinements based on the data and the current version of P. Extensive experiments on real-world domains demonstrate the utility of the iFlex approach.

REFERENCES

• 1: E. Agichtein and S. Sarawagi. Scalable information extraction and integration. In KDD-06.
• 2: L. Antova, T. Jansen, C. Koch, and D. Olteanu. Fast and simple relational processing of uncertain data. In ICDE-08.
• 3: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 4: Surajit Chaudhuri , Gautam Das , Vivek Narasayya, Optimized stratified sampling for approximate query processing, ACM Transactions on Database Systems (TODS), v.32 n.2, p.9-es, June 2007 [doi>10.1145/1242524.1242526]
• 5: H. Cunningham, D. Maynard, K. Bontcheva, and V. Tablan. GATE: A framework and graphical development environment for robust NLP tools and applications. In ACL-2002.
• 6: Nilesh Dalvi , Dan Suciu, Answering queries from statistics and probabilistic views, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 7: Pedro DeRose , Warren Shen , Fei Chen , AnHai Doan , Raghu Ramakrishnan, Building structured web community portals: a top-down, compositional, and incremental approach, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 8: Y. Ding, D. W. Embley, and S. W. Liddle. Automatic creation and simplified querying of semantic Web content: An approach based on information-extraction ontologies. In ASWC-06.
• 9: Y. Ding, D. W. Embley, and S. W. Liddle. Enriching OWL with instance recognition semantics for automated semantic annotation. In ER Workshops, 2007.
• 10: Y. Ding, D. W. Embley, and S. W. Liddle. Enriching OWL with instance recognition semantics for automated semantic annotation. In ER Workshops, 2007.
• 11: AnHai Doan , Raghu Ramakrishnan , Shivakumar Vaithyanathan, Managing information extraction: state of the art and research directions, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142595]
• 12: David Ferrucci , Adam Lally, UIMA: an architectural approach to unstructured information processing in the corporate research environment, Natural Language Engineering, v.10 n.3-4, p.327-348, September 2004 [doi>10.1017/S1351324904003523]
• 13: Georg Gottlob , Christoph Koch , Robert Baumgartner , Marcus Herzog , Sergio Flesca, The Lixto data extraction project: back and forth between theory and practice, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055560]
• 14: Rahul Gupta , Sunita Sarawagi, Creating probabilistic databases from information extraction models, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 15: Joseph M. Hellerstein , Ron Avnur , Andy Chou , Christian Hidber , Chris Olston , Vijayshankar Raman , Tali Roth , Peter J. Haas, Interactive Data Analysis: The Control Project, Computer, v.32 n.8, p.51-59, August 1999 [doi>10.1109/2.781635]
• 16: Shawn R. Jeffery , Michael J. Franklin , Alon Y. Halevy, Pay-as-you-go user feedback for dataspace systems, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376701]
• 17: Robert Lee Mccann , Anhai Doan, Efficient data integration: automation, collaboration, and relaxation, University of Illinois at Urbana-Champaign, Champaign, IL, 2007
• 18: Binjamin Rozenfeld , Ronen Feldman, High-Performance Unsupervised Relation Extraction from Large Corpora, Proceedings of the Sixth International Conference on Data Mining, p.1032-1037, December 18-22, 2006 [doi>10.1109/ICDM.2006.82]
• 19: Anish Das Sarma , Omar Benjelloun , Alon Halevy , Jennifer Widom, Working Models for Uncertain Data, Proceedings of the 22nd International Conference on Data Engineering, p.7, April 03-07, 2006 [doi>10.1109/ICDE.2006.174]
• 20: W. Shen, P. DeRose, R. McCann, R. Ramakrishnan, and A. Doan. Towards best-effort information extraction. Technical report, 2008.
• 21: Warren Shen , AnHai Doan , Jeffrey F. Naughton , Raghu Ramakrishnan, Declarative information extraction using datalog with embedded extraction predicates, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.m MISCELLANEOUS

General Terms:
Experimentation, Languages

Keywords:
approximate, best-effort, information extraction