Limits and rates of convergence for the distribution of search cost under the move-to-front rule

DOI10.1016/0304-3975(95)00210-3zbMath0871.68067OpenAlexW1983530372MaRDI QIDQ671429

James Allen Fill

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00210-3

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (14)

Optimal timer-based caching policies for general arrival processes ⋮ 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 ⋮ Limiting behaviour of the stationary search cost distribution driven by a generalized gamma process ⋮ Limiting search cost distribution for the move-to-front rule with random request probabilities ⋮ 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 ⋮ SIZE-BIASED PERMUTATION OF DIRICHLET PARTITIONS AND SEARCH-COST DISTRIBUTION ⋮ Functions of random walks on hyperplane arrangements ⋮ Unnamed Item ⋮ A fluid limit for a cache algorithm with general request processes ⋮ The Move-to-Front Rule: A Case Study for two Perfect Sampling Algorithms ⋮ Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strong uniform times and finite random walks
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• 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
• Spectral localization of operators in Banach spaces
• Shuffling Cards and Stopping Times
• Heuristics That Dynamically Organize Data Structures
• On the transition probabilities of the move-to-front scheme
• Real Analysis and Probability
• On Serial Files with Relocatable Records
• The stationary distribution of an interesting Markov chain

This page was built for publication: Limits and rates of convergence for the distribution of search cost under the move-to-front rule