text:
\section{Introduction}
Caching at the network edge plays a key role in reducing user-perceived latency, in-network traffic, and server load. In the most common setting, when a user requests a given \mbox{object $o$}, the cache provides $o$ if locally available (hit), and retrieves it from a remote server (miss) otherwise. In other cases, a user request can be (partially) satisfied by a similar object~$o'$. For example, a request for a high-quality video can still be met by a lower resolution version. In other scenarios, a user query is itself a query for objects similar to a given \mbox{object $o$}. This situation goes under the name of \emph{similarity searching},  {proximity searching}, or also metric searching~\cite{chavez01}. Similarity searching plays an important role in many application areas, like multimedia retrieval~\cite{falchi08}, recommender systems~\cite{pandey09,sermpezis18}, genome study~\cite{auch10}, machine learning training~\cite{weston15,graves14,santoro16}, and serving~\cite{crankshaw15,crankshaw17}. In all these cases, a cache can deliver to the user one or more  objects similar to $o$ among those locally stored, or decide to forward the request to a remote server. The answer provided by the cache is in general an \emph{approximate} one in comparison to the best possible answer the server could provide. Following the seminal papers~\cite{falchi08,pandey09}, we refer to this setting as \emph{similarity caching}, and to the classic one as \emph{exact caching}.

To the best of our knowledge, the first paper introducing the problem of caching for similarity searching was~\cite{falchi08}. The authors considered how caches can improve the scalability of content-based image retrieval systems. Almost at the same time,~\cite{pandey09} studied caches in content-match systems for contextual advertisement. Both papers propose some simple modifications to the least recently used policy (\textproc{LRU}{}) to account for the possibility of providing approximate answers.
More recently, in~\cite{weston15} and \cite{graves14}, similarity caching has been used to retrieve similar feature vectors from a memory unit with the goal of  improving the performance of sequence learning tasks. Previous approaches led to the concept of memory-augmented neural networks~\cite{santoro16}.
Clipper~\cite{crankshaw17}---a distributed system to serve machine learning predictions---includes similarity caches to provide low-latency, approximate answers. A  preliminary evaluation of the effect of different caching strategies for this purpose can be found in~\cite{crankshaw15}.
Recently,~\cite{sermpezis18} and a series of papers by the same authors have studied recommendation systems  in a cellular setting,
where contents can be stored close to the users. They focus on how to statically allocate the contents in each cache assuming to know the contents' popularities and the
utility for a user interested in content $o$ to receive a similar content $o'$.

Exact caching has been studied for decades in many areas of computer science,
and there is now a deep understanding of the problem. Optimal caching algorithms are known in specific settings, and general approaches to study caching policies have been developed both under adversarial and stochastic request processes. On the contrary, despite the many potential applications of similarity caching, there is still almost no theoretical study
of the problem, specially for dynamic policies. The only one we are aware of is the competitive analysis of a particular variant of similarity caching in~\cite{chierichetti09} (details in Sect.~\ref{s:adversarial}). Basic questions are still unanswered: are similarity and exact caching fundamentally different problems? Do low-complexity optimal similarity caching policies exist?
Are there margins of improvement with respect to heuristics proposed in the literature, like in~\cite{falchi08,pandey09}?
This paper provides the first answers to the above questions.
Our contributions are the following:
\begin{enumerate}
	\item we show that similarity caching gives rise to NP-hard problems even when exact caching lends itself to simple polynomial algorithms;

	\item we provide an optimal pseudo-polynomial algorithm when the sequence of future requests is known;
	\item we recognize that, in the adversarial setting, similarity caching is a $k$-server problem with excursions;
	\item we propose optimal dynamic policies, both when objects' popularities are known, and when they are unknown;
	\item we show by simulation that  our dynamic policies provide better performance than existing schemes,

                   both under the independent reference model (IRM) and under real request traces.
\end{enumerate}
A major technical challenge of our analysis is that we allow the object catalog to be potentially infinite and uncountable, as it happens when objects/requests are described by
vectors of real-valued features~\cite{crankshaw17}. Note that in this case exact caching
policies like \textproc{LRU}{} would achieve zero hit ratio, when the spatial distribution of
requests is described by a probability density function.

The rest of the paper is organized as follows. Section~\ref{s:model} introduces our main assumptions on request processes and caching policies. Sections~\ref{s:offline} and~\ref{s:adversarial} present results on similarity caching respectively in the offline and in the adversarial setting. Our new dynamic policies are described in Sect.~\ref{s:stochastic}, together with their optimality guarantees in the stochastic setting. We numerically explore the performance of our policies in Sect.~\ref{s:simulations}.

\begin{table}
\textcolor{black}{
\caption{Notation}
\centering
\begin{tabular}{ll}
\hline
$k$ 		& cache size \\
$\mathcal X$	& set of objects that can be requested\\
$\mathcal S_t$	& state of the cache at time $t$\\
$\norm{.}$	& a norm in $\mathbb R^p$\\
$C_r$ 	&  cost to retrieve an object from the remote server \\
$C_a(x,y)$ 	&  cost to approximate $x$ with $y$\\
$C_a(x,\mathcal S)$ 	&  minimum cost to approximate $x$ with the elements in $\mathcal S$\\
$C_m(\mathcal T,\mathcal S)$		& cost to move from cache state $\mathcal T$ to cache state $\mathcal S$\\
$C(x,\mathcal S)$	& cost to serve request $x$ from cache state $\mathcal S$\\
$C_e(x,y)$	& excursion cost to serve request $x$ using  (server) $y$\\
$\mathcal C_A(\mathcal S_1,\mathbf r_T)$ & time-average cost incurred by caching policy $A$ to serve \\
				& the request sequence $\mathbf r_T$ starting from state $\mathcal S_1$\\
$\EuScript C(\mathcal S)$	& expected cost to serve a request from cache state $\mathcal S$\\
$\lambda_x$	& request rate for object $x$ (finite case) \\
			& or request rate density in $x$ (continuous case)\\
$\mathcal B(x,V)$		& ball in $\mathbb R^p$ centered in $x$ and with volume $V$\\
$\mathcal B_r(x)$		& ball in $\mathbb R^p$ centered in $x$ and with radius $r$\\
\hline
\end{tabular}
\label{t:notation}
}
\end{table}

\section{Main assumptions}
\label{s:model}
Let $\mathcal X$
be the (finite or infinite) set of objects that can be requested by the users.
We assume that all objects
have equal size and the cache can store up to $k$ objects. The state of the cache at time $t$ is given by the set of objects  $\mathcal S_t$
currently stored in it, $\mathcal S_t=\{ y_1, y_2,\ldots y_k \}$, with $y_i\in \mathcal X$.

We assume that, given any two objects $x$ and $y$ in $\mathcal X$, there is a non-negative  (potentially infinite) cost $C_a(x,y)$ to approximate $x$ with $y$. We consider $C_a(x,x)=0$.
 Given a set $\mathcal A$ of elements in $\mathcal X$, let $C_a(x,\mathcal A)$ denote the minimum approximation cost provided by elements in $\mathcal A$, i.e., $C_a(x,\mathcal A)=\inf_{y\in \mathcal A} C_a(x,y)$.

In what follows, we consider two main instances for  $\mathcal X$ and $C_a()$.
In the first instance,  $\mathcal X$ is a finite set of objects and thus the approximation cost can be characterized by an $|\mathcal X| \times |\mathcal X|$ matrix of non-negative values.
This case could well describe the (dis)similarity of contents (e.g.~videos) in a finite catalog.
{\color{black} In the second instance, $\mathcal X$ is a compact  subset of $\mathbb R^p$ and $C_a(x,y)=h(\norm{x-y})$, where $h: \mathbb R^+ \to \mathbb R^+$ is a non-decreasing non-negative function and $\lVert  . \rVert$ is a norm in $\mathbb R^p$ (e.g.~the Euclidean one)}.
This case is more suitable for describing objects characterized by continuous features. \textcolor{black}{For example,   in the field of distance metric learning~\cite{bellet15metric}, supervised machine learning techniques are used to learn how to map similar objects to vectors in $\mathbb R^p$ that are close according to $q$-norm distances, cosine similarity, or Mahalanobis distances. We describe a specific application in Amazon recommendation systems in Sect.~\ref{s:simulations}.}
We will refer to the above two instances as \emph{finite} and \emph{continuous}, respectively.

Our goal is to design effective and efficient cache management policies that minimize the aggregate cost to serve a sequence of requests for objects in $\mathcal X$.
We assume that the function $C_a: \mathcal X \times \mathcal X \to \mathbb{R}^+ \cup \{+\infty\}$ is available for caching decisions and that the cache is able to compute the set of best approximators for $x$, i.e.,~$\arg \min_{y \in \mathcal S_t} C_a(x,y)$. This can be efficiently done using locality sensitive hashing (LSH)~\cite{pandey09}.
Moreover, we will restrict ourselves to online policies in which object insertion into the cache is triggered by requests (i.e., the cache cannot pre-fetch arbitrary objects).
Upon a request for object $r_t$ at time $t$, if the content is locally stored ($r_t \in \mathcal S_t$), then the cache directly provides  $r_t$ incurring a null cost ($C_a(r_t,\mathcal S_t)=0$) and we have an \emph{exact hit}.
Otherwise, the cache can either i) provide the best approximating object locally stored,
i.e.,~$y \in \arg \min_{y \in \mathcal S_t} C_a(x,y)$,
incurring the approximation cost $C_a(r_t,\mathcal S_t)$ (\emph{approximate hit}) or ii) retrieve
the content from the server incurring a fixed cost $C_r>0$ (\emph{miss}). Upon a miss, the cache retrieves the object $r_t$, serves it to the user, and then may replace one of the currently stored objects with $r_t$. We stress the caching policy is not required to store $r_t$.
Without loss of generality, we can restrict to caching policies providing an approximate hit only if the approximation cost is smaller than the retrieval cost ($C_a(r_t, \mathcal S_t) \le C_r$). The caching policy will then always reply to a request $r_t$ with an object $o$ such that $C_a(r_t, o) \le C_r$.
Indeed,
one could otherwise devise a new caching policy that retrieves content $r_t$ and then discards it, paying a smaller cost.

We also define the movement cost, \textcolor{black}{i.e., the cost of updating the cache state from $\mathcal T$ to $\mathcal S$,} as follows:
\begin{equation}
 C_m(\mathcal T,\mathcal S) \triangleq \begin{cases}
	0, 	 & \textrm{ if }\mathcal S = \mathcal T,\\
	C_r, 	 & \textrm{ if }|\mathcal S \setminus \mathcal T| =1,\\
	+\infty, & \textrm{ otherwise.}
\end{cases}
\label{e:movement_cost}
\end{equation}
\textcolor{black}{The definition captures the fact that it is possible to replace only one object in the cache paying the retrieval cost $C_r$.}
Given a finite sequence of requests $\mathbf r_T={r_1, r_2, \dots, r_T}$ and an initial state $\mathcal S_1$, the average cost paid by a given caching policy $A$ is
\begin{equation}
	\label{e:avg_cost}
	\mathcal C_A(\mathcal S_1,\mathbf r_T)=  \frac{1}{T} \sum_{t=1}^T \left[ C_m(\mathcal S_t,\mathcal S_{t+1}) + C(r_t, \mathcal S_{t+1})\right],
