On file structuring for non-uniform access frequencies

An important property of file structures is their behavior 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 results of Monte Carlo simulations are used to illustrate this improvement when access frequencies are non-uniform.