RECORD ALLOCATION TO MINIMIZE EXPECTED SEEK DELAY.

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

RECORD ALLOCATION TO MINIMIZE EXPECTED SEEK DELAY.

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

Research output: Contribution to conference › Paper › peer-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 language	English (US)
Pages	225-230
Number of pages	6
State	Published - 1979
Externally published	Yes
Event	Proc Annu Allerton Conf Commun Control Comput 17th - Monticello, IL, USA Duration: Oct 10 1979 → Oct 12 1979

Conference

Conference	Proc Annu Allerton Conf Commun Control Comput 17th
City	Monticello, IL, USA
Period	10/10/79 → 10/12/79

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

@conference{a695ab7adf3d4690aea36b55e0f46519,

title = "RECORD ALLOCATION TO MINIMIZE EXPECTED SEEK DELAY.",

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.",

author = "Gupta, \{U. I.\} and Lee, \{D. T.\} and Leung, \{J. Y.T.\} and Pruitt, \{J. W.\}",

year = "1979",

language = "English (US)",

pages = "225--230",

note = "Proc Annu Allerton Conf Commun Control Comput 17th ; Conference date: 10-10-1979 Through 12-10-1979",

}

TY - CONF

T1 - RECORD ALLOCATION TO MINIMIZE EXPECTED SEEK DELAY.

AU - Gupta, U. I.

AU - Lee, D. T.

AU - Leung, J. Y.T.

AU - Pruitt, J. W.

PY - 1979

Y1 - 1979

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0018555663

UR - https://www.scopus.com/pages/publications/0018555663#tab=citedBy

M3 - Paper

AN - SCOPUS:0018555663

SP - 225

EP - 230

T2 - Proc Annu Allerton Conf Commun Control Comput 17th

Y2 - 10 October 1979 through 12 October 1979

ER -

RECORD ALLOCATION TO MINIMIZE EXPECTED SEEK DELAY.

Abstract

Conference

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this