\end{equation}
where
\begin{equation}
	\label{e:service_cost}
	C(o,\mathcal S) \triangleq \min(C_a(o, \mathcal S),C_r)
\end{equation}
and we call it the service cost. In fact, if $\mathcal S_{t+1}\neq \mathcal S_t$, the cache has retrieved $r_t$ paying the retrieval cost $C_r=C_m(\mathcal S_t,\mathcal S_{t+1})$, but no approximation cost ($C(r_t,\mathcal S_{t+1})=C_a(r_t, \mathcal S_{t+1})=0)$. If $\mathcal S_{t+1}= \mathcal S_t$, the cache has provided an approximate answer or has retrieved (but not stored) $r_t$, paying $C(r_t,\mathcal S_t)\triangleq\min(C_r,C_a(r_t, \mathcal S_{t}))$.
Note that the average cost depends on \textcolor{black}{the caching policy} $A$, because the policy determines the evolution of the cache state $\mathcal S_t$. Policies differ in the choice of which requests are approximate hits
or misses (even if $C_a(r_t, \mathcal S_t)\le C_r$, the cache can decide to retrieve and store $r_t$) and in the choice of which object is evicted upon insertion of a new one.
We observe that, if $C_a(x,y)=\infty$ for all $x\neq y$, we recover the  exact caching setting. If, in addition, $C_r=1$, Eq.~\eqref{e:avg_cost} provides the miss ratio.
The  cost structure~\eqref{e:avg_cost}, together with a movement cost like~\eqref{e:movement_cost} that satisfies the triangle inequality, defines a metrical task system (MTS), first introduced by Borodin~{\emph{et al.}}~\cite{borodin92}, which is usually studied through competitive analysis (more in Sect.~\ref{s:adversarial}).

As  mentioned in the introduction, similarity caching lacks a solid theoretical understanding. From an algorithmic view-point, it is not clear if similarity caching is a problem intrinsically more difficult than exact caching.
From a performance evaluation view-point, we do not know if similarity caching can be studied resorting to the same approaches adopted for exact caching.
In this paper we provide the first answers to these questions, which
depend crucially on the nature of the requests' sequence.
Three scenarios are commonly considered in the literature:
\begin{description}
	\item[Offline:] the request sequence is known in advance. This assumption is made when one wants to determine the best possible performance of any policy. In the case of exact caching, it is well known
          that the minimum cost (miss ratio) is achieved by B\'el\'ady's policy~\cite{belady66}, that evicts at each time the object whose next request is further in the future.
	\item[Adversarial:] the request sequence is selected by an adversary who wants to maximize the cost incurred by a given caching policy.
           This approach leads to competitive \mbox{analysis}, which determines how much worse an online policy (without knowledge of future requests) performs in comparison to the optimal offline policy.
	\item[Stochastic:] requests arrive according to a stationary exogenous stochastic process. One example is the classic IRM, where  requests  for different objects are generated by
	independent  time-homogeneous  Poisson processes.
            The goal here is to minimize the expected cost or equivalently the average cost in~\eqref{e:avg_cost} over an infinite time horizon.
\end{description}
We separately consider the above three scenarios in the next sections.

\section{Offline optimization} \label{s:offline}
In this section we consider the offline setting in which a finite sequence of requests $\mathbf r_T$ is known in advance.
We distinguish between two cases: i) a first  preliminary scenario, in which a static set of objects has to be prefetched in the cache before the arrival of the first request (we refer to this scenario as static) and then the state of the cache can not be further modified; ii)  a more general case  in which the state of the cache can be  modified upon every miss  by inserting  in it
 the requested content, in place of a previously stored content
  (we refer to this scenario as dynamic).

\subsection{Static setting}
We first address the problem of finding a static set of objects to be prefetched in the cache, so as to minimize the cost in~\eqref{e:avg_cost}, i.e., we want to find:
\[\mathcal S^* \in \argmin_{\mathcal S_1} \sum_{t=1}^T C(r_t,\mathcal S_1).\]
Note that the corresponding version of this (static, offline) problem for exact caching has a simple polynomial solution
with $T \log T$ time complexity and $T$ space complexity: one simply needs to store in the cache the $k$ most requested objects in the trace.
For similarity caching the problem is much more difficult, in fact:
\begin{thm}
\label{t:np_hard_combinatorial}
The static offline similarity caching problem is NP-hard.
\end{thm}
\begin{proof}
The result follows from a reduction of the dominating set problem.  Consider an undirected graph $\mathcal G=(V,E)$ with set of nodes $V$ and set of edges $E$. Given $U\subset V$ we let $N[U]=\{U\}\cup \{u \in V : \exists v\in U, (u,v) \in E \}$ denote the (closed) neighborhood of $U$. The dominating set problem concerns testing, for a given graph $\mathcal G$ and value $k$, if there exists a set $U \subset V$ with size at most $k$ such that  $N[U]=V$. The dominating set problem is NP-complete~\cite[Sect.~A1.1]{garey90}.

{Consider now the following auxiliary decision problem: given a graph $\mathcal G$ and two values $k$ and $\ell$, does there exist a set $U \subset V$ with size at most $k$ such that  $|N[U]|\ge \ell$? This problem is NP-complete too, indeed i)  it is clearly  in NP and  ii) the dominating set problem can be reduced to it, by simply placing $\ell = |V|$.}
The corresponding NP-hard optimization problem can be formulated as:
\begin{equation}
\label{e:budgeted_ds}
\underset{U \subset V, |U|\le k}{\text{maximize}} \;\;\; |N[U]|,
\end{equation}
{To conclude our proof,}  we show that this problem can be reduced  to a static offline similarity caching problem.

We consider the static offline similarity caching problem with $\mathcal X = V$, $C_r=1$, and $C_a(x,y)=C_a(y,x)=0$ if $(x,y) \in E$ and $C_a(x,y)=C_a(y,x)=+\infty$ otherwise. The request sequence $\mathbf r_T$ contains one and only one request for each object.

Let $\mathcal S$ denote the set of objects in the cache and  $U \subset V$ the corresponding set of nodes in the graph $\mathcal G$. Consider a request $r$ for object $v\in V$. The request generates a miss and incurs a cost equal to $C_r=1$ if and only if $v$  does not belong to $N[U]$. It follows that the total cost incurred by the similarity cache is equal to the number of nodes in $V\setminus N[U]$.
Therefore finding the cache configuration $\mathcal S$ that
minimizes the total cost is equivalent to identifying the $k$ nodes $U$
with the largest  closed neighborhood $|N[U]|$ as in \eqref{e:budgeted_ds}.
\end{proof}

\begin{rem}
We observe that the static cache allocation problem can also be formulated as a particular maximum coverage problem. The maximum coverage problem cannot be approximated by a constant larger than $1-1/e$,  which is achieved by the greedy algorithm. The relation between the two problems suggests that a greedy algorithm would be a
reasonable approach to the static offline similarity caching problem, but there is no guaranteed approximation ratio (because of the transformation
from a maximization problem into a minimization one).
\end{rem}

In the continuous case, where objects are points in $\mathbb R^p$, and $C_a(x,y)$ is a function of a distance $d()$, one may think that the problem could become simpler.
The following theorem shows that this is not the case in general.
 \begin{thm}
\label{t:np_hard_geometric}
Let $\mathcal X= \mathbb R^2$,
and $C_a(x,y)=h(\norm{x-y})$, where $h(z)=0$ for $z \le 1$ and $h(z)=C_r=1$ otherwise. Finding the optimal static set of objects to store in the cache is NP-hard both for norm-2 and norm-1 distance.
 \end{thm}
\begin{proof}
We prove NP-hardness in the restricted case when every object is requested only once. We observe that any \mbox{object $y$} stored in the cache can satisfy requests for all the points in a disc (resp. square)
centered in $y$ in the case of norm-2 (resp. norm-1) distance.
The problem of determining the optimal static set of objects to store in the cache to maximize the number of hits is then equivalent to the problem of finding $k$ identical translated geometric shapes covering
the largest number of points in the request sequence. These shapes are, respectively, discs and squares in the case of norm-2 and norm-1 distance.
NP-hardness follows immediately from the NP-hardness of the two covering problems on the plane known as DISC-COVER and BOX-COVER~\cite{fowler81}.
\end{proof}
\begin{rem}
In $\mathbb R$, DISC-COVER and BOX-COVER are solvable in linear time.
\end{rem}
\begin{rem}
For geometric versions of the maximum coverage problem, better approximation ratios can be achieved. For example \cite{jin18} presents some efficient polynomial-time approximation schemes when the objects are point on a plane.
\end{rem}

We have already observed that exact caching is a particular case of similarity caching. Theorems~\ref{t:np_hard_combinatorial} and~\ref{t:np_hard_geometric} show that similarity caching is an intrinsically
 more difficult problem.

\subsection{Dynamic setting}
For the dynamic setting (i.e., when the state of the cache can be  modified at every request), we propose a dynamic programming algorithm adapted from that proposed in~\cite{manasse90} for exact caching.

Let $\mathbf r$ denote a finite sequence of requests for $m$ distinct objects, and $\mathbf r x$ the sequence obtained appending to $\mathbf r$ a new request for content $x$. We denote by $\mathcal S_1$ the initial cache state, and by $C_{\textrm{OPT}}(\mathbf r,\mathcal S)$, the minimum aggregate cost achievable under the request sequence $\mathbf r$, when the \emph{final} cache state {is~$\mathcal S$}.
 It is possible to write the following recurrence equations, where $\bm \epsilon$ denotes the empty sequence:
 \begin{align*}
 C_{\textrm{OPT}}(\bm \epsilon, \mathcal S) & = \begin{cases}
	0, & \textrm{ if }\mathcal S=\mathcal S_1,\\
	+\infty, & \textrm{otherwise.}
\end{cases}\\
C_{\textrm{OPT}}(\mathbf r x, \mathcal S) & = \begin{cases}
	\min\limits_{\mathcal T}\left(C_{\textrm{OPT}}(\mathbf r, \mathcal T) + C_m(\mathcal T,\mathcal S)\right), & \textrm{ if }x \in \mathcal S,\\
	C_{\textrm{OPT}}(\mathbf r, \mathcal S) + C(x,\mathcal S),  & \textrm{otherwise.}
\end{cases}
\end{align*}
These equations lead to a dynamic programming procedure that
iteratively computes the optimal cost for
$\mathbf r_T$ and determine the corresponding sequence of caching decisions.
The number of possible states is $\binom{m}{k}$. We can arrive to each state $\mathcal S$ potentially from $(m-k)k+1$ other states. $d(T,S)$ and $C_a(x,\mathcal S)$ can be evaluated with $\mathcal O(k)$ operations.
Algorithm's time complexity is $\mathcal O\left((m-k) k^2 \binom{m}{k} T\right)$. Space complexity is at least $\binom{m}{k}$.
As this algorithm can only be applied to small cache/catalog sizes, we will derive more useful bounds for the optimal cost in Sect.~\ref{s:bounds} for the stochastic scenario.

\begin{rem}
 This algorithm is especially suited for the case when the number of requests $T$ is much larger than the number $m$ of unique contents appearing in the sequence. For the classic $k$-server problem there exists also an alternative algorithm, based on minimum cost network flow, with complexity $k T^2$~\cite{chrobak91}, that is preferable in the opposite scenario. It is an open problem if a similar algorithm can be designed for similarity caching.
\end{rem}

\section{Competitive analysis under adversarial requests}
\label{s:adversarial}
The usual worst case analysis is not particularly illuminating for caching problems: if an adversary can arbitrarily select the request sequence, then the performance of any caching policy can be arbitrarily bad. For example, with a catalog of $k+1$ objects, the adversary can make any deterministic algorithm achieve a null hit rate by simply asking at any time the content that is not currently stored in the cache.

For this reason, the seminal work of Sleator and Tarjan~\cite{sleator85} introduced \emph{competitive analysis} to characterize the relative performance of caching policies in comparison \textcolor{black}{to the best possible offline policy with hindsight, i.e.,~under the assumption that the sequence of requests
is known before caching decisions are taken}.\footnote{
	By now, competitive analysis has become a standard approach to study the performance of many other algorithms.
}
In particular, an online caching algorithm $A$ is said to be $\rho$-competitive, if its performance is within a factor $\rho$ (plus a constant) from the optimum. More formally, there exists $a$ such that
\[\mathcal C_A(\mathcal S_1, \mathbf r_T) \le \rho \; \mathcal C_B(\mathcal S_1, \mathbf r_T) + \frac{a}{T}, \textrm{ for all } B \textrm{ and }\mathbf r_T. \]

A competitive analysis of similarity caching in the particular case when $C_a(x,y)=0$ if $d(x,y)\le r$, where $d()$ is a distance in $\mathcal X$, is in~\cite{chierichetti09} (the only theoretical study of similarity caching we are aware of). In this section we present results for other particular cases, relying on existing work for the $k$-server problem with excursions.

The $k$-server problem~\cite{manasse90} is perhaps the ``most influential online problem [\dots] that manifests the richness of competitive analysis''~\cite{koutsoupias09}. In the $k$-server problem, at each time instant a new request arrives over a metric space and the user has to decide which server to move to serve it, paying a cost equal to the distance between the previous position of the server and the request. It is well known that the $k$-server problem generalizes the exact caching problem.
In particular, in the case when distances are all equal to one (the uniform metric space), the cost of $k$-server is equal to the total number of misses achieved by a caching policy that is forced to store the
 requested content.

Interestingly, Manasse and McGeoch's seminal paper on the $k$-server problem~\cite{manasse90} also introduces the following variant: a server can perform an excursion to serve the new request and then come back to the original point paying a cost determined by a different function. Similarity caching problem can be considered as a $k$-server problem with excursions where server movements have uniform cost $C_r$ and the excursion of a server in $y$ to serve a request for $x$ has cost
\begin{equation}
\label{e:excursion_cost}
C_e(x,y) \triangleq \min(C_a(x,y),C_r).
\end{equation}

Unfortunately, while we have found a noble relative of our problem in the algorithmic field,
not much is known about the $k$-server problem with excursions in the scenario we are interested in (uniform metric space for movements and generic metric space for excursions). We rephrase a few existing results in terms of the similarity caching problem. The first one applies to the case when the cache can contain all objects but one. The second one applies to the uniform scenario where each object can  equally well approximate any other object.
We hope that the important applications of similarity caching will motivate further research on the $k$-server problem with excursions.
\begin{thm}
\label{t:small_catalogue}
\cite[Sect.~6, Thm~10]{manasse90} Let $\alpha_u$ be an upper bound for the set $\{C_e(x,y)/C_r \;|\; x, y \in \mathcal X
\}$. If $|\mathcal X|=k+1$, then the competitive ratio of any algorithm is bounded below by $(2 k+ 1)(1+\alpha_u)/(1+2 \alpha_u)$. Moreover, there exists a $(2 k +1)$-competitive deterministic algorithm (BAL).
\end{thm}
Note that we can always select $\alpha_u =1$.
\begin{thm}
\label{t:uniform_space}
\cite[Thms~4.1-2]{bartal01} If $|\mathcal X|>k$ and there exists $0<\alpha$ such that $C_e(x,y)=\alpha C_r$  for all $x, y \in \mathcal X$ with $x \neq y$, then the competitive ratio of any algorithm is at least $2k+1$. Moreover, there exists a $(2k+1)$-competitive deterministic algorithm (RFWF).
\end{thm}
A $(4k+1)$-competitive algorithm is proposed in~\cite{hollander96}.
\cite{chung01}~studies 1-server with limited look-ahead (i.e.~considers policies that know a given number of future requests).

\section{Stochastic request process}\label{s:stochastic}
We now consider the case \textcolor{black}{when requests arrival times follow a Poisson process with (normalized) intensity $1$ and the requested object is drawn from $\mathcal X$ according to the same distribution independently from the past, i.e., requests are i.i.d.~distributed}. In the finite case ($|\mathcal X|<\infty$), we have a request rate $\lambda_x$ for each content $x$
and we essentially obtain the classic IRM. In the continuous case,
we need to consider a spatial density of requests defined by a Borel-measurable
function $\lambda_x:\,\mathcal{X} \to \mathbb{R}_+$, i.e., for every Borel set $\mathcal A \subseteq \mathcal X$, the rate with which contents in $\mathcal A$ are requested is given by\footnote{More in general,
we could consider a generic compact metric space $\mathcal X$ endowed with the Haar measure, i.e.,
the unique (up to multiplicative constant) finite Borel measure, which is translation invariant over $\mathcal X$.}
$\int_{\mathcal A} \lambda_x {\rm\,d} x$.

Under the above assumptions, for a given cache state $\mathcal S=\{y_1 \ldots y_k\}$, we can compute the corresponding expected cost to serve a request:
\begin{equation}\label{eq:conditionalcost}
\EuScript C(\mathcal S) \triangleq
	\begin{cases}
		\sum_x \lambda_x C(x,\mathcal S), & \textrm{finite case}\\
		\int_{\mathcal X} \lambda_x C(x,\mathcal S) {\rm\,d} x, & \textrm{continuous case.}
	\end{cases}
\end{equation}

We observe that, as the sequence of future requests does not depend on the past, the average cost incurred over time by any online caching algorithm $A$ is bounded with probability 1 (w.p.~1) by the minimum expected cost $\min_\mathcal S \EuScript C(\mathcal S)$
\begin{align}
\label{e:opt_bound}
\liminf_{T \to \infty} \mathcal C_A(\mathcal S_1,\mathbf r_T)
	& \ge \min_{\mathcal S} \EuScript C(\mathcal S), \textrm{ w.p.} 1.
\end{align}
{\color{black} A  proof is given in Appendix \ref{a:mincost-pol}.
}
We then say that an online caching algorithm is optimal if its time-average cost achieves the lower bound in~\eqref{e:opt_bound} w.p.~$1$.
For example, an algorithm that reaches a state $\mathcal S^* \in \argmin_{\mathcal S} \EuScript C(\mathcal S)$ and, then, does not change its state is optimal. More in general, an optimal algorithm visits states with non minimum expected cost only a vanishing fraction of time.
Unfortunately, finding an optimal set of objects $\mathcal S^*$ to store is an NP-hard problem. In fact, minimizing \eqref{eq:conditionalcost} is a weighted version of the problem considered in~Sect.~\ref{s:offline}.
Despite the intrinsic difficulty of the problem, we present some online caching policies that achieve a global or local minimum of the cost.
We call a policy \mbox{$\lambda$-aware} (resp.~\mbox{$\lambda$-unaware}), if it relies (resp.~does not rely) on the knowledge of $\lambda_x$.

In practice, \mbox{$\lambda$-aware} policies are meaningful only when objects' popularities do not  vary wildly over time, remaining approximately constant over time-scales
in which $\lambda_x$ can be estimated through runtime measurements, similarly to what has been done in the case of exact caching by various implementations
of the Least Frequently Used (\textproc{LFU}) policy (see e.g.~\cite{einziger14}).
In contrast, \mbox{$\lambda$-unaware} policies do not suffer from this limitation.

Sections~\ref{s:lambda_aware} and~\ref{s:lambda_unaware} below are respectively devoted to  \mbox{$\lambda$-aware} and \mbox{$\lambda$-unaware} policies.
Section~\ref{s:bounds} presents some lower bounds for the cost of the optimal cache configuration in the continuous scenario.

\subsection{Online $\lambda$-aware policies}
\label{s:lambda_aware}
The first policy we present, \textproc{Greedy}, is based on the simple idea to systematically move to states with a smaller expected cost~\eqref{eq:conditionalcost}. It works as follows. Upon a request for content $x$ at time $t$, \textproc{Greedy}{} computes the  maximum decrement  in the expected cost that can be obtained by replacing one of the objects currently in the cache with $x$, i.e.,
$\Delta \EuScript C \triangleq \min_{y \in \mathcal S} \EuScript C(\mathcal S_t\cup \{x\} \setminus \{y\})-  \EuScript C(\mathcal S_t)$.
\begin{itemize}
\item if $\Delta \EuScript C < 0$ ($x$ contributes to decrease the cost), then the cache retrieves $x$, serves it to the user, and replaces $y_e \in \argmin_{y \in \mathcal S} \EuScript C(\mathcal S_t\cup \{x\} \setminus \{y\})$ with $x$;
\item if $\Delta \EuScript C \ge  0$, the cache state is not updated. If $C_a(x,\mathcal S_t) > C_r$, $x$ is retrieved to serve the request; otherwise the request is satisfied by one of the best approximating object in $\mathcal S_t$.
\end{itemize}

Intuitively, we expect \textproc{Greedy}{} to converge to a local minimum of the cost. In the continuous case, special attention is required to correctly define and prove this result.

\begin{dfn}\label{def:sig}
 A content $y_c$ is  said significant if, for any  $\delta>0$, it holds:
$ \int_{\mathcal B(y_c,\delta )}\lambda_x {\rm\,d}  x>0,$
where $\mathcal B(y_c,\delta )$ is the ball of volume $\delta$ centered at $y_c$.
\end{dfn}

\begin{dfn}
	A  cache configuration  $\mathcal S$ is locally optimal if
$	\EuScript C(\mathcal S) \le \EuScript C(\mathcal S'),	$
for all $\mathcal S'$  obtained from  $\mathcal S$  by replacing only one of the contents in the cache with a significant  content $y_c$.
\end{dfn}

\begin{thm}
\label{t:greedy}
	If  $C_a()$ and $\lambda()$ are smooth and $\mathcal X$ is a compact set, the   expected cost  of \textproc{Greedy}{} converges  to the expected  cost of a configuration that is locally optimal w.p.~1.
	If ${\mathcal X}$ is a finite set, the cache state converges to a locally optimal configuration in finite time w.p.~1.
\end{thm}
The proof is in Appendix~\ref{a:greedy}.

The \textproc{Greedy}{} policy converges to a locally optimal configuration. In the finite catalog case, under knowledge of content popularities, it is possible to asymptotically achieve the global optimal configuration using a policy that mimics a simulated annealing optimization algorithm. This policy is adapted from the \textproc{OSA}{} policy (Online Simulated Annealing) proposed in~\cite{neglia18ton}, and we keep the same name here.
\textproc{OSA}{} maintains a dynamic parameter $T(t)$ (the temperature). Upon a request for content $x$ at iteration $t$, \textproc{OSA}{} modifies the cache state as follows:
\begin{itemize}
\item If $x \in \mathcal S_t$, the state of  the cache is unchanged.
\item If $x \notin \mathcal S_t$, a content $y \in \mathcal S$ is randomly selected according to some vector of positive probabilities $p(\mathcal S_t)$, and the state of the cache is changed to $\mathcal S' = \mathcal S_t \setminus \{y\} \cup \{x\} $ with probability $\min\left(1, \exp((\EuScript C(\mathcal S_t)-\EuScript C(\mathcal S'))/T(t))\right)$.
\end{itemize}
In the first case, \textproc{OSA}{} obviously serves $x$ (a hit). In the second case, if the state changes to $\mathcal S'$, the cache  serves $x$. Otherwise, it serves  $x$ or $x' \in \argmin_{z \in \mathcal S} C_a(x,z)$, respectively,
 if $C_a(x,\mathcal S) > C_r$ or $C_a(x,\mathcal S) \le C_r$.
\textproc{OSA}{} always stores a new content if this reduces the cost (as \textproc{Greedy}{} does), but it does not get stuck in a local minimum because it can also accept  apparently harmful changes with a probability that is decreasing in the cost increase.
By letting the temperature $T(t)$ decrease  over time, the probability to move to worse states converges to 0 over time: the algorithm explores a larger part of the solution space at the beginning and becomes more and more ``greedy'' as time goes by.
The eviction probability vector $p(\mathcal S)$ can be arbitrarily chosen, as far as each content in $\mathcal S$ has a positive probability to be selected. In practice, we want to select with larger probability contents in $\mathcal S$, whose contribution to the cost reduction is smaller.

\textproc{OSA}{} provides the following theoretical guarantees. Let $\Delta \EuScript C_{\max}$ be the maximum absolute difference of costs between two neighboring states, then
 \begin{thm}
\label{t:osa}
When $|\mathcal{X}|<\infty$, if $T(t)=\Delta \EuScript C_{\max} k /(1+\log t)$, asymptotically only the states with minimum cost have a non-null probability to be visited.
\end{thm}
The proof is in Appendix~\ref{a:osa}.

As it is usual for simulated annealing results, convergence is guaranteed under very slow decrease of the temperature parameter (inversely proportional to the logarithm of the number of iterations). In practice, much faster cooling rates are adopted and convergence is still empirically observed.

Figure~\ref{f:toy_example} shows a toy case with a catalog of 4 contents and cache size equal to 2, for which \textproc{Greedy}{} with probability at least 9/20 converges to a suboptimal state $\mathcal S=\{1,3\}$ with corresponding cost $\EuScript C(\mathcal S)=17/128$. On the contrary, \textproc{OSA}{} escapes from this local minimum and asymptotically converges to the optimal state $\mathcal S^* =\{2,4\}$ with $\EuScript C(\mathcal S^*)=6/128$.

\begin{figure}
\centering
\includegraphics[scale=0.35]{toy_example4.png}
\caption{\textproc{OSA}{} converges to the minimum cost state. Catalog: $\{1,2,3,4\}$; $C_a(1,2)=C_a(2,1) = C_a(2,3)=C_a(3,2)=1/16$; for all other pairs $(x,y)$, $C_a(x,y)=\infty$; $C_r=1$; $\lambda_2=\lambda_4=1/8$,
$\lambda_1=\lambda_3= 3/8$, $T(t)=1/\sqrt{t}$.}
\label{f:toy_example}
\end{figure}

\subsection{Online $\lambda$-unaware policies}
\label{s:lambda_unaware}
In this section we present two new policies, \textproc{$q$LRU-$\Delta C$}{} and \textproc{Duel}, that, without knowledge of $\lambda_x$, bias admission and eviction decisions so to statistically  favour  configurations with
low {cost~$\EuScript C$}.

Policy \textproc{$q$LRU-$\Delta C$}{} is inspired by \mbox{$q$LRU-$\Delta$} proposed in~\cite{neglia19swiss_arxiv} to coordinate caching decisions across different base stations to maximize a generic utility function.
Despite the different application scenario, there are deep similarities between how different copies of the same content interact in the dense cellular network scenario of~\cite{leonardi18jsac} and how different contents interact in a similarity cache.

In~\textproc{$q$LRU-$\Delta C$}{} the cache is managed as a ordered list (queue)  as follows. Let $x$ be the content requested at time $t$.
\begin{itemize}
\item If $C_a(x,\mathcal S_t)>C_r$, there is a miss. The cache retrieves the content $x$ to serve it to the user. The content is inserted at the front of the queue, with probability $q$.
\item If $C_a(x,\mathcal S_t)\le C_r$, there is an approximate hit. The cache serves a content $z\in \argmin_{y \in \mathcal S_t} C_a(x,y)$, that is \emph{refreshed}, i.e., it is moved to the front of the queue,  with probability $\frac{C(x,\mathcal S_t \setminus \{z\})- C_a(x,z)}{C_r}$. With probability $q C_a(x,z)/C_r$ the content $x$ is still retrieved from the remote server and inserted at the head of the queue.
\end{itemize}
If needed, contents are evicted from the tail of the queue.
We observe that $C(x,\mathcal S_t \setminus \{z\})- C_a(x,z)$ corresponds to the cost saving for the request $x$ due to the presence of $z$ in the cache.

\begin{rem}
An approximate hit may jointly lead to insert the new content $x$ as well as to bring the approximating content $z$ to the head of the queue.
\end{rem}

When $|\mathcal{X}|$ is finite,  the following result holds under the characteristic time (or Che's) approximation (CTA)~\cite{che02} and the exponentialization approximation (EA), that has been recently proposed and validated in~\cite{leonardi18jsac}.
\begin{thm}
\label{t:qlru_opt}
Under CTA and EA, when $|\mathcal{X}|<\infty$ and $q$ converges to $0$, \textproc{$q$LRU-$\Delta C$}{} stores a set of contents that corresponds to a local minimum of the cost.
\end{thm}
The proof is in Appendix~\ref{a:qlru}.

The paper~\cite{pandey09} proposes two policies for similarity caching: \textproc{RND-LRU}{} and \textproc{SIM-LRU}.
In \textproc{RND-LRU}{} a request produces a miss with a probability that depends on the distance from the best approximating object $z$.
If it does not produce a miss, it refreshes the timer of $z$. Interestingly, \textproc{RND-LRU}{} can \mbox{emulate} in part
\textproc{$q$LRU-$\Delta C$}, by using $q C_a(x, \mathcal S_t)/C_r$ as its miss probability.
The only difference is the refresh probability:
in \textproc{RND-LRU}{} the best approximating content $z$ is refreshed with probability $1-q C_a(x, \mathcal S_t)/C_r$ (instead of $(C_r - C_a(x,\mathcal S_t))/C_r$ as in \textproc{$q$LRU-$\Delta C$}).
Our simulations in Sect.~\ref{s:simulations} confirm that, for  the same value of $q$, \textproc{RND-LRU}{} and \textproc{$q$LRU-$\Delta C$}{} exhibit very similar performance.
Given our result in Theorem~\ref{t:qlru_opt}, it is not surprising that \textproc{RND-LRU}{}  performs better than \textproc{SIM-LRU}~\cite[Fig.~9]{pandey09}.

\begin{rem}
It is possible to consider  admission probabilities of the form  $q_{x,t}= a(x,\mathcal S_t) q$, i.e, probabilities that depend on the requested content and the actual state of the cache. Theorem~\ref{t:qlru_opt} still holds,
when $q$ converges to $0$. This flexibility can be exploited to obtain better performance, by avoiding inserting contents that look less promising.
\end{rem}

As we will show in Sect.~\ref{s:simulations}, \textproc{$q$LRU-$\Delta C$}{} approaches the minimum cost only for very small values of $q$.
This is undesirable when contents' popularities change rapidly. To obtain a more responsive cache behavior, we propose a novel
online \mbox{$\lambda$-unaware} policy, that we call \textproc{Duel}.

Similarly to \textproc{Greedy}, upon a request at time $t$ for a content $y'$ which is not in the cache,
\textproc{Duel}{} estimates the potential advantage of replacing a cached content $y$ with $y'$, i.e.,~to move from the current  state $\mathcal S_t$ to state $\mathcal S'=\mathcal S_t \setminus \{y\} \cup \{y'\}$. As popularities are unknown, it is not possible to evaluate instantaneously  the two costs $\EuScript C(\mathcal S_t)$ and $\EuScript C(\mathcal S'_t)$. Then, the two contents engage in a `duel', i.e., they are compared during a certain
amount of time  (during this time we need to store only a reference to $y'$).
When a duel  between a real content $y$ and its virtual challenger $y'$ starts, we initialize to zero
a counter for each of them. If $y$  (resp.~$y'$) is the best approximating object for a following request $r_{\tilde t}$ occurring  at time $\tilde t>t$, then the corresponding counter is incremented by $C(r_{\tilde t},\mathcal S_{\tilde t} \setminus\{y\})- C_a(r_{\tilde t},y)$ (resp.~$C(r_{\tilde t},\mathcal S_{\tilde t} \setminus\{y\}   )- C_a(r_{\tilde t},y')$).
The counter associated to  a  dueling content accumulates then the aggregate cost savings due to that content.
A duel finishes in one of two possible ways: 1)~counters get separated by more than a fixed quantity
$\delta$ (a tunable parameter), or 2)~a maximum delay $\tau$ (another parameter) has elapsed since the start of the duel.
Duellist $y'$ replaces $y$ if and only if its counter exceeds the counter of $y$  by more than $\delta$ within the duel duration $\tau$.
Otherwise $y'$ is evicted, and $y$ becomes available again for a new duel.

A requested content is matched, whenever possible, with a content in the cache that is not engaged in an ongoing duel. At a given time, then, there can be up to $k$ ongoing duels.
A challenger $y'$ is matched to a stored object $y$ in two possible ways: with probability $\beta$, it is matched to the closest
object
 in the cache; with the complementary probability $1-\beta$, it is matched to a content selected uniformly at random. Duels between nearby contents allow for fine adjustments of the current cache configuration,
while duels between far contents enable fast macroscopic changes in
the density of stored objects.
Moreover, we avoid running concurrent duellists $y'$ and $y''$ which are too close to each other, because
the counter of a duellist should not be perturbed by the possible insertion of a close-by duellist.  To avoid such \lq interferring duels',
we do not admit a new duellist $y'$ if its counter could be fed by a request that is already feeding the counter of
another duellist~$y''$.

In essence, \textproc{Duel}{} provides a distributed, stochastic version of \textproc{Greedy}{} with delayed decisions (due to lack of knowledge of $\lambda_x$).

\subsection{Performance bound in the continuous scenario}
\label{s:bounds}
Besides being appropriate to describe objects/queries
in some applications, the continuous scenario is particularly interesting, because it marks a striking difference with exact caching.\footnote{Recall that
in the continuous case the rate of exact hits is null.}
For this scenario, we can derive some exact bounds and approximations of the minimum cost,
exploiting simple geometric considerations.

We start considering a homogeneous request process where $\lambda_x = \lambda$ over a bounded set $\mathcal X$. In what follows, all integrals are Lebesgue ones and all sets are Lebesgue measurable.
Given a set $\mathcal A \subset \mathbb R^p$, let $|\mathcal A|$ denote its volume (its measure), and $\mathcal B(x,|\mathcal A|)$ the ball with the same volume centered {in~$x$.\footnote{The geometric shape
 of a ball depends on the considered norm. For example, in $\mathbb R^2$, if $\lVert . \rVert$ is the usual norm-2, balls are circles; if it is the norm-1, balls are squares.}}

\begin{lem}\label{lemma-tiles}
For any $y \in \mathcal X$ and a set  $\mathcal A \subset \mathbb R^p$ it holds:
\begin{equation}
\label{e:tiles}
\int_{\mathcal A}C(x,y){\rm\,d} x \ge \int_{\mathcal B(y,|\mathcal A|)} C(x,y) {\rm\,d} x.
\end{equation}
\end{lem}
The lemma provides the intuitive result that, among all sets $\mathcal A$ with a given volume, the approximation cost for requests falling in $\mathcal A$ is minimized when $\mathcal A$ is a ball centered in $y$,
since $C(x,y)=\min(C_a(x,y),C_r)=\min(h(\lVert x-y\rVert),C_r)$ is a non-decreasing function of the distance between $x$ and $y$. We omit the simple proof.

Observe that the integral on the right hand size of~\eqref{e:tiles} does not depend on $y$ but only on the volume $|\mathcal A|$, {\color{black} because $C(x,y)$ depends only on the distance $\lVert x- y \rVert$}. We then write  $F(|\mathcal A|) \triangleq \int_{\mathcal B(y,|\mathcal A|)} C(x,y) {\rm\,d} x$. We are now able to express the following bound for the expected cost:
\begin{thm}
\label{t:lb}
In the continuous scenario with constant request rate $\lambda$ over $\mathcal X$, for any cache state $\mathcal S$,
\begin{equation}
\label{e:thm_lb}
\EuScript C(\mathcal S) \ge \lambda k F\left(\frac{|\mathcal X|}{k}\right).
\end{equation}
\end{thm}
\begin{proof}
Given $\mathcal S=\{y_1, y_2, \dots, y_k\}$, we denote by $\mathcal A_h$ the set of objects in $\mathcal X$ having $y_h$ as closest object in the cache, i.e., $\mathcal A_h = \{x \in \mathcal X \mid y_h \in \argmin d(x,\mathcal S) \}$.  The family $\{\mathcal A_1, \mathcal A_2, \dots, \mathcal A_k\}$ is a Voronoi tessellation of $\mathcal X$.
We have:
 \begin{align*}
\EuScript C(\mathcal S) &=  \lambda   \int_{ \mathcal \mathcal X} C(x,\mathcal S) {\rm\,d} x = \lambda  \sum_{h=1}^k \int_{ \mathcal A_h } C(x,y_h){\rm\,d} x\\
& \ge  \lambda  \sum_{h=1}^k \int_{\mathcal B(y_h, |\mathcal A_h|) } C(x,y_h) \mathrm{d}x = \lambda \sum_{h=1}^k F\left(|\mathcal A_h |\right) \\
& \ge \lambda k F\left(\frac{\sum_{h=1}^k |\mathcal A_h|}{k} \right) = \lambda k F\left(\frac{|\mathcal X|}{k}\right),
\end{align*}
where the first inequality follows from Lemma~\ref{lemma-tiles}, and the second one from Jensen's inequality, since $F(\cdot)$ is a convex function \textcolor{black}{(see Appendix~\ref{a:convexity})}.
\end{proof}
In some cases, it is possible to show that specific cache configurations achieve the lower bound in~\eqref{e:thm_lb} and then are optimal:
\begin{cor}
\label{cor1}
Let $\bar d$ be the distance for which the approximation cost is equal to the retrieval cost, i.e.,~$\bar d=\inf \{d: h(d)=C_r\}$. Let $\mathcal B_{\bar d}(x)$ be a ball of radius $\bar d$ centered in $x$. Any cache state $\mathcal S=\{y_1, \dots y_k\}$, such that the  balls $\mathcal B_{\bar d}(y_h)$ are contained in $\mathcal X$ and have intersections with null volume, is optimal.
\end{cor}

\begin{cor}\label{cor2}
Any cache state $\mathcal S=\{y_1, \dots, y_k\}$, such that, for some $d$, the balls $\mathcal B_{d}(y_h)$ for $h=1,\dots, k$ are a tessellation of $\mathcal X$ (i.e.,~$\cup_h \mathcal B_d(y_h)=\mathcal X$ and $|\mathcal B_d(y_i)\cap \mathcal B_d(y_j)|=0$ for each $i$ and $j$),  is optimal.
\end{cor}

If the request rate is not space-homogeneous, one can apply the results above over small regions $\mathcal X_i$ of $\mathcal X$ where $\lambda_x$ can be approximated by a constant value $\lambda_{\mathcal X_i}$, assuming a given number $k_i$ of cache slots is devoted to each area (with the constraint that $\sum_i k_i =k$). In the regime of large cache size $k$, it is possible to determine how $k_i$ should scale with the local request  rate $\lambda_{\mathcal X_i}$, obtaining an approximation of the minimum achievable cost through Theorem~\ref{t:lb}.

For example, consider the case when \textcolor{black}{the domain $\mathcal X$ lies in the plane ($\mathcal X \subset \mathbb R^2$), $C_r = \infty$, and $C_a(x,y)=\lVert x-y\rVert_1^\gamma$. We partition the domain into $M$ disjoint regions of unitary area, on which the
request rate  can be approximately assumed to be constant and equal to $\lambda_i$, $1 \leq i \leq M$. Let $k_i \geq 0$ be the number of cache slots devoted to region $i$, and $\bm k$ the vector storing $k_i$ values. Then each cache slot is used to approximate requests falling in a diamond of area $1/k_i$ and radius  $r_i = \sqrt{1/(2 k_i)}$, within region $i$ (we ignore border effects, supposing $r_i\ll 1$). The
approximation cost $c_i$ for each cell belonging to region $i$ is the same, as approximation costs are invariant to translation. Without lack of generality, we can then consider a cell centred in $y=0$. The approximation cost can be easily computed as:
\begin{align*}
c_i(r_i) & = \int_{{\mathcal B}_{r_i}\!(0)}\norm{x - 0}^\gamma {\rm\,d} x \\
	&= 4 \int_{0}^{r_i}\int_{0}^{r_i-x_1} (x_1+x_2)^\gamma {\rm\,d} x_2 {\rm\,d} x_1 = 4 \frac{r_i^{\gamma+2}}{\gamma+2},
\end{align*}
Expressing $c(r_i)$ as function of  $k_i$, we obtain:}
$$c_i(k_i) = \zeta k_i^{-\frac{\gamma+2}{2}}, $$
where $\zeta \triangleq 2^{(2-\gamma)/2}/(\gamma+2)$.
Hence the total approximation cost in the whole domain is $\EuScript C(\bm k) = \sum_{i=1}^{M} k_i \lambda_i c_i(k_i)$.

We select the values $\bm k$ that minimize the expected cost:
\begin{equation}\label{eq:opt1}
\begin{aligned}
& \underset{k_1, \dots, k_M}{\text{minimize}} & & \zeta \sum_{i=1}^{M} \lambda_i k_i^{-\gamma/2} \\
& \text{subject to} & & \sum_{i=1}^{M} k_i = k
\end{aligned}
\end{equation}

Employing the standard Lagrange method, we obtain that $\lambda_i k_i^{-(\gamma+2)/2}$ equals some unique constant for any region $i$, which means
that $k_i$ has to be proportional to $\lambda_i^{2/(\gamma+2)}$.
In the limit of large M, we substitute the sums in \equaref{opt1} with continuous integrals, obtaining:
\begin{equation}\label{eq:approx}
\min \EuScript C({\bm k}) \approx \zeta k^{-\gamma/2} \left(\int_{\mathcal X} \lambda(x)^{\frac{2}{\gamma+2}} {\rm\,d} x \right)^{\frac{\gamma+2}{2}}.
\end{equation}

The case when $C_r$ is finite is slightly more complex and it is studied in Appendix~\ref{a:approx}.

\begin{figure}
\centering
\includegraphics[scale=0.375]{grid2.png}
\caption{Example of perfect tessellation of a square grid with wrap-around conditions, in the case $l = 2$, $L = 13$. Black dots correspond to a minimum cost cache configuration under homogenous popularities.}
\label{f:grid}
\end{figure}

\section{Experiments}\label{s:simulations}
To evaluate the performance of different caching policies,
we have run extensive Monte-Carlo simulations in the following reference scenario:
a bidimensional $L \times L$ square grid of points, with unitary step and wrap-around conditions,
and $C_a(x,y) = \norm{x-y}_1$, i.e.,~the approximation cost equals the minimum number of hops between $x$ and $y$.
This is a finite scenario (with catalog size equal to $L^2$) that approximates the continuous scenario
in which $\mathcal X$ is a square.
We let $k = L = 1+2l(l+1)$, for some positive integer $l$. When $L=1+2l(l+1)$, there exists a regular tessellation of the grid with $L$ balls (squares in this case), each with $L$ points. Figure~\ref{f:grid} provides an example of such regular tessellation in the case  $l = 2$, $L = 13$.  When $k=L$, we can apply (the discrete versions of) Corollary~\ref{cor2} and approximation~\eqref{eq:approx} to compute the minimum cost.

We first consider traffic synthetically generated according to the IRM, in two cases:
{\em homogeneous}, in which all objects are requested with the same rate;
{\em Gaussian}, in which the request rate of object $i$
is proportional to $\exp(-d_i^2/(2 \sigma^2))$, where $d_i$ is the hop distance from the grid center. Under homogeneous traffic, Corollary~\ref{cor2} guarantees that a cache configuration storing the centers of the balls of any tessellation like the one in Fig.~\ref{f:grid} is optimal. The case of homogeneous popularities then tests the ability of similarity caching policies to converge to one of the $L$  optimal configurations (corresponding to translated tessellations). The case of Gaussian popularities, instead, tests their ability to reach a heterogeneous configuration richer of stored objects close to the center of the grid.

We consider the case $l = 12$, $L = 313$, with catalog size slightly less than $10^5$ objects. We set  $C_r = 1000 > 2L= \max_{x,y} C_a(x,y)$, i.e.,~a  setting very far from exact caching, where any request can in principle be approximated by any object.
For a fair comparison, all algorithms start from the same initial state, corresponding to
a set of (distinct) objects drawn uniformly at random from the catalog.
For the \textproc{Duel}{} policy, we experimentally found that, in the general case of grids with unitary step,
a good and robust way to set its various parameters
is $\beta = 3/4$, $\delta = f \cdot \min_{x\neq y} C_a(x,y)$, $\tau = f L/\lambda$, which requires to choose a single {parameter~$f$.}

\begin{figure}
\centering
\includegraphics[scale=0.38]{uniform_color.png}
\caption{Performance of different policies in the case of {\em homogeneous} traffic.}
\label{f:uniform}
\end{figure}

\begin{figure}
\centering
\includegraphics[scale=0.38]{gaussian_color.png}
\caption{Performance of different policies in the case of {\em Gaussian} traffic, with $\sigma = L/8$.}
\label{f:gaussian}
\end{figure}

Figures \ref{f:uniform} and~\ref{f:gaussian} show
the instantaneous cost \eqref{eq:conditionalcost} achieved by different policies
 as function of the number of arrived requests, respectively for homogeneous and Gaussian traffic (with $\sigma = L/8$). The optimal cost (approximated by~\eqref{eq:approx}, and also exactly computed thanks to Corollary~\ref{cor2} in the homogeneous case)  is also reported as reference.
In both cases, as expected, \textproc{Greedy}{} outperforms all $\lambda$-unaware policies and reaches an almost optimal cache configuration after a number of  arrivals of the order of the catalog size.
For \textproc{$q$LRU-$\Delta C$}, \textproc{RND-LRU}, and  \textproc{Duel}, we show two curves for different settings of their parameter (either $q$ or $f$),  leading to a faster convergence to more costly states (thin dotted curves), or a slower one to less costly states
(thick dash-dotted curves). As we mentioned in Sect.~\ref{s:lambda_unaware}, \textproc{$q$LRU-$\Delta C$}{} and \textproc{RND-LRU}{} are close (provided that we match their miss probability), and indeed they
exhibit very similar performance, with a slight advantage of~\textproc{$q$LRU-$\Delta C$}{} for small values of $q$ (remember that the local optimality in Theorem~\ref{t:qlru_opt} holds for vanishing $q$).
\textproc{Duel}{} achieves the best accuracy-responsiveness trade-off, i.e., for a given quality (cost) of the final configuration, it achieves it faster than the other $\lambda$-aware policies.
Figure \ref{f:final} shows the cache configuration achieved by \textproc{Duel}{} after $10^8$ arrivals, for both
types of traffic.

\begin{figure}
\centering
\begin{minipage}{.23\textwidth}
  \centering
  \includegraphics[scale=0.16]{finalduel_uniform.pdf}

\end{minipage}%
\begin{minipage}{.23\textwidth}
  \centering
  \includegraphics[scale=0.16]{finalduel_gaussian.pdf}

\end{minipage}
\caption{Final configuration produced by the \textproc{Duel}{} policy under
{\em homogeneous} traffic (left plot, with $f=300$), and {\em Gaussian} traffic (right plot, with $f = 100$).} \label{f:final}
\end{figure}

We have also evaluated the performance of the different policies using a real content request trace collected over 5 days from Akamai content delivery network.
The trace contains  roughly 418 million requests for about 13 million objects (more details about the trace are in~\cite{neglia17tompecs}).
By discarding the 116 least popular  objects (all requested only once) from the original trace,  we obtain a slightly reduced catalog that can be mapped to a square grid with $L = 3643$. We tested two extremely different ways to carry out the mapping.
In the {\em uniform} mapping, trace objects are mapped to the grid points according to a random permutation: popularities of close objects on the grid are, then,  uncorrelated.
In the {\em spiral} mapping, trace objects are ordered from the most popular
to the least popular, and then mapped to the grid points along an expanding spiral starting from the center: popularities  of
close-by objects are now strongly correlated, similarly to what happens under synthetic {\em Gaussian} popularities.

Figure \ref{f:trace} shows the accumulated cost achieved by different policies
as  function of the number of arrived requests, for both mappings.
For the \textproc{$q$LRU-$\Delta C$}{} and \textproc{Duel}{} policies, we performed a rough optimization of
their (unique) parameter (i.e., either $q$ or $f$), limiting ourselves to optimize the first significant digit.\footnote{This means that,
for example, \textproc{$q$LRU-$\Delta C$}{} with $q = 0.2$ achieves, at the end of trace, an accumulated cost
smaller than that achieved using either $q = 0.1$ or $q = 0.3$.}

To better appreciate the possible gains achievable by similarity caching, we have also added
the curves produced by a cache whose state evolves according to two exact caching policies: \textproc{LRU}{} and \textproc{Random}~\cite{garetto16}.
Since these policies produce a disproportionate number of misses,
their total aggregate cost~\eqref{e:avg_cost} is at least one order of magnitude larger than that~\textproc{$q$LRU-$\Delta C$}{} and~\textproc{Duel}. For a fair comparison, we only plot the aggregate approximation cost $\sum_t C_a(r_t,\mathcal S_t)$. Although retrieval costs incurred are ignored, \textproc{LRU}{} and \textproc{Random}{} still perform between 30\% and 50\% worse than~\textproc{Duel}.

The figure also shows the performance of  \textproc{Greedy}{}, using as $\lambda_x$ the empirical popularity distribution measured on the entire trace.
Interestingly, under non stationary, realistic traffic conditions, \textproc{Greedy}{} no longer outperforms $\lambda$-unaware policies.
In particular, \textproc{Duel}{} takes the lead under both mappings, due to its ability to dynamically adapt to shifts in contents' popularity.
{\color{black}To quantify the extent of popularity variation throughout the trace, we
separately computed the popularity distributions within the first and the second half of the trace,
and used Kendall's tau measure,\footnote{\textcolor{black}{We adopt the \lq\lq tau-b" version of this measure as defined in \cite{tau1945},
which accounts for ties. Values close to 1 indicate strong agreement, values close to -1 indicate strong disagreement.}}
as implemented in the \textsf{scipy} library \cite{scipytau},
to compare the objects' rankings in the first and second half of the trace,
obtaining the value $0.079$, which is an indication of strong popularity variation along the trace.}

\begin{figure}
\centering
\begin{minipage}{.23\textwidth}
  \centering
  \includegraphics[scale=0.385]{random.png}

\end{minipage}%
\begin{minipage}{.23\textwidth}
  \centering
  \includegraphics[scale=0.385]{spiral.png}

\end{minipage}
\caption{Performance of different policies under Akamai trace:
{\em uniform} mapping (left plot) and {\em spiral} mapping (right plot).} \label{f:trace}
\end{figure}

{\color{black} At last, we tested our policies on an Amazon trace.
In \cite{McAuley_amazon} the authors provide an image dataset
for millions of items sold by Amazon, and use a neural network to embed such images into a $d$-dimensional ``style'' space.
\emph{``The notion of style is learned by training the model on pairs of objects which Amazon considers to be related''}~\cite{McAuley_amazon} as multiple users purchased or viewed both objects. Style dissimilarity is captured  by the Euclidean distance and close objects in the style space can be recommended to the customers.
When a user is interested in a product, Amazon can check over the whole database which other products have a similar style. A similarity cache can be used to speed-up such search, similarly to what proposed for contextual advertising systems in \cite{pandey09}.
We consider $d=100$ and build a request trace from the timestamped reviews left by users for the 10000
most popular items belonging to the  category ``baby.''
The resulting trace, containing about 740K requests, is fed into a
cache of size $100$, and  Euclidean distance is used as approximation cost (because it captures items' dissimilarity).
Figure \ref{f:trace} shows the accumulated cost achieved by different policies
as function of the number of arrived requests.
We observe that \textproc{Duel}{} performs almost the same as \textproc{Greedy}, which suggests that the considered
trace does not contain significant popularity variations over time.
Actually, Kendall's tau measure of objects' ranking agreement between the two halves of the trace
is 0.452, significantly larger than the value obtained for the Akamai trace.}

\begin{figure}
\centering
\includegraphics[scale=0.38]{amazon.png}
\caption{\textcolor{black}{Performance of different policies under Amazon trace.}}
\label{f:amazon}
\end{figure}

\section{Model extensions}
Consider a request $r_t$ that generates the retrieval of object~$o$ from the server with consequent cost $C_r$.
Until now, we have assumed that 1) the retrieved object can only be the requested one ($o=r_t$), 2) the cache is not obliged to store the retrieved object $o$ after serving it to the user, and 3) in any case the cache serves to the user a content $o'$ such that $C_a(r_t,o')\le C_r$ (this is actually a consequence of 1)~and 2)~as we discussed in~Sect.~\ref{s:model}).

But it may also be meaningful to distinguish a cost paid by the user ($C_r^u$) and a cost paid by the network ($C_r^n$). The first one may capture the additional delay the user experiences to retrieve the content, the second one the additional network traffic or server load.
We may want to serve a content $o'$ to the user only if $C_a(r_t,o') \le C_r^u$.
Moreover, we may allow the cache to retrieve an approximation of $r_t$. Finally, many caching policies require the retrieved object to be stored locally.

We have then $8$ different possible cases, depending if
\begin{itemize}
	\item the cache is required to retrieve $r_t$, or not,
	\item the cache is required to store $o$, or not,
	\item the cache is allowed to serve a content $o'$ to the user only if $C_a(r_t,o') \le C_r^u$, or not.
\end{itemize}

Interestingly, all these cases can be captured by our model. In particular, $C_a(x,y)$ can be defined to be infinite any time the approximation cost exceeds $C_r^u$. Moreover, we can capture the choice about storing or not the retrieved object $o$ through the constant
\[\chi \triangleq
	\begin{cases}
		+\infty & \text{if the cache is required to store $o$,}\\
		C_r^u + C_r^n & \text{otherwise.}
	\end{cases}
\]
The system can always be modeled as an MTS where the total cost can be expressed as sum of movement costs ($C_m(\mathcal S_t,\mathcal S_{t+1})$) to change from one state to another and service costs ($C(r_t,\mathcal S_{t+1})$).  The movement cost has the same expression as in~\eqref{e:movement_cost} with $C_r$ replaced by $C_r^u+C_r^n$.
 The service cost needs now to be defined as
\begin{equation}
\label{e:service_cost2}
C(r,\mathcal S) \triangleq \min(C_a(r,\mathcal S),\chi).
\end{equation}

Results for the offline and stochastic scenarios, respectively in Sect.~\ref{s:offline} and~Sect.~\ref{s:stochastic}, hold also for these model variants. The adversarial scenario requires more discussion. Our system is not a $k$-server with excursions if the cache can retrieve an object different from the requested one (this would correspond to a server both moving to a new state and performing an excursion). In the other cases, excursion costs can be defined as
\[C_e(x,y) \triangleq \min(C_a(x,y),\chi).\]
Theorems~\ref{t:small_catalogue} and~\ref{t:uniform_space} hold if we replace $C_r$ by $C_r^u+C_r^n$ and add the additional requirement that $\alpha_u\le 2$ and $\alpha \le 2$, respectively.

\section{Conclusion and future work}
The analysis  provided in this paper  constitutes a first step toward the  understanding of similarity caching,
however it is far from being exhaustive.
In the offline dynamic setting, it is unknown if and under which conditions  there exists an efficient polynomial clairvoyant policy corresponding to B\'el\'ady's one~\cite{belady66} for exact caching. The adversarial setting calls for more general results for the $k$-server problem with excursions. For exact caching, the characteristic time approximation is rigorously justified under an opportune scaling of cache and catalogue sizes~\cite{fagin77,fricker12,jiang18}. It would be interesting to understand if and to what extent analogue results hold for similarity caching. Moreover, is it possible to use the CTA to compute the expected cost of a similarity caching policy, similarly to what can be  done for the miss ratio of \textproc{LRU}, \textproc{$q$LRU}, \textproc{Random}, and other policies in the classic setting?
There is surely still room for the design of efficient $\lambda$-unaware policies. Interestingly, in our experiments the smallest cost is achieved by \textproc{Duel}, a novel policy
that completely differs
from exact caching policies, suggesting that similarity caching may require to depart from traditional approaches. Another interesting direction would be to consider networks of similarity caches.
At last, the above issues should be specified in the context of the different application domains mentioned  in the introduction, ranging from
multimedia retrieval to recommender systems, from sequence learning tasks to low-latency serving of machine learning predictions.
The design of computationally efficient algorithms can, indeed, strongly depend on the specific application context.
In conclusion, our initial theoretical study and performance evaluation of similarity caching
opens many interesting directions and brings new challenges into the caching arena.

\bibliographystyle{unsrt}

redpajama_set_name: RedPajamaArXiv


text:
Q: PHP XML child parsing issue This is driving me nuts.  In my XML file, I have nested children of the same name <entry> and I am trying to get the top level only.  If I call getElementsByTagName() it grabs all of them, so I am parsing for direct children and nothing seems to be working correctly.
<locations>
  <devices>
    <entry>

      <c>
        <entry>
        ..
        </entry>
      </c>
    </entry>
    <entry>

      <c>
        <entry>
        ..
        </entry>
      </c>
    </entry>
  </devices>
</locations>

<?
$path = "Export.txt" ;
$xml = file_get_contents( $path );
$dom = new DOMDocument( '1.0', 'utf-8' );
$dom->preserveWhiteSpace = false;
$dom->formatOutput = true;

// use it as a source
$dom->loadXML($xml) ;

// grab all "devices" should ONLY be 1 device
$devices = $dom->getElementsByTagName('devices');

$entries = array() ;
// parse through each FIRST child...which should be the first level <entry>
// however, the below is empty.
for ($i = 0; $i < $devices->childNodes->length; ++$i) {
    echo $count++ ;
    $entries[] = $devices->childNodes->item($i);
}

// but I get the following error on this foreach:
// Warning: Invalid argument supplied for foreach() in process.php
foreach ($devices->childNodes as $node) {
    echo "This: " . $count++ ;
}

// this prints "1": which is correct.
echo sizeof($devices) ;

//extra question concerning extracting getElementsByTag from a childNode
foreach ($devices as $device) {
  foreach($device->childNodes as $child) { // this should be each parent <entry>
    $thisC = $child->getElementsByTagName('c') ;  // this should be only <c> tags BUT THIS NEVER SEEMS TO WORK
    foreach ($thisC->childNodes as $subEntry) {
      echo $subEntry->nodeValue ;
    }
  }
}

A: You can use an XPath query to get the relevant elements:
<?php
$dom = new DomDocument("1.0", "utf-8");
$dom->loadXML(file_get_contents("export.txt"));
$xpath = new DomXPath($dom);
$entries = $xpath->query("/locations/devices/entry");
$count = 0;
// $entries is a DomNodeList
var_dump($entries);
foreach ($entries as $entry) {
    //do stuff with $entry
}

Or, to use your original approach:
<?php
$dom = new DomDocument("1.0", "utf-8");
$dom->loadXML(file_get_contents("export.txt"));
$devices = $dom->getElementsByTagName('devices');
$entries = [];
foreach ($devices as $device) {
    foreach ($device->childNodes as $child) {
        if ($child instanceof DomElement && $child->tagName === "entry") {
            $entries[] = $child;
        }
    }
}
// $entries is an array of DomElement
var_dump($entries);
foreach ($entries as $entry) {
    //do stuff with $entry
}

redpajama_set_name: RedPajamaStackExchange


Some Ramblings - Jai Chiranjeeva!
'Vijaya' Bapineedu (along with Paruchuri Brothers) stumbled upon the perfect combination in "Gang Leader" that every typical telugu movie pines for - a hearty blend of romance, action, sentiment and loads of entertainment. Though all the telugu movies set out for finding this Holy Grail of concoctions, which entails a perfect combination of all the entertaining, heart-tugging, hair-raising and other engaging qualities, 1 in a million is blessed with stumbling upon one. The problem is not with finding the magic number - the ratio of action to sentiment, sentiment to romance and romance to entertainment. The problem lies with the formula itself. It is a mine field and a lot has to do with the segues in the script - the entry points of each scene that would ensure the transition from the previous scene seem as seamless as possible. For example, in Gang Leader, Chiru's grandmother chides him for cavorting with his "gaali gang" at the dinner table in a hilarious setup that oozes of natural comedy with no artificiality or forced humor. The scene gives way for the gang teasing a girl, ending up in a club to transition into the first song. Right after the song, the gang would be walking back to their quarters, gets stopped by the police on their beat, and an action episode follows. Paruchuri Brothers could not have penned the flow of the scenes any better. Right after the action episode, the villan is introduced and the movie moves along full steam. There were many Chiru movies after Gang Leader that went on to become bigger hits, but in terms of pure cinematic entertainment that highlighted all the talents (not some, but all) of Chiranjeevi, none came close to Gang Leader, and a lot of it has to be attributed to the near perfect screenplay that embedded the magic number (the perfect ratios) which balanced every commercial aspect of a telugu movie in an excellent way.
The second aspect that would stand out in Gang Leader was the perfect tone that Bapineedu found to run the movie on. The build up of the hero character is gradual and natural, from a loafing one at the beginning of the movie who wants no part in sharing the responsibility and the day-to-day running of the family to a seemingly dutiful and serious character who shoulders the entire burden of the family affairs mid-way till the end of the movie. And once the character turns serious, it does not go back being a frivolous one and the script does not confuse between these two tones and does not try to constantly switch between them, however enticing the opportunity might be. This is exactly where Jai Chiranjeeva falters big time. It doesn't know what kind of movie it wants to be and ends up trying to be everything in parts. As mentioned before, the problem is not with the ratios, the problem is the formula itself. If the script tries to achieve everything, more often than not, commerciality ensures that it ends up with neither. Though it is quite lucrative for the producer to tout his movie as one that has ALL the elements to attract all the sections of the movie-going audience, the chances that he finds himself the perfect script that balances all those elements are slim to none. From a producer's view point, he is better off taking a chance with one that strays away from the normal, because the odds for such kind to click with the audience is far greater than sticking with the same old and trying his luck with the oft-repeated themes and well-beaten track. After all it is business, as commercial producers keep reminding rebutting arguments about lack of realism and variety, and better business calls for calculating the odds properly.
Coming back to script, Vijaya Bhaskar seems to be more at fault than Trivikram in finding the right tone for such a script that widely swung from one end to the end. Once the director identifies the graph of the lead character (since almost all the telugu movie center around the lead character), he can adjust the sequences around it making sure that the other characters are not flying off tangentially to the lead character. If one observes Trivikram's scripts (not the ones he directed) till date (including Manamadhudu to some extent), it becomes fairly obvious that he places his characters in familiar setups - a middle class environment, where the hero is rooted in the real world and interacts with the situations around him in a fairly realistic way. Malliswari was the first digression from this path and he sticks with the same mould with Jai Chiranjeeva too. Both these movies fail miserably at identifying the kind of movie they want to be in the first place. It would be certainly interesting to trace the origins of the script to the story discussions. 1. The aim of the script is to show Chiranjeevi in a soft light as a next door middle class man, different from all his recent previous ventures. 2. The aim of the script is to balance the softness of his character with an angry past, that would only be revealed in flashes 3. The aim of the script is to find a romantic angle in between these two extremes and do a balacing act of all these elements. It is here that Paruchuri Brothers' script seems very relevant, in terms of finding a place for all the moods and yet remaining true to the tone of the movie. What Vijaya Bhaskar does (or does not do) is plainly translate the script completely misreading how the scenes would eventually play out, rendering them as flat, episodic and dull. If the script does not offer the required firepower, it becomes the responsibility of the director to at least play with the tone of the movie, either making it an over the top fare (Ex: Hello Brother) or having it respect at least the rules of reality. There is more to the job than have a Screenplay credit to the name.
The script would have been a lot more interesting, if the softness of the lead character has played out till the end, than shifting back and forth constantly between a macho one in one instant and a meek one in another. Add to that the unnecessary baggage in the form of arms dealing villain who quotes scriptures on the side, his running for the mayoral post aspect (for the sole purpose of hanging his banner on a sky scraper for the hero to identify his location to perform a borrowed stunt) and the even more ridiculous way of his killing of hero's niece, pulls the entire movie down. If the aim was to show Chiranjeevi as an every day common man (which the script and Chiranjeevi's portrayal do justice to some extent), a better alternative would have been to not go for a globe-trotting outlandish villain, whereupon there is no other way but to have the hero's character rise to those same proportions, to match the ridiculousness. And to make up for reasons to counter such a villain, logic, reasoning and many times, mere common sense, all of which have been trademarks to Trivikram's script, fall prey. At the end of it all, it all comes down to the one important questions - Why. Why have those laughable choices been made by Trivikram? When a script tries to add up to the numbers (a sentiment scene followed by a romantic interlude leading to a song, handing off to a emotional scene with an optional fight sequence and the like) by merely having one scene after another, without caring about how the emotions hand off from one scene to the next, the result is just a flat movement of the 24 frames per second, devoid of the any emotional quotient or any gripping content. What a loss of a golden opportunity!


Can't decide on which Scent-sation Aroma Therapy Shower Tab fragrance to choose....Chose 3 in this smaller sampler pack. We have grouped together 2 variety packs with our 3 most popular fragrances, Sinus, Awake & Calming or Sinus, Energize & Refresh. then added a 3 pack in each fragrance.


During a cruise vacation to France, Villefranche-sur-Mer is often on the program. This small town is wonderfully located along the Western Mediterranean and you would never expect it as a major cruise port. Its central location means you can make different excursions along the French Riviera. Therefore, cruises to Villefranche-sur-Mer are very popular.
The port and town of Villefranche-sur-Mer are small. Therefore, cruise ships cannot moor. Your cruise ship will drop anchor in the bay and you will come ashore by tender boat. The tender boats dock at Port de la Santé in the center of Villefranche-sur-Mer, close to most sights. The location of the port is ideal for an excursion along the Cote d'Azur to places such as Nice, Cannes or Monaco. Because of its convenient location, Villefranche-sur-Mer has become a major cruise port in the Mediterranean.
The citadel dates from 1557 and is now used as town hall, convention center, museum and summer theater.


text:
SHEIKH HASINA'S INDIA SOJOURN: TAKING STOCK OF INDIA AND BANGLADESH RELATION
Author: SMRUTI S PATTNAIK, September 26, 2022
India Bangladesh relations have emerged as a role model of the bilateral relationship in the context of India's relations with its neighbours. There exist differences between the two on many issues of mutual concern, which is natural between any neighbouring countries, yet, both have taken a conscious decision to move forward on issues that would turn around the economies of the two countries. Not surprisingly, infrastructure, trade and people-to-people contact have received priority. The two countries are working on resolving the long-standing Teesta river water sharing.
"BIOTERRORISM": The Palgrave Encyclopedia of Global Security Studies
Author: ANIMESH ROUL, September 15, 2021
The threat of the intentional or deliberate use of disease pathogens or biological agents emanating from both rogue state actors and violent non-state actors (NSAs) remains a major concern for national and international security. By violent non-state actors, we generally mean armed insurgent groups, criminal syndicates, apocalyptic religious cults and jihadi terrorist groups and individuals.
Comments on ISRO's Draft National Space Transportation Policy-2020
Author: AJEY LELE , July 12, 2021
Indian Space Research Organisation (ISRO) has presented a Draft National Space Transportation Policy-2020 in the public domain for comments. This issue brief is a humble attempt toward that effect. It identifies why ISRO has come out (timing) with this policy and offers some observations on this draft policy.
Orienting Technologies to Exploit Minorities: From Genocide to Human Rights Violations
Author: SAURABH SINGH, June 14, 2021
The world is witnessing a massive technological expansion. The advancement is such that we have entered into a phase where separating technologies from our lives is nearly impossible. These technologies are now programmed in such a manner that it can easily modify and change the behavioural pattern of individuals by greatly influencing their understanding, thinking and decision-making ability over a short period of time. Technology was created for the advancement of the human race, but every coin has two sides. It was created by humans who have motifs.
Firm on Modernisation: India's Defence Budget 2021-22
Author: LAXMAN KUMAR BEHERA, February 10, 2021
India- Bangladesh Relations: Bridging the Gap while Marching Forward
Author: Smruti S Pattanaik, September 11, 2020
Abstract: India's relations with Bangladesh have perhaps been more scrutinised in recent times. The bilateral ties are weighed mostly in terms of an imaginary competition between India and China, especially whether India is losing out to China has remained a major debating point for the political and social elites in both countries.
Rohingya Crisis: The Political and Humanitarian Discourse
Author: PRETY PRIYA, August 14, 2020
This paper seeks to analyse the current situation of Rohingya refugees and the threat to their security in the ongoing pandemic situation. It also aims to answer some important questions such as whether they are struggling to access basic necessities and if they are being forced to convert their religion to protect themselves.
Coronavirus as God's Soldier: Assessing the Divine Retribution Narrative of Jihadi Organisations
Author: ANIMESH ROUL, August 01, 2020
The SARS-CoV-2 (Coronavirus) that causes COVID-19 has engulfed the whole world within weeks of its outbreak in the Chinese city of Wuhan in late December 2019. Within six months of its advent, over 8.24 million people have been infected with over four lakh deaths (as of mid-June 2020) and an ongoing major global disruption. The deadly Coronavirus pandemic has occupied centre stage in the international security discourse at present. Amid this unprecedented global crisis and healthcare chaos, evil intentions of ever opportunistic Islamist jihadi forces have come to light.
"BUBONIC PLAGUE": Pandemic Through History
The plague, otherwise notorious as the Black Death or the Pestilence, often regarded as a curse from God, has its place in every religious scripture. For Christians, it was divine punishment, for Muslims, a symbol of self-sacrifice (martyrdom). In the Hindu scripture (Bhagwat Purana), the plague was known as Mahamari, the "great death" which was caused by rats or rodents (Park 2000). Originated from a Greek word, plaga, meaning a blow or sudden strike, the Plague has a detailed description, including its clinical manifestations, in Thucydides' The History of the Peloponnesian War (Crawley 2013; Rao 1994).
Critical Connection: COVID-19 Pandemic and National Security
Author: RAJAT KUMAR KUJUR, May 11, 2020
Pandemics brings immense human suffering, disrupts the socio-economic fabrics of society and impedes development across the affected geographical region. As Novel Coronavirus or COVID-19 reaches over 200 countries infecting millions of people and killing scores of them, it is imperative to examine the threat not just from health or medical point of view but from a larger perspective of national security. It is important that the nations wake up to this reality and any failure to restrict and mitigate the challenge at this stage will have a long term impact on international peace, stability and security. The paper attempts to examine the emerging and re-emerging infectious diseases (ERIDs), and their enormous security challenges to national security which would remain a central theme of any future security discourse hereafter.

redpajama_set_name: RedPajamaCommonCrawl


text:
(513) 338-1952 En Español
EB-1 Priority Workers
EB-2 Professionals / Advanced Degrees
EB-3 Skilled Workers / Basic Degrees
EB-4 Special Immigrant Religious Workers
Marriage Visa – Adjustment of Status
Marriage Visa – Consular Processing
K-3 Visa
National Interest Waiver
L-1 Intracompany Transfer Visas
O-1 Extraordinary Ability Worker Visas
P-1 Artists and Athletes Visas
TN Visa for Canadian Citizens
Employer I-9 Compliance
9089 for Employees
9089 for Employers
G-325A
I-129 for Employees
I-129 for Employers
Neil Fleischer
US Supreme Court affirms the doctrine of Consular Non-Reviewability
June 15, 2015 by Neil Fleischer
The U.S. Supreme Court on Monday upheld the long-standing doctrine of consular non-reviewability by ruling that visa refusals cannot be subjected to court review. Furthermore, the Supreme Court held that the denial of a visa to a U.S. citizen's spouse does not impact the citizen's own constitutionally protected interest.
The well-established doctrine of consular non-reviewability precludes judicial review of the visa decisions of State Department consular officers. It is a very similar of immigration law's exceptional "plenary power" doctrine, which generally immunizes from judicial review the substantive immigration decisions of Congress and the executive branch.
In refusing to disturb the federal government's reliance on secret evidence to deny the non-citizen spouse of a U.S. citizen admission into the country, the Supreme Court in 1950 summarized the plenary power doctrine as follows: "[w]hatever the procedure authorized by Congress is, it is due process as far as an alien denied entry is concerned."
According to the Department of Homeland Security (DHS) statistical yearbook, more than 200,000 noncitizens immigrate every year through a marriage to a U.S. citizen. The U.S. Census Bureau reports that over 1.5 million couples residing in the United States are native-born U.S. citizens married to noncitizens; another 4.4 million couples are naturalized citizens and noncitizens. U.S. citizens may file visa petitions for their spouses. However, the approval of a spouse's visa petition does not automatically confer the right to enter the United States. A visa must still be issued.
Here is a copy of the opinion:
http://www.supremecourt.gov/opinions/14pdf/13-1402_e29g.pdf
Categories Supreme court immigration rulings, UncategorizedTags consular nonreviwability, consular notice, supreme court, visa, visa denialLeave a comment
Supreme Court Rules for Due Process for Immigrants
The U.S. Supreme Court ruled Monday that an appeals court can review the Board of Immigration Appeals' refusal to toll a bid to reopen a removal case based on legal malpractice , siding with a both the U.S. government and a Mexican citizen whose former Attorney failed to timely file documents in a case.
The Supreme Court justices ruled Monday in favor of Noel Reyes Mata, a Mexican national who had lived in the United States years. The government began deportation proceedings after he pleaded guilty to an assault charge.
An immigration judge ordered him removed/ deported. He appealed, but his attorney missed the filing deadline ( 90 days) . A new attorney tried to reopen the case, but the Board of Immigration Appeals refused.
Mata appealed to the 5th Circuit U.S. Court of Appeals, but the court ruled it had no authority to order a deadline extension.
The Supreme Court said the court did have such authority.
http://www.supremecourt.gov/opinions/14pdf/14-185_i4
Categories UncategorizedTags due process, immigration, supreme courtLeave a comment
Thank you Jamesro Designs
Thank you, James for creating an awesome website. We could not be happier!! I highly recommend anyone who needs a website to contact James. Truly easy to work with, quick, efficient and receptive, James took our vision and created the site exactly how we wanted. Contact him at jamesro designs.
Categories UncategorizedTags webdesign, websiteLeave a comment
810 Sycamore Street, Floor 2
Cincinnati, Ohio, USA 45202-2179
© 2019 The Fleischer Law Firm LLC. All Rights Reserved


Universities of Benin and Calabar have qualified for the Quarter Final stage in the football category of the ongoing Nigerian Universities Game.
Other teams that also qualified for Quarter Final matches are – Niger Delta University; University of Nigeria, Nsuka; Obafemi Awolowo University, University of Calabar; Bayero University of Kano and University of Lagos.
UNIBEN qualified after defeating BUK, 2-0 and UNIJOS after beating, 2 – 0.
While OAU will battle with NDU; UNN and UNILAG will be playing against UNICAL and BUK on Thursday (today) respectively.
Winner between OAU and NDU will play against the winner between UNN and UNICAL also the victorious team between UNILAG and BUK will compete against either UNIBEN or UNIJOS in the Semi-final stage.
If UNILAG and UNIJOS defeat their opponents, it will be another tussle between the two teams who qualified from the same group. A win by UNILAG in their group stage was earlier protested by UNUIJOS.
In their group stages, OAU drew UNICAL, 1-1; while NDU lost to UNN with three goals to one.


I must admit I didn't get Cos when it first rocked up on London's Regent Street a decade ago. I took one look at rail after rail of shapeless-looking navy, black and grey pieces and wondered why all the fashion mags were so over-excited about the launch of H&M's supposedly cooler older sister brand. But but but. You gotta try it on and then it all makes sense.
They were the first to do that Scandi pared-down daytime look that everyone now copies, with the cuts, fabrics and attention to detail a notch above your average high street design. The everyday crew-cut T-shirts are the perfect fit, the grey and navy jumpers last forever (their waffle knits are especially good), their long cardigans make any jeans look brill and they know their way around a quirky white shirt. Plus, if you like black, you're definitely in luck. I'm also a big fan of their accessories – the leather handbags are chic and minimal and I have a pair of classic black suede court shoes that I bought the year Cos opened and still wear constantly.