A search engine for natural language applications

ABSTRACT

Many modern natural language-processing applications utilize search engines to locate large numbers of Web documents or to compute statistics over the Web corpus. Yet Web search engines are designed and optimized for simple human queries---they are not well suited to support such applications. As a result, these applications are forced to issue millions of successive queries resulting in unnecessary search engine load and in slow applications with limited scalability.In response, this paper introduces the Bindings Engine (BE), which supports queries containing typed variables and string-processing functions. For example, in response to the query "powerful ‹noun›" BE will return all the nouns in its index that immediately follow the word "powerful", sorted by frequency. In response to the query "Cities such as ProperNoun(Head(‹NounPhrase›))", BE will return a list of proper nouns likely to be city names.BE's novel neighborhood index enables it to do so with O(k) random disk seeks and O(k) serial disk reads, where k is the number of non-variable terms in its query. As a result, BE can yield several orders of magnitude speedup for large-scale language-processing applications. The main cost is a modest increase in space to store the index. We report on experiments validating these claims, and analyze how BE's space-time tradeoff scales with the size of its index and the number of variable types. Finally, we describe how a BE-based application extracts thousands of facts from the Web at interactive speeds in response to simple user queries.

REFERENCES

• 1: Corpus Colossal. The Economist, Jan. 2005.
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Searching with numbers, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511501]
• 3: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 4: Dirk Bahle , Hugh E. Williams , Justin Zobel, Optimised phrase querying and browsing of large text databases, Proceedings of the 24th Australasian conference on Computer science, p.11-19, January 29-February 02, 2001, Gold Coast, Queensland, Australia
• 5: Dirk Bahle , Hugh E. Williams , Justin Zobel, Efficient phrase querying with an auxiliary index, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564415]
• 6: Eric Brill, Some advances in transformation-based part of speech tagging, Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), p.722-727, October 1994, Seattle, Washington, United States
• 7: Eric Brill , Susan Dumais , Michele Banko, An analysis of the AskMSR question-answering system, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.257-264, July 06, 2002 [doi>10.3115/1118693.1118726]
• 8: E. Brill, J. Lin, M. Banko, S. T. Dumais, and A. Y. Ng. Data-Intensive Question Answering. In TREC 2001 Proceedings, 2001.
• 9: A Fast Regular Expression Indexing Engine, Proceedings of the 18th International Conference on Data Engineering, p.419, February 26-March 01, 2002
• 10: 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]
• 11: Oren Etzioni , Michael Cafarella , Doug Downey , Ana-Maria Popescu , Tal Shaked , Stephen Soderland , Daniel S. Weld , Alexander Yates, Unsupervised named-entity extraction from the web: an experimental study, Artificial Intelligence, v.165 n.1, p.91-134, June 2005 [doi>10.1016/j.artint.2005.03.001]
• 12: A. Y. Halevy and J. Madhavan. Corpus-Based Knowledge Representation. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1567--1572, 2003.
• 13: Marti A. Hearst, Automatic acquisition of hyponyms from large text corpora, Proceedings of the 14th conference on Computational linguistics, August 23-28, 1992, Nantes, France [doi>10.3115/992133.992154]
• 14: Cody C. T. Kwok , Oren Etzioni , Daniel S. Weld, Scaling question answering to the Web, Proceedings of the 10th international conference on World Wide Web, p.150-161, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371973]
• 15: Jayant Madhavan , Philip A. Bernstein , AnHai Doan , Alon Halevy, Corpus-Based Schema Matching, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.57-68, April 05-08, 2005 [doi>10.1109/ICDE.2005.39]
• 16: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 17: A. O. Mendelzon, G. A. Mihalia, and T. Milo. Querying the World Wide Web. International Journal on Digital Libraries, 1996.
• 18: R. C. Miller and B. C. Myers. Lightweight Structured Text Processing. In Proceedings of 1999 USENIX Annual Technical Conference, pages 131--144, Monterey, CA, 1999.
• 19: John Prager , Eric Brown , Anni Coden , Dragomir Radev, Question-answering by predictive annotation, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.184-191, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345574]
• 20: Ellen Spertus , Lynn Andrea Stein, Squeal: a structured query language for the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.95-103, June 2000, Amsterdam, The Netherlands
• 21: Peter D. Turney, Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL, Proceedings of the 12th European Conference on Machine Learning, p.491-502, September 05-07, 2001
• 22: Peter D. Turney, Thumbs up or thumbs down?: semantic orientation applied to unsupervised classification of reviews, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073153]
• 23: H. E. Williams, J. Zobel, and P. Anderson. What's Next? Index Structures for Efficient Phrase Querying. In J. Roddick, editor, Proceedings on the Australasian Database Conference, pages 141--152, Auckland, New Zealand, 1999.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
corpus, indexing, information extraction, language, query, search engine, variables