Incremental clustering for dynamic information processing

ABSTRACT

Clustering of very large document databases is useful for both searching and browsing. The periodic updating of clusters is required due to the dynamic nature of databases. An algorithm for incremental clustering is introduced. The complexity and cost analysis of the algorithm together with an investigation of its expected behavior are presented. Through empirical testing it is shown that the algorithm achieves cost effectiveness and generates statistically valid clusters that are compatible with those of reclustering. The experimental evidence shows that the algorithm creates an effective and efficient retrieval environment.

REFERENCES

• 1: ANDERBERG, M.R. Clustering Analysis for Applications. Academic Press, New York, 1973.
• 2: Nicholas J. Belkin , W. Bruce Croft, Retrieval techniques, Annual review of information science and technology, vol. 22, Elsevier Science Inc., New York, NY, 1987
• 3: Chris Buckley , Alan F. Lewit, Optimization of inverted vector searches, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.97-110, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253515]
• 4: CAN, F. Validation of clustering structures in information retrieval. In Proceedings of the Canadian Conference on Electrical and Computer Engineering (Montreal, Que., Sept., 1989). EIC, Montreal, Que., 1989, 572-575.
• 5: CAN, F. Experiments of incremental clustering. Working Paper 91-002, Dept. of Systems Analysis, Miami Univ., Oxford, Oh., Aug. 1991.
• 6: CAN, F. On the efficiency of best-match cluster searches. (Submitted for publication.)
• 7: CAN, F., AND DROCHAK II, N.D. Incremental clustering for dynamic document databases. In Proceedtngs of the 1990 Symposium on Applied Computing (Fayetteville, Ark., April 1990). IEEE, Los Alamitos, Calif., 1990, 61 67.
• 8: F. Can , E. Ozkarahan, A dynamic cluster maintenance system for information retrieval, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.123-131, June 03-05, 1987, New Orleans, Louisiana, United States [doi>10.1145/42005.42019]
• 9: F. Can , E. A. Ozkarahan, Dynamic cluster maintenance, Information Processing and Management: an International Journal, v.25 n.3, p.275-291, May 1989 [doi>10.1016/0306-4573(89)90045-9]
• 10: Fazli Can , Esen A. Ozkarahan, Concepts and effectiveness of the cover-coefficient-based clustering methodology for text databases, ACM Transactions on Database Systems (TODS), v.15 n.4, p.483-517, Dec. 1990 [doi>10.1145/99935.99938]
• 11: DIALOG. Dialog Database Catalog. Dialog Information Services Inc., 1989.
• 12: P. Willett , A. El-Hamdouchi, Comparison of hierarchic agglomerative clustering methods for document retrieval, The Computer Journal, v.32 n.3, p.220-227, June 1989 [doi>10.1093/comjnl/32.3.220]
• 13: Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
• 14: GRIFFITHS, h., LUCKHURST, C., AND WILLETT, P. Using interdocument similarity information in document retrieval systems. J. Am. Soc. Inf. Sci. 37, i (1986), 3 11.
• 15: HALL, J. L. Online Bibliographic Databases: A Directory and Sourcebook, 4th ed. Aslib, Great Britain, 1986.
• 16: H. S. Heaps, Information Retrieval: Computational and Theoretical Aspects, Academic Press, Inc., Orlando, FL, 1978
• 17: HODGES, J. L., ANn LEHMANN, E.L. Basic Concepts of Probabd~ty and Statistics. Holden-Day, San Fransisco, Calif., 1964.
• 18: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 19: J^RDINE, N., ~D V~a'~ RIJSBERGEN, C.J. The use of hierarchical clustering in information retrieval. Inf. Storage RetrLeval 7 (1971), 217-240.
• 20: Jakob Nielsen, Hypertext and hypermedia, Academic Press Professional, Inc., San Diego, CA, 1990
• 21: Gerard Salton, Dynamic information and library processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1975
• 22: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 23: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 24: G. Salton , A. Wong, Generation and search of clustered files, ACM Transactions on Database Systems (TODS), v.3 n.4, p.321-346, Dec. 1978 [doi>10.1145/320289.320291]
• 25: C. J. van Rijsbergen, The best-match problem in document retrieval, Communications of the ACM, v.17 n.11, p.648-649, Nov. 1974 [doi>10.1145/361179.361205]
• 26: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 27: Ellen Marie Voorhees, The effectiveness and efficiency of agglomerative hierarchic clustering in document retrieval, Cornell University, Ithaca, NY, 1986
• 28: Ellen M. Voorhees, The efficiency of inverted index and cluster searches, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.164-174, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253203]
• 29: 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]
• 30: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]
• 31: C. T. Yu , Y. T. Wang , C. H. Chen, Adaptive document clustering, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.197-203, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253525]

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.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Retrieval models

General Terms:
Algorithms, Design, Performance

Keywords:
best-match cluster search, cluster validity, cover coefficient, dynamic information retrieval environment, information retrieval, information retrieval effectiveness, information retrieval efficiency