Efficiently incorporating user feedback into information extraction and integration programs

ABSTRACT

Many applications increasingly employ information extraction and integration (IE/II) programs to infer structures from unstructured data. Automatic IE/II are inherently imprecise. Hence such programs often make many IE/II mistakes, and thus can significantly benefit from user feedback. Today, however, there is no good way to automatically provide and process such feedback. When finding an IE/II mistake, users often must alert the developer team (e.g., via email or Web form) about the mistake, and then wait for the team to manually examine the program internals to locate and fix the mistake, a slow, error-prone, and frustrating process.

In this paper we propose a solution for users to directly provide feedback and for IE/II programs to automatically process such feedback. In our solution a developer U uses hlog, a declarative IE/II language, to write an IE/II program P. Next, U writes declarative user feedback rules that specify which parts of P's data (e.g., input, intermediate, or output data) users can edit, and via which user interfaces. Next, the so-augmented program P is executed, then enters a loop of waiting for and incorporating user feedback. Given user feedback F on a data portion of P, we show how to automatically propagate F to the rest of P, and to seamlessly combine F with prior user feedback. We describe the syntax and semantics of hlog, a baseline execution strategy, and then various optimization techniques. Finally, we describe experiments with real-world data that demonstrate the promise of our solution.

REFERENCES

• 1: Philip A. Bernstein , Sergey Melnik , John E. Churchill, Incremental schema matching, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 2: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, ACM SIGMOD Record, v.15 n.2, p.61-71, June 1986
• 3: Philip Bohannon , Srujana Merugu , Cong Yu , Vipul Agarwal , Pedro DeRose , Arun Iyer , Ankur Jain , Vinay Kakade , Mridul Muralidharan , Raghu Ramakrishnan , Warren Shen, Purple SOX extraction management system, ACM SIGMOD Record, v.37 n.4, December 2008 [doi>10.1145/1519103.1519107]
• 4: Peter Buneman , Sanjeev Khanna , Wang Chiew Tan, Why and Where: A Characterization of Data Provenance, Proceedings of the 8th International Conference on Database Theory, p.316-330, January 04-06, 2001
• 5: Peter Buneman , Wang-Chiew Tan, Provenance in databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247646]
• 6: X. Chai, B.-Q. Vuong, A. Doan, and J. F. Naughton. Efficiently incorporating user feedback into information extraction and integration programs. Technical report. {Online} Available: http://www.cs.wisc.edu/~xchai/papers/hlog_report.pdf.
• 7: Fei Chen , AnHai Doan , Jun Yang , Raghu Ramakrishnan, Efficient Information Extraction over Evolving Text Data, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.943-952, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497503]
• 8: Fei Chen , Byron J. Gao , AnHai Doan , Jun Yang , Raghu Ramakrishnan, Optimizing complex extraction programs over evolving text data, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA [doi>10.1145/1559845.1559881]
• 9: Laura Chiticariu , Phokion G. Kolaitis , Lucian Popa, Interactive generation of integrated schemas, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376700]
• 10: Yingwei Cui , Jennifer Widom, Lineage Tracing for General Data Warehouse Transformations, Proceedings of the 27th International Conference on Very Large Data Bases, p.471-480, September 11-14, 2001
• 11: H. Cunningham, D. Maynard, K. Bontcheva, and V. Tablan. GATE: A framework and graphical development environment for robust NLP tools and applications. In ACL-02.
• 12: Pedro DeRose , Xiaoyong Chai , Byron J. Gao , Warren Shen , AnHai Doan , Philip Bohannon , Xiaojin Zhu, Building Community Wikipedias: A Machine-Human Partnership Approach, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.646-655, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497473]
• 13: 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
• 14: P. DeRose, W. Shen, F. Chen, Y. Lee, D. Burdick, A. Doan, and R. Ramakrishnan. DBLife: A community information management platform for the database research community. In CIDR-07.
• 15: AnHai Doan , Pedro Domingos , Alon Y. Halevy, Reconciling schemas of disparate data sources: a machine-learning approach, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.509-520, May 21-24, 2001, Santa Barbara, California, United States
• 16: AnHai Doan , Jeffrey F. Naughton , Raghu Ramakrishnan , Akanksha Baid , Xiaoyong Chai , Fei Chen , Ting Chen , Eric Chu , Pedro DeRose , Byron Gao , Chaitanya Gokhale , Jiansheng Huang , Warren Shen , Ba-Quy Vuong, Information extraction challenges in managing unstructured data, ACM SIGMOD Record, v.37 n.4, December 2008 [doi>10.1145/1519103.1519106]
• 17: A. Doan, R. Ramakrishnan, F. Chen, P. DeRose, Y. Lee, R. McCann, M. Sayyadian, and W. Shen. Community information management. IEEE Data Eng. Bull., 29(1), 2006.
• 18: 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]
• 19: Michael Franklin , Alon Halevy , David Maier, From databases to dataspaces: a new abstraction for information management, ACM SIGMOD Record, v.34 n.4, p.27-33, December 2005 [doi>10.1145/1107499.1107502]
• 20: 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]
• 21: J. Gray, R. A. Lorie, G. R. Putzolu, and I. L. Traiger. Granularity of locks and degrees of consistency in a shared data base. In IFIP-76.
• 22: Todd J. Green , Grigoris Karvounarakis , Zachary G. Ives , Val Tannen, Update exchange with mappings and provenance, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 23: Timothy Griffin , Leonid Libkin, Incremental maintenance of views with duplicates, ACM SIGMOD Record, v.24 n.2, p.328-339, May 1995
• 24: A. Gupta and I. S. Mumick. Maintenance of materialized views: Problems, techniques, and applications. Data Eng. Bulletin, 18(2), 1995.
• 25: Jiansheng Huang , Ting Chen , AnHai Doan , Jeffrey F. Naughton, On the provenance of non-answers to queries over extracted data, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453936]
• 26: Panagiotis G. Ipeirotis , Eugene Agichtein , Pranay Jain , Luis Gravano, To search or to crawl?: towards a query optimizer for text-centric tasks, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142504]
• 27: 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]
• 28: Gjergji Kasneci , Maya Ramanath , Fabian Suchanek , Gerhard Weikum, The YAGO-NAGA approach to knowledge discovery, ACM SIGMOD Record, v.37 n.4, December 2008 [doi>10.1145/1519103.1519110]
• 29: Y. Katsis, A. Deutsch, and Y. Papakonstantinou. Interactive source registration in community-oriented information integration. In VLDB-08.
• 30: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 31: Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
• 32: Frederick Reiss , Sriram Raghavan , Rajasekar Krishnamurthy , Huaiyu Zhu , Shivakumar Vaithyanathan, An Algebraic Approach to Rule-Based Information Extraction, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.933-942, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497502]
• 33: Sunita Sarawagi, Information Extraction, Foundations and Trends in Databases, v.1 n.3, p.261-377, March 2008 [doi>10.1561/1900000003]
• 34: Warren Shen , Pedro DeRose , Robert McCann , AnHai Doan , Raghu Ramakrishnan, Toward best-effort information extraction, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376718]
• 35: 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
• 36: Wensheng Wu , Clement Yu , AnHai Doan , Weiyi Meng, An interactive clustering-based approach to integrating source query interfaces on the deep Web, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007582]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Design, Management

Keywords:
incremental execution, information extraction, information integration, provenance, user feedback