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


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
Issue number3
StatePublished - 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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

Cite this