scientific article; zbMATH DE number 795110

MaRDI QIDQ4845259zbMATH OpenFDO

Authors Robert P. Dobrow, James Allen Fill

Publication date 26 November 1995

zbMATH Keywords

convergence to stationaritycouplingMarkov chainmove-to-front ruleself-organizing searchseparationstationary distributiontotal variation distance

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Data structures (68P05) Searching and sorting (68P10)

Recommendations

• An exact formula for the move-to-front rule for self-organizing lists
• Performance of the move-to-front algorithm with Markov-modulated request sequences
• The move-to-root rule for self-organizing trees with Markov dependent requests^∗
• scientific article; zbMATH DE number 2102775
• Limits and rates of convergence for the distribution of search cost under the move-to-front rule

Cited in

(23)

• Self-organizing sequential search and Hilbert's inequalities
• Random walks and hyperplane arrangements
• Optimality of move-to-front for self-organizing data structures with locality of references
• Perron eigenvector of the Tsetlin matrix
• On the Markov chain for the move-to-root rule for binary search trees
• Rates of convergence for the move-to-root Markov chain for binary search trees
• An exact formula for the move-to-front rule for self-organizing lists
• Geometric ergodicity and the spectral gap of non-reversible Markov chains
• Performance of the move-to-front algorithm with Markov-modulated request sequences
• Self-organizing files with dependent accesses
• scientific article; zbMATH DE number 3856448 (Why is no real title available?)
• On the asymptotics of fault probability in least-recently-used caching with Zipf-type request distribution
• Self-organizing lists and independent references: A statistical synergy
• On some multi-request move-to-front heuristics
• scientific article; zbMATH DE number 480526 (Why is no real title available?)
• On the move-to-front scheme with Markov dependent requests
• The move-to-partner rule for self-organizing task allocation on a linear array
• scientific article; zbMATH DE number 2102775 (Why is no real title available?)
• The move-to-root rule for self-organizing trees with Markov dependent requests^∗
• Enumerative theory for the Tsetlin library
• Least-recently-used caching with dependent requests
• Comparison of subdominant eigenvalues of some linear search schemes
• Functions of random walks on hyperplane arrangements

This page was built for publication:

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