Optimizing complex extraction programs over evolving text data

ABSTRACT

Most information extraction (IE) approaches have considered only static text corpora, over which we apply IE only once. Many real-world text corpora however are dynamic. They evolve over time, and so to keep extracted information up to date we often must apply IE repeatedly, to consecutive corpus snapshots. Applying IE from scratch to each snapshot can take a lot of time. To avoid doing this, we have recently developed Cyclex, a system that recycles previous IE results to speed up IE over subsequent corpus snapshots. Cyclex clearly demonstrated the promise of the recycling idea. The work itself however is limited in that it considers only IE programs that contain a single IE ``blackbox.'' In practice, many IE programs are far more complex, containing multiple IE blackboxes connected in a compositional ``workflow.''

In this paper, we present Delex, a system that removes the above limitation. First we identify many difficult challenges raised by Delex, including modeling complex IE programs for recycling purposes, implementing the recycling process efficiently, and searching for an optimal execution plan in a vast plan space with different recycling alternatives. Next we describe our solutions to these challenges. Finally, we describe extensive experiments with both rule-based and learning-based IE programs over two real-world data sets, which demonstrate the utility of our approach.

REFERENCES

• 1: http://langrid.nict.go.jp.
• 2: E. Agichtein and S. Sarawagi. Scalable information extraction and integration (tutorial). KDD-06.
• 3: K. Beyer, V. Ercegovac, R. Krishnamurthy, S. Raghavan, J. Rao, F. Reiss, E. J. Shekita, D. Simmen, S. Tata, S. Vaithyanathan, and H. Zhu. Towards a scalable enterprise content analytics platform. IEEE Data Eng. Bull., 32(1):28--35, 2009.
• 4: B. Bhattacharjee, V. Ercegovac, J. Glider, R. Golding, G. Lohman, V. Markl, H. Pirahesh, J. Rao, R. Rees, F. Reiss, E. Shekita, and G. Swart. Impliance: A next generation information management appliance. CIDR-07.
• 5: Yuhan Cai , Xin Luna Dong , Alon Halevy , Jing Michelle Liu , Jayant Madhavan, Personal information management with SEMEX, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066289]
• 6: 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]
• 7: F. Chen, B. J. Gao, A. Doan, J. Yang, and R. Ramakrishnan. Optimizing complex extraction programs over evolving text data. Technical report, UW-Madison, 2009. Availableat http://www.cs.wisc.edu/~fchen/delex-tr.pdf
• 8: J. Cho and H. Garcia-Molina. Effective page refresh policies for web crawlers. TODS-03.
• 9: Eric Chu , Akanksha Baid , Ting Chen , AnHai Doan , Jeffrey Naughton, A relational approach to incrementally extracting and querying structure in unstructured data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 10: W. Cohen and A. McCallum. Information extraction from the world wide web(tutorial). KDD-03.
• 11: H. Cunningham, D. Maynard, K. Bontcheva, and V. Tablan. GATE:A framework and graphical development environment for robust NLP tools and applications. ACL-02.
• 12: 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
• 13: 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 (demo). CIDR-07.
• 14: 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]
• 15: 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]
• 16: Jenny Edwards , Kevin McCurley , John Tomlin, An adaptive model for optimizing performance of an incremental web crawler, Proceedings of the 10th international conference on World Wide Web, p.106-113, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371960]
• 17: 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]
• 18: Ashish Gupta , Iderpal Singh Mumick, Materialized views: techniques, implementations, and applications, MIT Press, Cambridge, MA, 1999
• 19: M. Herscovici, R. Lempel, and S. Yogev. Efficient indexing of versioned document sequences. ECIR-07.
• 20: 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]
• 21: A. Jain, A. Doan, and L. Gravano. SQL queries over unstructured text batabases. ICDE-07.
• 22: 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]
• 23: Lipyeow Lim , Min Wang , Sriram Padmanabhan , Jeffrey Scott Vitter , Ramesh Agarwal, Dynamic maintenance of web indexes using landmarks, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775167]
• 24: E. Myers. An O(ND)difference algorithm and its variations. Algorithmica, 1(1):251--256, 1986.
• 25: 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]
• 26: Sunita Sarawagi, Information Extraction, Foundations and Trends in Databases, v.1 n.3, p.261-377, March 2008 [doi>10.1561/1900000003]
• 27: Sandeepkumar Satpal , Sunita Sarawagi, Domain Adaptation of Conditional Probability Models Via Feature Subsetting, Proceedings of the 11th European conference on Principles and Practice of Knowledge Discovery in Databases, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74976-9_23]
• 28: 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
• 29: D. S. Weld, F. Wu, E. Adar, S. Amershi, J. Fogarty, R. Hoffmann, K. Patel, and M. Skinner. Intelligence in wikipedia. AAAI-08.
• 30: Fei Wu , Daniel S. Weld, Autonomously semantifying wikipedia, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321449]
• 31: Jiangong Zhang , Torsten Suel, Efficient search in large textual collections with redundancy, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242628]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Design, Experimentation, Performance

Keywords:
evolving text, information extraction, optimization