This paper focuses on similarity caching systems, in which a user request for an object o that is not in the cache can be (partially) satisfied by a similar stored object o , at the cost of a loss of user utility. Similarity caching systems can be effectively employed in several application areas, like multimedia retrieval, recommender systems, genome study, and machine learning training/serving. However, despite their relevance, the behavior of such systems is far from being well understood. In this paper, we provide a first comprehensive analysis of similarity caching in the offline, adversarial, and stochastic settings. We show that similarity caching raises significant new challenges, for which we propose the first dynamic policies with some optimality guarantees. We evaluate the performance of our schemes under both synthetic and real request traces.

1 Similarity Caching: Theory and Algorithms Giovanni Neglia * , Michele Garetto † , Emilio Leonardi ‡

I. 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 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 object o. This situation goes under the name of similarity searching, proximity searching, or also metric searching [START_REF] Chávez | Searching in Metric Spaces[END_REF]. Similarity searching plays an important role in many application areas, like multimedia retrieval [START_REF] Falchi | A Metric Cache for Similarity Search[END_REF], recommender systems [START_REF] Pandey | Nearest-neighbor Caching for Content-match Applications[END_REF], [START_REF] Sermpezis | Soft Cache Hits: Improving Performance Through Recommendation and Delivery of Related Content[END_REF], genome study [START_REF] Auch | Standard operating procedure for calculating genome-to-genome distances based on high-scoring segment pairs[END_REF], machine learning training [START_REF] Weston | Memory networks[END_REF], [START_REF] Graves | Neural Turing Machines[END_REF], [START_REF] Santoro | Meta-Learning with Memory-Augmented Neural Networks[END_REF], and serving [START_REF] Crankshaw | Scalable training and serving of personalized models[END_REF], [START_REF] Crankshaw | Clipper: A Low-Latency Online Prediction Serving System[END_REF]. 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 approximate one in comparison to the best possible answer the server could provide. Following the seminal papers [START_REF] Falchi | A Metric Cache for Similarity Search[END_REF], [START_REF] Pandey | Nearest-neighbor Caching for Content-match Applications[END_REF], we refer to this setting as similarity caching, and to the classic one as exact caching.

To the best of our knowledge, the first paper introducing the problem of caching for similarity searching was [START_REF] Falchi | A Metric Cache for Similarity Search[END_REF]. The authors considered how caches can improve the scalability of content-based image retrieval systems. Almost at the same time, [START_REF] Pandey | Nearest-neighbor Caching for Content-match Applications[END_REF] studied caches in content-match systems for contextual advertisement. Both papers propose some simple modifications to the least recently used policy (LRU) to account for the possibility of providing approximate answers. More recently, in [START_REF] Weston | Memory networks[END_REF] and [START_REF] Graves | Neural Turing Machines[END_REF], 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 [START_REF] Santoro | Meta-Learning with Memory-Augmented Neural Networks[END_REF]. Clipper [START_REF] Crankshaw | Clipper: A Low-Latency Online Prediction Serving System[END_REF]-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 [START_REF] Crankshaw | Scalable training and serving of personalized models[END_REF]. Recently, [START_REF] Sermpezis | Soft Cache Hits: Improving Performance Through Recommendation and Delivery of Related Content[END_REF] 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 [START_REF] Chierichetti | Similarity Caching[END_REF] (details in Sect. IV). 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 [START_REF] Falchi | A Metric Cache for Similarity Search[END_REF], [START_REF] Pandey | Nearest-neighbor Caching for Content-match Applications[END_REF]? This paper provides the first answers to the above questions. Our contributions are the following:

1) we show that similarity caching gives rise to NP-hard problems even when exact caching lends itself to simple polynomial algorithms; 2) we provide an optimal pseudo-polynomial algorithm when the sequence of future requests is known; 3) we recognize that, in the adversarial setting, similarity caching is a k-server problem with excursions; 4) we propose optimal dynamic policies, both when objects' popularities are known, and when they are unknown; 5) 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.

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 [START_REF] Crankshaw | Clipper: A Low-Latency Online Prediction Serving System[END_REF]. Note that in this case exact caching a norm in R p Cr cost to retrieve an object from the remote server Ca(x, y) cost to approximate x with y Ca(x, S) minimum cost to approximate x with the elements in S Cm(T , S) cost to move from cache state T to cache state S C(x, S) cost to serve request x from cache state S Ce(x, y) excursion cost to serve request x using (server) y C A (S 1 , r T ) time-average cost incurred by caching policy A to serve the request sequence r T starting from state S 1 C(S)

expected cost to serve a request from cache state S λx request rate for object x (finite case) or request rate density in x (continuous case) B(x, V ) ball in R p centered in x and with volume V Br(x) ball in R p centered in x and with radius r policies like 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 II introduces our main assumptions on request processes and caching policies. Sections III and IV present results on similarity caching respectively in the offline and in the adversarial setting. Our new dynamic policies are described in Sect. V, together with their optimality guarantees in the stochastic setting. We numerically explore the performance of our policies in Sect. VI.

II. MAIN ASSUMPTIONS

Let 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 S t currently stored in it, S t = {y 1 , y 2 , . . . y k }, with y i ∈ X .

We assume that, given any two objects x and y in 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 A of elements in X , let C a (x, A) denote the minimum approximation cost provided by elements in A, i.e.,

C a (x, A) = inf y∈A C a (x, y).
In what follows, we consider two main instances for X and C a (). In the first instance, X is a finite set of objects and thus the approximation cost can be characterized by an |X | × |X | matrix of non-negative values. This case could well describe the (dis)similarity of contents (e.g. videos) in a finite catalog. In the second instance, X is a compact subset of R p and C a (x, y) = h( x -y ), where h : R + → R + is a non-decreasing non-negative function and . is a norm in R p (e.g. the Euclidean one). This case is more suitable for describing objects characterized by continuous features. For example, in the field of distance metric learning [START_REF] Bellet | Metric learning[END_REF], supervised machine learning techniques are used to learn how to map similar objects to vectors in 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. VI. We will refer to the above two instances as finite and 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 X . We assume that the function C a : X × X → R + ∪ {+∞} 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∈St C a (x, y). This can be efficiently done using locality sensitive hashing (LSH) [START_REF] Pandey | Nearest-neighbor Caching for Content-match Applications[END_REF]. 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 ∈ S t ), then the cache directly provides r t incurring a null cost (C a (r t , S t ) = 0) and we have an exact hit. Otherwise, the cache can either i) provide the best approximating object locally stored, i.e., y ∈ arg min y∈St C a (x, y), incurring the approximation cost C a (r t , S t ) (approximate hit) or ii) retrieve the content from the server incurring a fixed cost C r > 0 (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 , S t ) ≤ 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) ≤ 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, i.e., the cost of updating the cache state from T to S, as follows:

