Least-recently-used caching with dependent requests

DOI10.1016/j.tcs.2004.07.029zbMath1093.60066OpenAlexW1964774074MaRDI QIDQ703555

Predrag R. Jelenković, Ana Radovanović

Publication date: 11 January 2005

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.07.029

zbMATH Keywords

Zipf's lawAverage-case analysisHeavy-tailed distributionsLong-range dependenceMove-to-frontSemi-Markov processes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Markov renewal processes, semi-Markov processes (60K15)

Related Items

Optimal timer-based caching policies for general arrival processes ⋮ Stochastic ranking process with time dependent intensities ⋮ Critical sizing of LRU caches with dependent requests ⋮ Unnamed Item ⋮ A fluid limit for a cache algorithm with general request processes ⋮ Asymptotic optimality of the static frequency caching in the presence of correlated requests

Cites Work

• Unnamed Item
• 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
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities
• Asymptotic loss probability in a finite buffer fluid queue with heterogeneous heavy-tailed on-off processes
• Competitive paging with locality of reference
• 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
• On self-organizing sequential search heuristics
• 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
• On a model for storage and search
• The performance of the move-to-front scheme under some particular forms of Markov requests
• Strongly Competitive Algorithms for Paging with Locality of Reference
• On Serial Files with Relocatable Records
• Large deviations of sums of independent random variables