PaperlayerView exact revision on arXiv

Source-linked AI summary

Content Popularity Prediction Towards Location-Aware Mobile Edge Caching

Peng Yang, Ning Zhang, Shan Zhang, Li Yu, Junshan Zhang, Xuemin Shen

arXiv:1809.00232v1cs.NI

TL;DR

Existing caching schemes do not account for fine-grained popularity differences across nearby access points. The paper proposes two online prediction algorithms for different noise models, with RPUC approaching optimal caching under zero-mean noise and HPDT guaranteeing prediction accuracy under worst-case noise.

  • Problem

    Existing content caching schemes do not consider fine-grained popularity differences between even adjacent Wi-Fi access points and cellular base stations.

  • Method

    The paper develops two online popularity prediction algorithms for different noise models, including an H∞-filter-based HPDT algorithm.

  • Results

    RPUC content hit rate asymptotically approaches the optimal solution under zero-mean noise, while HPDT guarantees prediction accuracy under worst-case noise.

  • Takeaways & Limitations

    The proposed algorithms support customized caching decisions for popularity prediction under different noise processes.

  • Takeaways & Limitations

    Because noise may not be zero-mean, the zero-mean-noise RPUC setting does not cover all noise processes and motivates the H∞-filter-based HPDT algorithm.

Abstract

from arXiv · show

Mobile edge caching enables content delivery within the radio access network, which effectively alleviates the backhaul burden and reduces response time. To fully exploit edge storage resources, the most popular contents should be identified and cached. Observing that user demands on certain contents vary greatly at different locations, this paper devises location-customized caching schemes to maximize the total content hit rate. Specifically, a linear model is used to estimate the future content hit rate. For the case where the model noise is zero-mean, a ridge regression based online algorithm with positive perturbation is proposed. Regret analysis indicates that the proposed algorithm asymptotically approaches the optimal caching strategy in the long run. When the noise structure is unknown, an $H_{\infty}$ filter based online algorithm is further proposed by taking a prescribed threshold as input, which guarantees prediction accuracy even under the worst-case noise process. Both online algorithms require no training phases, and hence are robust to the time-varying user demands. The underlying causes of estimation errors of both algorithms are numerically analyzed. Moreover, extensive experiments on real world dataset are conducted to validate the applicability of the proposed algorithms. It is demonstrated that those algorithms can be applied to scenarios with different noise features, and are able to make adaptive caching decisions, achieving content hit rate that is comparable to that via the hindsight optimal strategy.

I. INTRODUCTION

The paper addresses location-aware caching under time-varying, unknown content popularity by modeling demand from content and location features. It develops two online predictors for different noise settings and evaluates their caching performance.

  • Motivation: Limited edge storage makes identifying the content set that maximizes cache utilization crucial.Caching at the network edge can reduce backhaul traffic, but not all content can be stored locally.
  • Problem: Existing popularity prediction can use context information, but context design is difficult and user-based differentiation may conflict with privacy regulations.The paper therefore investigates location as an alternative context dimension for time-varying and unknown popularity profiles.
  • Model: The proposed linear model treats demand for a content as a combination of content features and location characteristics with unknown noise.Popularity prediction becomes estimation of each edge node’s location feature vector in the presence of noise.
  • Online algorithms: RPUC applies ridge-regression prediction with positive perturbation for zero-mean noise and achieves sublinear regret relative to the hindsight optimal caching policy.The analysis states that its performance asymptotically approaches the optimal long-term strategy.
  • Online algorithms: HPDT uses an H∞ filter and a prescribed accuracy threshold to provide robust prediction when the noise structure is unknown, provided noise amplitude is finite.The paper describes this approach as guaranteeing accuracy even in the worst-case scenario.
  • Evaluation: Both algorithms require no training phase, adapt to time-varying demand, and achieve content hit rates comparable to the hindsight optimal strategy on real-world traces.The paper also numerically analyzes RPUC estimation errors and reports applicability across scenarios with different noise features.

