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
Zipf's lawAverage-case analysisHeavy-tailed distributionsLong-range dependenceMove-to-frontSemi-Markov processes
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)