Organization of Clustered Files for Consecutive Retrieval

J. S. Deogun, V. V. Raghavan, T. K.W. Tsou

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

This paper studies the problem of storing single-level and multilevel clustered files. Necessary and sufficient conditions for a single-level clustered file to have the consecutive retrieval property (CRP) are developed. A linear time algorithm to test the CRP for a given clustered file and to identify the proper arrangement of objects, if CRP exists, is presented. For the single-level clustered files that do not have CRP, it is shown that the problem of identifying a storage organization with minimum redundancy is NP-complete. Consequently, an efficient heuristic algorithm to generate a good storage organization for such files is developed. Furthermore, it is shown that, for certain types of multilevel clustered files, there exists a storage organization such that the objects in each cluster, for all clusters in each level of the clustering, appear in consecutive locations.

Original languageEnglish (US)
Pages (from-to)646-671
Number of pages26
JournalACM Transactions on Database Systems (TODS)
Volume9
Issue number4
DOIs
StatePublished - Dec 5 1984

Keywords

  • NP-complete
  • Single-level clustered files
  • consecutive retrieval property
  • heuristic algorithm
  • minimum redundancy organization
  • multilevel clustered files
  • overlapping and nonoverlapping clustering

ASJC Scopus subject areas

  • Information Systems

Fingerprint Dive into the research topics of 'Organization of Clustered Files for Consecutive Retrieval'. Together they form a unique fingerprint.

  • Cite this