Record allocation for minimizing seek delay

U. I. Gupta, D. T. Lee, J. Y.T. Leung, J. W. Pruitt, C. K. Wong

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Given a set of variable length records and their access probabilities, we address the problem of allocating these records on a linear storage device so as to minimize the expected seek time. A partial characterization of the optimal arrangement is given and the general problem of finding an optimal solution is shown to be NP-hard. Next, two heuristics are considered and performance bounds are derived for them. Although these bounds are not very encouraging, both heuristics are found to perform well in practice.

Original languageEnglish (US)
Pages (from-to)307-319
Number of pages13
JournalTheoretical Computer Science
Volume16
Issue number3
DOIs
StatePublished - 1981

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Record allocation for minimizing seek delay'. Together they form a unique fingerprint.

Cite this