Building query optimizers for information extraction: the SQoUT project

ABSTRACT

Text documents often embed data that is structured in nature. This structured data is increasingly exposed using information extraction systems, which generate structured relations from documents, introducing an opportunity to process expressive, structured queries over text databases. This paper discusses our SQoUT1 project, which focuses on processing structured queries over relations extracted from text databases. We show how, in our extraction-based scenario, query processing can be decomposed into a sequence of basic steps: retrieving relevant text documents, extracting relations from the documents, and joining extracted relations for queries involving multiple relations. Each of these steps presents different alternatives and together they form a rich space of possible query execution strategies. We identify execution efficiency and output quality as the two critical properties of a query execution, and argue that an optimization approach needs to consider both properties. To this end, we take into account the userspecified requirements for execution efficiency and output quality, and choose an execution strategy for each query based on a principled, cost-based comparison of the alternative execution strategies.

REFERENCES

• 1: Eugene Agichtein , Luis Gravano, Snowball: extracting relations from large plain-text collections, Proceedings of the fifth ACM conference on Digital libraries, p.85-94, June 02-07, 2000, San Antonio, Texas, United States [doi>10.1145/336597.336644]
• 2: E. Agichtein and L. Gravano. Querying text databases for efficient information extraction. In ICDE, 2003.
• 3: Sergey Brin, Extracting Patterns and Relations from the World Wide Web, Selected papers from the International Workshop on The World Wide Web and Databases, p.172-183, March 27-28, 1998
• 4: Mary Elaine Califf , Raymond J. Mooney, Relational learning of pattern-match rules for information extraction, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.328-334, July 18-22, 1999, Orlando, Florida, United States
• 5: W. Cohen and A. McCallum. Information extraction from the World Wide Web (tutorial). In KDD, 2003.
• 6: Hamish Cunningham , Diana Maynard , Kalina Bontcheva , Valentin Tablan, GATE: an architecture for development of robust HLT applications, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073112]
• 7: D. Downey, O. Etzioni, and S. Soderland. A probabilistic model of redundancy in information extraction. In IJCAI, 2005.
• 8: Oren Etzioni , Michael Cafarella , Doug Downey , Stanley Kok , Ana-Maria Popescu , Tal Shaked , Stephen Soderland , Daniel S. Weld , Alexander Yates, Web-scale information extraction in knowitall: (preliminary results), Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988687]
• 9: 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]
• 10: 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]
• 11: Panagiotis G. Ipeirotis , Eugene Agichtein , Pranay Jain , Luis Gravano, Towards a query optimizer for text-centric tasks, ACM Transactions on Database Systems (TODS), v.32 n.4, p.21-es, November 2007 [doi>10.1145/1292609.1292611]
• 12: A. Jain, A. Doan, and L. Gravano. Optimizing SQL queries over text databases. In ICDE, 2008.
• 13: Alpa Jain , Panagiotis G. Ipeirotis, A quality-aware optimizer for information extraction, ACM Transactions on Database Systems (TODS), v.34 n.1, p.1-48, April 2009 [doi>10.1145/1508857.1508862]
• 14: A. Jain, P. G. Ipeirotis, A. Doan, and L. Gravano. Join optimization of information extraction output: Quality matters! In ICDE, 2009. To appear.
• 15: A. Jain and D. Srivastava. Exploring a few good tuples from text databases. In ICDE, 2009. To appear.
• 16: Imran R. Mansuri , Sunita Sarawagi, Integrating Unstructured Data into Relational Databases, Proceedings of the 22nd International Conference on Data Engineering, p.29, April 03-07, 2006 [doi>10.1109/ICDE.2006.83]
• 17: M. Paşca, D. Lin, J. Bigham, A. Lifchits, and A. Jain. Organizing and searching the world wide web of facts - step one: The one-million fact extraction challenge. In WWW, 2007.
• 18: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill Science/Engineering/Math, 2002
• 19: F. Reiss, S. Raghavan, R. Krishnamurthy, H. Zhu, and S. Vaithyanathan. An algebraic approach to rule-based information extraction. In ICDE, 2008.
• 20: 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
• 21: Victor S. Sheng , Foster Provost , Panagiotis G. Ipeirotis, Get another label? improving data quality and data mining using multiple, noisy labelers, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401965]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Management, Performance