Evaluating document clustering for interactive information retrieval

ABSTRACT

We consider the problem of organizing and browsing the top ranked portion of the documents returned by an information retrieval system. We study the effectiveness of a document organization in helping a user to locate the relevant material among the retrieved documents as quickly as possible. In this context we examine a set of clustering algorithms and experimentally show that a clustering of the retrieved documents can be significantly more effective than traditional ranked list approach. We also show that the clustering approach can be as effective as the interactive relevance feedback based on query expansion while retaining an important advantage -- it provides the user with a valuable sense of control over the feedback process.

REFERENCES

• 1: James Allan, Incremental relevance feedback for information filtering, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.270-278, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243274]
• 2: James Allan, Building hypertext using information retrieval, Information Processing and Management: an International Journal, v.33 n.2, p.145-159, March 1997 [doi>10.1016/S0306-4573(96)00059-3]
• 3: J. Allan, J. Callan, W. B. Croft, L. Ballesteros, D. Byrd, R. Swan, and J. Xu. Inquery does battle with TREG6. In Sixth Tat REtrievol Conference (TREC-G), pages 16(t206, 1998.
• 4: A. Bookstein. Information retrieval: A sequential learning process. Journal of the American Society for Information Science, 34(5):331-342, 1983.
• 5: W. B. Croft. OrganGing and Searching Large Files of Documents. PhD thesis, University of Cambridge, October 1978.
• 6: W. B. Croft , R. H. Thompson, I3R: a new approach to the design of document retrieval systems, Journal of the American Society for Information Science, v.38 n.6, p.389-404, Nov. 1987 [doi>10.1002/(SICI)1097-4571(198711)38:6<389::AID-ASI1>3.0.CO;2-4]
• 7: Douglass R. Cutting , David R. Karger , Jan O. Pedersen, Constant interaction-time scatter/gather browsing of very large document collections, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.126-134, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160706]
• 8: David Dubin, Document analysis for visualization, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.199-204, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215360]
• 9: Google. http://VVV.gOOglB.com/.
• 10: D. Harman and E. Voorheq editors. The Sh Tat REtvial Conference (TREC-6). NIST, 1998.
• 11: Marti A. Hearst , Jan O. Pedersen, Reexamining the cluster hypothesis: scatter/gather on retrieval results, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.76-84, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243216]
• 12: Jürgen Koenemann , Nicholas J. Belkin, A case for interaction: a study of interactive information retrieval behavior and effectiveness, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.205-212, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/238386.238487]
• 13: Eric Lagergren , Paul Over, Comparing interactive information retrieval systems across sites: the TREC-6 interactive track matrix experiment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.164-172, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290986]
• 14: G. N. Lance and W. T. Williams. A general theory of classificatory sorting strategies: 1. hierarchical systems. Computer Journal, 9:373-380, 1967.
• 15: Anton Leuski, Relevance and reinforcement in interactive browsing, Proceedings of the ninth international conference on Information and knowledge management, p.119-126, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354809]
• 16: Anton V. Leuski , James Allan, Interactive information organization: techniques and evaluation, 2001
• 17: A. Leuski and J. Allan. Evaluating a visual navigation system for a digital library. International Journal on Digital Libraries, 3(2):170--184, 2000.
• 18: A. Leuski and J. Allan. Improving interactive retrieval by combining ranked lists and clustering. In Proceedings of RIAO'2000, pages 6655681, April 2000.
• 19: A. Leuski and W. B. Croft. An evaluation of techniques for clustering search results. Technical Report IR-76, Department of Computer Science, University of Massachusetts, Amherst, 1996.
• 20: David D. Lewis, An evaluation of phrasal and clustered representations on a text categorization task, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.37-50, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133172]
• 21: B. Mirkin. Mathematical Classification and Clustering. Kluwer, 1996.
• 22: Northern light. http: //www. northernlight. corn/.
• 23: S. E. Robertson, S. Walker, S. Jones, M. M. Hancock-Beaulieu, and M. Gatford. Okapi at TRECS. In D. Harman and E. Voorhees, editors, Third Text REtrieval Conference (TREC-3). NIST, 1995.
• 24: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 25: Howard Turtle , W. Bruce Croft, Evaluation of an inference network-based retrieval model, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.187-222, July 1991 [doi>10.1145/125187.125188]
• 26: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 27: Ellen M. Voorhees, The cluster hypothesis revisited, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.188-196, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253524]
• 28: Peter Willett, Recent trends in hierarchic document clustering: a critical review, Information Processing and Management: an International Journal, v.24 n.5, p.577-597, 1988 [doi>10.1016/0306-4573(88)90027-1]
• 29: Jinxi Xu , W. Bruce Croft, Query expansion using local and global document analysis, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.4-11, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243202]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation; Relevance feedback

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.5 Document Capture
          Subjects: Document analysis

General Terms:
Algorithms, Design, Performance