Publication
Theoretical Computer Science
Paper

Record allocation for minimizing seek delay

View publication

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. © 1981.

Date

01 Jan 1981

Publication

Theoretical Computer Science

Authors

Topics

Share