On the asymptotics of fault probability in least‐recently‐used caching with Zipf‐type request distribution

No abstract is available for this paper.

• Publication year

  2006

• Venue

  Random Struct. Algorithms

• Publication date

  2006-10-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1002/rsa.20098
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Gamma function and related functions

  2008cited by this paper
• Influence of cultivation temperature on the ligninolytic activity of selected fungal strains

  2006cited by this paper
• Some counterexamples in positive dependence

  2004cited by this paper
• Least-recently-used caching with dependent requests

  2004cited by this paper
• Asymptotic insensitivity of least-recently-used caching to statistical dependency

  2003influential reference
• Comparison Methods for Stochastic Models and Risks

  2003cited by this paper
• The content and access dynamics of a busy Web site: findings and implications

  2000cited by this paper
• Performance of the move-to-front algorithm with Markov-modulated request sequences

  1999cited by this paper
• Web caching and Zipf-like distributions: evidence and implications

  1999cited by this paper
• Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities

  1999influential reference
• LUMPABILITY IN LRU STACK. WITH MARKOVIAN PAGE REFERENCES

  1998cited by this paper
• Balls and Bins: A Study in Negative Dependence

  1996cited by this paper
• Limits and Rates of Convergence for the Distribution of Search Cost Under the Move-to-Front Rule

  1996cited by this paper
• On the distribution of search cost for the move-to-front rule

  1996cited by this paper
• The performance of the move-to-front scheme under some particular forms of Markov requests

  1995cited by this paper
• THE MOVE-TO-FRONT RULE FOR SELF-ORGANIZING LISTS WITH MARKOV DEPENDENT REQUESTS·

  1995cited by this paper
• A New Method for Computing Page-Fault Rates

  1993cited by this paper
• Birthday Paradox, Coupon Collectors, Caching Algorithms and Self-Organizing Search

  1992cited by this paper
• Stationary Stochastic Models.

  1992cited by this paper
• Stationary Stochastic Models

  1991cited by this paper
• Exponential convergence under mixing

  1989influential reference
• Self-organizing files with dependent accesses

  1984cited by this paper
• Negative Association of Random Variables with Applications

  1983cited by this paper
• The Art of Computer Programming, Vol. 3: Sorting and Searching

  1974cited by this paper
• Operating Systems Theory

  1973cited by this paper
• On a model for storage and search

  1973cited by this paper
• The stationary distribution of an interesting Markov chain

  1972cited by this paper
• Association of Random Variables, with Applications

  1967cited by this paper
• On Serial Files with Relocatable Records

  1965cited by this paper

• Spectral Algorithms Optimally Recover Planted Sub-structures

  2022cites this paper
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: 𝓁2, ∞ Statistical Guarantees

  2021cites this paper
• iBTune: Individualized Buffer Tuning for Large-scale Cloud Databases

  2019cites this paper
• Subspace Estimation from Unbalanced and Incomplete Data Matrices: $\ell_{2,\infty}$ Statistical Guarantees.

  2019cites this paper
• LRU Caching with Dependent Competing Requests

  2018influential citation
• On Resource Pooling and Separation for LRU Caching

  2018cites this paper
• Shortest path queries, graph partitioning and covering problems in worst and beyond worst case settings

  2018cites this paper
• New Abilities and Limitations of Spectral Graph Bisection

  2017influential citation
• On Resource Pooling and Separation for LRU Caching

  2017cites this paper
• Approximation of LRU Caches Miss Rate: Application to Power-law Popularities

  2017cites this paper
• Local Algorithms for Block Models with Side Information

  2015cites this paper
• On the decomposition of stochastic cellular automata

  2015cites this paper
• Subsampled Power Iteration: a New Algorithm for Block Models and Planted CSP's

  2014cites this paper
• Repetition-free longest common subsequence of random sequences

  2013cites this paper
• Sorting noisy data with partial information

  2013cites this paper
• Reconstruction in the labeled stochastic block model

  2013cites this paper
• Beyond Worst Case Analysis in Approximation Algorithms

  2012influential citation
• Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs

  2012cites this paper
• Message Passing Algorithms for MLS-3LIN Problem

  2012cites this paper
• Approximation Algorithms for Semi-random Graph Partitioning Problems

  2012cites this paper
• Approximation algorithms for semi-random partitioning problems

  2012influential citation
• Cancellation of fluctuation in stochastic ranking process with space-time dependent intensities

  2012cites this paper
• A fluid limit for a cache algorithm with general request processes

  2010influential citation
• Analysis of Page Replacement Policies in the Fluid Limit

  2010cites this paper
• Stochastic ranking process with time dependent intensities

  2010cites this paper
• Structural Similarity: Spectral Methods for Relaxed Blockmodeling

  2010cites this paper
• Stochastic minority on graphs

  2010cites this paper
• An efficient sparse regularity concept

  2009cites this paper
• A Fluid Limit for Cache Algorithms with General Request Processes

  2009influential citation
• Group-Level Analysis and Visualization of Social Networks

  2009cites this paper
• Algorithmen und Komplexität

  2009cites this paper
• Hydrodynamic limit of move-to-front rules and search cost probabilities

  2009influential citation
• Theory of Computing Systems (TOCS) Submission Version Finding Most Likely Solutions

  2009cites this paper
• The persistent‐access‐caching algorithm

  2008cites this paper
• Scale-Free Cortical Planar Networks

  2008influential citation
• Clustering algorithms for random and pseudo-random structures

  2008cites this paper
• On variants of the Johnson–Lindenstrauss lemma

  2008cites this paper
• Structural Similarity of Vertices in Networks (Strukturelle Ähnlichkeit von Knoten in Netzwerken)

  2007cites this paper
• Metrics for sparse graphs

  2007cites this paper
• A simple solution to the k-core problem

  2007cites this paper
• A Spectral Method for MAX2SAT in the Planted Solution Model

  2007cites this paper
• On the Laplacian Eigenvalues of Gn,p

  2007influential citation
• Finding Most Likely Solutions

  2007cites this paper
• Spectral methods for reconstruction problems

  2007cites this paper
• A Simple Message Passing Algorithm for Graph Partitioning Problems

  2006cites this paper
• An Adaptive Spectral Heuristic for Partitioning Random Graphs

  2006cites this paper
• Spectral Clustering by Recursive Partitioning

  2006cites this paper
• Average-case analysis for combinatorial problems

  2006cites this paper
• Finding a Maximum Independent Set in a Sparse Random Graph

  2005cites this paper
• Rigorous analysis of heuristics for NP-hard problems

  2005influential citation
• Comparing Strength of Locality of Reference: Popularity, Temporal Correlations, and Some Folk Theorems for the Miss Rates and Outputs of Caches

  2005cites this paper