Toggle Main Menu Toggle Search


On File Structuring for Non-Uniform Access Frequencies

Lookup NU author(s):



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.

Publication metadata

Author(s): Coffman EG, Bruno J

Series Editor(s): Cox NSM

Publication type: Report

Series Title: Computing Laboratory Technical Report Series

Year: 1970

Pages: 18

Source Publication Date: January 1970

Report Number: 6

Institution: Computing Laboratory, The University of Newcastle upon Tyne

Place Published: Newcastle upon Tyne