Real-Time Video Content Popularity Detection Based on Mean Change Point Analysis
Sotiris Skaperas Lefteris Mamatas Arsenia Chorti
eess.SP











Real-Time Video Content Popularity Detection Based on Mean Change Point Analysis
    Sotiris Skaperas, Student Member, IEEE,
        Lefteris Mamatas, Member, IEEE,
        and Arsenia Chorti, Member, IEEE
Sotiris Skaperas and Lefteris Mamatas  are with the Department of Applied Informatics,
University of Macedonia, Greece, {sotskap,
emamatas}@uom.edu.gr
Arsenia Chorti is with ETIS / Université Paris Seine, Université Cergy-Pointoise, ENSEA, CNRS, France,
arsenia.chorti@ensea.fr.
Manuscript received July 2019.

    December 30, 2023
===================================================================================================================================================================================================================================================================================================================================================================================================================================================






Video content is responsible for more than 70% of the global IP traffic. Consequently, it is important for content delivery infrastructures to rapidly detect and respond to changes in content popularity dynamics. In this paper, we propose the employment of on-line change point (CP) analysis to implement real-time, autonomous and low-complexity video content popularity detection. Our proposal, denoted as real-time change point detector (RCPD), estimates the existence, the number and the direction of changes on the average number of video visits by combining: (i) off-line and on-line CP detection algorithms; (ii) an improved time-series segmentation heuristic for the reliable detection of multiple CPs; and (iii) two algorithms for the identification of the direction of changes. The proposed detector is validated against synthetic data, as well as a large database of real YouTube video visits. It is demonstrated that the RCPD can accurately identify changes in the average content popularity and the direction of change. In particular, the success rate of the RCPD over synthetic data is shown to exceed 94% for medium and large changes in content popularity. Additionally, the dynamic time warping distance, between the actual and the estimated changes, has been found to range between 20 samples on average, over synthetic data, to 52 samples, in real data. The rapid responsiveness of the RCPD is instrumental in the deployment of real-time, lightweight load balancing solutions, as shown in a real example.




Video content popularity detection, change point analysis, on-line change point detection, binary segmentation algorithm, load balancing.























§ INTRODUCTION


Video content is projected to account for 82% of the global Internet traffic by 2020, significantly increased from 72% in 2016 <cit.>. In parallel, novel emerging networking, cloud and edge computing paradigms with significant elasticity capabilities appeared recently, e.g., software-defined networks (SDN) <cit.>, cloud orchestration proposals <cit.> and content distribution networks (CDNs) <cit.>. These advances offer the means to respond quickly to changes in content popularity dynamics with appropriate adaptations, e.g., in terms of efficient server resource allocation schemes, load balancing or content caching. As a result, the early detection of changes in content popularity <cit.>, <cit.> is proving a highly important topic and can have a significant impact on the network traffic and the utilization of servers.

So far, the vast majority of research efforts have focused on the prediction of content popularity dynamics, as opposed to their real time detection, which is the focus of this study. There is a multitude of reasons as to why the precision of even state-of-the-art prediction algorithms can be impaired. A variety of factors – both from the digital and the physical world – can influence the users' Internet surfing behavior, e.g., <cit.>: (i) the quality, type (e.g., commercial or user-provided) and life-time of content; (ii) its relevance to users and physical events; (iii) the social interactions between users; and (iv) the content promotion strategies involved. Importantly, mid-term and long-term content popularity prediction <cit.> – and corresponding adaptations in the network or cloud environment – can prove highly inaccurate <cit.> and thus result in sub-optimal service planning, provisioning, and utilization of resources or violation of service level agreements. 

In this work, to address the aforementioned shortcomings of the commonly employed prediction algorithms, we propose a corresponding detector, referred to as the “real-time change point detector” (RCPD). The RCPD is compatible with modern, flexible networking and cloud approaches, that are highly adaptive and can respond to short-term network dynamics. With accurate, on-line content popularity detection, discrepancies between inaccurate predictions and actual changes can be alleviated. The RCPD is real-time, lightweight, accurate and is parameterized autonomously by analyzing historical data. 

In the RCPD, we employ the change point (CP) detection theory and algorithms; their suitability is confirmed against a large number of synthetic as well as real YouTube video datasets. In this contribution, the early detection of changes in the average content popularity is addressed with a novel CP detection methodology, consisting of a training phase, using historical data, and, an on-line phase. In the training phase, we employ a modified off-line CP detection scheme to configure the on-line (sequential) algorithm's parameters. This approach is shown to greatly improve the accuracy of the on-line detector, as in essence, the algorithm parameterization is not arbitrary but rather extracted from corresponding historical data. To the best of our knowledge, it is the first time in the literature that retrospective (off-line) and sequential (on-line) CP detection schemes are combined in a single algorithm operating autonomously (i.e., without manual configuration of parameters).  




