About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Theoretical Computer Science
Paper
Record allocation for minimizing seek delay
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.