C m (T , S)      0, if S = T , C r , if |S \ T | = 1, +∞, otherwise. (1)
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 r T = r 1 , r 2 , . . . , r T and an initial state S 1 , the average cost paid by a given caching policy A is

C A (S 1 , r T ) = 1 T T t=1 [C m (S t , S t+1 ) + C(r t , S t+1 )] , (2)
where

C(o, S) min(C a (o, S), C r ) (3)
and we call it the service cost. In fact, if S t+1 = S t , the cache has retrieved r t paying the retrieval cost C r = C m (S t , S t+1 ), but no approximation cost (C(r t , S t+1 ) = C a (r t , S t+1 ) = 0).

If S t+1 = S t , the cache has provided an approximate answer or has retrieved (but not stored) r t , paying C(r t , S t ) min(C r , C a (r t , S t )). Note that the average cost depends on the caching policy A, because the policy determines the evolution of the cache state S t . Policies differ in the choice of which requests are approximate hits or misses (even if C a (r t , S t ) ≤ 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) = ∞ for all x = y, we recover the exact caching setting. If, in addition, C r = 1, Eq. ( 2) provides the miss ratio. The cost structure (2), together with a movement cost like (1) that satisfies the triangle inequality, defines a metrical task system (MTS), first introduced by Borodin et al. [START_REF] Borodin | An Optimal On-line Algorithm for Metrical Task System[END_REF], which is usually studied through competitive analysis (more in Sect. IV).

As mentioned in the introduction, similarity caching lacks a solid theoretical understanding. From an algorithmic viewpoint, 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: 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élády's policy [START_REF] Bélády | A Study of Replacement Algorithms for a Virtual-storage Computer[END_REF], that evicts at each time the object whose next request is further in the future. 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 analysis, which determines how much worse an online policy (without knowledge of future requests) performs in comparison to the optimal offline policy. 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 (2) over an infinite time horizon. We separately consider the above three scenarios in the next sections.

III. OFFLINE OPTIMIZATION

In this section we consider the offline setting in which a finite sequence of requests 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).

A. 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 (2), i.e., we want to find:

S * ∈ arg min S1 T t=1 C(r t , 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:

Theorem III.1. The static offline similarity caching problem is NP-hard.

Proof. The result follows from a reduction of the dominating set problem. Consider an undirected graph G = (V, E) with set of nodes V and set of edges E. Given U ⊂ V we let

N [U ] = {U } ∪ {u ∈ V : ∃v ∈ U, (u, v) ∈ E}
|N [U ]|, (4)
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 X = V , C r = 1, and C a (x, y) = C a (y, x) = 0 if (x, y) ∈ E and C a (x, y) = C a (y, x) = +∞ otherwise. The request sequence r T contains one and only one request for each object.

Let S denote the set of objects in the cache and U ⊂ V the corresponding set of nodes in the graph G. Consider a request r for object v ∈ 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 \ N [U ]. Therefore finding the cache configuration S that minimizes the total cost is equivalent to identifying the k nodes U with the largest closed neighborhood |N [U ]| as in (4).

Remark 1. 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).

In the continuous case, where objects are points in 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.

Theorem III.2. Let X = R 2 , and C a (x, y) = h( x -y ), where h(z) = 0 for z ≤ 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.

Proof. We prove NP-hardness in the restricted case when every object is requested only once. We observe that any 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 NPhardness of the two covering problems on the plane known as DISC-COVER and BOX-COVER [START_REF] Fowler | Optimal packing and covering in the plane are np-complete[END_REF].

Remark 2. In R, DISC-COVER and BOX-COVER are solvable in linear time. Remark 3. For geometric versions of the maximum coverage problem, better approximation ratios can be achieved. For example [START_REF] Jin | Near-linear time approximation schemes for geometric maximum coverage[END_REF] presents some efficient polynomial-time approximation schemes when the objects are point on a plane.

We have already observed that exact caching is a particular case of similarity caching. Theorems III.1 and III.2 show that similarity caching is an intrinsically more difficult problem.

B. 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 [START_REF] Manasse | Competitive Algorithms for Server Problems[END_REF] for exact caching.

Let r denote a finite sequence of requests for m distinct objects, and rx the sequence obtained appending to r a new request for content x. We denote by S 1 the initial cache state, and by C OPT (r, S), the minimum aggregate cost achievable under the request sequence r, when the final cache state is S. It is possible to write the following recurrence equations, where denotes the empty sequence:

C OPT ( , S) = 0, if S = S 1 , +∞, otherwise. C OPT (rx, S) = min T (C OPT (r, T ) + C m (T , S)) , if x ∈ S, C OPT (r, S) + C(x, S), otherwise.
These equations lead to a dynamic programming procedure that iteratively computes the optimal cost for r T and determine the corresponding sequence of caching decisions. The number of possible states is m k . We can arrive to each state S potentially from (m -k)k + 1 other states. d(T, S) and C a (x, S) can be evaluated with

O(k) operations. Algorithm's time complexity is O (m -k)k 2 m k T . Space complexity is at least 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. V-C for the stochastic scenario. Remark 4. 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 kT 2 [START_REF] Chrobak | New results on server problems[END_REF], that is preferable in the opposite scenario. It is an open problem if a similar algorithm can be designed for similarity caching.

IV. COMPETITIVE ANALYSIS UNDER ADVERSARIAL

REQUESTS

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 [START_REF] Sleator | Amortized Efficiency of List Update and Paging Rules[END_REF] introduced competitive analysis to characterize the relative performance of caching policies in comparison 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. 1 In particular, an online caching algorithm A is said to be ρ-competitive, if its performance is within a factor ρ (plus a constant) from the optimum. More formally, there exists a such that

C A (S 1 , r T ) ≤ ρ C B (S 1 , r T ) + a T
, for all B and r T .

