On File Structuring for Non-Uniform Access Frequencies

  1. Lookup NU author(s)
Author(s)Coffman EG, Bruno J
Series Editor(s)Cox NSM
Publication type Report
Series TitleComputing Laboratory Technical Report Series
Source Publication DateJanuary 1970
Report Number6
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.
InstitutionComputing Laboratory, The University of Newcastle upon Tyne
Place PublishedNewcastle upon Tyne
ActionsLink to this publication