On Serial Files with Relocatable Records

John McCabe
Additional contact information
John McCabe: General Electric Company, Bethesda, Maryland

Operations Research, 1965, vol. 13, issue 4, 609-618

Abstract: A serial file is considered in which, after a query is processed, the order in the file is changed by moving the record to which the query referred into the first place in the file. The theory of regular Markov chains is used to demonstrate the existence of E ( X ) and to show that the law of large numbers holds, where E ( X ) is the limiting average position of a queried record. A closed-form expression for E ( X ) is determined. A second method of relocation is proposed, in which the queried record exchanges positions with the record immediately before it in the file. It is conjectured that this method of relocation is at least as good as the first method. It is pointed out that, whichever method of relocation is used, if one only relocated after every M th query, the limiting average position of a queried record is the same as it is if we relocate after every query.

Date: 1965
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.13.4.609 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:13:y:1965:i:4:p:609-618

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().