Generation and search of clustered files

ABSTRACT

A classified, or clustered file is one where related, or similar records are grouped into classes, or clusters of items in such a way that all items within a cluster are jointly retrievable. Clustered files are easily adapted to broad and narrow search strategies, and simple file updating methods are available. An inexpensive file clustering method applicable to large files is given together with appropriate file search methods. An abstract model is then introduced to predict the retrieval effectiveness of various search methods in a clustered file environment. Experimental evidence is included to test the versatility of the model and to demonstrate the role of various parameters in the cluster search process.

REFERENCES

• 1: ANDERBERG, M.R. Cluster Analysis for Applications. Academic Press, New York, 1973.
• 2: J. Gary Augustson , Jack Minker, An Analysis of Some Graph Theoretical Cluster Techniques, Journal of the ACM (JACM), v.17 n.4, p.571-588, Oct. 1970 [doi>10.1145/321607.321608]
• 3: Frank B. Baker, Information Retrieval Based upon Latent Class Analysis, Journal of the ACM (JACM), v.9 n.4, p.512-521, Oct. 1962 [doi>10.1145/321138.321148]
• 4: BAYER, R. Symmetric binary B-trees: data structure and maintenance algorithms. Acta Infor. matica 1, 4 (1972), 290-306.
• 5: BAYER, R., AND MCCREmHT, E. Organization and maintenance of large ordered indices. Acta Informatica 1, 3 (1972), 173-189.
• 6: BORKO, H. Research in automatic generation of classification systems. Proc. AFIPS 1964 SJCC, Vol. 25, AFIPS Press, Montvale, N.J., 1964, pp. 529-536.
• 7: Harold Borko , Myrna Bernick, Automatic Document Classification, Journal of the ACM (JACM), v.10 n.2, p.151-162, April 1963 [doi>10.1145/321160.321165]
• 8: CROFT, W.B. Clustering large files of documents using the single link method. Comptr. Lab. Rep., Cambridge U., Cambridge, England, 1977.
• 9: CROVCH, D.M. Cluster analysis: bibliography. SIGIR Forum (ACM) 6, 3 (Fall 1973), 11-14.
• 10: CROUCH, D.B. A file organization and maintenance procedure for dynamic document collections. Inform. Processing and Manage. 11 (1975), 11-21.
• 11: DALe., A.G. Some clumping experiments for associative document retrieval. Amer. Documentation 16, 1 (Jan. 1965), 5-9.
• 12: DATTOLA, R.T. Experiments with a fast clustering algorithm for automatic classification. In The SMART Retrieval System--Experiments in Automatic Document Processing, G. Salton, Ed., Prentice-Hall, Englewood Cliffs, N.J., 1971, chap. 12.
• 13: DIDAY, E. The dynamic cluster method and sequentialization in nonhierarchical clustering. Int. J. Comptr. and Inform. Sci. 2, 1 (1973), 63-69.
• 14: DOYLE, L.B. Some compromises between word grouping and document grouping. In Proc. Syrup. Statist. Assoc. Methods for Mechanized Documentation, M.E. Stevens, V.E. Giuliaho, and L.B. Heilprin, Eds., Nat. Bur. Stand., Miscellaneous Pub. 269, Washington, D.C., pp. 15-24.
• 15: EVERITT, B.S. Cluster Analysis. Halstead Press, London, 1974.
• 16: S. Kumar, Semantic Clustering of Index Terms, Journal of the ACM (JACM), v.15 n.4, p.493-513, Oct. 1968 [doi>10.1145/321479.321480]
• 17: John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
• 18: JACKSOS, D.M. The construction of retrieval environments and pseudo-classification based on external relevance. Inform. Storage and Retrieval 6, 2 (June 1970), 187-219.
• 19: JARDINE, N., AND SIBSON, R. Mathematical Taxonomy. Wiley, New York, 1971.
• 20: JARDINE, N., AND VAN RIJSBERGEN, C.J. The use of hierarchic clustering in information retrieval. Inform. Storage and Retrieval 7, 5 (1971), 217-240.
• 21: JOHNSON, D.B., AND LAFUENTE, J.M. A controlled single pass algorithm with applications to multi-level clustering. Rep. No. ISR-17 to NSF, ComeU U., Ithaca, N.Y., 1970.
• 22: Barry Litofsky, Utility of automatic classification systems for information storage and retrieval, 1969
• 23: MARATHE, V., AND RXEBER, S. The single pass cluster method. Rep. No. ISR-16 to NSF, CorneU U., Ithaca, N.Y., 1969.
• 24: MINKER, J., WILSON, G.A., AND ZIMMERMAN, B.H. An evaluation of query expansion by the addition of clustered terms for a document retrieval system. Inform. Storage and Retrieval 8, 6 (Dec. 1972), 329-348.
• 25: NEEDHAM, R.M. Applications of the theory of clumps. Mechanical Translation 8, 3-4 (June 1965), 113-127.
• 26: NEEDHAM, R.M., AND SPARCK JONES, K. Keywords and clumps. J. Documentaton 20, 1 (March 1964}, 5-15.
• 27: PRICE, N., AND SCHIMINOVICH, S. A clustering experiment: first step towards a computergenerated classification scheme. Inform. Storage and Retrieval 4, 3 (Aug. 1968), 271-280.
• 28: Roccmo, J.J. Document retrieval systems--optimization and evaluation. Rep. No. ISR-10 to NSF, Harvard Comput. Lab., Cambridge, Mass., 1966.
• 29: James B. Rothnie, Jr. , Tomas Lozano, Attribute based file organization in a paged memory environment, Communications of the ACM, v.17 n.2, p.63-69, Feb. 1974 [doi>10.1145/360827.360831]
• 30: SALTOS, G. Experiments in automatic thesaurus construction for information retrieval. Information Processing 71, North-Holland Pub. Co., Amsterdam, 1972, pp. 115-123.
• 31: Gerard Salton, Dynamic information and library processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1975
• 32: SALTON, G., YANC, C.S., AND YU, C.T. A theory of term importance in automatic text analysis. J. ASIS 26, 1 (Jan.-Feb. 1975), 33-44.
• 33: SCHIMINOVlCH, S. Automatic classification and retrieval of documents by means of a bibliographic pattern discovery algorithm. Inform. Storage and Retrieval 6, 6 (May 1971), 417-435.
• 34: SNEATH, P.H.A., AND SOKAL, R.R. Numerical Taxonomy. W.H. Freeman, San Francisco, 1973.
• 35: SPARCK JONES, K. Automatic Keyword Classifications. Butterworths, London, 1971.
• 36: SPARCK JONES, K., AND JACKSON, D.M. The use of automatically obtained keyword classifications for information retrieval. Inform. Storage and Retrieval 5, 4 (Feb. 1970), 175-201.
• 37: SPARCK JONES, K., AND NEEDHAM, R.M. Automatic term classifications and retrieval. Inform. Storage and Retrieval 4, 2 (June 1968), 91-100.
• 38: VAN RIJSBERGEN, C.J. A fast hierarchical clustering algorithm. Comptr. J. I3, 3 (Aug. 1970), 324-326.
• 39: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 40: VASWANI, P.K.T. A technique for cluster emphasis and its application to automatic indexing. Information Processing 68, Vol. II, North-Holland Pub. Co., Amsterdam, 1969, pp. 1300-1303.
• 41: WHITE, L.J., et al. CIRC II Data Base Classifications. Final Tech. Rep. RADC-77-211, Ohio State U., Columbus, Ohio, June 1977.
• 42: WILLIAMSON, R.E. Real time document retrieval. Ph.D. Th., Cornell U., Ithaca, N.Y., 1974.
• 43: C. T. Yu , W. S. Luk , M. K. Siu, On the estimation of the number of desired records with respect to a given query, ACM Transactions on Database Systems (TODS), v.3 n.1, p.41-56, March 1978 [doi>10.1145/320241.320245]
• 44: C. T. Yu , G. Salton , M. K. Siu, Effective Automatic Indexing Using Term Addition and Deletion, Journal of the ACM (JACM), v.25 n.2, p.210-225, April 1978 [doi>10.1145/322063.322066]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

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

General Terms:
Design

Keywords:
automatic classification, cluster searching, clustered files, fast classification, file organization, probabilistic models