Technical Report CS0656

Authors: H. Shachnai and M. Hofri
Abstract: The structure we consider is a linear list of n records, L = {R l' ... ,Rn }. Each record Rj , is uniquely identified by a key Kj , 1SiS n. . Requests for the keys are drawn from a multinomial distribution driven by the reference probability vector (rpv): p =(Pl' " . ,Pn)' Thus, Rj may be accessed at any stage with a fixed probability Pi. We assume the independent reference model (irm). As each of the references requires a sequential search of the list, we let C , the cost of a single access be defined as the number of key comparisons made till reaching the specified record. Under the irm, with a fixed rpv, the average access cost to the list is minimized when permuting the records to the optimal static order: Ri precedes RI whenever Pi >Pi' Doing that requires a complete knowl~dge of the rpv, or at least ofthe relative'magnitude·Ofthe access probabilities. 'Ibis knowledge is assumed unavailable. Previous works considered the situation where there is no initial information at all concerning the correct order of the records. Thus, the initial arrangement is chosen randomly (with equal probability) out of all possip1e permutations, and thereafter the list is constantly reorganized, with the aim of approaching the optimal ordering as the reference sequence grows longer. A comprehensive survey of many permutation rules suggested for the above model and their analyses appears in [Hester and Hirschberg, 1985]. Recent work. [Hofri and Shachnai, 1989] proves the optimality of Counter Scheme (CS) among all deterministic policies. It hinges on the assumption that throughout the reference history, the only criteria for distinguishing between the list records are their relative position at every stage and the history of requests for each.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1990
To the main CS technical reports page

Computer science department, Technion