Searching with context

ABSTRACT

Contextual search refers to proactively capturing the information need of a user by automatically augmenting the user query with information extracted from the search context; for example, by using terms from the web page the user is currently browsing or a file the user is currently editing.We present three different algorithms to implement contextual search for the Web. The first, it query rewriting (QR), augments each query with appropriate terms from the search context and uses an off-the-shelf web search engine to answer this augmented query. The second, rank-biasing (RB), generates a representation of the context and answers queries using a custom-built search engine that exploits this representation. The third, iterative filtering meta-search (IFM), generates multiple subqueries based on the user query and appropriate terms from the search context, uses an off-the-shelf search engine to answer these subqueries, and re-ranks the results of the subqueries using rank aggregation methods.We extensively evaluate the three methods using 200 contexts and over 24,000 human relevance judgments of search results. We show that while QR works surprisingly well, the relevance and recall can be improved using RB and substantially more using IFM. Thus, QR, RB, and IFM represent a cost-effective design spectrum for contextual search.

REFERENCES

• 1: K. Ali, C. Chang, and Y. F. Juan. Exploring cost-effective approaches to human evaluation of search engine relevance. In Proceedings of the 27th European Conference on Information Retrieval (ECIR), pages 360--374, 2005.
• 2: N. J. Belkin, R. Oddy, and H. M. Brooks. ASK for Information Retrieval: Part I. Background and Theory, Part II. Results of a Design Study. Journal of Documentation, 38(3):61--71, 145--164, 1982.
• 3: Daniel M. Bikel , Richard Schwartz , Ralph M. Weischedel, An Algorithm that Learns What‘s in a Name, Machine Learning, v.34 n.1-3, p.211-231, Feb. 1999 [doi>10.1023/A:1007558221122]
• 4: Daniel Billsus , David M. Hilbert , Dan Maynes-Aminzade, Improving proactive information systems, Proceedings of the 10th international conference on Intelligent user interfaces, January 10-13, 2005, San Diego, California, USA [doi>10.1145/1040830.1040869]
• 5: A. Borthwick, J. Sterling, E. Agichtein, and R. Grishman. Exploiting diverse knowledge sources via maximum entropy in named entity recognition. In Proceedings of the 6th Workshop on Very Large Corpora, 1998.
• 6: J. Budzik and K. Hammond. Watson: Anticipating and contextualizing information needs. In Proceedings of the 62nd Annual Meeting of the American Society for Information Science (ASIS), pages 727--740, 1999.
• 7: M. K. C.W. Cleverdon, J. Mills. Factors determining the performance of indexing systems. Volume I - Design, Volume II - Test Results, ASLIB Cranfield Project, Reprinted in Sparck Jones & Willett, Readings in Information Retrieval, 1966.
• 8: Mary Czerwinski , Susan Dumais , George Robertson , Susan Dziadosz , Scott Tiernan , Maarten van Dantzich, Visualizing implicit queries for information management and retrieval, Proceedings of the SIGCHI conference on Human factors in computing systems: the CHI is the limit, p.560-567, May 15-20, 1999, Pittsburgh, Pennsylvania, United States [doi>10.1145/302979.303158]
• 9: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 10: O. Etzioni. Moving up the information food chain: Deploying softbots on the world wide web. In Proceedings of the 13th National Conference on Artificial Intelligence and the 8th Conference on Innovative Applications of Artificial Intelligence, pages 1322--1326, 1996.
• 11: R. Fagin, R. Kumar, M. Mahdian, D. Sivakumar, and E. Vee. Rank aggregation: An algorithmic perspective. Manuscript, 2005.
• 12: Ronald Fagin , Ravi Kumar , Kevin S. McCurley , Jasmine Novak , D. Sivakumar , John A. Tomlin , David P. Williamson, Searching the workplace web, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775204]
• 13: Ronald Fagin , Ravi Kumar , D. Sivakumar, Efficient similarity search and classification via rank aggregation, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872795]
• 14: Placing search in context: the concept revisited, ACM Transactions on Information Systems (TOIS), v.20 n.1, p.116-131, January 2002 [doi>10.1145/503104.503110]
• 15: A. Goker. Capturing information need by learning user context. In Proceedings of the 16th International Joint Conference in Artificial Intelligence: Learning About Users Workshop, pages 21--27, 1999.
• 16: Monika Henzinger , Bay-Wei Chang , Brian Milch , Sergey Brin, Query-free news search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775154]
• 17: A. E. Howe and D. Dreilinger. SAVVYSEARCH: A metasearch engine that learns which search engines to query. AI Magazine, 18(2):19--25, 1997.
• 18: Reiner Kraft , Farzin Maghoul , Chi Chao Chang, Y!Q: contextual search at the point of inspiration, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099746]
• 19: Reiner Kraft , Raymie Stata, Finding Buying Guides with a Web Carnivore, Proceedings of the First Conference on Latin American Web Congress, p.84, November 10-12, 2003
• 20: Reiner Kraft , Jason Zien, Mining anchor text for query refinement, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988763]
• 21: S. Lawrence. Context in web search. IEEE Data Engineering Bulletin, 23(3):25--32, 2000.
• 22: Weiyi Meng , Clement Yu , King-Lup Liu, Building efficient and effective metasearch engines, ACM Computing Surveys (CSUR), v.34 n.1, p.48-89, March 2002 [doi>10.1145/505282.505284]
• 23: B. Rhodes and T. Starner. The remembrance agent: A continuously running automated information retrieval system. In Proceedings of 1st International Conference on the Practical Application of Intelligent Agents and Multi Agent Technology (PAAM), pages 487--495, 1996.
• 24: E. Selberg and O. Etzioni. The MetaCrawler Architecture for Resource Aggregation on the Web. IEEE Expert, 12(1):8--14, 1997.
• 25: Raymie Stata , Krishna Bharat , Farzin Maghoul, The term vector database: fast access to indexing terms for Web pages, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.247-255, June 2000
• 26: C. T. Yu , K. Lam , G. Salton, Term Weighting in Information Retrieval Using the Term Precision Model, Journal of the ACM (JACM), v.29 n.1, p.152-170, Jan. 1982 [doi>10.1145/322290.322300]

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.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Experimentation

Keywords:
contextual search, meta-search, rank aggregation, specialized search engines, web search