Besides that, our approach complements the off-line scheme with an improved time-series segmentation heuristic for the detection of multiple CPs.  Furthermore, we propose two possible variations for the on-line CP algorithm, the first based on the standard cumulative sum (CUSUM) procedure <cit.> and the second on the ratio-type CUSUM procedure <cit.>[The advantage of ratio-type CUSUM is that it does not require the estimation of long-run covariance (variance) matrices, which is the case for the standard CUSUM method.]. Additionally, we introduce two alternative indicators to detect the direction of changes: the first one is directly derived from the statistical test of the on-line CP procedure, while the second is based on a modified exponential moving average filter, extensively used in econometrics. As discussed in Sections III and IV, the RCPD combines all the above mentioned algorithmic elements, and is based on sufficiently general and convenient assumptions. Moreover, unlike other approaches e.g., <cit.>, we employ methods that allow dependence between observations (in the form of t-dependence), leading to more realistic assumptions for the statistical structure of the content visits. 

We evaluate the proposed detector and its individual algorithmic components (i.e., the off-line / on-line test statistics, the time-series segmentation algorithm and the trend indicator), over synthetic and real YouTube content views data. Our experiments using synthetic data, generated by an autoregressive moving average (ARMA) filter, demonstrate: 


  * The superior performance of the proposed time-series segmentation heuristic over the standard approach, improving the true alarm rates by up to 43%. 

  * The ability of the two proposed trend indicators to identify the direction of estimated changes, with successful identification rates exceeding 99%, in all cases.

  * The RCPD performance; the true alarm rates surpass 94% for medium / large changes in the mean number of content views, while the corresponding CP identification lag ranges between 10 to 20 instances, confirming the real-time operation of the detector. On the other hand, the RCPD achieves very small false alarm rates, well within the limits of the statistical error specified by the chosen significance level of the CP algorithms.


Furthermore, our tests on real YouTube content views datasets show that:


  * YouTube video views match the underlying assumptions of the RCPD, i.e., the content popularity time-series datasets can be modeled as t-dependent.

  * The RCPD can detect CPs in more than 70% of the videos in our dataset, implying a sufficiently high number of content popularity changes and the suitability of the CP theory framework for content popularity detection. 

  * The successful CP direction identifications exceed 91%, i.e., the proposed trend indicators work for real data. 

  * The average dynamic time warping (DTW) distance <cit.>, <cit.> between the identified CPs and a benchmark off-line algorithm was estimated to be 52 time instances on average, showcasing the rapid responsiveness of the RCPD. 

  * The overall processing cost of the RCPD is very low; notably, it took less than one second to process 882 videos on a typical personal computer (PC).


Finally, as a proof-of-concept, we demonstrate the applicability of the proposed algorithm in a real load balancing scenario. We provide a set of measurements showcasing improvements in terms of the clients' connectivity time to download specific content, without a significant impact on the utilization of the content servers. This is achieved due to the deployment of additional content caches, an event triggered by the output of the proposed RCPD detector. 

The rest of the paper is organized as follows. In Section II, we discuss our approach with respect to related works. In Section III, we present the training phase of the RCPD algorithm, while the on-line phase is discussed in Section IV. In Section V, we present four experiments over synthetic data, providing an extensive validation of the RCPD and its subroutines, while in Section VI, we discuss corresponding experiments using a database of real YouTube video views. In Section VII, we demonstrate the load balancing gains achieved through the use of the RCPD, in a realistic content provisioning scenario. Our conclusions and directions for future work are presented in Section VIII.
  





§ RELATED WORKS


In this Section, we discuss how this work relates to the literature of video content popularity prediction, on one hand, and, anomaly detection (i.e., CP analysis), on the other hand.

The topic of content popularity attracted a lot of attention in recent years, because of its importance in a number of applications, such as network dimensioning (e.g., capacity planning or scaling of resources), on-line marketing (e.g., advertising, recommendation systems) or real-world outcome prediction (e.g., analysis of economical trends) <cit.>. The main approaches used for content popularity estimation can be categorized as: (i) cumulative growth studies, estimating the “amount of attention" from the publication instance to the prediction moment  <cit.>; (ii) temporal analysis approaches, i.e., how content visits evolve over time <cit.>; and (iii) clustering methods of content with similar popularity trends <cit.>. We note that many content popularity studies consider the aggregate behavior of a particular content, e.g., <cit.>, <cit.>, whereas we study the real-time behavior of video views time-series. In addition, studies using clustering methods <cit.> are based on content popularity prediction and adopt parametric models, unlike the RCPD algorithm that is non-parametric.  




