RECORD ALLOCATION TO MINIMIZE EXPECTED SEEK DELAY.

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

Research output: Contribution to conferencePaperpeer-review

Abstract

Given a set of variable length records and their access probabilities, the problem is addressed 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)
Pages225-230
Number of pages6
StatePublished - 1979
Externally publishedYes
EventProc Annu Allerton Conf Commun Control Comput 17th - Monticello, IL, USA
Duration: Oct 10 1979Oct 12 1979

Conference

ConferenceProc Annu Allerton Conf Commun Control Comput 17th
CityMonticello, IL, USA
Period10/10/7910/12/79

All Science Journal Classification (ASJC) codes

  • General Engineering

Fingerprint

Dive into the research topics of 'RECORD ALLOCATION TO MINIMIZE EXPECTED SEEK DELAY.'. Together they form a unique fingerprint.

Cite this