Efficient Miss Ratio Curve Computation for Heterogeneous Content Popularity
summary
The paper shows that sampling-based MRC reconstruction breaks when a few very popular items dominate, producing large head errors, and it builds a hybrid estimator that keeps an exact head+sampled tail by tracking a few hundred top items and sampling the rest. Implemented on real and synthetic traces, the algorithm reduces reconstruction error up to 10x smaller than state-of-the-art samplers while keeping similar CPU and memory overhead, and it reports the concrete thresholds and trace sizes used.
AI-written summary · about
chapters (13)
- 0:00Efficient miss ratio computation
- 1:36Cache resource contention
- 3:21Computational complexity challenges
- 5:21Sampling for miss ratio curves
- 7:51Limitations of current approaches
- 10:00Evaluating approximation errors
- 12:33Impact of distribution tails
- 14:06Small cache sizes in sampling
- 15:56Comparison with existing solutions
- 17:26Performance results
- 18:51Multiple object size distributions
- 20:20Adaptive sampling rates
- 21:44Conclusion
related talks
11meMRC: Efficient Miss Ratio Approximation for Multi-Tier Caching
19mKosmo: Efficient Online Miss Ratio Curve Generation for Eviction Policy Evaluation
24mLHD: Improving Cache Hit Rate by Maximizing Hit Density
17mParaRC: Embracing Sub-Packetization for Repair Parallelization in MSR-Coded Storage
45mMost of the Time It Works Every Time: The Mindset Behind Using Probabilistic Data Structures
01h 06mSampling in Query Evaluation 2
27mImproved Frequency Estimation Algorithms with and without Predictions
25mQuantiles at Scale: Choosing the Right Estimation Algorithms for Observability