To the best of our knowledge, our earlier conference paper <cit.> is the first in the literature proposing CP techniques <cit.> for content popularity detection. The RCPD algorithm falls into the general category of anomaly detection <cit.>; in essence, we assume that no changes in popularity constitutes the normal behavior of video content and search for deviations from this behavior. Non-parametric anomaly detection has typically been considered for the detection of abnormalities in the network traffic. As an example, in <cit.> an algorithm was proposed based on the Shiryaev-Roberts procedure for anomaly detection in computer network traffic. In <cit.> and <cit.>, CUSUM based approaches were introduced for the detection of SYN attacks. 

Further examples of parametric anomaly detection methods include <cit.>, in which a bivariate sequential generalized likelihood ratio test (LRT) was proposed, accounting for the packet rate – assumed to follow a Poisson distribution – and the packet size  – assumed to follow a normal distribution. Other parametric anomaly detection approaches assume a particular underlying process for the normal behavior and search for anomalies on the residuals of the process. For example, in <cit.>, Kalman filtering is combined with several CP methods, such as CUSUM and LRT, to detect anomalies in origin-destination flows. In <cit.>, traffic flows (in the form of TCP's finite state machine), are modeled using Markov chains and an anomaly detection mechanism based on the generalized LRT algorithm is developed. 
As opposed to previous content popularity prediction works, in this paper we introduce a novel CP detection methodology that provides accurate, lightweight, autonomous and on-line CP detection of content popularity. We formulate the detection of a change in the average content popularity as a statistical hypothesis test and employ non-parametric procedures to avoid a particular distribution assumption (such as a specific copula model). This context ensures low convergence time since it avoids estimating a large number of model parameters and restrictive assumptions that may not match the structure of the time-series. Furthermore, we avoid problems of parametric models that require parameters' fitting and selection, which become challenging as new data become available. In the proposed RCPD algorithm, an off-line phase specifies important parameters for the on-line phase; these parameters are re-evaluated dynamically after a detected CP. Our load-balancing experiments, elaborated in <cit.>, demonstrate the RCPD's behavior in a real test-bed deployment. 
Up to now there are only a handful of proposals addressing the challenges of new flexible networking and cloud architectures accounting for content popularity. Exceptions include <cit.> in which a logistic-loss machine learning approach to content popularity prediction is applied for a Fog RAN environment, and, our recent papers <cit.> and <cit.>. In  <cit.>, the algorithm – outlined in <cit.> and presented extensively in the present – is integrated into an elastic CDN framework based on lightweight cloud capabilities using Unikernels. <cit.> focuses on the platform details rather than on the CP algorithm; it confirms experimentally the suitability of the latter for relevant flexible network and cloud architectures. The first detailed description of the proposed CP detection algorithm is presented in the following Sections, along with a rich set of validation results.
We elaborate on the two phases of the RCPD in Sections III and IV respectively and provide the corresponding pseudo-code.       



§ TRAINING (OFF-LINE) PHASE

In this Section, the training phase of the algorithm is discussed and the fundamental components of the off-line scheme are presented. We note that standard off-line CP schemes can only detect a single CP. To address the issue of detection of multiple CPs, we modify the basic algorithm with a novel time-series segmentation heuristic, that belongs to the family of binary segmentation algorithms. 



 §.§ Basic Off-line Approach
 

Let {X_n:n∈ℕ} be a sequence of r- dimensional random vectors (r.v.). The first dimension represents the number of views for a specific video content within a time period n∈{1,…, N}, while the other dimensions could be optionally used to represent other content popularity features, such as likes, comments, etc. We assume that X_1,...,X_N can be written as, 

    X_n=μ_n+Y_n,   1⩽n⩽N

where {μ_n:n∈ℕ} is the mean value of video visits, {Y_n:n∈ℕ} a random component with zero mean E[Y_n]=0 and positive definite covariance matrix, E[Y_nY^T_n]=Σ, while E[·] denotes expectation. We further assume that the time-series is t-dependent, implying that for t_1, t_2, t ∈ℕ, Y_t_1 is independent of Y_t_2 if |t_1-t_2|>t.   

The model in (<ref>) and the underlying assumption of t-dependence are in agreement with statistical characterizations of the distribution of visits, which have been shown in numerous analyses to follow either a Zipf <cit.> or a Zipf-Mandelbrot <cit.> distribution for both commercial and user-generated content. Furthermore, it is confirmed in the real YouTube datasets used in the present work through the evaluation of the time-series's Hurst exponents, as will be discussed in Section <ref>. 

The off-line analysis tests the constancy (or not) of the mean values up to the current time N. Hence, we define the following null hypothesis of constant mean, 
    	
    H_0:  μ_1=…=μ_N,

against the alternative,

    H_1:   μ_1=…=μ_k_off^*≠μ_k_off^*+1=…=μ_N,

indicating that the mean value changed at the unknown (time) point k_off^*∈{ 1,… ,N}.
Considering (<ref>) and the corresponding assumptions for the stochastic process X_n, we develop a non-parametric CUSUM test statistic following <cit.>. The test statistic TS_off, can be viewed as a max-type procedure,

    TS_off=max_1⩽n⩽NC^T_nΩ_N^-1C_n,

where the parameter C_n is the retrospective CUSUM detector,

    C_n=1√(N)(∑_i=1^nX_i-nX_1,N),

while X_1,N=1/N∑_i=1^NX_i denotes the sample mean. Ω_N represents a suitable estimator of the long-run covariance Ω, where

    Ω=∑_i=-∞^∞𝐂𝐨𝐯(X_nX_n-i).

The estimator should satisfy,

    Ω_NΩ

where  denotes convergence in probability. 
Several estimators have been proposed in the literature that satisfy (<ref>), including kernel-based <cit.>, bootstrap-based <cit.>, etc. Considering our requirement for real-time detection (low computational time), a kernel-based estimator is more suitable; in this context, we employ the Bartlett estimator, so that

    Ω_N=Σ_0+∑_w=1^Wk_BT(w/W+1)(Σ_w+Σ^T_w),

which satisfies (<ref>), while 
the function k_BT(.) corresponds to the Bartlett weight,

    k_BT(x)=  
             1-x, for x⩽1 
    
    0, otherwise,

and Σ_w denotes the empirical auto-covariance matrix for lag w, 

    Σ_w=1/N∑_n=w+1^N(X_n-X)(X_n-w-X)^T.

Finally, we chose W=log_10(N) as in <cit.>.
The long-run covariance is involved in the test statistic to incorporate the dependence structure of the r.v. into the statistical analysis, through the integration of second order statistical properties. This approach is suitable for the targeted context since we avoid a restrictive assumption for the dependence structure of the observations. 
Going back to the basic question of rejecting or not H_0, we need to obtain critical values, denoted by cv_off, for the test statistic. We approach this issue by considering the asymptotic distribution of the test statistic under H_0,

    TS_offcv_off=sup_0⩽t⩽1∑_j=1^rB_j^2(t)  (N→∞),

where  denotes convergence in distribution, (B_j(t):t∈[0,1]),  1⩽j⩽r, are independent standard Brownian bridges B(t)=W(t)-tW(1), and W(t) denotes the standard Brownian motion with mean 0 and variance t. The critical values for several significance levels α can be computed using Monte Carlo simulations that  approximate the paths of the Brownian bridge on a fine grid. The last step is to estimate the unknown CP, defined previously as k_off^*, under H_1, given by:

    k̂^*_off=1N_1⩽n⩽NTS_off.




 §.§ Extended Off-line Approach
   
The above hypothesis test identifies the existence of at most one CP and does not ensure that the sample remains statistically stationary in either direction of the detection. In particular, by construction (see (<ref>)),  the off-line test statistic detects the CP with the highest magnitude. Therefore, for the detection of multiple CPs we need to rephrase the hypothesis test H_1, as follows:

    H_1:   μ_1=…=μ_k_1≠μ_k_1+1=…=μ_k_2≠…
    ⋯≠μ_k_τ-1+1=…=μ_k_τ≠μ_k_τ+1=…=μ_N.

A greedy technique to identify multiple CPs is the binary segmentation (BS) algorithm. The standard BS algorithm relies on the general concept of binary segmentation and is an extension of the single CP estimator. First, a single CP is searched for in the time-series. In case of no change, the procedure stops and H_0 is accepted. Otherwise, the detected CP is used to divide the time-series into two segments in which new searches are performed. The procedure is iterated until no more CPs are detected. The BS algorithm is lightweight (computational time O(NlogN)), while its conceptual simplicity leads to efficient implementations. On the other hand, it has been shown in the literature <cit.>, <cit.>,

that the standard BS algorithm tends to overestimate the number of CPs, as it does not cross-validate them after their detection. 
In the extended off-line approach, we propose the modification of the standard BS with a cross-validation step of the estimated CPs. The cross-validation step is similar to that used in the iterative cumulative sum of squares (ICSS) segmentation algorithm <cit.>, which is used to search for CPs on the marginal variance of independent and identically distributed (i.i.d.) r.vs. In the extended off-line algorithm we consider the CPs estimated from the standard BS in pairs and check if H_0 is rejected in the segment delimited by each pair. If H_0 is not rejected in a particular segment, then no change can be detected in it; as a result, all CPs that fall in the respective segment are eliminated. 
The improvement, in terms of accuracy, is shown through simulation results in Section IV. The pseudo-code of the modified BS algorithm is given in Algorithm 1; note that we integrate the algorithm with the test statistic TS_off, given in equation (<ref>) and the corresponding critical value (cv_off) given in (<ref>). 
    
     
	
	
	