A competitive analysis of similarity caching in the particular case when C a (x, y) = 0 if d(x, y) ≤ r, where d() is a distance in X , is in [START_REF] Chierichetti | Similarity Caching[END_REF] (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 [START_REF] Manasse | Competitive Algorithms for Server Problems[END_REF] is perhaps the "most influential online problem [. . . ] that manifests the richness of competitive analysis" [START_REF] Koutsoupias | The k-server problem[END_REF]. 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 [START_REF] Manasse | Competitive Algorithms for Server Problems[END_REF] 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

C e (x, y) min(C a (x, y), C r ). (5)
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.

Theorem IV.1. [18, Sect. 6, Thm 10] Let α u be an upper bound for the set

{C e (x, y)/C r | x, y ∈ X }. If |X | = k + 1,
then the competitive ratio of any algorithm is bounded below by (2k + 1)(1 + α u )/(1 + 2α u ). Moreover, there exists a (2k + 1)-competitive deterministic algorithm (BAL).

Note that we can always select α u = 1.

Theorem IV.2. [22, Thms 4.1-2] If |X | > k and there exists 0 < α such that C e (x, y) = αC r for all x, y ∈ X with x = y, then the competitive ratio of any algorithm is at least 2k + 1. Moreover, there exists a (2k + 1)-competitive deterministic algorithm (RFWF).

A (4k + 1)-competitive algorithm is proposed in [START_REF] Hollander | A (4k+1)-competitive algorithm for the kserver with fixed cost excursion problem[END_REF]. [START_REF] Chung | Dynamic location problems with limited lookahead[END_REF] studies 1-server with limited look-ahead (i.e. considers policies that know a given number of future requests).

V. STOCHASTIC REQUEST PROCESS

We now consider the case when requests arrival times follow a Poisson process with (normalized) intensity 1 and the requested object is drawn from X according to the same distribution independently from the past, i.e., requests are i.i.d. distributed. In the finite case (|X | < ∞), we have a request rate λ 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 λ x : X → R + , i.e., for every Borel set A ⊆ X , the rate with which contents in A are requested is given by2 A λ x dx.

Under the above assumptions, for a given cache state S = {y 1 . . . y k }, we can compute the corresponding expected cost to serve a request:

C(S) x λ x C(x, S), finite case X λ x C(x, S) dx, continuous case. ( 6
)
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 S C(S),

lim inf T →∞ C A (S 1 , r T ) ≥ min S C(S), w.p.1. ( 7
)
A proof is given in Appendix A. We then say that an online caching algorithm is optimal if its time-average cost achieves the lower bound in (7) w.p. 1. For example, an algorithm that reaches a state S * ∈ arg min S C(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 S * to store is an NP-hard problem. In fact, minimizing ( 6) is a weighted version of the problem considered in Sect. III. 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 λ-aware (resp. λ-unaware), if it relies (resp. does not rely) on the knowledge of λ x .

In practice, λ-aware policies are meaningful only when objects' popularities do not vary wildly over time, remaining approximately constant over time-scales in which λ 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 (LFU) policy (see e.g. [START_REF] Einziger | TinyLFU: A Highly Efficient Cache Admission Policy[END_REF]). In contrast, λ-unaware policies do not suffer from this limitation.

Sections V-A and V-B below are respectively devoted to λ-aware and λ-unaware policies. Section V-C presents some lower bounds for the cost of the optimal cache configuration in the continuous scenario.

A. Online λ-aware policies

The first policy we present, GREEDY, is based on the simple idea to systematically move to states with a smaller expected cost [START_REF] Weston | Memory networks[END_REF]. It works as follows. Upon a request for content x at time t, 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., ∆C min y∈S C(S t ∪ {x} \ {y}) -C(S t ).

• if ∆C < 0 (x contributes to decrease the cost), then the cache retrieves x, serves it to the user, and replaces y e ∈ arg min y∈S C(S t ∪ {x} \ {y}) with x;

• if ∆C ≥ 0, the cache state is not updated. If C a (x, S t ) > C r ,
x is retrieved to serve the request; otherwise the request is satisfied by one of the best approximating object in S t . Intuitively, we expect 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. Definition V.1. A content y c is said significant if, for any δ > 0, it holds: B(yc,δ) λ x dx > 0, where B(y c , δ) is the ball of volume δ centered at y c . Definition V.2. A cache configuration S is locally optimal if C(S) ≤ C(S ), for all S obtained from S by replacing only one of the contents in the cache with a significant content y c . Theorem V.3. If C a () and λ() are smooth and X is a compact set, the expected cost of GREEDY converges to the expected cost of a configuration that is locally optimal w.p. 1. If X is a finite set, the cache state converges to a locally optimal configuration in finite time w.p. 1.

The proof is in Appendix B. The 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 OSA policy (Online Simulated Annealing) proposed in [START_REF] Neglia | Cache Policies for Linear Utility Maximization[END_REF], and we keep the same name here. OSA maintains a dynamic parameter T (t) (the temperature). Upon a request for content x at iteration t, OSA modifies the cache state as follows:

• If x ∈ S t , the state of the cache is unchanged.

• If x / ∈ S t , a content y ∈ S is randomly selected according to some vector of positive probabilities p(S t ), and the state of the cache is changed to S = S t \ {y} ∪ {x} with probability min (1, exp((C(S t ) -C(S ))/T (t))).

In the first case, OSA obviously serves x (a hit). In the second case, if the state changes to S , the cache serves x. Otherwise, it serves x or x ∈ arg min z∈S C a (x, z), respectively, if C a (x, S) > C r or C a (x, S) ≤ C r . OSA always stores a new content if this reduces the cost (as 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(S) can be arbitrarily chosen, as far as each content in S has a positive probability to be selected. In practice, we want to select with larger probability contents in S, whose contribution to the cost reduction is smaller.

OSA provides the following theoretical guarantees. Let ∆C max be the maximum absolute difference of costs between two neighboring states, then

Theorem V.4. When |X | < ∞, if T (t) = ∆C max k/(1+log t),
asymptotically only the states with minimum cost have a nonnull probability to be visited.

The proof is in Appendix C. 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 1 shows a toy case with a catalog of 4 contents and cache size equal to 2, for which GREEDY with probability at least 9/20 converges to a suboptimal state S = {1, 3} with corresponding cost C(S) = 17/128. On the contrary, OSA escapes from this local minimum and asymptotically converges to the optimal state S * = {2, 4} with C(S * ) = 6/128.

B. Online λ-unaware policies

In this section we present two new policies, qLRU-∆C and DUEL, that, without knowledge of λ x , bias admission and eviction decisions so to statistically favour configurations with low cost C.

λ 2 = λ 4 = 1/8, λ 1 = λ 3 = 3/8, T (t) = 1/ √ t.
Policy qLRU-∆C is inspired by qLRU-∆ proposed in [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF] 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 [START_REF] Leonardi | Implicit coordination of caches in small cell networks under unknown popularity profiles[END_REF] and how different contents interact in a similarity cache.

In qLRU-∆C the cache is managed as a ordered list (queue) as follows. Let x be the content requested at time t.

• If C a (x, 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. • If C a (x, S t ) ≤ C r , there is an approximate hit. The cache serves a content z ∈ arg min y∈St C a (x, y), that is refreshed, i.e., it is moved to the front of the queue, with probability C(x,St\{z})-Ca(x,z)

Cr

. With probability qC a (x, z)/C r the content x is still retrieved from the remote server and inserted at the head of the queue. If needed, contents are evicted from the tail of the queue. We observe that C(x, S t \ {z}) -C a (x, z) corresponds to the cost saving for the request x due to the presence of z in the cache.

Remark 5. 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.

When |X | is finite, the following result holds under the characteristic time (or Che's) approximation (CTA) [START_REF] Che | Hierarchical Web caching systems: modeling, design and experimental results[END_REF] and the exponentialization approximation (EA), that has been recently proposed and validated in [START_REF] Leonardi | Implicit coordination of caches in small cell networks under unknown popularity profiles[END_REF].

Theorem V.5. Under CTA and EA, when |X | < ∞ and q converges to 0, qLRU-∆C stores a set of contents that corresponds to a local minimum of the cost.

The proof is in Appendix D. The paper [START_REF] Pandey | Nearest-neighbor Caching for Content-match Applications[END_REF] proposes two policies for similarity caching: RND-LRU and SIM-LRU. In 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, RND-LRU can emulate in part qLRU-∆C, by using qC a (x, S t )/C r as its miss probability. The only difference is the refresh probability: in RND-LRU the best approximating content z is refreshed with probability 1 -qC a (x, S t )/C r (instead of (C r -C a (x, S t ))/C r as in qLRU-∆C). Our simulations in Sect. VI confirm that, for the same value of q, RND-LRU and qLRU-∆C exhibit very similar performance. Given our result in Theorem V.5, it is not surprising that RND-LRU performs better than SIM-LRU [3, Fig. 9]. Remark 6. It is possible to consider admission probabilities of the form q x,t = a(x, S t )q, i.e, probabilities that depend on the requested content and the actual state of the cache. Theorem V.5 still holds, when q converges to 0. This flexibility can be exploited to obtain better performance, by avoiding inserting contents that look less promising.

As we will show in Sect. VI, qLRU-∆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 λ-unaware policy, that we call DUEL.

Similarly to GREEDY, upon a request at time t for a content y which is not in the cache, DUEL estimates the potential advantage of replacing a cached content y with y , i.e., to move from the current state S t to state S = S t \ {y} ∪ {y }. As popularities are unknown, it is not possible to evaluate instantaneously the two costs C(S t ) and C(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 t occurring at time t > t, then the corresponding counter is incremented by C(r t, S t \ {y}) -C a (r t, y) (resp. C(r t, S t \ {y}) -C a (r 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 δ (a tunable parameter), or 2) a maximum delay τ (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 δ within the duel duration τ . 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 β, it is matched to the closest object in the cache; with the complementary probability 1 -β, 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 '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, DUEL provides a distributed, stochastic version of GREEDY with delayed decisions (due to lack of knowledge of λ x ).

C. Performance bound in the continuous scenario

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. 3 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 λ x = λ over a bounded set X . In what follows, all integrals are Lebesgue ones and all sets are Lebesgue measurable. Given a set A ⊂ R p , let |A| denote its volume (its measure), and B(x, |A|) the ball with the same volume centered in x. 4Lemma V.6. For any y ∈ X and a set A ⊂ R p it holds:

A C(x, y) dx ≥ B(y,|A|) C(x, y) dx. ( 8
)
The lemma provides the intuitive result that, among all sets A with a given volume, the approximation cost for requests falling in A is minimized when A is a ball centered in y, since C(x, y) = min(C a (x, y), C r ) = min(h( x -y ), 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 ( 8) does not depend on y but only on the volume |A|, because C(x, y) depends only on the distance x-y . We then write F (|A|) B(y,|A|) C(x, y) dx. We are now able to express the following bound for the expected cost: Theorem V.7. In the continuous scenario with constant request rate λ over X , for any cache state S,

C(S) ≥ λkF |X | k . (9)
Proof. Given S = {y 1 , y 2 , . . . , y k }, we denote by A h the set of objects in X having y h as closest object in the cache, i.e., A h = {x ∈ X | y h ∈ arg min d(x, S)}. The family {A 1 , A 2 , . . . , A k } is a Voronoi tessellation of X . We have:

C(S) = λ X C(x, S) dx = λ k h=1 A h C(x, y h ) dx ≥ λ k h=1 B(y h ,|A h |) C(x, y h )dx = λ k h=1 F (|A h |) ≥ λkF k h=1 |A h | k = λkF |X | k ,
where the first inequality follows from Lemma V.6, and the second one from Jensen's inequality, since F (•) is a convex function (see Appendix E).

In some cases, it is possible to show that specific cache configurations achieve the lower bound in (9) and then are optimal:

Corollary 1. Let d be the distance for which the approximation cost is equal to the retrieval cost, i. If the request rate is not space-homogeneous, one can apply the results above over small regions X i of X where λ x can be approximated by a constant value λ Xi , assuming a given number k i of cache slots is devoted to each area (with the constraint that 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 λ Xi , obtaining an approximation of the minimum achievable cost through Theorem V.7.

For example, consider the case when the domain X lies in the plane (X ⊂ R 2 ), C r = ∞, and C a (x, y) = x -y γ 1 . 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 λ i , 1 ≤ i ≤ M . Let k i ≥ 0 be the number of cache slots devoted to region i, and 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 = 1/(2k i ), within region i (we ignore border effects, supposing r i 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:

c i (r i ) = Br i (0) x -0 γ dx = 4 ri 0 ri-x1 0 (x 1 + x 2 ) γ dx 2 dx 1 = 4 r γ+2 i γ + 2 ,
Expressing c(r i ) as function of k i , we obtain:

c i (k i ) = ζk -γ+2 2 i
, where ζ 2 (2-γ)/2 /(γ + 2). Hence the total approximation cost in the whole domain is

C(k) = M i=1 k i λ i c i (k i ).
We select the values k that minimize the expected cost:

minimize k1,...,k M ζ M i=1 λ i k -γ/2 i subject to M i=1 k i = k (10)
Employing the standard Lagrange method, we obtain that λ i k -(γ+2)/2 i equals some unique constant for any region i, which means that k i has to be proportional to λ 2/(γ+2) i . In the limit of large M, we substitute the sums in ( 16) with continuous integrals, obtaining:

min C(k) ≈ ζk -γ/2 X λ(x) 2 γ+2 dx γ+2 2 . ( 11
)
The case when C r is finite is slightly more complex and it is studied in Appendix F.

VI. EXPERIMENTS

To evaluate the performance of different caching policies, we have run extensive Monte-Carlo simulations in the following reference scenario: a bidimensional L × L square grid of points, with unitary step and wrap-around conditions, and C a (x, y) = 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 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 2 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 2 and approximation [START_REF] Chierichetti | Similarity Caching[END_REF] to compute the minimum cost.

We first consider traffic synthetically generated according to the IRM, in two cases: homogeneous, in which all objects are requested with the same rate; Gaussian, in which the request rate of object i is proportional to exp(-d 2 i /(2σ 2 )), where d i is the hop distance from the grid center. Under homogeneous traffic, Corollary 2 guarantees that a cache configuration storing the centers of the balls of any tessellation like the one in Fig. 2 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 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 β = 3/4, δ = f • min x =y C a (x, y), τ = f L/λ, which requires to choose a single parameter f . Figures 3 and4 show the instantaneous cost ( 6) achieved by different policies as function of the number of arrived requests, respectively for homogeneous and Gaussian traffic (with σ = L/8). The optimal cost (approximated by [START_REF] Chierichetti | Similarity Caching[END_REF], and also exactly computed thanks to Corollary 2 in the homogeneous case) is also reported as reference. In both cases, as expected, GREEDY outperforms all λ-unaware policies and reaches an almost optimal cache configuration after a number of arrivals of the order of the catalog size. For qLRU-∆C, RND-LRU, and 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. V-B, qLRU-∆C and RND-LRU are close (provided that we match their miss probability), and indeed they exhibit very similar performance, with a slight advantage of qLRU-∆C for small values of q (remember that the local optimality in Theorem V.5 holds for vanishing q). 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 λ-aware policies. Figure 5 shows the cache configuration achieved by DUEL after 10 8 arrivals, for both types of traffic.

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 [START_REF] Neglia | Access-time-aware cache algorithms[END_REF]). 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 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 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 Gaussian popularities.

Figure 6 shows the accumulated cost achieved by different policies as function of the number of arrived requests, for both mappings. For the qLRU-∆C and 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. 5To 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: LRU and RANDOM [START_REF] Garetto | A Unified Approach to the Performance Analysis of Caching Systems[END_REF]. Since these policies produce a disproportionate number of misses, their total aggregate cost ( 2) is at least one order of magnitude larger than that qLRU-∆C and DUEL. For a fair comparison, we only plot the aggregate approximation cost t C a (r t , S t ). Although retrieval costs incurred are ignored, LRU and RANDOM still perform between 30% and 50% worse than DUEL.

The figure also shows the performance of GREEDY, using as λ x the empirical popularity distribution measured on the entire trace. Interestingly, under non stationary, realistic traffic conditions, GREEDY no longer outperforms λ-unaware policies. In particular, DUEL takes the lead under both mappings, due to its ability to dynamically adapt to shifts in contents' popularity. 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, 6 as implemented in the scipy library [33], 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.

At last, we tested our policies on an Amazon trace. In [START_REF] Mcauley | Image-based recommendations on styles and substitutes[END_REF] 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. "The notion of style is learned by training the model on pairs of objects which Amazon considers to be related" [START_REF] Mcauley | Image-based recommendations on styles and substitutes[END_REF] 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 [START_REF] Pandey | Nearest-neighbor Caching for Content-match Applications[END_REF]. 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 6 shows the accumulated cost achieved by different policies as function of the number of arrived requests. We observe that DUEL performs almost the same as 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. VII. 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 ) ≤ C r (this is actually a consequence of 1) and 2) as we discussed in Sect. II).

But it may also be meaningful to distinguish a cost paid by the user (C u r ) and a cost paid by the network (C n r ). 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 ) ≤ C u r . 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

• the cache is required to retrieve r t , or not,

• the cache is required to store o, or not,

• the cache is allowed to serve a content o to the user only if C a (r t , o ) ≤ C u r , or not. 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 u r . Moreover, we can capture the choice about storing or not the retrieved object o through the constant χ +∞ if the cache is required to store o, C u r + C n r otherwise.

The system can always be modeled as an MTS where the total cost can be expressed as sum of movement costs (C m (S t , S t+1 )) to change from one state to another and service costs (C(r t , S t+1 )). The movement cost has the same expression as in ( 1) with C r replaced by C u r +C n r . The service cost needs now to be defined as C(r, S) min(C a (r, S), χ).

Results for the offline and stochastic scenarios, respectively in Sect. III and Sect. V, 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) min(C a (x, y), χ).

Theorems IV.1 and IV.2 hold if we replace C r by C u r + C n r and add the additional requirement that α u ≤ 2 and α ≤ 2, respectively.

VIII. 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élády's one [START_REF] Bélády | A Study of Replacement Algorithms for a Virtual-storage Computer[END_REF] 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 [START_REF] Fagin | Asymptotic miss ratios over independent references[END_REF], [START_REF] Fricker | A Versatile and Accurate Approximation for LRU Cache Performance[END_REF], [START_REF] Jiang | On the Convergence of the TTL Approximation for an LRU Cache Under Independent Stationary Request Processes[END_REF]. 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 LRU, qLRU, RANDOM, and other policies in the classic setting? There is surely still room for the design of efficient λunaware policies. Interestingly, in our experiments the smallest cost is achieved by 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 lowlatency 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.

APPENDIX A PROOF OF [START_REF] Graves | Neural Turing Machines[END_REF] To ensure that the LHS in ( 7) is bounded, we assume that Ĉ = sup x,S =∅ C(x, S) < ∞, i.e. the cost paid to serve any request from any state is finite.

Under such condition, we prove that:

lim inf T →∞ C A (S 1 , r T ) ≥ min S C(S), w.p.1.
First, observe that

C A (S 1 , r T ) = 1 T T t=1 C m (S t , S t+1 ) + C(r t , S t+1 ) ≥ 1 T T t=1 C(
M t = t i=0 Y i with M 0 = 0; M t is a martingale, since i) E[M t | F t-1 ] = M t-1 + E[Y t ] = M t-1 , where {F t } t∈N is the associated natural filtration F n = σ({Y i } i≤n ); ii) E[|M t |] < t Ĉ < ∞, given that by construction |M t+1 -M t | = |Y t | ≤ Ĉ.
Let S t = 1 t M t (with S 0 = 0), by applying Azuma inequality to M t , we have that, for any > 0:

P(|S t | ≥ ε) = P(|M t | ≥ εt) = P(|M t -M 0 | ≥ εt) ≤ 2 exp - ε 2 t 2 Ĉ2 .
Therefore by a standard application of the Borel-Cantelli lemma we can claim that:

lim t→∞ S t = 0 w.p. 1.
In other words. we have that: APPENDIX B PROOF OF THEOREM V.3 Proof. We start with the finite case. Let (t n ) be the sequence of time instants at which contents are requested, and (S n ) = (S tn ) be the corresponding sequence of cache configurations. The sequence (C(S n )) is non increasing and then convergent. Therefore, there exists a finite random variable C ∞ such that lim n→∞ C(S n ) = C ∞ w.p. 1. Moreover, as the set of possible cache configurations (and then the set of possible costs) is finite, the limit is necessarily reached within a finite number of requests. Also the sequence (S n ) converges after a finite number of requests w.p. 1 to a random configuration S ∞ , such that C(S ∞ ) = C ∞ . Observe, indeed, that no configuration can be visited more than once by construction. We prove that S ∞ is locally optimal w.p. 1. Consider the event E composed of all path trajectories of (S n ) converging to a specific configuration S that is not locally optimal. By definition, there exists a significant object y c / ∈ S , whose insertion in the cache strictly reduces the cost of S . By construction, in E, y c can be requested only before the convergence of (S n ) to S . Then, necessarily P(E) = 0, because λ yc > 0 and, therefore, w.p. 1 sample-paths contain an unbounded sequence of time-instants at which requests for y c arrive.

lim inf T →∞ 1 T
The proof for the continuous case is significantly more technical and complex. Let Y n = Y(t n ) be the sequence of caching configurations observed under policy GREEDY (i.e., {t n } n is the sequence of random instants at which the contents in the cache are modified), and C(Y n ). the corresponding average costs. We set conventionally Y n+1 = Y n whenever t n+1 = ∞.

Note that Y n = Y(t n ) is a stochastic sequence of set valued random variables (i.e Y n ∈ X k , where X k is endowed with with the metric d(Y, Y ) = min π i d(y i , y π(i) ), where π denotes a generic permutation of order k), with associated law P n (dY). Note that, by construction, the sequence of associated costs satisfies

E[C(Y n ) | Y n-1 ] ≤ C(Y n-1 ) i.e. sequence C(Y n ) it is a non-negative uniformly-bounded super-martingale. Therefore lim n→∞ C(Y n ) = C ∞ exists w.p.1 by Doob Convergence Theorem. Moreover since C(Y n ) is uniformly bounded E[|C(Y n ) -C ∞ |]
→ 0 as well. Note that not necessarily {Y n } n converges point-wise: however, observe that, since the domain of configurations X k is compact, by Prokhorov's theorem, there exists a sub-sequence (Y ni ) that converges weakly (i.e. in distribution) to a random variable Y ∞ . In addition

E[C ∞ ] = lim E[C(Y n )] = lim E[C(Y ni )] = E[C(Y ∞ )],
E[E[C(Y ∞ ) | Y n ]] ≤ E[E[C(Y n +1 ) | Y n ]] ≤ E[C(Y n )] -apP(Y n ∈ Z a,p )
but this is in contradiction with the fact that by construction Observe that previous result can be strengthened under the additional assumption that system configuration Y n converges w.p.1 to a variable Y ∞ (as for the case in which |X | is finite or denumerable). In such a case we can prove w.p.1 convergence to an optimal local configuration.

E P M [C(Y n )] ≤ E[C(Y ∞ ) | Y n ]+ , unless apP(Y n ∈ Z a,

APPENDIX C PROOF OF THEOREM V.4

Proof. If the content to be evicted were selected uniformly at random from the cache, then the proof would be the same as the one of Proposition IV.2 in [START_REF] Neglia | Cache Policies for Linear Utility Maximization[END_REF]. A key point in that proof is that, when the temperature is constant (T (t) = T ), the homogeneous Markov chains induced by OSA are reversible, so that one can easily write their stationary probability distributions. Here, it is not the case, but we can use the more general result for weakly-reversible time-variant Markov chains in [START_REF] Hajek | Cooling Schedules for Optimal Annealing[END_REF].

In simulated annealing, it is usual to consider the transition probability from state S t = S to state S as combination of two different random choices. First, S is selected as a potential candidate with probability R(S, S ). In our case, non null R(S, S ) are associated only to transitions between states S and S = S \ {y} ∪ {x}. Furthermore, S is selected as candidate only if x has been requested and y has been selected for eviction, i.e., R(S, S ) = λ x (p(S)) y . Second, this transition is accepted with a probability that depends on the corresponding costs of the two states, i.e., min (1, exp((C(S) -C(S ))/T (t))).

In [START_REF] Hajek | Cooling Schedules for Optimal Annealing[END_REF] weak-reversibility is a structural property of the MC, which is determined by the configuration of possible state transitions S → S (i.e., those that have R(S, S ) > 0) and by the behavior of state function C(S), which deterministically determines the acceptance probabilities. We say that state U is reachable from state S = U at height E, if there exists a sequence of states S = S 1 , S 2 , • • • , S n = U, such that all transitions S i → S i+1 have positive probability R(S i , S i+1 ) and C(S i ) ≤ E for each i. The MC is weakly-reversible if, for every value E, state U is reachable at height E from state S if and only if state S is reachable at height E from state U. The policy OSA defines a weakly-reversible MC. Observe, indeed, that R(S , S) > 0 if and only if R(S, S ) > 0 . Moreover note that the MC is irreducible. In particular, any state U is reachable from any state S at height at most C(S) + k∆C max . In fact, at most k transitions are required to move from S to U, corresponding to a request for each object that is in U, but not in S. In particular, any global minimum is reachable from any local minimum S at height at most C(S) + k∆C max . The thesis then follows from a direct application of [START_REF] Hajek | Cooling Schedules for Optimal Annealing[END_REF]Thm. 1].

APPENDIX D PROOF OF THEOREM V.5

Proof. We start by extending the CTA to similarity caching. Given an object x, let T (x) c (S) denote the time content x stays in the cache until eviction if 1) the cache is in state S just after its insertion and 2) x is never refreshed (i.e., moved to the front) during its sojourn in the cache. In general T (x) c (S) is a random variable, whose distribution depends both on x and on the cache state S. The basic assumption of CTA is that T (x) c (S) = d T (x ) c (S ) for each x, x , S, and S , i.e., we can ignore dependencies on the content and on the state. Moreover, for caching policies where contents are maintained in a priority queue ordered by the time of the most recent refresh, and where evictions occur from the tail (as in LRU, qLRU, and qLRU-∆C), CTA approximates T c with a constant.

The strong advantage of CTA is that the interaction among different contents in the cache is now greatly simplified as in a TTL-cache [START_REF] Choungmo Fofack | Analysis of TTL-based Cache Networks[END_REF]. In a TTL-cache, upon insertion, a timer with value T c is activated. It is restarted upon each new request for the same content. Once the timer expires, the content is removed from the cache. Under CTA, the instantaneous cache occupancy can violate the hard buffer constraint. 7 The value of T c is obtained by imposing the expected occupancy to be equal to the buffer size, i.e., x∈X

π x = k, (13)
where π x is the stationary probability that x is stored in the cache. For exact caching, it is relatively easy to express π x as function of T c and, then, to numerically compute the value of T c . For similarity caching, additional complexity arises because the timer refresh rate for each content x depends on the other contents in the cache (as x can be used to provide approximate answers), i.e., dynamics of different contents are still coupled. Nevertheless, the TTL-cache model allows us to study this complex system as well.

The expected marginal cost reduction due to x in state S is ∆C x (S) C(S \ {x}) -C(S).

If the state of the cache does not change, the expected sojourn time of content x in the cache can be computed as:

E[T S ] =
EA assumes that S t evolves as a Markov Chain (MC) with transition rate from S to S \ {x} equal to ν x (S) from [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF], and from S to S ∪ {x} equal to qλ x C a (x, S)/C r (if x is not already in S). [START_REF] Leonardi | Implicit coordination of caches in small cell networks under unknown popularity profiles[END_REF] shows that EA is very precise in practice for complex systems of interacting caches.

Results for regular perturbations of Markov chains [START_REF] Peyton | The Evolution of Conventions[END_REF] allow us to study the asymptotic behavior of the MC (S t ) when q vanishes, and in particular to determine which states are stochastically stable, i.e., have a non-null probability to occur as q converges to 0. The proof is analogous to the one in [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF].

Reference [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF] proposes a caching policy that can coordinate content allocation across different caches in a dense cellular network to maximize a performance metric. Despite the different application scenario, there is an analogy between the two problems. Here, two similar/close contents interact because they can satisfy the same requests. In [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF], two copies of the same content at two close base stations interact because they can satisfy requests from users in the transmission range of both base stations. More formally, the gain from a given allocation of copies of content f , G f (x f )), corresponds here to the cost reduction C(∅) -C(S). Similarly, the gain from the copy at base station b, ∆G (b) f (x f ), corresponds to the gain from content x, ∆C x (S). Moreover, transition rates of the MC when adding/removing a content x, as function of the current set of contents S, have the same "structure" of the transition rates in [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF]. It follows that many results in [START_REF] Neglia | A Swiss Army Knife for Dynamic Caching in Small Cell Networks[END_REF] have a corresponding result for our problem, that can often be obtained simply replacing the matching quantities. For example, from the rate expressions and the constraint [START_REF] Borodin | An Optimal On-line Algorithm for Metrical Task System[END_REF] we can conclude that there exists a sequence (q n ) converging to 0, such that T c (q n ) = C r /γ log(1/q n ) [27, Sect. IV.C].

In particular, we can adapt the proof of [27, Prop. IV.1] to our problem, and show that the stochastically stable states are locally optimizers in the sense that it is not possible to replace a content in such states while reducing the cost. More formally, given two states that differ only for one element, i.e. S = U ∪ {x} and S = U ∪ {x } with x, x / ∈ U, we can prove that if S is stochastically stable then C(S) ≤ C(S ).

We briefly present the steps of the proofs that need to be adapted. As for any cache state S = {y 1 , y 2 , . . . , y l } holds C(∅) -C(S) = l i=1 ∆C yi ∪ i j=1 {y j } (corresponding to [27, Eq. ( 5)]), the inequality C(S) ≤ C(S ) holds if and only if ∆C x (S) ≥ ∆C x (S ). We can prove the last inequality showing that ∆C x (S) ≥ γ and ∆C x (S ) ≤ γ. The proof exploits an additional state function φ(S) C(∅) -C(S) -γ|S|, that characterizes the dominant transitions [27, Sect. IV.E].

Fig. 1 .

 1 Fig. 1. OSA converges to the minimum cost state. Catalog: {1, 2, 3, 4}; Ca(1, 2) = Ca(2, 1) = Ca(2, 3) = Ca(3, 2) = 1/16; for all other pairs (x, y), Ca(x, y) = ∞; Cr = 1; λ 2 = λ 4 = 1/8, λ 1 = λ 3 = 3/8, T (t) = 1/ √ t.

Corollary 2 .

 2 e., d = inf{d : h(d) = C r }. Let B d(x) be a ball of radius d centered in x. Any cache state S = {y 1 , . . . y k }, such that the balls B d(y h ) are contained in X and have intersections with null volume, is optimal. Any cache state S = {y 1 , . . . , y k }, such that, for some d, the balls B d (y h ) for h = 1, . . . , k are a tessellation of X (i.e., ∪ h B d (y h ) = X and |B d (y i ) ∩ B d (y j )| = 0 for each i and j), is optimal.

Fig. 2 .

 2 Fig. 2. 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.

Fig. 3 .

 3 Fig. 3. Performance of different policies in the case of homogeneous traffic.

Fig. 4 .

 4 Fig. 4. Performance of different policies in the case of Gaussian traffic, with σ = L/8.

Fig. 5 .

 5 Fig. 5. Final configuration produced by the DUEL policy under homogeneous traffic (left plot, with f = 300), and Gaussian traffic (right plot, with f = 100).

Fig. 6 .

 6 Fig. 6. Performance of different policies under Akamai trace: uniform mapping (left plot) and spiral mapping (right plot).

Fig. 7 .

 7 Fig. 7. Performance of different policies under Amazon trace.

  r t , S t ) -C(S t )] = lim inf T →∞ S T = lim T →∞ S T = 0, w.p. 1, from which the assertion follows immediately.

