Answering relationship queries on the web

ABSTRACT

Finding relationships between entities on the Web, e.g., the connections between different places or the commonalities of people, is a novel and challenging problem. Existing Web search engines excel in keyword matching and document ranking, but they cannot well handle many relationship queries. This paper proposes a new method for answering relationship queries on two entities. Our method first respectively retrieves the top Web pages for either entity from a Web search engine. It then matches these Web pages and generates an ordered list of Web page pairs. Each Web page pair consists of one Web page for either entity. The top ranked Web page pairs are likely to contain the relationships between the two entities. One main challenge in the ranking process is to effectively filter out the large amount of noise in the Web pages without losing much useful information. To achieve this, our method assigns appropriate weights to terms in Web pages and intelligently identifies the potential connecting terms that capture the relationships between the two entities. Only those top potential connecting terms with large weights are used to rank Web page pairs. Finally, the top ranked Web page pairs are presented to the searcher. For each such pair, the query terms and the top potential connecting terms are properly highlighted so that the relationships between the two entities can be easily identified. We implemented a prototype on top of the Google search engine and evaluated it under a wide variety of query scenarios. The experimental results show that our method is effective at finding important relationships with low overhead.

REFERENCES

• 1: http://www.google.com/apis (Google APIs), 2005.
• 2: http://www.itl.nist.gov/iaui/894.02/projects/aquaint (AQUAINT), 2005.
• 3: S. Blair-Goldensohn, K. McKeown, and A. H. Schlaikjer. Answering Definitional Questions: a Hybrid Approach. New Directions in Question Answering 2004: 47--58.
• 4: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 5: Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1467-1479, May 17, 1999
• 6: Daniela Florescu , Alon Levy , Alberto Mendelzon, Database techniques for the World-Wide Web: a survey, ACM SIGMOD Record, v.27 n.3, p.59-74, Sept. 1, 1998 [doi>10.1145/290593.290605]
• 7: http://www.google.com (Google), 2005.
• 8: Taher H. Haveliwala , Aristides Gionis , Dan Klein , Piotr Indyk, Evaluating strategies for similarity search on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511502]
• 9: Sanda Harabagiu , Finley Lacatusu , Andrew Hickl, Answering complex questions with random walk models, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148211]
• 10: D. Mahler. Holistic Query Expansion Using Graphical Models. New Directions in Question Answering 2004: 203--214.
• 11: Mark T. Maybury, New Directions in Question Answering, AAAI Press, 2004
• 12: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 13: M. F. Porter. An Algorithm for Suffix Stripping. Program 14(3): 130--137, 1980.
• 14: J. Prange. Making the Case for Advanced Question Answering. Keynote Speech to Pragmatics of Question Answering Workshop at HLT/NAACL 2004.
• 15: http://trec.nist.gov/data/qa/t2005_qadata.html (QA Collections of TREC), 2005.
• 16: Getting answers to natural language questions on the web, Journal of the American Society for Information Science and Technology, v.53 n.5, p.359-364, May 2002 [doi>10.1002/asi.10053]
• 17: S. E. Robertson, S. Walker, and M. Hancock-Beaulieu. Okapi at TREC-7: Automatic Ad Hoc, Filtering, VLC and Interactive. TREC 1998: 199--210.
• 18: A. Singhal. Modern Information Retrieval: A Brief Overview. IEEE Data Eng. Bull. 24(4): 35--43, 2001.
• 19: N. R. Smalheiser. The Arrowsmith Project: 2005 Status Report. Discovery Science 2005: 26--43.
• 20: SMART Stopword List. http://www.lextek.com/manuals/onix/stopwords2.html, 2006.
• 21: Padmini Srinivasan, Text mining: generating hypotheses from MEDLINE, Journal of the American Society for Information Science and Technology, v.55 n.5, p.396-413, March 2004 [doi>10.1002/asi.10389]
• 22: Neel Sundaresan , Jeonghee Yi, Mining the Web for relations, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.699-711, June 2000
• 23: Pang-Ning Tan , Vipin Kumar , Jaideep Srivastava, Indirect Association: Mining Higher Order Dependencies in Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.632-637, September 13-16, 2000
• 24: http://trec.nist.gov/pubs/trec14/t14_proceedings.html. TREC 2005 Proceedings (relationship task in the QA track).

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
relationship query, web search