Placing Dynamic Content in Caches with Small Population

I. INTRODUCTION

• Small local populations provide limited observations of ephemeral demand, complicating timely popularity estimates needed for effective caching.The paper frames this as a central obstacle to good hit rates in caches serving small populations.Source: §I · p. 1

B. Related Work

• Prior work largely assumed large caches and known or static popularity, while the small-population problem remained underexplored because sparse requests impede estimation.The paper positions its study at the interface of caching and learning.Source: A. Reducing Content Latency with Base… · p. 1, B. Related Work · p. 2

A. Reducing Content Latency with Base Station Caches

• For latency reduction, partial caching stores initial content chunks; a cache of size C can match the chunk-hit probability of a cache of size ξC.Here ξ is the inverse of the file fraction needed for smooth display.Source: A. Reducing Content Latency with Base… · p. 1, Figure 2 · p. 2

C. Our Contribution

• ABT stores content when its request count exceeds an age-dependent threshold and is asymptotically optimal as the number of contents grows.This provides a characterization of joint caching and learning under time-varying popularity.Source: C. Our Contribution · p. 2
• Global learning aggregates requests across L local caches, but correlated locations make local popularity more skewed and potentially more useful when accurately estimated.The paper proposes clustering to retain local characteristics while accumulating more request samples.Source: C. Our Contribution · p. 2
• A score combining request frequency and content age supports coordinated score-gated LRU and prefetching, which simulations show is crucial for small-population caches.Prefetching can improve hit rate but adds core-network traffic; simulations report a worst-case total-bandwidth increase of 3%.Source: C. Our Contribution · pp. 2–3

II. REQUESTS WITH TIME-VARYING POPULARITY

• The request model uses Poisson shot arrivals, fixed-duration rectangular shots, power-law shot volumes, and independent Poisson requests at each content's rate.The analysis fixes shot shape and duration T; the authors note that other shapes require revisiting details, though the main insights may guide heuristics.Source: §II · p. 3

A. Hit Rate Optimization With Estimated Popularities

• Because the controller does not know true popularities, it estimates them from past requests; the analysis assumes known shot arrival times and zero cache-update cost.Zero update cost lets the authors decouple horizon-wide hit-rate optimization into per-time-instance problems.Source: A. Hit Rate Optimization With… · p. 3
• At each time, the controller selects up to C active contents using their ages and observed request counts to maximize conditional expected hit probability.The instantaneous hit rate depends on unknown popularities, so the objective conditions on observed counts and ages.Source: A. Hit Rate Optimization With… · pp. 3–4
• The optimization stores the C contents with highest estimated popularity, but its expected performance is difficult to compute because active contents and their decisions are dependent.The paper therefore characterizes a simple policy that is asymptotically optimal for large catalogs.Source: A. Hit Rate Optimization With… · p. 4

B. Age-Based Threshold Policy

• ABT stores content m when its request count Nm reaches an age-dependent threshold Ñ(τm), with the threshold set by a conditional expected-popularity cutoff.The cutoff is the smallest request count whose conditional expected popularity reaches θ(γc), the γc-th upper percentile of estimated popularity.Source: B. Age-Based Threshold Policy · p. 4
• The age-dependent threshold can be computed offline for given cache size, shot rate, duration, and popularity-distribution parameters.The policy then bases each caching decision on the observed request count and content age.Source: B. Age-Based Threshold Policy · p. 4
• The threshold is more conservative for recent content because its popularity estimate is less accurate; Figure 4 compares the threshold and marginal hit-rate improvement across ages.The threshold roughly follows the expected request count of the Cth most popular active content, but is higher for low-age content.Source: B. Age-Based Threshold Policy · pp. 4–5, Figure 4 · p. 4
• ABT is almost surely asymptotically optimal as the number of contents grows, with cache capacity increasing so C/(λT)=γc.In this regime, its threshold converges to the optimal policy’s threshold, so the policies asymptotically cache the same contents.Source: B. Age-Based Threshold Policy · p. 5
• The cutoff separates the fraction γc=C/(λT) of contents deemed popular, corresponding to the relative cache size in the model.The paper considers the many-contents regime λ→∞ with the cache size increasing so that this ratio remains fixed.Source: B. Age-Based Threshold Policy · p. 5

IV. AGGREGATING ESTIMATES FROM L CACHES

• The proposed hierarchy links L local caches to a central cache, with each request first arriving at a local cache and then being observed globally.The section examines whether popularity estimation at the global cache can improve local-cache hit rates.Source: §IV · p. 5
• The global cache observes requests from all local caches, providing the basis for estimating popularity centrally rather than separately at each local cache.The passage frames this as a potential way to improve local-cache hit-rate performance.Source: §IV · p. 5
• The section considers whether global popularity estimates can improve the hit rates of the local caches.Source: §IV · p. 5

1) Request Model for Uncorrelated Requests:

• Each global content-request process is thinned by assigning requests uniformly to one of L local caches.The resulting thinned process is observed at the selected local cache.Source: 1) Request Model for Uncorrelated… · p. 5

2) Global is Faster:

• Aggregating requests from all locations helps detect changing popularities and improves hit rates.The paper attributes the benefit to collecting more samples and effectively slowing popularity dynamics.Source: 2) Global is Faster · p. 6
• Global estimation can match any local-estimation policy at shot duration T using shot duration T/L.The proof states this equivalence for policies using local or global estimation.Source: 2) Global is Faster · p. 6
• 35% absolute hit rate improvement is reached at a specific T when requests are aggregated under ABT.Figure 5 compares global learning, local learning, and storing entire files; gains occur across a wide range of T values.Source: Figure 5 · p. 6, 2) Global is Faster · p. 6

B. Correlated Popularities