II. RELATED WORK

Prior caching studies address edge deployment, content delivery, and popularity learning, but many assume known popularity or rely on context information that may be unavailable. This paper uses location features to predict time-varying popularity and proposes online algorithms for different noise conditions.

  • Edge caching and delivery: Earlier work studied edge architectures, resource provisioning, D2D cooperation, and content caching to improve delivery efficiency and quality of experience.These studies include cloud-edge interoperation, hierarchical edge designs, vehicular networks, small-cell cooperation, and D2D caching.
  • Popularity learning: Existing caching studies commonly assume known popularity, whereas practical popularity can be unknown and time-varying.User interests change and new contents appear, motivating online methods without a separate training phase.
  • Popularity learning: Learning-based approaches use training, multi-armed bandits, social streams, or context-aware demand models to predict popularity.Context differentiation has also used content features and system states.
  • Limitations of prior context models: Prediction accuracy depends strongly on the information used for context differentiation, while user and detailed system information may be sensitive or unavailable.This limits the practicality of approaches relying on user profiles or network information.
  • Paper’s approach: The paper instead exploits easily obtained location features to differentiate contexts and model unknown, time-varying content popularity.Users attached to different edge nodes are naturally divided into geographical groups.
  • Paper’s approach: It extends zero-mean-noise prediction with a robust algorithm for unknown noise statistics and analyzes estimation errors using real-world experiments.The proposed robust method is described as guaranteeing prediction accuracy regardless of noise statistics.

III. SYSTEM MODEL AND PROBLEM FORMULATION

The system places storage at edge nodes serving disjoint user groups and predicts location-dependent content demand from content attributes. Because popularity varies over time and location, caching must use predicted hit rates rather than fixed popularity profiles.

  • A. Network Model: Mobile edge nodes use nearby storage resources to cache content and reduce request latency for their associated users.Edge nodes may be capacity-augmented base stations, WiFi access points, or other devices with excess capacity.
  • A. Network Model: The network contains edge nodes with separate backhaul links, and each edge node serves a disjoint set of mobile users.Contents are dynamically pushed to edge nodes for local request processing.
  • B. Content Popularity and Location Diversity: A video’s popularity varies over time because daily views and the relative popularity of other videos change as new videos are uploaded.The paper illustrates these trends using YouTube statistics and a popularity score based on daily views.
  • B. Content Popularity and Location Diversity: Location diversity also changes content popularity, so fixed-profile caching strategies are not optimal in practice.The paper motivates location-customized caching by considering different demand patterns across edge nodes.
  • B. Content Popularity and Location Diversity: Each file-edge-node pair has an attribute vector containing content characteristics such as quality, genre, length, and historical views.The model also includes a time-invariant location feature vector and a random noise term for each edge node.
  • B. Content Popularity and Location Diversity: The linear model predicts a file’s hit rate from its attributes and location features, allowing equal-content attributes to produce different demand across edge nodes.Relevant location factors include area characteristics, served-user counts, and content-update frequency.
  • B. Content Popularity and Location Diversity: Hit rate is defined as the number of content requests rather than a ratio, and the model uses a matrix-weighted Euclidean norm in its analysis.These definitions support the formulation of prediction and caching objectives.

C. Problem Formulation

The paper formulates location-aware caching as maximizing time-averaged hit rate when demand is unknown and popularity changes over time. It reduces the problem to estimating location feature vectors under noisy linear demand observations.

  • C. Problem Formulation: The system caches a capacity-limited set of files at each edge node and seeks to maximize time-averaged content hit rate.The formulation assumes equal-sized contents and a normalized cache capacity.
  • C. Problem Formulation: Because popularity is time-varying, higher-popularity contents should be cached proactively while less-popular contents are evicted.The objective is defined over a sequence of time slots and edge-node cache sets.
  • C. Problem Formulation: The optimal cache set cannot be selected directly because user demand and the optimal strategy are unknown before caching decisions are made.The paper therefore seeks a policy that continually estimates the optimal set and minimizes time-averaged caching regret.
  • C. Problem Formulation: The problem is recast as time-averaged regret minimization under an ergodic underlying process.Different-content sizes are excluded by assuming equal-sized contents, and the paper identifies unequal-size caching as future work.
  • C. Problem Formulation: Accurate demand prediction reduces to estimating each edge node’s location feature vector from the linear demand model.The location feature vector is assumed time-invariant, while the noise process lacks an established statistical model.
  • C. Problem Formulation: Two online prediction algorithms address different noise settings: near-optimal performance under zero-mean noise and robust guarantees when noise statistics are unknown.Both algorithms dynamically estimate location features for content popularity prediction.
  • Location Feature Vector Estimation: Ridge regression uses historical attribute matrices and empirical hit rates to estimate the location feature vector.The estimation trades bias for stability by penalizing parameter magnitude, with µ controlling shrinkage.
  • Location Feature Vector Estimation: The ridge estimator’s accuracy depends on data quantity and µ, and its error admits a probabilistic upper bound used to form a confidence interval.The confidence interval supports subsequent content popularity prediction.

B. RPUC Caching Algorithm

RPUC repeatedly predicts demand, caches the contents with the highest predicted hit rates, and updates its estimates from observed demands. A positive perturbation converts ridge estimates into an upper-confidence prediction to account for uncertainty.

  • Algorithm workflow: RPUC initializes the edge nodes, obtains file attributes, and iterates over time slots without a separate training phase.Its output is the set of files to cache in each edge node.
  • Observe and update: After each time slot, RPUC records empirical hit rates for cached files and updates parameter matrices for later estimation.This creates the algorithm’s iterative observe-and-update phase.
  • Predict: At each time slot, the algorithm updates the location feature estimate using demand observed in the previous slot.The updated estimate is combined with the linear prediction model to obtain estimated demand.
  • Predict: RPUC adds a positive perturbation to the estimated hit rate to account for random fluctuations and estimation uncertainty.The perturbation follows the probabilistic estimation-error bound and represents an upper confidence estimate.
  • Optimize and cache: The algorithm caches the set of contents with the largest predicted hit rates at each edge node.The selected set maximizes predicted content hit rate for that time slot, and a content may be cached at multiple edge nodes.

C. Regret Analysis

The section analyzes regret for RPUC under zero-mean noise and motivates HPDT for unknown noise structures. RPUC approaches optimal caching asymptotically, while H∞ filtering provides performance-guaranteed location-feature estimation without prior noise-process information.

  • RPUC regret analysis: Under zero-mean noise, RPUC achieves near-optimal performance with time-averaged regret of order O(...).The regret is analyzed theoretically under bounded attributes and demands.
  • RPUC regret analysis: RPUC estimation error combines linear-model error with ridge-regression bias and an added perturbation for uncertainty.The perturbation is managed by a time-varying control parameter α_t.
  • Motivation for HPDT: When noise is not zero-mean or its statistics are unavailable, RPUC may perform poorly, motivating robust prediction for uncertain noise.Noise can depend on population, social function, or weather conditions.
  • HPDT estimation: HPDT uses H∞ filtering to estimate location features without a priori noise-process information, assuming only finite noise magnitude.Its prescribed performance bound supports robust estimation over finite disturbances.
  • HPDT estimation: The resulting iterative H∞ filtering procedure produces performance-guaranteed location-feature estimates that support subsequent popularity prediction and caching.The estimates are updated online from observed demand and used for content-popularity prediction.

C. From Determining ψ to the HPDT Caching Algorithm

HPDT dynamically selects its performance threshold so the filter remains feasible while controlling estimation cost. It then alternates prediction, location-aware caching, and demand-based updates at each time slot.

  • Threshold selection: A smaller prescribed threshold ψ can reduce estimation error, but overly small values may make the H∞ recursion infeasible.The matrix update can become singular when ψ is too small.
  • HPDT caching algorithm: Algorithm 2, HPDT, outputs the files cached in each edge node and takes ξ close to but larger than one as input.The algorithm is an H∞ filter prediction method with a dynamic threshold.
  • HPDT caching algorithm: The online HPDT iteration therefore consists of prediction, optimization and caching, followed by observation and filter updating.Different edge nodes may cache overlapping content sets.
  • HPDT caching algorithm: At each time slot, HPDT predicts location features, caches contents with the highest predicted hit rates at each edge node, and observes cached-file demand.Observed empirical hit rates update the H∞ filter and produce the next location-feature estimate.
  • Threshold selection: HPDT adaptively tunes ψ_{t+1} to maintain positive definiteness and minimize the upper bound of the cost function.The threshold is selected at each iteration rather than fixed throughout operation.

D. Regret Analysis

HPDT has a bounded-regret guarantee under the linear content-hit model and bounded attributes, but its worst-case robustness can be conservative. In the noise-free case, its time-averaged regret tends to zero as the horizon grows.

  • HPDT guarantee: The H∞ filter provides robust location-feature estimation without assuming a statistical noise model, while its matrix state remains positive definite under adaptive thresholding.The threshold controls feasibility and the resulting performance bound.
  • HPDT guarantee: Theorem 2 bounds HPDT time-averaged regret by an order O(...) expression under the linear model and bounded attributes and disturbances.The theorem assumes bounded feature vectors and corresponding bounds on initial states and noise.
  • HPDT guarantee: When the linear model is noise-free, HPDT time-averaged regret tends to zero as T grows to infinity.With noise, HPDT may not approach the optimum, and performance depends on noise magnitude.
  • HPDT limitation: H∞ filtering can be over-conservative because it accommodates all possible noise processes to minimize worst-case estimation error.This robustness trades statistical assumptions for broader disturbance tolerance.
  • Comparison: Under zero-mean noise, HPDT has lower regret than the corresponding comparison using RPUC.The cited discussion identifies this as a consequence of the H∞ filter’s behavior under zero-mean noise.

VI. NUMERICAL ANALYSIS AND EXPERIMENTAL RESULTS

The experiments decompose estimation error into variance and bias, compare ridge regression with HPDT across noise settings, and evaluate initialization and real-world caching behavior. HPDT is more robust in bias and MSE, while ridge regression is more stable with little historical data.

  • Experimental setting: The experiments use synthesized sequences and a YouTube dataset to assess estimator behavior and practical caching performance.The video set is randomly crawled from YouTube, and its popularity is highly skewed and long-tailed.
  • Error analysis: Mean square error is decomposed into variance and squared bias to analyze the proposed estimators’ accuracy.The two terms in the decomposition correspond to variance and bias of the estimated feature vector.
  • Error comparison: Ridge regression has smaller variance than HPDT when historical data are scarce, reflecting the stabilizing effect of its intentional penalty.The comparison is reported across the scenarios shown in Fig. 3.
  • Error comparison: HPDT achieves better bias and MSE under varying sampling rates across all tested scenarios, supporting its robustness.Its advantage over ridge regression increases as noise magnitude increases.
  • Initialization sensitivity: Larger eigenvalues in the initial matrix P_0 achieve better HPDT performance when the initial-state estimate has low confidence.The matrix should be selected using prior information about the initial condition.

1) Experiment Setup:

The experiments use crawled YouTube view statistics, transformed to emulate location diversity, and compare adaptive caching algorithms against hindsight, location-oblivious, and random benchmarks. Results show that popularity skewness affects performance, while location-based approaches outperform location-oblivious caching across caching sizes.

  • Dataset: The dataset contains 800 randomly crawled YouTube videos with view statistics through May 2017.The most popular video exceeded 2.85 billion views, whereas the least popular was rarely viewed.
  • Popularity profile: The most popular 10% of videos attract almost 90% of requests, indicating strongly skewed and long-tailed popularity.The top 50 videos account for almost 80% of total requests, and popularity is divided into highly, medium, and less skewed groups.
  • Location emulation: Global video statistics are shifted and randomly scaled to emulate request processes at different locations while preserving their patterns.This transformation represents location diversity despite unavailable local-area statistics.
  • Experimental configuration: The experiment uses 800 videos cached across 3 edge nodes, with view amounts from the past 7 days as content attributes.Algorithms gradually select predicted popular contents for each edge node, using caching sizes of 5, 20, and 100.
  • Baselines: The benchmarks are hindsight optimal, location oblivious, and random caching.The hindsight benchmark uses future information and therefore cannot be implemented in practice.
  • Results: Location-based RPUC and HPDT outperform location-oblivious caching across varying caching sizes, with HPDT stronger in highly skewed settings.RPUC and HPDT perform equally well in the medium-skewed area; RPUC is limited by significant nonzero-mean noise, while HPDT is conservative in worst-case noise.
  • Results: Content hit rates do not increase linearly with caching size because less popular contents attract nearly vanishing requests.Both proposed algorithms run online with typical sorting complexity O(nFlogF).

C. Discussions

The discussion frames location-aware popularity prediction as a linear-model problem with algorithms tailored to different noise processes. It reports asymptotic or guaranteed prediction behavior, practical applicability without training, and scope boundaries involving features, bandwidth, and neighboring edge nodes.

  • Extensions: The HPDT algorithm can be directly extended to time-variant location features.This extension is stated for the location-feature setting represented in the paper’s equations.
  • State estimation: H∞ filtering provides guaranteed-accuracy adaptive estimation for the linear state equation.The state evolves as θ_t+1 = Aθ_t + v_t, and H∞ estimation is applied to θ_n,t.
  • Practical scope: The approach can support push-based content distribution and various content types, including HAS video delivery.The work focuses on popularity prediction; available bandwidth estimation remains outside scope, with updates scheduled during off-peak periods.
  • Practical scope: For HAS streaming, popularity and network conditions jointly contribute to improved video streaming.The discussion relates caching full representations of popular videos and selected segments of less popular ones to caching resources.
  • Prediction framework: The paper models content popularity with a linear model and proposes online algorithms for different statistical noise models.The approach focuses on estimating location features and does not require training phases.
  • Theoretical results: RPUC asymptotically approaches the optimal content-hit-rate solution under zero-mean noise.The conclusion contrasts this condition with HPDT’s use when noise need not be zero-mean.
  • Theoretical results: HPDT uses an H∞ filter to achieve guaranteed prediction accuracy under worst-case noise.Both algorithms can be implemented without training phases, and their noise-related performance differences are numerically analyzed.
  • Conclusion: Real-dataset experiments demonstrate customized caching decisions in practical scenarios.Future work will exploit locational features of neighboring edge nodes to make better caching decisions.

APPENDIX A

The appendix decomposes prediction error into variance and ridge-regression bias, then bounds regret through confidence intervals and standard matrix inequalities. The analysis connects estimation accuracy to cumulative caching regret.

  • Error analysis: The estimation error decomposes into a variance term from the linear model and a bias term from ridge parameter µ.The variance term is bounded probabilistically using Azuma’s inequality.
  • Regret analysis: Confidence intervals define events where true content hit rates either fall outside or remain within their predicted intervals.The regret proof analyzes these two cases separately.
  • Regret analysis: When an estimate deviates beyond its confidence radius, the deviation probability is bounded by 2F^-1t^-2.This bound controls the frequency of the corresponding event across edge nodes.
  • Regret analysis: When all true hit rates lie within their confidence intervals, selected files’ regret is bounded using their upper-confidence estimates.The proof compares the selected file set with the optimum set.
  • Regret analysis: Determinant-trace and related matrix inequalities bound the cumulative contribution of confidence widths.These bounds support the second term in the regret decomposition.
  • Regret analysis: The final time-averaged caching regret follows by combining the estimation-error and event-frequency bounds.The derivation assumes bounded initialization error and bounded noises.
Loading 1809.00232v1…