Scatter/Gather: a cluster-based approach to browsing large document collections

ABSTRACT

Document clustering has not been well received as an information retrieval tool. Objections to its use fall into two main categories: first, that clustering is too slow for large corpora (with running time often quadratic in the number of documents); and second, that clustering does not appreciably improve retrieval.

We argue that these problems arise only when clustering is used in an attempt to improve conventional search techniques. However, looking at clustering as an information access tool in its own right obviates these objections, and provides a powerful new access paradigm. We present a document browsing technique that employs document clustering as its primary operation. We also present fast (linear time) clustering algorithms which support this interactive browsing paradigm.

References

1. 1.Chris Buckley and Alan F. Lewit. Optimizations of inverted vector searches. In Proceedings of the Eighth Annual International A CM SIGIR Conference on Research and Development in {nfoT'mat~on Retrieval, pages 97-110, 1985.
2. 2.W.B. Croft. Clustering large files of documents using the single-link method. Journal of the Amemcan Soczety for Informatzon Science, 28:341-344, 1977.
3. 3.A. E1-Hamdouchi and P. Willett. Hierarchical document clustering using Ward's method. In Proceedzngs of the N, nth InternatzonaI Conference on Research and Development in Informatzon Retrieval, pages 149-156, 1986.
4. 4.A. Grifiiths, H.C. Luckhurst, and P. Willett. Using inter-document similarity information in document retrieval systems. Journal of the American Society for Information Sczence, 37:3-11, 1986.
5. 5.Anil K. aain and Richard C. Dubes. Algorithms for Clustering Data. Pretice Hall, Engelwood Cliffs, N.J. 07632, 1988.
6. 6.N. aardine and C.J. van Rijsbergen. The use of hierarchical clustering in information retrieval. Informatzon Storage and Retrzeval, 7:217-240, 1971.
7. 7.O. Pedersen, D. R. Cutting, and a. w. Tukey. Snippet search: a single phrase approach to text access. In Proceedings of the 1991 Yoznt Statistical Meetings. American Statistical Association, 1991. Also available as Xerox PARC technical report SSL- 91-08.
8. 8.G. Salton. The SMART Retmeval System. Prentice- Hall, Englewood Cliffs, N.J., 1971.
9. 9.G. Salton and M. a. McGill. Introduction to Modern Information Retrieval. McGraw-Hill, 1983.
10. 10.R. Sibson. SLINK: an optimally efficient algorithm for the single link cluster method. Computer Journal, 16:30-34, 1973.
11. 11.C.J. van Rijsbergen. Information Retmeval. Butterworths, London, second edition, 1979.
12. 12.C.j. van Rijsbergen and W.B. Croft. Document clustering: An evaluation of some experiments with the Cranfield 1400 collection. Information Processing Management, 11:171-182, 1975.
13. 13.P. Willett. Document clustering using an inverted file approach. Journal of Informatzon Sczence, 2:223- 231, 1980.
14. 14.P. Willett. A fast procedure for the calculation of similarity coefficients in automatic classification. Informatzon Processzng ~ Management, 17:53-60, 1981.
15. 15.P. Willett. Recent trends in hierarchical document clustering: A critical review. Information Processing Management, 24(5):577-597, 1988.

Index Terms

• Information systems

  • Information retrieval

    • Information retrieval query processing

    • Retrieval models and ranking

• Theory of computation

  • Design and analysis of algorithms