Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities

DOI10.1214/aoap/1029962750zbMath0940.60044OpenAlexW1965375374MaRDI QIDQ1305419

Predrag R. Jelenković

Publication date: 30 September 1999

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1029962750

zbMATH Keywords

data structuresself-organizing listssearching and sorting

Mathematics Subject Classification ID

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

Related Items (13)

Optimal timer-based caching policies for general arrival processes ⋮ Transient and steady-state regime of a family of list-based cache replacement algorithms ⋮ On the distribution of the search cost for the move-to-front rule with random weights ⋮ A Transposition Rule Analysis Based on a Particle Process ⋮ The coupon collector’s problem revisited: generalizing the double Dixie cup problem of Newman and Shepp ⋮ Performance of the move-to-front algorithm with Markov-modulated request sequences ⋮ Limiting behaviour of the stationary search cost distribution driven by a generalized gamma process ⋮ The limiting move-to-front search-cost in law of large numbers asymptotic regimes ⋮ Stochastic ranking process with time dependent intensities ⋮ Least-recently-used caching with dependent requests ⋮ Critical sizing of LRU caches with dependent requests ⋮ Unnamed Item ⋮ A fluid limit for a cache algorithm with general request processes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Limits and rates of convergence for the distribution of search cost under the move-to-front rule
• Self-organizing sequential search and Hilbert's inequalities
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• Competitive paging with locality of reference
• An exact formula for the move-to-front rule for self-organizing lists
• Some Distribution-Free Aspects of Paging Algorithm Performance
• On the matrix occurring in a linear search problem
• Asymptotic properties of supercritical branching processes I: The Galton-Watson process
• On self-organizing sequential search heuristics
• Single-shelf library-type Markov chains with infinitely many books
• Heuristics That Dynamically Organize Data Structures
• Subexponential asymptotics of a Markov-modulated random walk with queueing applications
• On the transition probabilities of the move-to-front scheme
• Asymptotic results for multiplexing subexponential on-off processes
• On a model for storage and search
• Strongly Competitive Algorithms for Paging with Locality of Reference
• On Serial Files with Relocatable Records
• The stationary distribution of an interesting Markov chain

This page was built for publication: Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities