text:
\section{Introduction}
Networked services in the Web 2.0 era focus increasingly on the user participation in producing and interacting with rich media. The role of the Internet itself has evolved from the original use as a communication infrastructure, where users passively receive and consume media content to a social ecosystem, where users equipped with mobile devices constantly generate  media  data through a variety of sensors (cameras, GPS, accelerometers, etc.) and applications and, subsequently, share this acquired data through social media. Hence, social media is recently being used to provide situational awareness and inform predictions and decisions in a variety of application domains, ranging from live or on-demand event broadcasting, to security and surveillance~\cite{Trottier}, to health communication~\cite{Chou}, to disaster management~\cite{Sakaki},  to economic forecasting~\cite{Choi}. In all these applications, forecasting the popularity of the content shared in a social network is vital due to a variety of reasons. For network and cloud service providers, accurate forecasting facilitates prompt and adequate reservation of computation, storage, and bandwidth resources~\cite{Liu}, thereby ensuring smooth and robust content delivery at low costs. For advertisers, accurate and timely popularity prediction provides a good revenue indicator, thereby enabling targeted ads to be composed for specific videos and viewer demographics. For content producers and contributors, attracting a high number of views is paramount for attracting potential revenue through micro-payment mechanisms.

While popularity prediction is a long-lasting research topic~\cite{Szabo}~\cite{Cha}~\cite{Wu}~\cite{Pinto}, understanding how social networks affect the popularity of the media content and using this understanding to make better forecasts poses significant new challenges. Conventional prediction tools have mostly relied on the history of the past view counts, which worked well when the popularity solely depended on the inherent attractiveness of the content and the recipients were generally passive. In contrast, social media users are proactive in terms of the content they watch and are heavily influenced by their social media interactions; for instance, the recipient of a certain media content may further forward it or not, depending on not only its attractiveness, but also the situational and contextual conditions in which this content was generated and propagated through social media~\cite{Li}. For example, the latest measurement on Twitter's Vine, a highly popular short mobile video sharing service, has suggested that the popularity of a short video indeed depends less on the content itself, but more on the contributor's position in the social network~\cite{Zhang}. Hence, being situation-aware, e.g. considering the content initiator's information and the friendship network of the sharers, can clearly improve the accuracy of the popularity forecasts. However, critical new questions need to be answered: which situational information extracted from social media should be used, how to deal with dynamically changing and evolving situational information, and how to use this information efficiently to improve the forecasts?

As social media becomes increasingly more ubiquitous and influential, the video propagation patterns and users' sharing behavior dynamically change and evolve as well. Offline prediction tools~\cite{Szabo}~\cite{Galuba}~\cite{Hong}~\cite{Lerman} depend on specific training datasets, which may be biased or outdated, and hence may not accurately capture the real-world propagation patterns promoted by social media. Moreover, popularity forecasting is a \textit{multi-stage} rather than a single-stage task since each video may be propagated through a cascaded social network for a relatively long time and thus, the forecast can be made at any time while the video is being propagated. A fast prediction has important economic and technological benefits; however, too early a prediction may lead to a low accuracy that is less useful or even damaging (e.g. investment in videos that will not actually become popular). The timeliness of the prediction has yet to be considered in existing works~\cite{Cha}-\cite{Lerman}~\cite{Wu}~\cite{Pinto} which solely focus on maximizing the accuracy. Hence, we strongly believe that developing a systematic methodology for accurate and timely popularity forecasting is essential.

In this paper, we propose for the first time a systematic methodology and associated online algorithm for forecastingl popularity of videos promoted by social media. Our Social-Forecast algorithm is able to make predictions about the popularity of videos while jointly considering the accuracy and the timeliness of the prediction. We explicitly consider the unique situational conditions that affect the video propagated in social media, and demonstrate how this \textit{context information} can be incorporated to improve the accuracy of the forecasts. The unique features of Social-Forecast as well as our key contributions are summarized below:

\begin{itemize}
\item We rigorously formulate the online popularity prediction as a multi-stage sequential decision and online learning problem. Our solution, the Social-Forecast algorithm, makes multi-level popularity prediction in an online fashion, requiring no {\em a priori} training phase or dataset. It exploits the dynamically changing and evolving video propagation patterns through social media to maximize the prediction reward. The algorithm is easily tunable to enable tradeoffs between the accuracy and timeliness of the forecasts as required by various applications, entities and/or deployment scenarios.
\item We analytically quantify the regret of Social-Forecast, that is, the performance gap between its expected reward and that of the best prediction policy which can be only obtained by an omniscient oracle having complete knowledge of the video popularity trends. We prove that the regret is sublinear in the number of video arrivals, which implies that the expected prediction reward asymptotically converges to the optimal expected reward. The upper bound on regret also gives a lower bound on the convergence rate to the optimal average reward.
\item We validate Social-Forecast's performance through extensive experiments with real-world data traces from RenRen (the largest Facebook-like online social network in China). The results show that significant improvement can be achieved by exploiting the situational and contextual meta-data associated with the video and its propagation through the social media. Specifically, the Social-Forecast algorithm outperforms existing view-based approaches by more than 30\% in terms of prediction rewards.
\end{itemize}
The rest of the paper is organized as follows. Section II discusses related works. In Section III, we describe the system model and rigorously formulate the online popularity prediction problem. Section IV presents a systematic methodology for determining the optimal prediction policy with complete prior knowledge of the video propagation pattern. In Section V, we propose the online learning algorithm for the optimal prediction policy and prove that it achieves sublinear regret bounds. Section VI discusses the experimental results and our findings. Section VII concludes this paper.

\section{Related Works}
In this section, we review the representative related works from both the application and the theoretical foundation perspectives.

\subsection{Popularity Prediction for Online Content}
Popularity prediction of online content has been extensively studied in the literature. Early works have focused on predicting the future popularity of content (e.g. video) on conventional websites such as YouTube. Various solutions are proposed based on time series models like ARMA (Autoregressive moving average)~\cite{Niu}~\cite{Glzrsun}~\cite{Amondeo}, regression models~\cite{Wang}~\cite{Lee}~\cite{Rowe} and classification models~\cite{Wang}~\cite{Shamma}~\cite{Siersdorfer}. These methods are generally view-based, meaning that the prediction of the future views is solely based on the early views, while disregarding the situational context during propagation. For instance, it was found that a high correlation exists between the number of video views on early days and later days on YouTube~\cite{Cha}. By using the history of views within the past 10 days, the popularity of videos can be predicted up to 30 days ahead~\cite{Szabo}. While these predictions methods provide satisfactory performance for YouTube-like accesses, their performance is largely unacceptable~\cite{Li} when applied to predicting popularity in the social media context. This is because in this case the popularity of videos evolves in a significantly different manner which is highly influenced by the situational and contextual characteristics of the social networks in which the video has propagated~\cite{Li-IWQoS}.

Recently, there have been numerous studies aiming to accurately predicting the popularity of content promoted by social media~\cite{Chou}~\cite{Sakaki}~\cite{Asur}-\cite{Kooti}. For instance, a propagation model is proposed in~\cite{Galuba} to predict which users are likely to mention which URLs on Twitter. In~\cite{Hong}, the retweets prediction on Twitter is modeled as a classification problem, and a variety of context-aware features are investigated. For predicting the popularity of news in Digg, such aspects as website design have been incorporated~\cite{Lerman}, and for predicting the popularity of short messages, the structural characteristics of social media have been used~\cite{Bao}. For video sharing in social media, our earlier work~\cite{Li} has identified a series of context-aware factors which influence the propagation patterns.

Our work in this paper is motivated by these studies, but it is first systematic solution for forecasting the video popularity based on the situational and contextual characteristics of social media. First, existing works are mostly measurement-based and their solutions generally work offline, requiring existing training data sets. Instead, Social-Forecast operates entirely online and  does not require any a priori gathered training data set. Second, Social-Forecast is situation-aware and hence it can inherently adapt on-the-fly to the underlying social network structure and user sharing behavior. Last but not least, unlike the early empirical studies which employ only simulations to validate the performance of their predictions, we can rigorously prove performance bounds for Social-Forecast.

Importantly, our Social-Forecast can be easily extended to predict other trends in social media (such as predicting who are the key influencers in social networks, which tweets and news items may become viral, which content may become popular or relevant etc.) by exploiting contextual and situational awareness. For instance, besides popularity, social media has been playing an increasingly important role in predicting present or near future events. Early studies show that the volume and the frequency of Twitter posts can be used to forecast box-office revenues for movies~\cite{Asur} and detect earthquakes~\cite{Sakaki}. Sentiment detection is investigated in~\cite{Barbosa} by exploring characteristics of how tweets are written and meta-information of the words that compose these messages. In~\cite{Chou}, Google Trends uses search engine data to forecast near-term values of economic indicators, such as automobile sales, unemployment claims, travel destination planning, and consumer confidence. Social-Forecast can be easily adapted for deployment in these applications as well.

Table \ref{comparisontable} provides a comprehensive comparison between existing works on popularity prediction and Social-Forecast, highlighting their differences.

\subsection{Quickest Detection and Contextual Bandits Learning}
In our problem formulation, for each video, the algorithm can choose
to make a prediction decision using the currently observed context
information or wait to make this prediction until the next period,
when more context information arrives. This introduces a tradeoff
between accuracy and delay which relates to the literature on quickest
detection~\cite{Poor}~\cite{Krishnamruthy}~\cite{Lai} which
is concerned with the problem of detecting the change in the underlying
state (which has already occurred in the past). For example,
authors in~\cite{Lai} study how to detect the presence of primary
users by taking channel sensing samples in cognitive radio systems.
In the considered problem, there is no underlying state; in fact, the state is continuously and dynamically changing, and the problem becomes forecasting how it will evolve and which event will occur in the future. Moreover, many quickest detection solutions assume prior knowledge of the hypotheses
~\cite{Lai} while this knowledge is unknown a priori in our problem
and needs to be discovered over time to make accurate forecasts.

Our forecasting algorithm is based on the contextual bandits framework
~\cite{Tekin}-\cite{Chu} but with
significant innovations aimed at tackling the unique features of the
online prediction problem. First, most of the prior work~\cite{Slivkins}-\cite{Chu}
on contextual bandits is focused on an agent making a single-stage
decision based on the provided context information for each incoming
instance. In this paper, for each incoming video instance, the agent
needs to make a sequence of decisions at multiple stages. The context
information is stage-dependent and is revealed only when that stage
takes place. Importantly, the reward obtained by selecting an action
at one stage depends on the actions chosen at other stages and thus,
rewards and actions at different stages are coupled. Second, in existing
works~\cite{Tekin}-\cite{Chu}, the estimated rewards of an action can be updated only after the action is selected. In our problem, because the prediction action does not
affect the underlying popularity evolution, rewards can be computed
and updated even for actions that are not selected. In particular, we update the reward of an action as if it was selected. Therefore, exploration
becomes virtual in the sense that explicit explorations are not needed and hence, in each period, actions with the best estimated rewards can always be selected, thereby improving the learning performance.

\begin{table}
  \centering

  \includegraphics[scale=0.7]{ComparisonTable.eps}\\
  \caption{Comparison with existing works on popularity prediction for online content.}\label{comparisontable}
\end{table}

\section{System Model}
\begin{figure*}[t]
  \centering

  \includegraphics[scale=0.8]{systemdiagram.eps}\\
  \caption{System diagram.}\label{system}
\end{figure*}

\subsection{Sharing Propagation and Popularity Evolution}
We consider a generic Web 2.0 information sharing system in which videos are shared
by users through social media (see Figure \ref{system} for
a system diagram). We assign each video with an index $k\in\{1,2,...,K\}$
according to the absolute time $t_{init}^{k}$ when it is initiated\footnote{It is easy to assign unique identifiers if multiplel videos which are generated/initiated at the same time.}. Once a video is initiated, it will be propagated through the social media for some time duration. We assume a discrete time model where a period can be minutes, hours, days, or any suitable time duration. A video is said to have an age of $n\in\{1,2,...\}$ periods if it has been propagated through the social media for $n$ periods. In each period, the video is further shared and viewed by users depending on the sharing and viewing status of the previous period. The propagation characteristics of video $k$ up to age $n$ are captured by a $d_{n}$-dimensional vector ${\boldsymbol{x}}_{n}^{k}\in\mathcal{X}_{n}$ which includes information such as the total number of views and other situational and contextual information such as the characteristics
of the social network over which the video was propagated. The specific
characteristics that we use in this paper will be discussed in Section
VI. In this section, we keep ${\boldsymbol{x}}_{n}^{k}$ in an abstract form and
call it succinctly the \textit{context (and situational) information}
at age $n$.

Several points regarding the context information are noteworthy. First, the context space $\mathcal{X}_{n}$ can be different at different ages $n$. In particular, ${\boldsymbol{x}}^k_n$ can include all history information of video $k$'s propagation characteristics up to age $n$ and hence ${\boldsymbol{x}}^k_{n}$ includes all information of ${\boldsymbol{x}}^k_{m},\forall m < n$ (See Figure \ref{contexthistory}). Thus the type of contextual/situational information is also age-dependent. Second, ${\boldsymbol{x}}_{n}^{k}$ can be taken from a large space, e.g. a finite space with a large number of values or even an infinite space. For example, some dimensions of ${\boldsymbol{x}}^k_n$ (e.g. the Sharing Rate used in Section VI) take values from a continuous value space and ${\boldsymbol{x}}^k_n$ may include all the past propagation characteristics (e.g. ${\boldsymbol{x}}^k_{m} \in {\boldsymbol{x}}^k_n, \forall m < n$). Third, at age $n$, ${\boldsymbol{x}}_{m}^{k},\forall m>n$ are not yet revealed since they represent
future situational and contextual information which is yet to be realized. Hence, given the context information ${\boldsymbol{x}}^k_n$ at age $n$, the future context information ${\boldsymbol{x}}_{m}^{k},\forall m>n$ are random variables.

\begin{figure}
  \centering

  \includegraphics[scale=0.9]{contexthistory.eps}\\
  \caption{An illustration of context information taking the history characteristics.}\label{contexthistory}
\end{figure}

We are interested in predicting the future popularity status of the video by the end of a pre-determined age $N$, and we aim to make the prediction as soon as possible. The choice of $N$ depends on the specific requirements of the content provider, the advertiser and the web hosts. In this paper, we will treat $N$ as given\footnote{This assumption is generally valid given that the video sharing events have daily and weekly patterns, and the active lifespans of most shared videos through social media are quite limited~\cite{Li-IWQoS}}. Thus, the context information for video $k$ during its lifetime of $N$ periods is collected in ${\boldsymbol{x}}^{k}=({\boldsymbol{x}}_{1}^{k},{\boldsymbol{x}}_{2}^{k},...,{\boldsymbol{x}}_{N}^{k})$. For expositional simplicity, we also define ${\boldsymbol{x}}_{n^{+}}=({\boldsymbol{x}}_{n+1},...,{\boldsymbol{x}}_{N})$, ${\boldsymbol{x}}_{n^{-}}=({\boldsymbol{x}}_{1},...,{\boldsymbol{x}}_{n-1})$ and ${\boldsymbol{x}}_{-n}=({\boldsymbol{x}}_{n^{-}},{\boldsymbol{x}}_{n^{+}})$.

Let $\mathcal{S}$ be the popularity status space, which is assumed to be finite. For instance, $\mathcal{S}$ can be either a binary space \{Popular, Unpopular\} or a more refined space containing multiple levels of popularity such as \{Low Popularity, Medium Popularity, High Popularity\} or any such refinement. We let $s^k$ denote the popularity status of video $k$ by the end of age $N$. Since $s^k$ is realized only at the end of $N$ periods, it is a random variable at all previous ages. However, the conditional distribution of $s^k$ will vary at different ages since they are conditioned on different context information. In many scenarios, the conditional distribution at a higher age $n$ is more informative for the future popularity status since more contextual information has arrived. Nevertheless, our model does not require this assumption to hold.

\subsection{Prediction Reward}
For each video $k$, at each age $n=1,...,N$, we can make a prediction decision $a^k_n \in \mathcal{S}\cup \{\textrm{Wait}\}$. If $a^k_n \in \mathcal{S}$, we predict $a^k_n$ as the popularity status by age $N$. If $a^k_n = \textrm{Wait}$, we choose to wait for the next period context information to decide (i.e. predict a popularity status or wait again). For each video $k$, at the end of age $N$, given the decision action vector ${\boldsymbol{a}}^k$, we define the {\it age-dependent reward} $r^k_n$ at age $n$ as follows,
\begin{equation}\label{reward}
r^k_n = \left\{
\begin{array}{ll}
U(a^k_n, s^k, n), &\textrm{if}~a^k_n \in \mathcal{S}\\
r^k_{n+1}, &\textrm{if}~a^k_n = \textrm{Wait}
\end{array}\right.
\end{equation}
where $U(a^k_n, s^k, n)$ is a reward function depending on the accuracy of the prediction (determined by $a^k_n$ and the realized true popularity status $s^k$) and the timeliness of the prediction (determined by the age $n$ when the prediction is made).

The specific form of $U(a^k_n, s^k, n)$ depends on how the reward is derived based on the popularity prediction based on various economical and technological factors. For instance, the reward can the ad revenue derived from placing proper ads for potential popular videos or the cost spent for adequately planning computation, storage, and bandwidth resources to ensure the robust operation of the video streaming services. Even though our framework allows any general form of the reward function, in our experiments (Section VI), we will use a reward function that takes the form of $U(a^k_n, s^k, n) = \theta(a^k_n, s^k) + \lambda \psi(n)$ where $\theta(a^k_n, s^k)$ measures the prediction accuracy, $\psi(n)$  accounts for the prediction timeliness and $\lambda > 0$ is a trade-off parameter that controls the relative importance of accuracy and timeliness.

Let $n^*$ be the first age at which the action is not ``Wait'' (i.e. the first time a forecast is issued). The {\it overall prediction reward} is defined as the $r^k = r^k_{n^*}$. According to equation \eqref{reward}, when the action is ``Wait'' at age $n$, the reward is the same as that at age $n+1$. Thus $r^k_{1} = r^k_{2} = ... = r^k_{n^*}$. This suggests that the overall prediction reward is the same as the age-dependent reward at age 1, i.e. $r^k = r^k_1$. For age $n > n^*$, the action $a^n_k$ and the age-dependent reward $r^k_n$ do not affect the realized overall prediction result since a prediction has already been made. However, we still select actions and compute the age-dependent reward since it helps learning the best action and the best reward for this age $n$ which in turn will help decide whether or not we should wait at an early age. Figure \ref{msd} provides an illustration on how the actions at different ages determine the overall prediction reward.

\begin{figure}
  \centering

  \includegraphics[scale=0.9]{multistagedecision.eps}\\
  \caption{An illustration for the multi-stage decision making. The first $n-1$ action is ``Wait''. If the age-$n$ action is ``Wait'', then $r^k_n = r^k_{n+1}$ which depends on later actions. If the age-$n$ action is not ``Wait'', then $r^k_{n} \neq r^k_{n+1}$ and $r^k$ does not depend on later actions. However, we can still learn the reward of action at age $n+1$ as if all actions before $n+1$ were ``Wait''. }\label{msd}
\end{figure}

{\it Remark}: The prediction action itself does not generate rewards. It is the action (e.g. online ad investment) taken using the prediction results that is rewarding. In many scenarios, this action can only be taken once and cannot be altered afterwards. This motivates the above overall reward function formulation in which the overall prediction reward is determined by the first non-``Wait'' action. Nevertheless, our framework can also be easily extended to account for more general overall reward functions which may depend on all non-``Wait'' actions. For instance, the action may be revised when a more accurate later prediction is made. In this case, the reward function $U(a^k_n, s^k, n)$ in \eqref{reward} will depend on not only the current prediction action $a^k_n \in \mathcal{S}$ but also all non-``Wait'' actions after age $n$. We will use the reward function in \eqref{reward} because of its simplicity for the exposition but our analysis also holds for general reward functions.

\subsection{Prediction Policy}
In this paper, we focus on prediction policies that depend on the
current contextual information. Let $\pi_{n}:\mathcal{X}_{n}\to\mathcal{S}\cup \{\textrm{Wait}\}$
denote the prediction policy for a video link of age $n$ and $\pi=(\pi_{1},...,\pi_{N})$
be the complete prediction policy. Hence, a prediction policy $\pi$ prescribes actions for all possible context information at all ages. For expositional simplicity, we also define $\pi_{n^{+}}=(\pi_{n+1},...,\pi_{N})$ as the policy vector
for ages greater than $n$, $\pi_{n^{-}}=(\pi_{1},...,\pi_{n-1})$
as the policy vector for ages smaller than $n$ and $\pi_{-n}=(\pi_{n^{-}},\pi_{n^{+}})$.
For a video with context information ${\boldsymbol{x}}^{k}$, the prediction policy
$\pi$ determines the prediction action at each age and hence the overall prediction reward, denoted by $r({\boldsymbol{x}}|\pi)$, as well as the age-dependent rewards $r_n({\boldsymbol{x}}|\pi), \forall n = 1,...,N$. Let $f({\boldsymbol{x}})$ be the probability
distribution function of the video context information, which also gives information of the popularity evaluation patterns. The expected
prediction reward of a policy $\pi$ is therefore,
\begin{align}
V(\pi) = \int_{{\boldsymbol{x}}\in\mathcal{X}} r({\boldsymbol{x}}|\pi) f({\boldsymbol{x}}) d{\boldsymbol{x}}
\end{align}
Note that the age-$n$ policy $\pi_n$ will only use the context information ${\boldsymbol{x}}_n$ rather than ${\boldsymbol{x}}$ to make predictions since ${\boldsymbol{x}}_{n^+}$ has not been realized at age $n$.

Our objective is to determine the optimal policy $\pi^{opt}$ that
maximizes the expected prediction reward, i.e. $\pi^{opt}=\arg\max\limits _{\pi}V(\pi)$.
In the following sections, we will propose a systematic methodology
and associated algorithms that find the optimal policy for the case
when $f({\boldsymbol{x}})$ is known or unknown, which are referred to as the complete
and incomplete information scenarios, respectively.

\section{Why Online Learning is Important?}
In this section, we consider the optimal policy design problem with the complete information of the context distribution $f({\boldsymbol{x}})$ and compute the optimal policy $\pi^{opt}$. In the next section in which $f({\boldsymbol{x}})$ is unknown, we will learn this optimal policy $\pi^{opt}$ online and hence, the solution that we derive in this section will serve as the benchmark. Even when having the complete information, determining the optimal prediction policy faces great challenges: first, the prediction reward depends on \textit{all} decision actions at \textit{all} ages; and second, when making the decision at age $n$, the actions for ages larger than $n$ are not known since the corresponding context information has not been realized yet.

Given policies $\pi_{-n}$, we define the expected reward when taking action $a_n$ for ${\boldsymbol{x}}_n$ as follows,
\begin{align}
\mu_n({\boldsymbol{x}}'_n|\pi_{-n},a_n) = \int_{{\boldsymbol{x}}} I_{{\boldsymbol{x}}_n = {\boldsymbol{x}}'_n} r_n({\boldsymbol{x}}|\pi_{-n}, a_n) f({\boldsymbol{x}}) d{\boldsymbol{x}}
\end{align}
where $I_{{\boldsymbol{x}}_n = {\boldsymbol{x}}'_n}$ is an indicator function which takes value 1 when the age-$n$ context information is ${\boldsymbol{x}}'_n$ and value 0 otherwise. The optimal $\pi^*(\pi_{-n})$ given $\pi_{-n}$ thus can be determined by
\begin{equation}\label{best_response}
\pi_n^*({\boldsymbol{x}}_n|\pi_{-n}) = \arg\max\limits_{a}\mu({\boldsymbol{x}}_n|\pi_{-n},a), \forall {\boldsymbol{x}}_n
\end{equation}
and in which we break ties deterministically. Equation \eqref{best_response} defines a best response function from a policy to a new policy $F: \Pi \to \Pi$ where $\Pi$ is the space of all policies. In order to compute the optimal policy $\pi^{opt}$, we iteratively use the best response function in \eqref{best_response} using the output policy computed in the previous iteration as the input for the new iteration. Note that a computation iteration is different from a time period. ``Period'' is used to describe the time unit of the discrete time model of the video propagation. A period can be a miniute, an hour or any suitable time duration. In each period, the sharing and viewing statistics of a {\it specific} video may change. ``Iteration'' is used for the (offline) computation method for the optimal policy (which prescribes actions for {\it all} possible context information in {\it all} periods). Given the complete statistical information (i.e. the video propagation characteristics distribution $f({\boldsymbol{x}})$) of videos, a new policy is computed using best response update in each iteration.

We prove the convergence and optimality of this best response update as follows.
\begin{lemma}
$\pi_n^*({\boldsymbol{x}}_n|\pi_{-n})$ is independent of $\pi_m, \forall m < n$, i.e. $\pi_n^*({\boldsymbol{x}}_n|\pi_{-n}) = \pi_n^*({\boldsymbol{x}}_n|\pi_{n^+})$.
\end{lemma}
\begin{proof}
By the definition of age-dependent reward, the prediction actions before age $n$ does not affect the age-$n$ reward. Hence, the optimal policy depends only on the actions after age $n$.
\end{proof}

Lemma 1 shows that the optimal policy $\pi_n$ at age $n$ is fully determined by the policies for ages larger than $n$ but does not depend on the policies for ages less than $n$. Using this result, we can show the best response algorithm converges to the optimal policy within a finite number of computation iterations.

\begin{theorem}
Starting with any initial policy $\pi^0$, the best response update converges to a unique point $\pi^*$ in $N$ computation iterations. Moreover, $\pi^* = \pi^{opt}$.
\end{theorem}
\begin{proof}
Given the context distribution $f({\boldsymbol{x}})$ which also implies the popularity evolution, the optimal age-$N$ policy can be determined in the first iteration. Since we break ties deterministicaly when rewards are the same, the policy is unique. Given this, in the second iteration, the optimal age-$(N-1)$ policy can be determined according to \eqref{best_response} and is also unique. By induction, the best response update determines the unique optimal age-$n$ policy after $N+1-n$ iterations. Therefore, the complete policy is found in $N$ iterations and this policy maximizes the overall prediction reward.
\end{proof}

Theorem 1 proves that we can compute the optimal prediction policy using a simple iterative algorithm as long as we have complete knowledge of the popularity evolution distribution. In practice, this information is unknown and extremely difficult to obtain, if not possible. One way to estimate this information is based on a training set. Since the context space is usually very large (which usually involves infinite number of values), a very large volume of training set is required to obtain a reasonably good estimation. Moreover, existing training sets may be biased and outdated as social media evolves. Hence, prediction policies developed using existing training sets may be highly inefficient~\cite{Sollich}. In the following section, we develop learning algorithms to learn the optimal policy in an online fashion, requiring no initial knowledge of the popularity evolution patterns.

\section{Learning the Optimal Forecasting Policy with Incomplete Information}
In this section, we develop a learning algorithm to determine the optimal prediction policy without any prior knowledge of the underlying context distribution $f({\boldsymbol{x}})$. In the considered scenario, videos arrive to the system in sequence\footnote{To simplify our analysis, we will assume that one video arrives at one time. Nevertheless, our framework can be easily extended to scenarios where multiple videos arrive at the same time.} and we will make popularity prediction based on past experiences by exploiting the similarity information of videos.

Since we have shown in the last section that we can determine the complete policy $\pi$ using a simple iterative algorithm, we now focus mainly on learning $\pi_n$ for one age by fixing the policies $\pi_{-n}$ for other ages. Importantly, we will provide not only asymptotic convergence results but also prediction performance bounds during the learning process.

\subsection{Learning Regret}
In this subsection, we define the performance metric of our learning algorithm. Let $\sigma_n$ be a learning algorithm of $\pi_n$ which takes action $\sigma^k_n({\boldsymbol{x}}^k_n)$ at instance $k$. We will use learning regret to evaluate the performance of a learning algorithm. Since we focus on $\pi_n$, we will use simplified notations in this section by neglecting $\pi_{-n}$. However, keep in mind that the age-$n$ prediction reward depends on actions at all later ages $a_{n^+}$ besides $a_n$ when $a_n = \textrm{Wait}$. Let $\mu_n({\boldsymbol{x}}_n|a_n)$ denote the expected reward when age-$n$ context information is ${\boldsymbol{x}}_n$ and the algorithm takes the action $a_n \in \mathcal{S}\cup \{\textrm{Wait}\}$.  We make a widely adopted assumption~\cite{Slivkins}~\cite{Dudik}~\cite{Langford} that the expected reward of an action is similar for similar contextual and situational information; we formalize this in terms of (uniform) Lipschitz condition.

\begin{assumption*}(Lipschitz)
For each $a_n \in \mathcal{S}\cup \{\textrm{Wait}\}$, there exists $L > 0, \alpha > 0$ such that for all ${\boldsymbol{x}}_n, {\boldsymbol{x}}'_n \in \mathcal{X}_n$, we have $|\mu({\boldsymbol{x}}_n|a_n) - \mu({\boldsymbol{x}}'_n|a_n)|\leq L\|{\boldsymbol{x}}_n, {\boldsymbol{x}}'_n\|^\alpha$.
\end{assumption*}

The optimal action given a context ${\boldsymbol{x}}_n$ is therefore, $a^*({\boldsymbol{x}}_n) = \arg\max_{a_n} \mu_n({\boldsymbol{x}}_n|a_n)$ (with ties broken deterministically) and the optimal expected reward is $\mu^*_n({\boldsymbol{x}}_n) = \mu_n({\boldsymbol{x}}_n|a^*_n)$. Let $\Delta = \max_{{\boldsymbol{x}}_n\in \mathcal{X}_n} \{\mu^*_n({\boldsymbol{x}}_n) - \mu_n({\boldsymbol{x}}_n|a_n\neq a^*_n)\}$ be the maximum reward difference between the optimal action and the non-optimal action over all context ${\boldsymbol{x}}_n \in \mathcal{X}_n$. Finally, we let $r_n({\boldsymbol{x}}_n^k|\sigma^k_n)$ be the realized age-$n$ reward for video $k$ by using the learning algorithm $\sigma$. The expected regret by adopting a learning algorithm $\sigma_n$ is defined as
\begin{equation}\label{regret}
R_n(K) = \mathbb{E}\{\sum\limits_{k=1}^K  \mu^*_n({\boldsymbol{x}}^k_n) - \sum\limits_{k=1}^K r_n({\boldsymbol{x}}^k_n|\sigma^k_n)\}
\end{equation}

Our online learning algorithm will estimate the prediction rewards by selecting different actions and then choose the actions with best estimates based on past experience. One way to do this is to record the reward estimates without using the context/situational information. However, this could be very inefficient since for different contexts, the optimal actions can be very different. Another way is to maintain the reward estimates for each individual context ${\boldsymbol{x}}_n$ and select the action only based on these estimates. However, since the context space $\mathcal{X}_n$ can be very large, for a finite number $K$ of video instances, the number of videos with the same context ${\boldsymbol{x}}_n$ is very small. Hence it is difficult to select the best action with high confidence. Our learning algorithm will exploit the similarity information of contexts, partition the context space into smaller subspaces and learn the optimal action within each subspace. The key challenge is how and when to partition the subspace in an efficient way. Next, we propose an algorithm that adaptively partitions the context space according the arrival process of contexts.

\subsection{Online Popularity Prediction with Adaptive Partition}
In this subsection, we propose the online prediction algorithm with adaptive partition (Adaptive-Partition) that adaptively partitions the context space according to the context arrivals. This will be the key module of the Social-Forecast algorithm. For analysis simplicity, we normalize the context space to be $\mathcal{X}_n = [0,1]^d$. We call a $d$-dimensional hypercube which has sides of length $2^{-l}$ a level $l$ hypercube. Denote the partition of $\mathcal{X}_n$ generated by level $l$ hypercubes by $\mathcal{P}_l$. We have $|\mathcal{P}_l|=2^{ld}$. Let $\mathcal{P}:=\cup_{l=0}^\infty \mathcal{P}_l$ denote the set of all possible hypercubes. Note that $\mathcal{P}_0$ contains only a single hypercube which is $\mathcal{X}_n$ itself. For each instance arrival, the algorithm keeps a set of hypercubes that cover the context space which are mutually exclusive. We call these hypercubes {\it active} hypercubes, and denote the set of active hypercubes at instance $k$ by $\mathcal{A}_k$. Clearly, we have $\cup_{C\in \mathcal{A}_k} = \mathcal{X}_n$. Denote the active hypercube that contains ${\boldsymbol{x}}^k_n$ by $C_k$. Let $M_{C_k}(k)$ be the number of times context arrives to hypercube $C_{k}$ by instance $k$. Once activated, a level $l$ hypercube $C$ will stay active until the first instance $k$ such that $M_{C_k}(k) \geq  A2^{pl}$ where $p>0$ and $A>0$ are algorithm design parameters. When a hypercube $C_{k}$ of level $l$ becomes inactive, the hypercubes of level $l+1$ that constitute $C_{k}$, denoted by $\mathcal{P}_{l+1}(C_k)$, are then activated.

When a context ${\boldsymbol{x}}^k_n$ arrives, we first check to which active hypercube $C_k \in \mathcal{A}_k$ it belongs. Then we choose the action with the highest reward estimate $a_n = \arg\max\limits_a \bar{r}_{a,C_k}(k)$, where $\bar{r}_{a,C_k}(k)$ is the sample mean of the rewards collected from action $a$ in $C_k$ which is an activated hypercube at instance $k$. When the prediction reward is realized for instance $k$ (i.e. at the end of age $N$), we perform a {\it virtual update} for the reward estimates for all actions (see Figure \ref{virtualupdate}). The reason why we can perform such a virtual update for actions which are not selected is because the context transition over time is independent of our prediction actions and hence, the reward by choosing any action can still be computed even though it is not realized.

\begin{figure}
  \centering

  \includegraphics[scale=0.9]{virtualupdate.eps}\\
  \caption{Illustration for virtual reward update in Adaptive Partition.}\label{virtualupdate}
\end{figure}

Algorithm \ref{PopPred-AP} provides a formal description for the Adaptive-Partition algorithm. Figure \ref{partition} illustrates the adaptive partition process of Adaptive-Partition algorithm. Next, we bound the regret by running the Adaptive-Partition algorithm.

\begin{algorithm}
\caption{Adaptive-Partition Algorithm}\label{PopPred-AP}
\begin{algorithmic}
\State Initialize $\mathcal{A}_1 = P_0$, $M_C(0) = 0$, $\bar{r}_{a,C}(0) = 0, \forall a, \forall C \in \mathcal{P}$.
\For {each video instance $k$}
\State Determine $C\in \mathcal{A}_k$ such that ${\boldsymbol{x}}^k_n \in C$.
\State Select $a_n = \arg\max\limits_a \bar{r}_{a,C}(k)$.
\State After the prediction reward is realized, update $\bar{r}_{a,C}(k+1)$ for all $a$.
\State Set $M_C(k)\leftarrow M_C(k-1) + 1$.
\If{ $M_C(k) \geq A2^{pl}$ }
\State Set $\mathcal{A}_{k+1} = (\mathcal{A}_k\backslash C)\cup \mathcal{P}_{l+1}(C)$ \EndIf
\EndFor
\end{algorithmic}
\end{algorithm}

\begin{figure*}[t]
  \centering

  \includegraphics[scale=1.1]{partition.eps}\\
  \caption{The context space partitioning of the Adaptive-Partition algorithm.}\label{partition}
\end{figure*}

In order to get the regret bound of the Adaptive-Partition algorithm, we need to consider how many hypercubes of each level is formed by the algorithm up to instance $K$. The number of such hypercubes explicitly depends on the context arrival process. Therefore, we investigate the regret for different context arrival scenarios.
\begin{definition*}
We call the context arrival process the {\bf the worst-case arrival process} if it is uniformly distributed inside the context space, with minimum distance between any two context samples being $K^{-1/d}$, and {\bf the best-case arrival process} if ${\boldsymbol{x}}^k \in C, \forall k$ for some level $\lceil (\log_2(K)/p\rceil +1$ hypercube $C$.
\end{definition*}

In Theorem 2, we determine the finite time, uniform regret bound for the Adaptive-Partition algorithm. The complete regret analysis and proofs can be found in the appendix.

\begin{theorem}\label{thmreg}
\begin{itemize}
  \item For the worst case arrival process, if $p = \frac{3\alpha + \sqrt{9\alpha^2+8\alpha d}}{2}$, then $R_n(K)=O(K^{\frac{d+\alpha/2 + \sqrt{9\alpha^2 + 8\alpha d}/2}{d+3\alpha/2 + \sqrt{9\alpha^2 + 8\alpha d}/2}})$.
  \item For the best case arrival process, if $p = 3\alpha$, then $R_n(K) = O(K^{2/3})$.
\end{itemize}
\end{theorem}
\begin{proof}
See Appendix.
\end{proof}
The regret bounds proved in Theorem 2 are sublinear in $K$ which guarantee convergence in terms of the average reward, i.e. $\lim_{K\to \infty} \mathbb{E}[R_n(K)]/K = 0$. Thus our online prediction algorithm makes the optimal predictions as sufficiently many videos instances have been seen. More importantly, the regret bound tells how much reward would be lost by running our learning algorithm for any finite number $K$ of videos arrivals. Hence, it provides a rigorous characterization on the learning speed of the algorithm.

\subsection{Learning the Complete Policy $\pi$}
In the previous subsection, we proposed the Adaptive-Partition algorithm to learn the optimal policy $\pi^*_n(\pi_{-n})$ by fixing $\pi_{-n}$. We now present in Algorithm \ref{complete} the Social-Forecast algorithm that learns the complete policy.

\begin{algorithm}
\caption{Social-Forecast Algorithm}\label{complete}
\begin{algorithmic}
\For {each video instance $k$}
\For {each age $n = 1$ to $N$}
\State    Get context information ${\boldsymbol{x}}^k_n$.
\State    Select $a^k_n$ according to Adaptive-Partition.
\State    Perform context partition using Adaptive-Partition.
\EndFor
\State    Popularity status $s^k$ is realized.
\For {each age $n = 1$ to $N$}
\State    Compute the age-dependent reward $r^k_n$.
\State    Update reward estimates using Adaptive-Partition.
\EndFor
\EndFor
\end{algorithmic}
\end{algorithm}

Social-Forecast learns all age-dependent policies $\pi_n, \forall n$ simultaneously. For a given age $n$, since $\pi_{-n}$ is not fixed to be the optimal policy $\pi^{opt}_{-n}$ during the learning process, the learned policy $\pi_{n}$ may not be the global optimal $\pi^{opt}_n$. However, as we have shown in Section IV, in order to determine $\pi^{opt}_n$, only the policies for ages greater than $n$, i.e.  $\pi^{opt}_{n^+}$ need to be determined. Thus even though we are learning $\pi_n, \forall n$ simultaneously, the learning problem of $\pi_N$ is not affected and hence, $\pi^{opt}_N$ will be learned with high probability after a sufficient number of video arrivals. Once $\pi^{opt}_N$ is learned with high probability, $\pi^{opt}_{N-1}$ can also be learned with high probability after an additional number of video arrivals. By this induction, such a simultaneous learning algorithm can still learn the global optimal complete policy with high probability. In the experiments we will show the performance of this algorithm in practice.

\subsection{Complexity of Social-Forecast}
For each age of one video instance arrival, Social-Forecast needs to do one comparison operation and one update operation on the estimated reward of each forecast action. It also needs to update the counting of context arrivals to the current context subspace and perform context space partitioning if necessary. In sum, the time complexity has the order $O(|\mathcal{S}|N)$ for each video instance and $O(|\mathcal{S}|NK)$ for $K$ video arrivals. Since the maximum age $N$ of interest and the popularity status space is given, the time complexity is linear in the number of video arrivals $K$. The Social-Forecast algorithm maintains for each \textit{active} context subspace reward estimates of all forecast actions. Each partitioning creates $2^d - 1$ more \textit{active} context subspaces and the number of partitioning is at most $K/A$. Thus the space complexity for $K$ video arrivals is at most $O(2^d N K/A)$. Since the context space dimension $d$ and the algorithm parameter $A$ are given and fixed, the space complexity is at most linear in the number of video arrivals $K$.

\section{Experiments}
In this section we evaluate the performance of the proposed Social-Forecast algorithm. We will first examine the unique propagation characteristics of videos shared through social media. Then we will use these as the context (and situational) information for our proposed online prediction algorithm. Our experiments are based on the dataset that tracks the propagation process of videos shared on RenRen (\texttt{www.renren.com}), which is one of the largest Facebook-like online social networks in China. We set one period to be 2 hours and are interested in predicting the video popularity by 100 periods (8.3 days) after its initiation. In most of our experiments, we will consider a binary popularity status space \{Popular, Unpopular\} where ``Popular'' is defined for videos whose total number of views exceeds 10000. However, we also conduct experiments on a more refined popularity status space in Section VI(F).

The prediction reward function that we use is $U(a^k_n, s^k, n) = \theta(a^k_n, s^k) + \lambda \psi(n)$. For the case of binary popularity status space, the accuracy reward function $\theta$ is chosen as follows
\begin{equation}
\theta(a^k_n, s^k) =\left\{
\begin{array}{ll}
1, &\textrm{if}~a^k_n = s^k = \textrm{Unpopular}\\
w, &\textrm{if}~a^k_n = s^k = \textrm{Popular}\\
0, &\textrm{if}~a^k_n \neq s^k
\end{array}\right.
\end{equation}
where $w > 0$ is fixed reward for correctly predicting popular videos and hence controls the relative importance of true positive and true negative. The timeliness reward function $\psi$ is simply taken as $\psi(n) = N - n$. Recall that the prediction reward function is a combination of the two and we use $\lambda > 0$ to trade-off accuracy and timeliness. In the experiments, we will vary both $w$ and $\lambda$ to investigate their impacts on the prediction performance. Note that we use these specific reward functions in this experiment but other reward functions can easily be adopted in our algorithm.

\subsection{Video propagation characteristics}
A RenRen user can post a link to a video taken by him/herself or from an external video sharing website such as Youtube. The user, referred to as an {\it initiators}~\cite{Li}, then starts the sharing process. The friends of these initiators can find this video in their ``News Feed''. Some of them may watch this video and some may re-share the video to their own friends. We call the users who watched the shared video {\it viewers} and those who re-shared the video {\it spreaders}. Since spreaders generally watched the video before re-shared it, most of them are also viewers. In the experiment, we will use two characteristics of videos promoted by social media as the context (and situational) information for our algorithm. The first is the initiator's {\it Branching Factor (BrF)}, which is the number of viewers who directly follow the initiator. The second is the {\it Share Rate (ShR)}, which is the ratio of the viewers that re-share the video after watching it. Figure \ref{context} shows the evolution of the number of views, the BrF and the ShR for three representative videos over 100 periods. Among these three videos, video 1 is an unpopular video while video 2 and video 3 are popular videos, which become popular at age 37 and age 51, respectively. We analyze the differences between popular and unpopular videos as follows.
\begin{itemize}
  \item {\it Video 1 vs Video 2}. The ShRs of both videos are similar. The BrF of video 2 is much larger than that of video 1. This indicates that video 1 may be initiated by users with a large number of friends, e.g. celebrities and pubic accounts. Thus, videos with larger BrF potentially will achieve popularity in the future.
  \item {\it Video 1 vs Video 3}. The BrFs of both videos are low (at least before video 3 becomes popular). Video 3 has a much larger ShR than video 1. This indicates that video 3 is being shared with high probability and thus, videos with larger ShR will potentially become popular in the future.
\end{itemize}

The above analysis shows that BrF and ShR are good situational metrics for videos promoted by social media. Therefore we will use these two metrics in addition to the total and per-period numbers of views as the context information for our proposed online prediction algorithms. Nevertheless, our algorithms are general enough to take other situational metrics to further improve the prediction performance, e.g. the type of the videos, the number of spreaders, the propagation topology etc.

\begin{figure}
  \centering

  \includegraphics[scale=0.6]{context.eps}\\
  \caption{Popularity evolution of 3 representative videos.}\label{context}
\end{figure}

\subsection{Benchmarks}
We will compare the performance of our online prediction algorithm with four benchmarks.
\begin{itemize}
  \item {\bf All Unpopular (AU)}. The first benchmark is a naive scheme which predicts that all videos are not popular at age 1. This is equivalent to $a^k_1 = \textrm{Unpopular},\forall k$.
  \item {\bf All Popular (AP)}. The second benchmark is another naive scheme which makes the prediction at age 1 that the video will become popular in the future. This is equivalent to take the action $a^k_1 = \textrm{Popular},\forall k$.
  \item {\bf View-based Prediction (VP)}. The third benchmark is a conventional view-based prediction algorithm based on~\cite{Szabo}. It uses training sets to establish log-linear correlations between the early number of views and the later number of views. Since this algorithm does not explicitly consider timeliness in prediction, we will investigate different versions that make predictions at different ages. Intuitively, the time when the prediction is made has oppositive affects on the prediction accuracy and timeliness. A later prediction predicts the video with higher confidence but is less timely.
  \item {\bf Perfect Prediction}. The last benchmark provides the best prediction results: for each unpopular video, it predicts unpopular at age 1; for each popular video, it predicts popular at age 1. Since this benchmark generates the highest possible prediction reward, we normalize the rewards achieved by other algorithms with respect to this reward.
\end{itemize}

\subsection{Performance comparison}
In this subsection, we compare the prediction performance of our proposed algorithm with the benchmarks. This set of experiments are carried out on a set of 10000 video links, among which 10\% are popular videos. The videos were initiated in sequence and thus, initially we do not have any knowledge of the videos or video popularity evolution patterns. For the VP algorithm, we use three versions, labeled as VP-25, VP-50, VP-75, in which the prediction is made at age 25, 50, 75, respectively.

Table \ref{comparisonW} records the normalized prediction rewards obtained by our proposed algorithm and the benchmarks for $\lambda = 0.010$ and $w = 5, 10, 15$. The trade-off parameter $\lambda$ for accuracy and timeliness is set to be small because the lifetime $N$ is large. The Social-Forecast algorithm is labeled by SF.
\begin{itemize}
  \item For AU and AP, even though their accuracy is expected to be bad, they will obtain full timeliness rewards because they make the predictions at the first age for each video. However, since their prediction accuracy is low, their overall prediction rewards are the lowest among all algorithms. The reward achieved by AU is decreasing in $w$ and the reward achieved by AP is increasing in $w$. This is because a larger $w$ assigns higher importance to correct prediction for popular videos and the fact that AP predicts all popular videos correctly and AU predicts all unpopular videos correctly.
  \item VP algorithms achieve better prediction rewards than AU and AP. As can be seen from the table, an early prediction generates higher rewards because a large portion of the reward is derived from the timeliness of the prediction. The reward achieved by VP-25 is decreasing in $w$ while those achieved by VP-50 and VP-75 are increasing in $w$. This implies that VP-25 has a better performance on predicting unpopular videos than predicting popular videos.
  \item The proposed algorithm Social-Forecast generates significantly higher prediction rewards than all benchmark algorithms. Its performance is not sensitive to the specific value of $w$ which implies that it is able to predict both popular and unpopular videos very accurately and in a timely manner.
\end{itemize}

\begin{table}
\centering
\caption{Comparison of normalized prediction reward with varying $w$}\label{comparisonW}
\begin{tabular}{|c|c|c|c|c|c|c|}
  \hline

  ~ & AU & AP & VP-25 & VP-50 & VP-75 & SF \\
  \hline
  $w = 5$ & 0.795 & 0.622 & 0.831 & 0.763 & 0.643 & 0.986 \\
  \hline
  $w = 10$ & 0.663 & 0.685 & 0.823 & 0.803 & 0.671 & 0.983 \\
  \hline
  $w = 15$ & 0.549 & 0.740 & 0.814 & 0.837 & 0.691 & 0.981 \\
  \hline
\end{tabular}
\end{table}

Next, we fix $w$ and vary $\lambda$. Table \ref{comparisond} records the normalized prediction rewards obtained by our proposed algorithm and the benchmarks for $W = 10$ and $\lambda = 0.005,0.010,0.015$. Several points are worth discussing:
\begin{itemize}
  \item The rewards obtained by both and AU and AP are increasing in $\lambda$. This is because both benchmarks derive full reward from the timeliness prediction since they make prediction at the first age for all videos.
  \item The rewards obtained by all three versions of VP are decreasing in $\lambda$. This suggests the rewards are mainly derived from prediction accuracy but the VP algorithms are not able to make the prediction in a timely manner.
  \item Our proposed Social-Forecast algorithm significantly outperforms all other benchmark algorithms and achieve close-to-optimal rewards for all values of $\lambda$.
\end{itemize}

\begin{table}
\centering
\caption{Comparison of normalized prediction reward with varying $\lambda$}\label{comparisond}
\begin{tabular}{|c|c|c|c|c|c|c|}
  \hline

  ~ & AU & AP & VP-25 & VP-50 & VP-75 & SF \\
  \hline
  $\lambda = 0.005$ & 0.601 & 0.612 & 0.835 & 0.862 & 0.757 & 0.980 \\
  \hline
  $\lambda = 0.010$ & 0.663 & 0.685 & 0.823 & 0.803 & 0.671 & 0.983 \\
  \hline
  $\lambda = 0.015$ & 0.701 & 0.737 & 0.816 & 0.762 & 0.613 & 0.983 \\
  \hline
\end{tabular}
\end{table}

We also investigate the achieved predication accuracy in terms of true positive rate and true negative rate. We define the true positive rate as the ratio of correctly predicted videos among all popular videos and the true negative rate as the ratio of correctly predicted videos among all unpopular videos. Table \ref{TPTN} illustrates the true positive rates and true negative rates achieved by different algorithms. As can be seen from the table, in general prediction at a later age for the VP algorithms improves the accuracy. However, it is not always the case since the true negative rate achieved by VP-75 is low. This suggests that the correlation used by VP-75 for unpopular videos does not accurately reflect the true popularity evolution trend. Instead, our proposed Social-Forecast is able to achieve both a high true positive rate and a high true negative rate, at the same time predicting in a timely manner.

\begin{table}
\centering
\caption{True Positive and True Negative.}\label{comparison}
\begin{tabular}{|c|c|c|c|c|c|c|}
  \hline

  ~ & AU & AP & VP-25 & VP-50 & VP-75 & SF \\
  \hline
  True Positive & 0 & 1 & 0.918 & 0.917 & 0.995 & 0.983 \\
  \hline
  True Negative & 1 & 0 & 0.804 & 0.994 & 0.789 & 0.972 \\
  \hline
\end{tabular}\label{TPTN}
\end{table}

\subsection{Learning performance}
Our proposed Social-Forecast algorithm is an online algorithm and does not require any prior knowledge of the video popularity evolution patterns. Hence, it is important to investigate the prediction performance during the learning process. Our analytic results have already provided sublinear bounds on the prediction performance for any given number of video instances which guarantee the convergence to the optimal prediction policy. Now, we show how much prediction reward that we can achieve during the learning process in experiments. Figure \ref{learning} shows the normalized prediction reward of Social-Forecast as the number of videos instances increases.  As more video instances arrive, our algorithm learns better the optimal prediction policy and hence, the prediction reward improves with the number of video instances. In particular, the proposed prediction algorithm is able to achieve more than 90\% of the best possible reward even with a relatively small number of video instances.

\begin{figure}
  \centering

  \includegraphics[scale=0.6]{learning.eps}\\
  \caption{Prediction performance during the learning process.}\label{learning}
\end{figure}

\subsection{Choices of lifetime $N$}
So far in our analysis, we treated the prediction reference age $N$ as fixed. In practice, this is a parameter that can be set by the content providers, the advertisers and the web hosts depending on their specific requirements. In this experiment, we show the performance of our algorithm for different choices of $N$. Table \ref{comparisonN} provides the prediction rewards obtained by different algorithms for $N = 60, 70, 80, 90, 100$ when $d = 0.010$ and $w = 10$. In all experiments, the proposed algorithm achieves significant higher prediction rewards than the benchmarks. This shows that our methodology and associated algorithm is general and applicable for problems with different requirements.

\begin{table}
\centering
\caption{Impact of reference age $N$}\label{comparisonN}
\begin{tabular}{|c|c|c|c|c|}
  \hline

  ~ & AU & AP & VP-25 &  SF \\
  \hline
  $N = 60$ & 0.600 & 0.569 & 0.722 & 0.920  \\
  \hline
  $N = 70$ & 0.612 & 0.655 & 0.801 & 0.992  \\
  \hline
  $N = 80$ & 0.645 & 0.657 & 0.814 & 0.989  \\
  \hline
  $N = 90$ & 0.642 & 0.678 & 0.816 & 0.986  \\
  \hline
  $N = 100$ & 0.663 & 0.685 & 0.823 & 0.983  \\
  \hline
\end{tabular}
\end{table}

\subsection{More refined popularity prediction}
In the previous experiments, we considered a binary popularity status space. Nevertheless, our proposed popularity prediction methodology and associated algorithm can also be applied to predict popularity in a more refined space. In this experiment, we consider a refined popularity status space \{High Popularity, Medium Popularity, Low Popularity\} where ``High Popularity'' is defined for videos with more than 10000 views, ``Medium Popularity'' for videos with views between 2000 and 10000, and ``Low Popularity'' for videos with views below 2000. The portions of High, Medium and Low videos are 10\%, 30\% and 60\%, respectively. We set rewards for correctly predicting High, Medium, Low videos to be 10, 5 and 1, respectively. The proposed Social-Forecast algorithm is compared against the view-based algorithm VP performed at different prediction ages. Table \ref{refinement} illustrates the normalized rewards obtained by different algorithms for $\lambda = 0.005, 0.010, 0.015$. As can been seen from the table, the rewards obtained by all algorithms decrease compared with the binary popularity status case since prediction becomes more difficult. However, the performance improvement of Social-Forecast against VP becomes even larger. This suggests that our algorithm, which explicitly considers the situational/contextual information, is able to achieve a higher performance gain against view-based approaches for more refined popularity prediction.

\begin{table}
\centering
\caption{Performance comparison for refined popularity space.}\label{refinement}
\begin{tabular}{|c|c|c|c|c|}
  \hline

  ~ & VP-25 & VP-50 & VP-75 & SF \\
  \hline
  $\lambda = 0.005$ & 0.487 & 0.601 & 0.627 & 0.938 \\
  \hline
  $\lambda = 0.010$ & 0.493 & 0.580 & 0.578 & 0.928 \\
  \hline
  $\lambda = 0.015$ & 0.492 & 0.558 & 0.545 & 0.920 \\
  \hline
\end{tabular}
\end{table}

\section{Conclusions and Future Work}
In this paper, we have proposed a novel, systematic and highly-efficient
online popularity forecasting algorithm for videos promoted by social media. We have shown that by incorporating situational and contextual information, significantly better prediction performance can be achieved than existing approaches which disregard this information and only consider the number of times that videos have been viewed so far. The proposed Social-Forecast algorithm does not require prior knowledge of popularity evolution or a training set and hence can operate easily and successfully in online, dynamically-changing environments such as social media. We have systematically proven sublinear regret bounds on the performance loss incurred by our algorithm due to online learning. Thus Social-Forecast guarantees both short-term performance as well as its asymptotic convergence to the optimal performance in the long term.

This paper considered a single learner who observes the propagation patterns of videos promoted by one social media. One important future work direction is to extend to scenarios where there are multiple distributed learners (e.g. multiple advertisers, content producers and web hosts) who have access to multiple different social medias or different sections of one social media. In such scenarios, significant improvement is expected by enabling cooperative learning among the distributed learners~\cite{Tekin13}. The challenges in these scenarios are how to design efficient cooperative learning algorithms with low communication complexity~\cite{Xu13} and, when the distributed learners are self-interested and have conflicting goals, how to incentivize them to participate in the cooperative learning process using, e.g. rating mechanisms~\cite{Xu14}~\cite{XuNetecon}. Finally, while this paper has studied the specific
problem of online prediction of video popularity based on contextual
and situational information, our methodology and associated algorithm
can be easily adapted to predict other trends in social media (such
as identifying key influencers in social networks, the potential for
becoming viral of contents or tweets, identifying popular or relevant
content, providing recommendations for social TV etc.).

redpajama_set_name: RedPajamaArXiv


For the Super Nintendo in great working condition. Pictures are of actual items. ALL GAMES AND SYSTEMS WE SELL ARE.
We will be listing several N64, Original Nintendo (NES), SNES, Sega Genesis, Game Boy, Xbox, Playstation, and Master System items so keep checking back with us often! See our other items by clicking. We do not take offers unless there is a "best offer" option in the listing. The item "Mega Man X2 (Super Nintendo SNES 1996) with Box game WORKS! Megaman" is in sale since Saturday, February 7, 2015. This item is in the category "Video Games & Consoles\Video Games". The seller is "discountgames101" and is located in ALL GAMES SHIP FOR FREE!!. This item can be shipped to United States, Canada, United Kingdom, Denmark, Romania, Slovakia, Bulgaria, Czech republic, Finland, Hungary, Latvia, Lithuania, Malta, Estonia, Australia, Greece, Portugal, Cyprus, Slovenia, Japan, Sweden, South Korea, Indonesia, Taiwan, Thailand, Belgium, France, Hong Kong, Ireland, Netherlands, Poland, Spain, Italy, Germany, Austria, Israel, Mexico, New Zealand, Philippines, Singapore, Switzerland, Norway, Saudi arabia, Ukraine, United arab emirates, Qatar, Kuwait, Bahrain, Croatia, Malaysia, Chile, Colombia, Costa rica, Dominican republic, Panama, Trinidad and tobago, Guatemala, El salvador, Honduras, Jamaica, Antigua and barbuda, Aruba, Belize, Dominica, Grenada, Saint kitts and nevis, Saint lucia, Montserrat, Turks and caicos islands, Barbados, Bangladesh, Bermuda, Brunei darussalam, Bolivia, Ecuador, Egypt, French guiana, Guernsey, Gibraltar, Guadeloupe, Iceland, Jersey, Jordan, Cambodia, Cayman islands, Liechtenstein, Sri lanka, Luxembourg, Monaco, Macao, Martinique, Maldives, Nicaragua, Oman, Pakistan, Paraguay, Reunion.


Hey guys. I wanna ask questions about damage reports. Mainlyis it a bad mindset to compare drg to drk and war? Also damage wise it seems i can keep up with near perfectly geared samurai, keep in mind i am lacking augs for trish and regal ring. Is this just a me thing or is drg just not able to win the damage race. I usually pop stardivers off as soon as i hit 1k. Maybe thats part of the problem. Any advice?
DRG generally struggles against WAR and DRK in full buff scenarios because lack of attack boosting abilities. I think the recent patch helped a little bit because TP overflow for Stardiver.
However DRG has more utility than WAR, can manage its own hate, and does exceptionally well in low-buff scenarios.
Trishula DRG is perfectly fine for endgame DD content though. Comparing yourself to DRK or WAR will just make you sad, unless it's a huge margin, in which case you should reevaluate your gear choices. I think most (good) players recognize the value of DRG nowadays.
I've been undefeated in Dynamis-D for months running with full REMA DRK, WAR, BLU, etc. You are really at zero risk of dying the entire run. You generate more than 3x the total weaponskills of your DD brethren. You'll never hit hate cap on the final boss like the other DD.
Everything else it's only acceptable, not exceptional.
Also guns. TP Bonus gun now, please. Gimme those 2750 TP Stardivers @1000 TP.
I was hitting 56k Impulse Drive averages with 60 WSD in gear and capped pDiff.
If you didn't need 102 STP, an XI Sam roll (with sam bonus) to get a fake 2 hit, it might even be competitive as-is with only TP-Bonus earring on 1min uptime on Warcry.
Does DRG still suffer that much due to not having attack buffs? We have a permanent +20% attack, plus the job point +attack from wyvern attributes (+60?). WAR gets more with their buffed berserk (+35%), but its not fulltime like ours is, though they get a 4% higher Smite.
It's not that bad, but it's very noticeable in everything except the highest buff situations or low level content.
War with all berserk duration items (not counting weapon slot) and berserk recast merits, has 4min3sec duration on Berserk and 4min10sec recast. This is rather close to full time.
That said, that attack buff is mostly only relevant in Dynamis-D, if you're not stacking defense down effects like you should be.
Multiple targets/long fights are great for DRG. Bursty zerg ***favors other jobs by a significant margin due to their ability kits. Reverting Fly High to no recast (outside of animation lock) jumps would fix this.
Ah ok cool. So I should be fine then. Thanks dudes. Confidence boost +1 to drg.
I've been undefeated in Dynamis-D for months running with full REMA DRK, WAR, BLU, etc.
People post same stuff on DRK, WAR, SAM and BLU forum.
You generate more than 3x the total weaponskills of your DD brethren.
You want to tell me that you make 3x more WSs than BLU, WAR, DRK and especially SAM? If that's true for you runs, it's not a surprise you beat everyone. Your team mates are VERY VERY bad at engaging mobs or like me, they have terrible lags during Dynamis-D. There is no way DRG can do that much more WSs if everyone have no lag and people have same skill. Sure you have jumps, but WAR has 100%DA, SAM has Zanhasso and massive STP, BLU has very big STP and AM3.
Just gonna throw out there; DRG can 100%DA with Fighter's roll.
Well yeah but no DD in game can do 3x more ws than other DD unless they are competing with mages with 0 MA.
Certain job tp faster, thats for sure. But its more like difference between 1.9 rounds/ws v.s 2.1 or something.
Edit: reading the origional post, he meant reduce hate with jumps=more ws in the long run since other DD either need to turtle or die. That makes sense though.
MA set is better than WSDMG until ~1300 TP before Moonshade. For Kaja Impulse Drive.
3x WS in the total run is very possible. Jumps are a free weaponskill, you have 4 of them (one of which reduces your enmity by 29%..... If you're not getting at least 1k off jumps, your gear is wrong or your SAM roll is off. If you're NOT doing that many WS more than other DD you're doing it wrong.
I'll post breakdowns upcoming, but I guarantee that you're doing it wrong if you're not seeing a large amount of weaponskills over other DD.
Also, anyone coming at my DD is a bad choice. Ricon, Xenophane, myself, Justthetip, and Llucian are all top 1%'ers. Any two of these players can carry a full zone clear without COR cheese. We're on Bahamut and run every Tuesday and Sautrday at 8pm CST if anyone thinks they can prove otherwise.
I had a chance to test Kaja Lance in Dyna on Tuesday. It actually performs remarkably well on Wave 3 because your jumps CD fast enough to 3k your WSs (with moonshade) every pull. That raises weaponskill average for wave 3 to about 35k (my max being about 50k) instead of 20k and increases your DPS for the wave quite a bit. It's still best to use R15 Trishula on Wave 1 and 2 and for the mega boss.
So to confirm what you are saying is basically for the wave 3 mobs the new lance outperforms trish then? If so thats pretty neat.
Yeah man, it's just the right combination of downtime between pulls so that at least two jumps will be up during. Those two jumps will help you hit 2750 pretty easily.
A 3k Impulse Drive does like 45~50k depending on your gear in there. After those two jumps are burned, I just WS at 1750 and it still comes out to about 35k every time. In normal circumstances, waiting to WS is a DPS loss, but the nature of wave 3 (except the boss) makes it ok.
Oh thats bad ***. Imma have to double check my wsdamage sets. They might be able to get some love.
Another ambuscade weapon upgrade incoming next month. What does this mean for the current weapon hierarchy for drg? The world may know next month.
I really hope SE doesn't ruin REMA like they did during SoA. They might make it so that unless you have augmented rank 15 REMA weapons, they won't even compare to the Ambuscade ones. Which would be disappointing for my Aeonic polearm to say the least.
I do not think that is at risk of happening.
Impulse Drive at 3k TP has slowly been gaining ground on Stardiver over the last few years every time another chunk of WSD gets released. As of the Relic Hands release, I have been using Impulse Drive when I get stuck at 3k TP, like on Kin. I am not sure if it mathed out as better, but it may have, and it is far more consistent and doesn't rely on multiattack rng. It does 35-39k every time.
With this new weapon giving it a true 40% Bonus, a 3k (2750) Impulse Drive with it will be Dragoon's strongest 1 hit potential. But do not confuse that with it being our best weapon. While I am not sure I agree with Shozokui's assessment, it's also a niche start/stop 3k start situation which would favor the weapon more. For any continuous damage situation, assuming 1 more normalish upgrade, the weapon will not outperform the existing REMA AG Options. On the T3 boss, for instance, the REMA options would all smoke it. Impulse Drive has a Modifier of 1 at 1k - A Moonshade and 40% bonus don't save that. Aside from higher TP, you are just going to be Stardivering with an inferior weapon.
Ah to bad then that impulse drive isnt on a rema instead then huh.
To me, it sounds like you're agreeing with my opinion more than refuting it :P. If you don't have an R15 Trish, this weapon will still perform rather close to it, subtract about 500~1000 DPS on the wave 3 boss, your overall average won't be too different though. In any situation where you can cap your TP easily, it'll still perform higher than Trish.
I've not been able to DD in dynamis for a few runs, so I don't have hard number comparisons to back anything up.
If I had the weapon, I would not use it in Dynamis D. So while I agree the gap may be closed in that type of situation, I don't think it would beat REMA options.
The weapon has 1 thing going for it: Stronger weaponskills at higher TP due to ID's superior scaling. And it doesn't need 2750 TP, it's stronger than Stardiver at some level even below that with it's 40% bonus. So like right after a 3K TP start, or a Double attack'd Soul Jump. But in every combat round after that it is going to lose ground. The 480 delay means you need more STP to hit a 5hit. So you are going to have less multiattack than a Gung or Rhon (meaning less quantity of ws) would, and way less than the 4hit counterparts. And every 1k WS eats into that lead of the initial weaponskill. It ain't gonna take 3 minutes of weaponskilling to pass it up.
If you have to build TP, a 3k ID with it is not stronger than 3x Stardiver than any of the other weapons. And it's white damage will also be lower than any of them besides maybe Trish. I would roll with even just a normal AG Gungnir over it in the vast majority of situations. On a 3k TP start fight where we aren't skillchaining, I might use it for the first WS, Soul Jump to another ID, and then swap immediately to Trish.
This may have been discussed prior but the search function doesnt seem to be working for me on the forum.
Stardiver set. For those who have a Dagon Breastplate, would it be more beneficial to slip a Windbuffet Belt +1 in place of Fotia. It would give a bump to the Niqmaddu ring and 5% QA, bump the TA up to 17%.
That would devalue the Niqmaddu. Adding more QA also devalues the TA on the Dagon. Fotia is superior.
Back of napkin (this is close math not perfect math, as it doesn't take into account other MA rates - which is best case scenario for Windbuffet): Fotia is about an 11% gain.
You'll spike higher slightly more often, but your lows and mids will suffer a fair bit.
Everyone needs an epeen set though.
1.) Get max buffs with multiple one hours from buffers.
2.) WS in high variable gear until you get your highest number.
3.) Screenshot it and chop off your buffs and party members, displaying primarily the log and maybe your char doing the WS.
4.) Claim that's your average WS on that NM, and say you're not even sure you got proper buffs. And that you think there were several WSes that were much higher than that, and that if others don't get those numbers you don't know what they could be doing wrong - because such and such is easy.
Holy ***did you nail the *** outta that, that is a spot on representation.
You forgot one thing though: "I outparsed my friend on (this) job, and he's superfuckingamazing"
I think there's a thread for asssura ***posting. Kindly go back.


Yo-Ho Ho and a Bucket of Candy!
With Halloween less than 2 weeks away, we are all busy trying to figure out unique costume ideas for our kids. There are so many different options this year, it's hard to choose. Pirates have always been and will always be a very popular choice. Especially with the Disney Channel hit Jake and the Never Land Pirates on Disney Junior, and of course the Pirates of the Caribbean franchise.
Our friend Jasmine aka So You Think You Can Mom recently threw a Jake and the Never Land Pirates Party and all of the little Pirates had a swash-bucklin' good time!
Here on Disney Sisters we've covered everything from How to Talk Like A Pirate, to Mermaid MakeUp, and even had an Interview with Sharky and Bones. Now it's time to show you how to Dress Like a Pirate! Yay-Hay!
Disney asked one of their costume designers Zachary Bilemdjian to come up with some quick, easy and affordable instructions on how to create Jake, Izzy and Cubby costumes at home! (These costumes are not currently available in stores) Zachary is an expert, having worked as the costume designer on the new live-action music videos with The Never Land Pirate Band for the second season of "Jake and the Never Land Pirates" premiering in early 2012.
4. Don't forget to add Cubby's map in the back pocket. A rolled up newspaper will do the trick. Yo Ho Let's Go!
If you do end up making a costume for your child this year, Disney wants to see the photos! Please share with them by posting to their Facebook Page or this Twitter Account.


Preparing for a first date can be stressful and you will probably forget to do several things in all that hurry. While we're certain you'll remember to put on your makeup and grab your car keys, there is also an entire list of things that you should do if you want to have a pleasant dating experience. Therefore, regardless of whether you are going out with a member of the cowboy, biker or HIV dating community, we suggest you read the following so that you can arrive at your date completely prepared.
It's only natural if you want to look great on your first date with a handsome guy, but not at the cost of comfort. Therefore, give those new shoes a test run before your date, not during it, or you will spend the evening counting the minutes until you get to go home and take them off, which can be rather distracting.
We know this one sounds silly, but you are probably talking to a lot of guys online in this modern age of dating sites and apps, so forgetting your date's name is not entirely impossible. If you are bad at remembering names, think of something that rhymes with his. This trick might be simple but it works!
If you have some food allergies, you should know where you are going before you agree to go on a date. What will happen if you are allergic to shellfish and he is taking you to a seafood restaurant? Therefore, ask your guy what he has planned for your date, and if you do not know anything about that place, look it up online.
Nothing can ruin the first impression more than being late. Therefore, check out your planner and make sure you have enough time to prepare for it. Based on other things you have planned for that day, you will know whether you have time to visit your hairstylist and choose several outfits or just take a quick shower and make a ponytail.


text:
Step up this September to help Kiwis breathe better
The Asthma and Respiratory Foundation NZ (ARFNZ) is encouraging Kiwis to show their support for fellow New Zealanders with asthma and other respiratory conditions by setting an active 'Better Breathing Challenge' for the month of September
The Asthma and Respiratory Foundation NZ (ARFNZ) is encouraging Kiwis to show their support for fellow New Zealanders with asthma and other respiratory conditions by setting an active 'Better Breathing Challenge' for the month of September.
ARFNZ's Breathe Better September has been running for six years. Last year was a huge success, with a record number of people taking part and raising over $20,000.
"We are hoping that this year will build on last year's success and be bigger and better than ever," says ARFNZ Chief Executive Letitia Harding. "This year, we're encouraging Kiwis to Step Up for Breathe Better September and complete a step challenge. You can sign up as an individual or as a team. People are also welcome to come up with their own fundraising ideas - runs around the block, star jumps or any other fun challenge could be an awesome way to raise awareness and funds."
Almost 70 heroes have signed up already, and there has been a surge in registrations since New Zealand went into Level 4 lockdown. "While the lockdown might present a challenge for some activities, runs and walks in your local area are a great way to stay fit and raise funds at the same time," says Letitia. "It seems people are even more keen to sign up in lockdown - why not set yourself a fun and worthwhile fitness challenge to work towards while your normal activities are suspended?"
New Zealand has one of the highest rates of asthma in the world, with 1 in 7 children and 1 in 8 adults living with the condition. Breathe Better September is a fun way to help raise the national profile of respiratory health in New Zealand and encourage better breathing.
The money raised contributes to the work the Foundation does to support the 700,000 Kiwis living with asthma and other respiratory diseases. The Foundation supports health professionals with resources that help people living with these conditions better manage their respiratory health. We also run asthma educational shows in schools with our ever-popular Sailor the Pufferfish Show, which is in both te reo Māori and English. The Foundation also advocates for better lung health for all New Zealanders, by ensuring we are on top of pivotal legislative changes that can affect respiratory health outcomes.
The ARFNZ team have set their own Better Breathing team challenge: walking 700,000 steps over the course of September for the 700,000 people with respiratory disease in New Zealand. You can follow them on the BBS website.
You can sign up to complete a Better Breathing Challenge as an individual, family, or as a team, with schools and workplaces encouraged to take part too.
It's fun, it's simple, and the money raised makes a real difference for Kiwis with asthma and other respiratory conditions. What's more, there are some great prizes to be won, kindly donated by our Friends of the Foundation.
To find out more, sign up or donate, visit: www.breathebetterseptember.co.nz
23/08/2021 - Waatea News
Keeping yourself and others safe in Level 4 lockdown
As New Zealand heads back into Alert Level 4, the Asthma and Respiratory Foundation is reminding Kiwis how vital it is to follow the rules and keep each other safe.

redpajama_set_name: RedPajamaCommonCrawl


This soap contains natural plant extracts and whitening factor, external cleaning and rapid improvements in the crotch, buttocks and other parts of the phenomenon of bold, deep clean the skin at the private, promote metabolism, hormonal balance while conditioning maintenance privates young, plump, pink state.
Natural & beneficial ingredients that make this soap super-efficient. Completely safe for your skin, which will become visibly lighter, softer, cleaner, healthier and beautiful in no time.
Get rid of your summer freckles, acne scars, blemishes and excess skin oil. Your skin will revitalize, become vibrant, clear and strong, the health of your skin will be restored.
The Soap will have great results in both your face and your whole body. Can be used regularly in all surfaces and parts of our body.
Extremely easy to use. Dampen your face, lather and massage your face or body for 3 minutes and then rinse off.
Lightly exfoliate your skin and control your pigmentation, to reveal a fair and smooth skin surface.


text:
Q: check if object exists in Cloud Files (PHP API) I've just started working with the PHP API for Rackspace Cloud Files. So far so good-- but I am using it as sort of a poor man's memcache, storing key/value pairs of serialized data.
My app attempts to grab the existing cached object by its key ('name' in the API language) using something like this:
$obj = $this->container->get_object($key);

The problem is, if the object doesn't exist, the API throws a fatal error rather than simply returning false. The "right" way to do this by the API would probably be to do a
$objs = $this->container->list_objects();

and then check for my $key value in that list. However, this seems way more time/CPU intensive than just returning false from the get_object request.
Is there a way to do a "search for object" or "check if object exists" in Cloud Files?
Thanks

A: I sent them a pull request and hope it'll get included.
https://github.com/rackspace/php-cloudfiles/pull/35
My pull-request includes an example, for you it would be similar to this:
$object = new CF_Object($this->container, 'key');
if ($object->exists() === false) {
    echo "The object '{$object->name}' does not exist.";
}

A: I have more general way to check if object exists:
    try {
        $this->_container->get_object($path);
        $booExists = true;
    } catch (Exception $e) {
        $booExists = false;
    }

A: If you dump the $object, you'll see that content_length is zero.  Or, last modified will be a zero length string.
Example:
$object = new CF_Object($container, 'thisdocaintthere.pdf');
print_r($object->content_length);

There is also, deep in the dumped parent object, a 404 that will return, but it's private, so you'd need to some hackin' to get at it.
To see this, do the following:
$object = new CF_Object($container, 'thisdocaintthere.pdf');
print_r($object->container->cfs_http);

You'll see inside that object a response_status that is 404
[response_status:CF_Http:private] => 404

A: I know I'm a little late to the party, but hopefully this will help someone in the future: you can use the objectExists() method to test if an object is available.
public static function getObject($container, $filename, $expirationTime = false)
{
    if ($container->objectExists($filename)) {

        $object = $container->getPartialObject($filename);

        // return a private, temporary url
        if ($expirationTime) {
            return $object->getTemporaryUrl($expirationTime, 'GET');
        }

        // return a public url
        return $object->getPublicUrl();
    }

    // object does not exist
    return '';
}

Use like...
// public CDN file
$photo = self::getObject($container, 'myPublicfile.jpg');

// private file; temporary link expires after 60 seconds
$photo = self::getObject($container, 'myPrivatefile.jpg', 60);

A: If you do not want to import opencloud to perform this check you can use the following:
$url = 'YOUR CDN URL';
$code = FALSE;
$options['http'] = array(
    'method' => "HEAD",
    'ignore_errors' => 1,
    'max_redirects' => 0
);
$body = file_get_contents($url, NULL, stream_context_create($options));
sscanf($http_response_header[0], 'HTTP/%*d.%*d %d', $code);

if($code!='200') {
    echo 'failed';
} else {
    echo 'exists';
}

redpajama_set_name: RedPajamaStackExchange


text:
Q: Testing SQLite database in Robolectric I'm trying to test a simple SQLite database using Robolectric in my Android application. I'm putting in some values, but when reading them back 0 rows are returned.
I'm using the SQLiteOpenHelper class to access the database.
// RequestCache extends SQLiteOpenHelper
RequestCache cache = new RequestCache(activity);
SQLiteDatabase db = cache.getWritableDatabase();

// Write to DB
ContentValues values = new ContentValues();
values.put(REQUEST_TIMESTAMP, TEST_TIME);
values.put(REQUEST_URL, TEST_URL);
db.insertOrThrow(TABLE_NAME, null, values);

// Read from DB and compare values
Vector<Request> matchingRequests = new Vector<Request>();
db = cache.getReadableDatabase();
Cursor cursor = db.query(TABLE_NAME, SEARCH_URL_RETURN_COLUMNS, SEARCH_URL_WHERE, new String[] {url}, null, null, ORDER_BY, null);
int id = 0;

while(cursor.moveToNext()) {
    long timestamp = cursor.getLong(0);
    Request request = new Request(id++);
    request.setUrl(url);
    request.setCreationTimestamp(new Date(timestamp));
    matchingRequests.add(request);
}

// Assert that one row is returned
assertThat(matchingRequests.size(), equalTo(1));  // fails, size() returns 0

When debugging the code outside robolectric this works as expected. Am I doing anything wrong or is it not possible to test SQlite databases using Robolectric?

A: Robolectric 2.3 uses a real implementation of SQLite instead of a collection of shadows and fakes. Tests can now be written to verify real database behavior.

A: The code linked in the accepted answer did not work for me; it may be out of date.  Or perhaps my setup is just different.  I am using Robolectric 2.4 snapshot, which does not seem to include a ShadowSQLiteOpenHelper, unless I missed something.  In any case, I figured out a solution.  Here's what I did:

*

*I created a class called ShadowSQLiteOpenHelper and copy-pasted the contents of the code linked above (https://github.com/waltsu/robolectric/blob/de2efdca39d26c5f18a3d278957b28a555119237/src/main/java/com/xtremelabs/robolectric/shadows/ShadowSQLiteOpenHelper.java), and fixed the imports.

*Following the instructions on http://robolectric.org/custom-shadows/ for using custom shadows, I annotated my test class with @Config( shadows = { ShadowSQLiteOpenHelper.class } ).  No need for a custom test runner.

*In my tests, I instantiated my subclass of SQLiteOpenHelper, passing in a new Activity() as the Context (Robolectric happily takes care of that), and used it per usual.

Now, at this point, I noticed that an actual database file was getting created locally:  after the first run of a test that used my SQLiteOpenHelper subclass, I kept getting an SQLiteException on subsequent tests because my table already existed; and I could see a file called "path" and a file called "path-journal" sitting in my local repository.  This confused me because I was under the impression that the shadow class was using an in-memory database.
It turns out the offending line in the shadow class is:
database = SQLiteDatabase.openDatabase( "path", null, 0 );

in both getReadableDatabase() and getWriteableDatabase().  I knew that the real SQLiteOpenHelper could create an in-memory database, and after looking at the source to see how it's done, I replaced the above line with:
database = SQLiteDatabase.create( null );

after which, everything seems to work.  I am able to insert rows and read them back.
Hopefully this helps someone else.
One weird thing that happened to me that isn't exactly related to this question, but might help someone further, is that I'm also using jmockit, and I had used it in one test in the same class; but for some reason, this caused my custom shadow class to not be used.  I switched to Mockito for just that class, and it works fine.

A: NOTE: This answer is outdated. If you are using Roboletric 2.X, please see https://stackoverflow.com/a/24578332/850787
The problem is that Robolectric's SQLiteDatabase is stored only in
memory, so when you call getReadableDatabase or getWritableDatabase,
the existing database will be overridden with new empty database.
I was running to the same problem and only solution I found
was that I needed to fork the Robolectric project and added
ShadowSQLiteOpenHelper to save database if same context is given two
times. However the problem with my fork is that I had to 'disable'
close()-function when contex is given because otherwise
Connection.close() will destroy the database in memory. I have made pull request for it but it isn't merged to project yet.
But feel free to clone my version and it should fix your problem (If I
understood it correctly :P ).
It can be found on GitHub: https://github.com/waltsu/robolectric
Here is a example how to use the modification:
Context c = new Activity();
SQLiteOpenHelper helper = new SQLiteOpenHelper(c, "path", null, 1);
SQLiteDatabase db = helper.getWritableDatabase();
// With the db write something to the database
db.query(...);
SQLiteOpenHelper helper2 = new SQLiteOpenHelper(c, "path", null, 1);
SQLitedatabase db2 = helper2.getWritableDatabase();
// Now db and db2 is actually the same instance
Cursor c = db2.query(...) ; // Fetch the data which was saved before

Ofcourse you don't need to create new SQLiteOpenHelper, but that is just example that passing same context to two different SQLiteOpenHelper will give same database.


text:
Cookie's Fortune (1999)
Comedy Crime Suspense
April 2, 1999 (Limited)
Anne Rapp
Niecy Nash, John M. Sullivan II, Ruby Wilson, Rufus Thomas, Preston Strobel, Matt Malloy, Shari Schneider, Randle Mell, Danny Darst, Lyle Lovett, Julianne Moore, Liv Tyler, Chris O'Donnell, Charles Dutton, Patricia Neal, Ned Beatty, Courtney B. Vance, Donald Moffat, Glenn Close
October Films
Rated PG-13 for depiction of a violent act and sensuality
The ingredients of an archetypal southern town (the blues, catfish, and scrabble), a deliciously chosen cast, and the creative skills of Robert Altman make for a wonderfully engaging film that adds to the accolades that have distinguished his outstanding career. Delectably combining farce, moral passion play, and social drama with a soupcon of mystery/suspense, Altman drives us to his grandly executed finale with a constantly inventive comedic theatricality. Generations of the Orcutt family have inhabited... Full synopsis »
Cookie's Fortune is one of those films that never gets much publicity but manages to hit the big time theaters and stay out for a surprisingly long amount of time. I had heard nothing about this film except that it was good - I did not even know who was in it, let alone what the film was about. But it has an all star cast, a good story, and interesting characters. Full movie review »


On Sunday 9th July 2017 there was a Museum Member's day trip to Ardo House in Ardmore, led by Liam Suipéal.
Ardo House has a very interesting history and Liam gave a wonderful talk which brought the history of the house alive for the group. The trip was thoroughly enjoyed by all.
Our thanks to Liam Suipéal, and to Eddie Cantwell and all involved in organising this memorable trip.


Fetches user lists. Supports filtering and sorting.
get AdsApp.UserListIterator Fetches the requested user lists and returns an iterator.
orderBy AdsApp.UserListSelector Specifies the ordering of the resulting entities.
withCondition AdsApp.UserListSelector Adds the specified condition to the selector in order to narrow down the results.
withIds AdsApp.UserListSelector Restricts this selector to return only user lists with the given user list IDs.
withLimit AdsApp.UserListSelector Specifies limit for the selector to use.
Fetches the requested user lists and returns an iterator.
AdsApp.UserListIterator Iterator of the requested user lists.
orderBy("MembershipLifeSpan") - orders results by MembershipLifeSpan, in ascending order.
orderBy("SizeForSearch ASC") - orders results by SizeForSearch, in ascending order.
See UserListSelector.withCondition(String) for enumeration of columns that can be used.
The results will be ordered by Name in ascending order. Results with equal Name values will be ordered by MembershipLifeSpan in descending order.
AdsApp.UserListSelector The selector with ordering applied.
All specified conditions are AND-ed together. The above example will retrieve entities with a membership life span of more then 30 days and 100 members eligible for search campaigns/ad groups.
Id Long withCondition("Id = 123456789").
AdsApp.UserListSelector The selector with the condition applied.
Restricts this selector to return only user lists with the given user list IDs.
will only get the user list with ID 34567, since it would be the only user list that satisfies both ID conditions.
ids long Array of user list IDs.
AdsApp.UserListSelector The selector restricted to the given IDs.
AdsApp.UserListSelector The selector with limit applied.