Navigationaided retrieval

ABSTRACT

Users searching for information in hypermedia environments often perform querying followed by manual navigation. Yet, the conventional text/hypertext retrieval paradigm does not explicity take post-query navigation into account. This paper proposes a new retrieval paradigm, called navigation-aided retrieval (NAR), which treats both querying and navigation as first-class activities. In the NAR paradigm, querying is seen as a means to identify starting points for navigation, and navigation is guided based on information supplied in the query. NAR is a generalization of the conventional probabilistic information retrieval paradigm, which implicitly assumes no navigation takes place. This paper presents a formal model for navigation-aided retrieval, and reports empirical results that point to the real-world applicability of the model. The experiments were performed over a large Web corpus provided by TREC, using human judgments on a new rating scale developed for navigation-aided retrieval. In the case of ambiguous queries, the new retrieval model identifies good starting points for post-query navigation. For less ambiguous queries that need not be paired with navigation, the output closely matches that of a conventional retrieval system.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: M. J. Bates. The Design of Browsing and Berrypicking Techniques for the On-line Search Interface. Online Review, 13:407--431, 1989.
• 3: N. J. Belkin. Anomalous States of Knowledge as the Basis of Information Retrieval. Canadian Journal of Information Science, 5:133--143, 1980.
• 4: Krishna Bharat , Andrei Broder , Monika Henzinger , Puneet Kumar , Suresh Venkatasubramanian, The connectivity server: fast access to linkage information on the Web, Proceedings of the seventh international conference on World Wide Web 7, p.469-477, April 1998, Brisbane, Australia
• 5: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 6: Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of the seventh international conference on World Wide Web 7, p.65-74, April 1998, Brisbane, Australia
• 7: S. Chakrabarti, B. E. Dom, D. Gibson, R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Experiments in topic distillation. In Proc. SIGIR Workshop on Hypertext Information Retrieval on the Web, 1998.
• 8: Soumen Chakrabarti , Mukul Joshi , Vivek Tawde, Enhanced topic distillation using text, markup tags, and hyperlinks, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.208-216, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383990]
• 9: Ed H. Chi , Peter Pirolli , Kim Chen , James Pitkow, Using information scent to model user information needs and actions and the Web, Proceedings of the SIGCHI conference on Human factors in computing systems, p.490-497, March 2001, Seattle, Washington, United States [doi>10.1145/365024.365325]
• 10: Ed H. Chi , Adam Rosien , Gesara Supattanasiri , Amanda Williams , Christiaan Royer , Celia Chow , Erica Robles , Brinda Dalal , Julie Chen , Steve Cousins, The bloodhound project: automating discovery of web usability issues using the InfoScentπ simulator, Proceedings of the SIGCHI conference on Human factors in computing systems, April 05-10, 2003, Ft. Lauderdale, Florida, USA [doi>10.1145/642611.642699]
• 11: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 12: N. Craswell, D. Hawking, A. McLean, T. Upstill, R. Wilkinson, and M. Wu. TREC12 web and interactive track at CSIRO, 2003.
• 13: Nick Craswell , David Hawking , Stephen Robertson, Effective site finding using link anchor information, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.250-257, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383999]
• 14: Steve Cronen-Townsend , Yun Zhou , W. Bruce Croft, Predicting query performance, 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.564429]
• 15: Susan Dumais , Edward Cutrell , Hao Chen, Optimizing search by showing results in context, Proceedings of the SIGCHI conference on Human factors in computing systems, p.277-284, March 2001, Seattle, Washington, United States [doi>10.1145/365024.365116]
• 16: J. English, M. Hearst, R. Sinha, K. Swearingen, and K. Yee. Flexible Search and Browsing using Faceted Metadata. http://bailando.sims.berkeley.edu/papers/flamenco02.pdf, Jan. 2002.
• 17: D. Hawking. Overview of the TREC-9 web track.
• 18: David Hawking , Trystan Upstill , Nick Craswell, Toward better weighting of anchors, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009096]
• 19: B. He and I. Ounis. Inferring query performance using pre-retrieval predictors. In Proc. Symposium on String Processing and Information Retrieval, 2004.
• 20: T. Joachims, D. Freitag, and T. Mitchell. WebWatcher: A tour guide for the World Wide Web. In Proc. International Joint Conference on Artificial Intelligence (IJCAI), 1997.
• 21: David Kempe , Jon Kleinberg , Éva Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956769]
• 22: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 23: Victor Lavrenko , W. Bruce Croft, Relevance based language models, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.120-127, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383972]
• 24: H. Lieberman. Letizia: An agent That assists Web browsing. In Proc. IJCAI, 1995.
• 25: Joel C. Miller , Gregory Rae , Fred Schaefer , Lesley A. Ward , Thomas LoFaro , Ayman Farahat, Modifications of Kleinberg's HITS algorithm using matrix exponentiation and web log records, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.444-445, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384086]
• 26: D. Mladenic. Using text learning to help Web browsing. In Proc. SIGCHI, 2001.
• 27: MySQL DBMS. http://www.mysql.com/.
• 28: Christopher Olston , Ed H. Chi, ScentTrails: Integrating browsing and searching on the Web, ACM Transactions on Computer-Human Interaction (TOCHI), v.10 n.3, p.177-197, September 2003 [doi>10.1145/937549.937550]
• 29: P. Pirolli and S. Card. Information Foraging. Psychological Review, 1999.
• 30: F. Qiu, Z. Liu, and J. Cho. Analysis of user web traffic with a focus on search activities. In Proc. International Workshop on the Web and Databases (WebDB), June 2005.
• 31: S. Robertson, S. Walker, M. Hancock-Beaulieu, A. Gull, and M. Lau. Okapi at TREC. In Proc. TREC, 1992.
• 32: S. E. Robertson, S. Walker, M. Hancock-Beaulieu, A. Gull, and M. Lau. Okapi at TREC. In Text REtrieval Conference, 1992.
• 33: Vineet Sinha , David R. Karger, Magnet: supporting navigation in semistructured data environments, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066169]
• 34: Ian Soboroff, Do TREC web collections look like the web?, ACM SIGIR Forum, v.36 n.2, Fall 2002 [doi>10.1145/792550.792554]
• 35: K. Sparck Jones , S. Walker , S. E. Robertson, A probabilistic model of information retrieval: development and comparative experiments, Information Processing and Management: an International Journal, v.36 n.6, p.779-808, Nov.06.2000 [doi>10.1016/S0306-4573(00)00015-7]
• 36: Jaime Teevan , Christine Alvarado , Mark S. Ackerman , David R. Karger, The perfect search engine is not enough: a study of orienteering behavior in directed search, Proceedings of the SIGCHI conference on Human factors in computing systems, p.415-422, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985745]
• 37: Apache Tomcat. http://tomcat.apache.org/.
• 38: TREC-2003 Web Track: Guidelines. http://es.csiro.au/TRECWeb/guidelines 2003.html.
• 39: Richard Wheeldon , Mark Levene, The Best Trail Algorithm for Assisted Navigation of Web Sites, Proceedings of the First Conference on Latin American Web Congress, p.166, November 10-12, 2003
• 40: Oren Zamir , Oren Etzioni, Web document clustering: a feasibility demonstration, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.46-54, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290956]
• 41: Hua-Jun Zeng , Qi-Cai He , Zheng Chen , Wei-Ying Ma , Jinwen Ma, Learning to cluster web search results, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009030]

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation

Keywords:
browsing, link analysis, navigation, underspecified search tasks, web search