1 √ m , 1 √

 11 p ) ≤ . The assertion follows from the arbitrariness of . Indeed for any fixed m ≥ 1 choosing a = 1/ √ m, p = 1/ √ m and = 1/(mk) with k ≥ 1 sufficiently large we obtain that: is open). Therefore, by continuity of probability with respect to increasing events, we have P(Y ∞ ∈ ∪ m Z m ) = 0, i.e. w.p.1, Y ∞ is local optimal. The assertion holds since, as already observed, E[C ∞ ] = E[C(Y ∞ )].

  r t , S t ), as C(r t , S t+1 ) = C a (r t , S t ), if S t+1 = S t , or C m (S t , S t+1 ) = C r otherwise. Then it is sufficient to prove thatWe define Y t = C(r t , S t ) -C(S t ) and observe that by construction E[C(r t , S t )] = C(S t ), therefore E[Y t ] = 0. Now let

	lim inf T →∞	1 T	T t=1	C(r t , S t ) ≥ min S	C(S), w.p.1.

  due to the continuity and boundness of C() with respect to its argument. Let n < ∞ be the minimum (discrete) time, such that E[C(Y n )] < E[C(Y ∞ )] + for an arbitrary > 0. We denote with P n (dY) the law of Y n . Now we define as Z a,p the open set of configurations Y such that:B a (Y) := {Y = Y ∪ y c \ y e : C(Y) > C(Y ) + a, Y ∈ S} = ∅Note that Z a,p , provided that C a () and λ() are continuous, is by definition an open set. Now, note that any configuration Y which is not local optimal, necessarily lies in some Z a,p . In particular any configuration Y which is not local optimal must belong to Z 1/

	and
				p a (Y) =	Ba(Y) λ(x) dx X λ(x) dx	> p.
	√	m,1/	√	m for sufficiently large m. Therefore the set of non local optimal configurations lies in ∪ m≥1 Z 1/	√	m,1/	√	m .
	Now by construction, we have:

