Scalable ad-hoc entity extraction from text collections

ABSTRACT

Supporting entity extraction from large document collections is important for enabling a variety of important data analysis tasks. In this paper, we introduce the "ad-hoc" entity extraction task where entities of interest are constrained to be from a list of entities that is specific to the task. In such scenarios, traditional entity extraction techniques that process all the documents for each ad-hoc entity extraction task can be significantly expensive. In this paper, we propose an efficient approach that leverages the inverted index on the documents to identify the subset of documents relevant to the task and processes only those documents. We demonstrate the efficiency of our techniques on real datasets.

REFERENCES

• 1: E. Agichtein and L. Gravano. Querying text databases for efficient information extraction. In Proceedings of ICDE Conference, 2003.
• 2: A. Agresti. An introduction, to categorical data analysis. Wiley, 2007.
• 3: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 4: D. E. Appelt and D. Israel. Introduction to Information Extraction Technology. IJCAI-99 Tutorial, 1999.
• 5: Arvind Arasu , Venkatesh Ganti , Raghav Kaushik, Efficient exact set-similarity joins, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 6: Michael J. Cafarella , Oren Etzioni, A search engine for natural language applications, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060811]
• 7: Kaushik Chakrabarti , Surajit Chaudhuri , Venkatesh Ganti , Dong Xin, An efficient filter for approximate membership checking, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376697]
• 8: Amit Chandel , P. C. Nagesh , Sunita Sarawagi, Efficient Batch Top-k Search for Dictionary-based Entity Recognition, Proceedings of the 22nd International Conference on Data Engineering, p.28, April 03-07, 2006 [doi>10.1109/ICDE.2006.55]
• 9: Surajit Chaudhuri , Prasanna Ganesan , Sunita Sarawagi, Factorizing complex predicates in queries to exploit indexes, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872802]
• 10: William W. Cohen , Sunita Sarawagi, Exploiting dictionaries in named entity extraction: combining semi-Markov extraction processes and data integration methods, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014065]
• 11: 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]
• 12: Ralph Grishman, Information Extraction: Techniques and Challenges, International Summer School on Information Extraction: A Multidisciplinary Approach to an Emerging Information Technology, p.10-27, January 1997
• 13: 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]
• 14: H. Jerry, R. Douglas, E. Appelt, J. Bear, D. Israel, M. Kameyama, M. Stickel, and M. Tyson. Fastus: A cascaded finite-state transducer for extracting information from natural-language text, 1996.
• 15: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 16: Sunita Sarawagi , Alok Kirpal, Efficient set joins on similarity predicates, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007652]
• 17: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 18: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms, Design, Performance