Heuristic reorganization of clustered files

Peter I Scheuermann, Young Chul Park, Edward Omiecinski

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The problem of file reorganization which we consider involves altering the placement of records on pages of a secondary storage device. In addition, we want this reorganization to be done in-place, i.e., using the file's original storage space for the newly reorganized file. The motivation for such a physical change is to improve the database system's performance. For example, by placing frequently and jointly accessed records on the same page or pages, we can try to minimize the number of page accesses made in answering a set of queries. The optimal assignment (or reassignment) of records to clusters is exactly what record clustering algorithms [1,2,4,9] attempt to do. However, record clustering algorithms usually do not solve the entire problem, i.e., they do not specify how to efficiently reorganize the file to reflect the clustering assignment which they determine. Our algorithm is a companion to general record clustering algorithms since it actually transforms the file. The problem of optimal file reorganization is NP-hard [3]. Consequently, our reorganization algorithm is based on heuristics for which we prove three important observations.

Original languageEnglish (US)
Title of host publicationFoundations of Data Organization and Algorithms - 3rd International Conference, FODO 1989, Proceedings
EditorsWitold Litwin, Hans-Jorg Schek
PublisherSpringer Verlag
Number of pages15
ISBN (Print)9783540512950
StatePublished - Jan 1 1989
Event3rd International Conference on Foundations of Data Organization and Algorithms, FODO 1989 - Paris, France
Duration: Jun 21 1989Jun 23 1989

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume367 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd International Conference on Foundations of Data Organization and Algorithms, FODO 1989

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Heuristic reorganization of clustered files'. Together they form a unique fingerprint.

Cite this