By now, competitive analysis has become a standard approach to study the performance of many other algorithms.

More in general, we could consider a generic compact metric space X endowed with the Haar measure, i.e., the unique (up to multiplicative constant) finite Borel measure, which is translation invariant over X .

Recall that in the continuous case the rate of exact hits is null.

The geometric shape of a ball depends on the considered norm. For example, in R 2 , if . is the usual norm-2, balls are circles; if it is the norm-1, balls are squares.

This means that, for example, qLRU-∆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.

We adopt the "tau-b" version of this measure as defined in[START_REF] Kendall | The treatment of ties in ranking problems[END_REF], which accounts for ties. Values close to 1 indicate strong agreement, values close to -1 indicate strong disagreement.

Under CTA the number of contents stored in the cache is a Poisson random variable with expected value equal to k. Since its coefficient of variation tends to 0 as k grows large, CTA is expected to be asymptotically accurate.

APPENDIX E CONVEXITY OF F (v)

Let F (v) = B(y,v) C(x, y) dx, where B(y, v) denotes the ball of volume v with center y. Remember that C(x, y) depends on x and y through the norm-induced distance d(x, y) = x -y . By the change of variable z = x -y, we obtain

C(z, 0) dz.

We use the short form B(v) for B(0, v) and c(z) for C(z, 0). Note that c(z) is an increasing function of z .