• Correlated locations may have distinct popularities, so aggregating only caches with similar traffic patterns may be more efficient than global aggregation.The paper motivates these similarities with regional differences in user backgrounds and activities.Source: B. Correlated Popularities · p. 6

1) Request Model for Correlated Locations:

• The model associates each content and location with independently uniform feature vectors and links their popularity through a correlation kernel.The kernel is defined from a continuous, symmetric, periodic, strictly decreasing function normalized over locations.Source: 1) Request Model for Correlated… · p. 6
• As L increases, the normalization constant almost surely becomes deterministic under basic conditions on the kernel.The supplied passage states this asymptotic property without specifying the constant's value.Source: 1) Request Model for Correlated… · pp. 6–7

2) Local is More Accurate:

• Local popularity is more skewed than popularity aggregated across caches, and that skewness benefits caching.This explains the static-system advantage of local learning when popularities are known.Source: 2) Local is More Accurate · p. 7
• In the static limit, local learning has higher hit probability than aggregate global learning for any global popularity distribution.The theorem states this result for T → ∞.Source: 2) Local is More Accurate · p. 7
• With unknown popularities, aggregation trades more accurate estimates from additional samples against the higher skewness retained by subset aggregation.The paper identifies these as competing benefits of global and subset aggregation.Source: 2) Local is More Accurate · p. 7

3) Clustering:

• Clusters aggregate requests from locations with similar popularity profiles to balance local-popularity fidelity against faster detection of dynamics.The paper frames this as retaining local popularity skew while using more information than local estimation alone.Source: 3) Clustering · p. 7
• The analysis assumes cache embeddings are known rather than learning cluster assignments from request histories.For the modeled kernel, caches with similar feature vectors are grouped; the study considers clusters covering a feature-space subset.Source: 3) Clustering · p. 7
• Smaller clusters yield better hit rates as T → ∞, but can perform poorly when popularity changes faster.Small clusters then fail to estimate aggregated popularities effectively; a single global cluster is advantageous when T is small.Source: 3) Clustering · pp. 7–8
• Global learning smooths the correlation kernel to a flat function, while smaller clusters produce smoothed kernels closer to the true kernel.The closer approximation preserves more location information and local popularity characteristics.Source: 3) Clustering · p. 8, Figure 6 · p. 8

A. Age-based Popularity Scores

• Age-based popularity scores use content-age thresholds to distinguish super-unpopular from super-popular content without complicating score design.Changing β relative to γC corresponds to a virtual cache of larger or smaller size; the resulting score accounts for content age.Source: A. Age-based Popularity Scores · p. 8

B. Score-gated LRU

• Score-gated LRU applies LRU to high-score requests and never caches low-score requests; prediction benefits appear only at high T, when popularity is semi-static.In more dynamic scenarios, each of the 1000 local caches receives only a handful of requests per content, making adaptive caching ineffective.Source: B. Score-gated LRU · p. 8

C. LRU with Prefetching

• The prefetching mechanism periodically sends a fake request for globally identified super-popular content, prompting a local cache without that content to prefetch it.A cache that already holds the content instead moves it to the head of its LRU list.Source: C. LRU with Prefetching · pp. 8–9
• 30 transmissions may be needed per request in very dynamic settings; prefetching improves hit rate, while the example's total-bandwidth increase is 3%.The traffic comparison accounts for partial caching and ξ = 1000; varying β2 at T = 1 exposes diminishing hit-rate returns against traffic footprint.Source: C. LRU with Prefetching · p. 9, Figure 7 · p. 9

VI. CONCLUSIONS

• The conclusion states that age-based thresholds exploit time-varying popularity, while global learning combined with clustering maximizes caching efficiency.The paper also proposes score mechanisms for practical use at local caches.Source: §VI · p. 9

• For finite λ, the optimal policy stores the C contents with the highest posterior popularity estimates E[µm|Nm, τm].Because the estimates are almost surely distinct, a threshold can separate the top C estimates without a tie-breaking rule.Source: Appendix A · p. 10
• As λ grows with C/(λT) tending to γc, the empirical estimate distribution converges to F and its C/|M| upper quantile converges to the γc upper quantile.The proof assumes F has a density, making the limiting quantile well-defined.Source: Appendix A · p. 10
• The limiting threshold is the age-dependent ABT cutoff, so ABT is the limit of the finite-system optimal policy and is asymptotically optimal.The fraction of contents initially stored by ABT tends to γc, making the final cache-size adjustment negligible.Source: Appendix A · p. 10

• The proof establishes the comparison by showing that local observations and global observations under accelerated time have the same distribution.It then constructs corresponding caching mappings for the two information settings.Source: Appendix B · p. 10
• Under L-speedup dynamics, aggregate requests form a process statistically identical to the requests seen by one local cache in the original system.Time runs L times faster, so a request rate λ becomes λL and shot duration T becomes T/L.Source: Appendix B · p. 10
• Mapped policies have equal hit probabilities in distribution, and the mapping works in both directions, yielding the theorem by considering optimal policies.Source: Appendix B · pp. 10–11

• After rescaling, local popularity distributions are larger than global popularity distributions in convex stochastic order.The proof assumes local popularity distributions are identically distributed across edge caches.Source: Appendix C · p. 11
• Optimal expected hit probability is convex in popularity, so the distributional comparison supports the hit-probability result, including its stated limit.The proof notes that convexity follows from the maximum in the finite-system optimization.Source: Appendix C · p. 11
• As L grows, local thresholds become independent of cache location and Yl and converge to a common limiting threshold.The inner probability can be computed explicitly under the assumed form of g, whose inverse is well-defined and onto.Source: Appendix C · p. 11
• The proof obtains the claimed expression for the optimal expected hit probability by computing the inner expectation explicitly.Source: Appendix C · p. 11