On File Structuring for Non-Uniform Access Frequencies
- Lookup NU author(s)
|
|
|
|
| Author(s) | | Coffman EG, Bruno J |
| Series Editor(s) | | Cox NSM |
| Publication type | | Report |
| Series Title | | Computing Laboratory Technical Report Series |
| Year | | 1970 |
| Date | | January 1970 |
| Report Number | | 6 |
| Pages | | 18 |
|
|
|
| Full text is available for this publication: |
|
|
|
|
| An important property of file structures is their behaviour when the underlying distribution of access frequencies is non-uniform. In this note we consider methods for structuring files so that initially unknown but non-uniform access frequencies are exploited in a way that reduces mean search times. As a specific illustration a simple algorithm is applied to sequence search trees and shown to produce structures with mean search times that are significantly less than those produced by an algorithm creating tree structures independent of access frequencies. An analytic result is obtained for this improvement when access frequencies are uniform. Samples from the result of Monte Carlo simulations are used to illustrate this improvement when access frequencies are non-uniform. |
|
|
|
| Institution | | Computing Laboratory, The University of Newcastle upon Tyne |
| Place Published | | Newcastle upon Tyne |
| Actions | |  |