We prove convexity of F (v) over R + using the definition. Consider

We also denote by c α = max z∈B(vα) c(z) (that is achieved at the points z at the boundary of the ball B(v α )). We want to prove that αF

where the inequality follows from the monotonicity of c(z)

When C r is finite, the cost c i within a cell takes two different expression depending on whether r i is smaller than or greater than d = C 1/γ r :

or, as a function of k i :

where k is the value for which diamonds in the region have radius d, i.e., k 1/(2 d2 ) = 1/(2C 2/γ r ). We observe that c i (k i ) is a decreasing function of k i (as intuitively expected).

The optimization problem becomes:

Let us suppose that

Consider an allocation of cache slots k such that there exist i and j with i < j such that k i < k and k j > 0. We can improve such allocation by moving cache slots from region j to region i at least as far as the number of slots for region i does not reach k. Formally, one can check that the allocation k such that

, and k l = k l for l / ∈ {i, j}, has a smaller cost than k. From this observation it follows that the optimal allocation has the following structure: the most popular i * regions receive more than k slots, region i * + 1 may receive k i * +1 > 0 slots (but k i * +1 < k) , and all other regions do not receive any slot.

In the limit for large M we can ignore the effect of the region i * + 1 and only consider the regions that are popular enough to receive more than k slots and those that do not receive any cache slot. If the measure of each level set of λ(x) is null, a threshold λ * can be identified, such that the first (resp. second) set of regions corresponds to the part of the Euclidean space where the request rate exceeds (resp. does not exceed) λ * . We obtain the approximate cost:

Under the assumptions above and that the density λ(x) is a continuous function, λ * can be determined considering that in the popular space region

As λ(x) is continuous, we can select points x whose request rate is arbitrarily close to (but larger than) λ * , and then we obtain the inequality k(λ * + )