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