Least-recently-used caching with dependent requests

DOI10.1016/J.TCS.2004.07.029zbMATH Open1093.60066OpenAlexW1964774074MaRDI QIDQ703555FDOQ703555

Authors: 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

Recommendations

• LRU caching with moderately heavy request distributions
• Critical sizing of LRU caches with dependent requests
• On the asymptotics of fault probability in least-recently-used caching with Zipf-type request distribution
• The persistent-access-caching algorithm
• Asymptotic optimality of the static frequency caching in the presence of correlated requests

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Competitive paging with locality of reference
• On self-organizing sequential search heuristics
• Large deviations of sums of independent random variables
• 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
• An exact formula for the move-to-front rule for self-organizing lists
• Subexponential asymptotics of a Markov-modulated random walk with queueing applications
• On a model for storage and search
• On Serial Files with Relocatable Records
• Strongly Competitive Algorithms for Paging with Locality of Reference
• Heuristics That Dynamically Organize Data Structures
• Title not available (Why is that?)
• Limits and rates of convergence for the distribution of search cost under the move-to-front rule
• On the transition probabilities of the move-to-front scheme
• Asymptotic loss probability in a finite buffer fluid queue with heterogeneous heavy-tailed on-off processes
• Performance of the move-to-front algorithm with Markov-modulated request sequences
• Title not available (Why is that?)
• The performance of the move-to-front scheme under some particular forms of Markov requests

Cited In (16)

• A fluid limit for a cache algorithm with general request processes
• Analysis of LRU cache trees with a power law reference distribution
• On the asymptotics of fault probability in least-recently-used caching with Zipf-type request distribution
• Critical sizing of LRU caches with dependent requests
• LRU caching with moderately heavy request distributions
• Functional central limit theorem for tagged particle dynamics in stochastic ranking process with space-time dependent intensities
• Optimizing LRU Caching for Variable Document Sizes
• Asymptotic optimality of the static frequency caching in the presence of correlated requests
• Near optimality of the discrete persistent access caching algorithm
• Optimal timer-based caching policies for general arrival processes
• Cache miss estimation for non-stationary request processes
• Asymptotic optimality of the static frequency caching in the presence of correlated requests
• Modeling least recently used caches with shot noise request processes
• Comparing locality of reference -- some folk theorems for the miss rate and the output of caches
• Approximate analysis of LRU in the case of short term correlations
• Stochastic ranking process with time dependent intensities

This page was built for publication: Least-recently-used caching with dependent requests

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