A Transposition Rule Analysis Based on a Particle Process

DOI10.1239/JAP/1110381383MaRDI QIDQ5312853zbMATH OpenOpenAlexFDO

Authors David Gamarnik, Petar Momčilović

Publication date 25 August 2005

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0404021

Mathematics Subject Classification ID

Limit theorems in probability theory (60F99) Data structures (68P05) Searching and sorting (68P10)

Abstract: A linear list is a collection of items that can be accessed sequentially. The cost of a request is the number of items that need to be examined before the desired item is located, i.e., the distance of the requested item from the beginning of the list. The transposition rule is one of the algorithms designed to reduce the search cost by organizing the list. In particular, upon a request for a given item, the item is transposed with the preceding one. We develop a new approach for analyzing the algorithm. The approach is based on a coupling with a certain constrained asymmetric exclusion process. This allows us to establish an asymptotic optimality of the rule for two families of request distributions.

Recommendations

• The Move-to-Front Rule for Multiple Lists
• MOVE-TO-FRONT RULE FOR ACCESSING SEVERAL RECORDS
• Limiting behavior of the search cost distribution for the move-to-front rule in the stable case
• scientific article; zbMATH DE number 3888923
• On some multi-request move-to-front heuristics

Cites work

• A counterexample to a conjecture on optimal list ordering
• An exact formula for the move-to-front rule for self-organizing lists
• Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 903457 (Why is no real title available?)
• scientific article; zbMATH DE number 6472578 (Why is no real title available?)
• Limits and rates of convergence for the distribution of search cost under the move-to-front rule
• On self-organizing sequential search heuristics
• On the distribution of the search cost for the move-to-front rule with random weights
• Optimal list order under partial memory constraints
• Self-organizing files with dependent accesses
• Two Spectra of Self-Organizing Sequential Search Algorithms

Cited in

(2)

• Applying POS(i) rules to communication problems
• Comparison of subdominant eigenvalues of some linear search schemes

This page was built for publication: A Transposition Rule Analysis Based on a Particle Process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5312853)