Michele Garetto

Emilio Leonardi

Giovanni Neglia

Content Placement in Networks of Similarity Caches

Similarity caching systems have recently attracted the attention of the scientific community, as they can be profitably used in many application contexts, like multimedia retrieval, advertising, object recognition, recommender systems and online content-match applications. In such systems, a user request for an object o, which is not in the cache, can be (partially) satisfied by a similar stored object o', at the cost of a loss of user utility. In this paper we make a first step into the novel area of similarity caching networks, where requests can be forwarded along a path of caches to get the best efficiency-accuracy tradeoff. The offline problem of content placement can be easily shown to be NP-hard, while different polynomial algorithms can be devised to approach the optimal solution in discrete cases. As the content space grows large, we propose a continuous problem formulation whose solution exhibits a simple structure in a class of tree topologies. We verify our findings using synthetic and realistic request traces.

Introduction

Similarity caching is an extension to traditional (exact) caching, whereby a request for an object can be satisfied by providing a similar cached item, under a dissimilarity cost. In some cases, user requests are themselves queries for objects similar to a given one (similarity searching [START_REF] Gionis | Similarity search in high dimensions via hashing[END_REF]). Caching at network edges can drastically reduce the latency experienced by users, as well as backbone traffic and server provisioning.

Similarity searching and caching have several applications in multimedia retrieval [2], contextual advertising [START_REF] Pandey | Nearest-neighbor Caching for Content-match Applications[END_REF], object recognition [START_REF] Drolia | Cachier: Edge-caching for recognition applications[END_REF][START_REF] Drolia | Precog: Prefetching for image recognition applications at the edge[END_REF][START_REF] Guo | Foggycache: Cross-device approximate computation reuse[END_REF][START_REF] Venugopal | Shadow puppets: Cloud-level accurate AI inference at the speed and economy of edge[END_REF], caching of videos with different qualities/resolutions [START_REF] Araldo | Representation Selection Problem : Optimizing Video Delivery through Caching[END_REF][START_REF] Choi | Wireless Video Caching and Dynamic Streaming Under Differentiated Quality Requirements[END_REF][START_REF] Qu | Cooperative caching for multiple bitrate videos in small cell edges[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], online prediction serving systems [START_REF] Crankshaw | Clipper: A Low-Latency Online Prediction Serving System[END_REF][START_REF] Jin | Provisioning Edge Inference as a Service via Online Learning[END_REF][START_REF] Tareq | Towards Inference Delivery Networks: Distributing Machine Learning with Optimality Guarantees[END_REF]. Figure 1 shows an application scenario of similarity caching in the context of Mobile Edge Computing [START_REF]Multi-access edge computing[END_REF]. Mobile users accessing cloud services from an ultra-low latency, high bandwidth cellular wireless networks (e.g., 5G) can strongly benefit from the availability of a cache installed directly at the radio network controller: in such a way, the need for a particular object, for example by an Augmented Reality application, can be satisfied locally with minimum latency by a sufficiently similar object, without having to traverse a possible long path towards the object repository. References [START_REF] Drolia | Cachier: Edge-caching for recognition applications[END_REF][START_REF] Drolia | Precog: Prefetching for image recognition applications at the edge[END_REF][START_REF] Guo | Foggycache: Cross-device approximate computation reuse[END_REF][START_REF] Venugopal | Shadow puppets: Cloud-level accurate AI inference at the speed and economy of edge[END_REF] consider this specific scenario for object recognition applications. In this case, the request is an image, for which the MEC server provides some labels extracted from similar images found in a local database. Note that several caches can be deployed along the path from the user to the cloud (e.g., at micro regional data centers) forming a tree-like similarity caching network (in the case of many geographically spread users).

Despite its interesting applications, theoretical understanding of similarity caching and development of related algorithms and policies are still at their early stages.

Paper contribution

Our contributions can be summarized as follows:

1. while the content placement problem in networks of similarity caches is NP-hard, we show that it can be formulated as the maximization of a sub-modular function over a matroid; therefore a polynomial Greedy algorithm can be defined with 1/2 approximation ratio;

2. we propose the randomized LocalSwap algorithm that does not enjoy worst-case guarantees as Greedy, but asymptotically converges to a locally optimal solution;

3. we characterize the structure of the optimal similarity-caching placement problem in special cases; in particular, we show that, under mild assumptions, when the cache network has a regular tree structure and requests arrive only at the leaves the optimal solution in the large catalog regime has a relatively simple structure;

4. we show that the above structure is lost in general networks, analyzing a simple tandem network where requests arrive at both caches;

5. we propose an online, λ-unaware policy called NetDuel, that extends Duel [START_REF] Garetto | Similarity caching: Theory and algorithms[END_REF] to the networked setting;

6. we illustrate our findings considering both synthetic and real request processes for Amazon items.

Paper outline

We discuss related work in Section 2. In Section 3 we present the main system assumptions and we formulate the problem. In Sections 4 and 5 we analyse respectively the discrete content case and the continuous content case, presenting algorithms and theoretical performance results. In Section 6 we introduce NetDuel, an efficient on-line caching policy. In Section 7 we report simulation results, obtained both in synthetic scenarios and more realistic scenarios based on Amazon traces. We conclude in Section 8, pointing out directions of future research.

Related Work

Despite the multiple applications of similarity caching, our theoretical understanding of the general problem is still limited even in the single-cache scenario, and similarity caching policies have mostly been proposed in an ad-hoc way without taking advantage of the body of work built in the last decades for exact caching (e.g., [START_REF] Choungmo Fofack | Performance evaluation of hierarchical ttl-based cache networks[END_REF][START_REF] Daniel | Exact analysis of ttl cache networks[END_REF][START_REF] Ioannidis | Adaptive caching networks with optimality guarantees[END_REF][START_REF] Dehghan | A utility optimization approach to network cache design[END_REF]).

For example the seminal papers [2,[START_REF] Pandey | Nearest-neighbor Caching for Content-match Applications[END_REF], which introduced the concept of similarity caching, proposed only simple modifications to the Least Recently Used policy (LRU) and evaluated them empirically. Similarly, references [START_REF] Crankshaw | Clipper: A Low-Latency Online Prediction Serving System[END_REF][START_REF] Drolia | Cachier: Edge-caching for recognition applications[END_REF][START_REF] Drolia | Precog: Prefetching for image recognition applications at the edge[END_REF][START_REF] Guo | Foggycache: Cross-device approximate computation reuse[END_REF][START_REF] Guo | Potluck: Cross-application approximate deduplication for computation-intensive mobile applications[END_REF][START_REF] Venugopal | Shadow puppets: Cloud-level accurate AI inference at the speed and economy of edge[END_REF] focused more on the specific application system (machine learning prediction serving and object recognition), without specific contributions in terms of cache management policies (e.g., they apply minor changes to exact caching policies like LRU or LFU).

An adversarial setting was studied in [START_REF] Chierichetti | Similarity Caching[END_REF] by competitive analysis. The authors of [START_REF] Sabnis | Grades: Gradient descent for similarity caching[END_REF] have proposed a similarity caching policy (for a single cache) tailored for the case when cached objects may be embedded in R d with a distance that captures dissimilarity costs. The work most closely related to this paper is [START_REF] Garetto | Similarity caching: Theory and algorithms[END_REF], where we have analyzed a single similarity cache in the offline, adversarial, and stochastic settings, proposing also some dynamic online policies to manage the cache.

We mention that many researchers have studied networks of exact caches (e.g., [START_REF] Rosensweig | On the steady-state of cache networks[END_REF][START_REF] Shanmugam | Femtocaching: Wireless content delivery through distributed caching helpers[END_REF][START_REF] Choungmo Fofack | Performance evaluation of hierarchical ttl-based cache networks[END_REF][START_REF] Ioannidis | Adaptive caching networks with optimality guarantees[END_REF][START_REF] Leonardi | Implicit coordination of caches in small cell networks under unknown popularity profiles[END_REF][START_REF] Li | Universally stable cache networks[END_REF]), however their results cannot be applied to the similarity caching setting, which is a fundamentally different problem (in exact caching there is no notion of distance between objects).

Networks of caches for videos with different qualities have been studied in [START_REF] Araldo | Representation Selection Problem : Optimizing Video Delivery through Caching[END_REF][START_REF] Choi | Wireless Video Caching and Dynamic Streaming Under Differentiated Quality Requirements[END_REF][START_REF] Qu | Cooperative caching for multiple bitrate videos in small cell edges[END_REF], but references [START_REF] Choi | Wireless Video Caching and Dynamic Streaming Under Differentiated Quality Requirements[END_REF][START_REF] Qu | Cooperative caching for multiple bitrate videos in small cell edges[END_REF] consider a single layer of caches deployed at the edge of the network (the request is served by one of these caches or forwarded to the authoritative server), while we study more complex architectures like trees. The authors of [START_REF] Araldo | Representation Selection Problem : Optimizing Video Delivery through Caching[END_REF] consider a general architecture, but, while they correctly model user's QoE dependence on video quality, they ignore the cost of retrieving the videos from farther caches. Moreover, video placement is based on heuristic policies with no performance guarantees.

Similarity caches for content recommendation have been considered in [START_REF] Sermpezis | Soft Cache Hits: Improving Performance Through Recommendation and Delivery of Related Content[END_REF][START_REF] Costantini | Impact of popular content relational structure on joint caching and recommendation policies[END_REF]. The authors have studied how to statically place contents in edge caches of a cellular network, given their popularity and the utility for a user interested in content o to receive a similar content o . In contrast to us, they focus on the cellular scenario with spatial cache overlaps (also known as "femtocaching" [START_REF] Golrezaei | Femtocaching: Wireless video content delivery through distributed caching helpers[END_REF]).

The recent letter [START_REF] Zhou | Adaptive offline and online similarity-based caching[END_REF] has considered a network of similarity caches, where requests can be forwarded along a path of caches towards a repository storing all objects, at the cost of increasing delays and resource consumption. The authors of [START_REF] Zhou | Adaptive offline and online similarity-based caching[END_REF] have proposed a heuristic based on the gradient descent/ascent algorithm to jointly decide request routing and caching, similarly to what was done in [START_REF] Ioannidis | Adaptive caching networks with optimality guarantees[END_REF] for exact caches but without the corresponding theoretical guarantees. The proposed algorithm requires memory proportional to the size of the catalog, and appears to be computationally

Papers

Application

Architecture Catalog [2,[START_REF] Pandey | Nearest-neighbor Caching for Content-match Applications[END_REF][START_REF] Sabnis | Grades: Gradient descent for similarity caching[END_REF][START_REF] Chierichetti | Similarity Caching[END_REF] generic single cache discrete [START_REF] Garetto | Similarity caching: Theory and algorithms[END_REF] generic single cache discrete/continuous [START_REF] Crankshaw | Clipper: A Low-Latency Online Prediction Serving System[END_REF][START_REF] Drolia | Cachier: Edge-caching for recognition applications[END_REF][START_REF] Drolia | Precog: Prefetching for image recognition applications at the edge[END_REF][START_REF] Guo | Foggycache: Cross-device approximate computation reuse[END_REF][START_REF] Guo | Potluck: Cross-application approximate deduplication for computation-intensive mobile applications[END_REF][START_REF] Venugopal | Shadow puppets: Cloud-level accurate AI inference at the speed and economy of edge[END_REF] machine learning single cache discrete [START_REF] Choi | Wireless Video Caching and Dynamic Streaming Under Differentiated Quality Requirements[END_REF][START_REF] Qu | Cooperative caching for multiple bitrate videos in small cell edges[END_REF] video single layer caching systems discrete [START_REF] Araldo | Representation Selection Problem : Optimizing Video Delivery through Caching[END_REF] video network of caches discrete [START_REF] Zhou | Adaptive offline and online similarity-based caching[END_REF] generic network of caches discrete this paper generic network of caches discrete/continuous In our work, similarly to [START_REF] Zhou | Adaptive offline and online similarity-based caching[END_REF], we focus mainly on the offline setting, i.e., the problem of statically placing objects in the caches so as to minimize the expected cost under known content request rates and routing. In contrast to [START_REF] Zhou | Adaptive offline and online similarity-based caching[END_REF], we first propose algorithms with guaranteed performance, and then we move to the continuous limit of the large requests/catalog space, where we investigate the structure of the optimal solution.

In the recent publication [START_REF] Tareq | Towards Inference Delivery Networks: Distributing Machine Learning with Optimality Guarantees[END_REF], one of the authors has proposed the idea of inference delivery networks, an Internet-wide architecture for fast delivery of machine learning predictions. Inference delivery networks can be seen as a particular network of similarity caches. Beside the focus on a specific application, reference [START_REF] Tareq | Towards Inference Delivery Networks: Distributing Machine Learning with Optimality Guarantees[END_REF] considers an adversarial request process for a finite number of possible objects (machine learning models in their case), while we focus on more common stochastic request process and consider both finite and infinite catalogs of objects.

In summary, our paper advances the state of art by providing a first analysis of networks of similarity caches in the same spirit of works devoted to networks of exact caches. Specifically, we focus on the offline setting and characterize the structure of the optimal solution in the large catalog regime.

Main assumptions and problem formulation

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 cache i can store up to k i objects.

We consider a network of caches with requests potentially arriving at every node. Some nodes can act as content repositories, where (a subset of) requests can be satisfied exactly or with a small approximation cost. Specifically, we assume that each request has at least one repository acting as 'authoritative server' for it, meaning that the approximation cost at the content repository is either zero or it is negligible as compared to the fixed cost to reach the repository (see next). Let K be the set of all nodes in the network (including caches and repositories).

A request r is a pair (o, i) where o is the requested object and i is the node where the request first enters the network. Every request is issued according to a Poisson process with rate λ r .

At each cache, for any two objects x and y in X there is a non-negative (potentially infinite) cost C a (x, y) to locally approximate x with y. We consider C a (x, x) = 0. We assume that caches can efficiently compute, upon arrival of a request for x, the closest stored object y. This is typically done resorting to locality sensitive hashing (LSH) [START_REF] Pandey | Nearest-neighbor Caching for Content-match Applications[END_REF].

Moreover, there is an additional retrieval cost h(i, j) to reach node j from cache i, which is assumed to increase as more and more hops need to be traversed by the request. Costs h(i, j) represent the additional penalty (in terms of network delay) incurred by requests, in addition to the approximation cost C a . If a request from i cannot be forwarded to cache j, then h(i, j) = +∞.

We call an approximizer α a pair (o , j), where object o has been placed at cache j. If a request r = (o, i) is served by object o at node j, it will incur a total cost C(r, α) = C a (o, o ) + h(i, j), that depends on how dissimilar o is from o and how far node i is from node j. For approximizers located at a content repository j, we take C(r, α) = h(i, j), neglecting the local approximation cost.

We assume that each cache knows how to route each request to a corresponding repository. Nevertheless, deciding if a request should be served locally or should be forwarded along the path to the repository is still a challenging problem to solve in a distributed way: while a relatively good approximizer can be found at a cache i, a better one may be located at an upstream cache j, justifying the additional cost h(i, j). This is in sharp contrast to what happens in exact caching network, where the forwarding operation is straightforward (a request is forwarded upon a miss).

In our initial investigation, we will suppose that optimal forwarding strategy is available at all caches, i.e., that each cache knows whether to solve a request locally or forward it towards the repository. This assumption is reasonable in two possible scenarios: i) when caches exchange metadata information about their stored objects (this is acceptable when content is static or quasi-static); ii) when the dominant component of the delay is content download, so that, prior to download, small request messages can go all the way up to the repository and back, dynamically finding the best approximizer along the path. We leave to future work the challenging case in which optimal forwarding is not available at the nodes.

A consequence of our assumptions is that each request r will be served minimizing the total cost, i.e., given S the initial set of approximizers at content repositories, and A the set of approximizers at the caches, we have

C(r, A) = min α∈A∪S C(r, α). (1)
In what follows we will 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 subset of R p and C a (x, y) = f (d(x, y)), where f : R + → R + is a non-decreasing non-negative function and d(x, y) is a metric in R p (e.g. the Euclidean one). This case is more suitable to describe objects characterized by continuous features, as in machine learning applications. For example, consider a query to retrieve similar images, as one can issue to images.google.com. The set of images the user may query Google for is essentially unbounded, and in any case it is larger than the catalog of images Google has indexed.

In the continuous case, we assume a spatial density of requests arriving at each cache defined by a Borel-measurable function λ x,i : X × K → R + , i.e., for every Borel set B ⊆ X , and every cache i ∈ K, the rate with which requests for objects in B arrive at node i is given by B λ x,i dx. We will refer to the above two instances as discrete and continuous, respectively.

Under the above assumptions, our goal is to find the optimal static allocation A that minimizes the expected cost C(A) per time unit (or per request, if we normalize the aggregate request arrival rate to 1):

C(A) r λ r C(r, A), discrete case i∈K X λ x,i C((x, i), A) dx, continuous case (2)
i.e., minimize

A C(A) subject to o:(o,i)∈A 1 ≤ k i , ∀i ∈ K (3)
Having mathematically formalized the problem, in the next section we take an algorithmic perspective to characterize and approximate its optimal solution.

Algorithms for the Discrete case

In this section, we restrict ourselves to the discrete scenario, as this allows us to make rigorous statements about NP-hardness and algorithms' complexity. This is an immediate consequence of the fact that, as shown in [16, Thm. III.1], the static off-line similarity caching problem is already NPhard for a single cache. Nevertheless, we will show in Sec. 5 that, when the cache network has a regular tree structure, a simple characterization of the optimal solution can be determined in the large catalog regime, by exploiting a continuous approximation.

NP-Hardness and Submodularity

Given the initial set S of objects allocated at content repositories, we want to pick an additional set A of objects and place them at the caches. Let I denote the set of possible allocations that satisfy cardinality constraints at each cache (corresponding to the constraints in ( 3)). Let G(A) quantify the caching gain [START_REF] Golrezaei | Femtocaching: Wireless video content delivery through distributed caching helpers[END_REF][START_REF] Ioannidis | Adaptive caching networks with optimality guarantees[END_REF] from allocation A in comparison to the case when each request needs to be served by its content repository, i.e.,

G(A) = C(∅) -C(A). (4)
Problem ( 3) is equivalent to the following maximization problem maximize A∈I G(A).

(

) 5
Proposition 4.2. The static off-line similarity caching problem in a network is a submodular maximization problem with matroid constraints.

The result does not rely on any specific assumption on C(r, α) but for the cost being non-negative. In particular, we can define C(r, α) to embed requests' routing constraints. For example, given a request r = (o, i), we can enforce the request to be satisfied by the repository of content o or by one of the caches on the routing path between node i and the repository (we denote it as P i,o ). This constraint can be imposed by selecting C((o, i), (o , j)) = ∞ for each j / ∈ P i,o . The proof is quite standard and we report it in A for completeness.

In the next subsections we introduce two different algorithms to deal in practice with the off-line similarity caching problem.

Greedy algorithm and its complexity

As Problem ( 5) is the maximization of a monotone non-negative submodular function with matroid constraints, the Greedy algorithm has 1/2 guaranteed approximation ratio, i.e., G(A Greedy ) ≥ 1 2 max A∈I G(A) [START_REF] Fisher | An analysis of approximations for maximizing submodular set functions-II[END_REF]. We mention that there exists also a randomized algorithm that combines a continuous greedy process and pipage rounding to achieve a 1 -1/e approximation ratio in expectation [START_REF] Calinescu | Maximizing a monotone submodular function subject to a matroid constraint[END_REF].

The Greedy algorithm proceeds from an empty allocation A = ∅ and progressively adds to the current allocation an approximizer in argmax α G(A∪ {α})-G(A) = argmax α r λ r (C(r, A)-C(r, A∪{α})) up to select i k i = K objects, where K is the total cache capacity in the network (by respecting local constraints at individual caches). The detailed pseudocode is reported in B.

Let O, O R , and N denote the number of objects in the catalog, the number of objects that can be requested, and the number of caches in the network. When choosing the i-th approximizer the greedy algorithms needs in general to evaluate ON -i + 1 possible approximizers, and how they reduce the cost for the set of requests with cardinality at most O R N . The time-complexity of the algorithm is then bounded by

K i=1 O R N (ON -i + 1) = O R N (ON K -K(K -1)/2).
A smart implementation can avoid to evaluate the gain of all possible approximizers at each step, but despite the optimizations, the Greedy algorithm would be too complex for catalogue sizes O beyond a few thousands of objects. Moreover, the set of possible requested objects O R may be much larger than O.

LocalSwap algorithm and its complexity

We now present a different algorithm, called LocalSwap, which is based on the simple idea to systematically move to states with a smaller expected cost (2). LocalSwap can be used both in an off-line and on-line scenario. It works as follows. At the beginning the state of caches is populated by random contents. Then, in the on-line scenario the algorithm adapts the cache state upon every request. In the off-line scenario, instead, a sequence of emulated requests is generated (satisfying the same statistical properties of the original arrival process), and applied to drive cache state changes. Let A t be the allocation obtained by the algorithm at iteration t. Upon an (emulated) request r for o, LocalSwap computes the maximum decrement in the expected cost that can be obtained by replacing one of the objects currently stored at some cache along the forwarding path with o, i.e., ∆C

min α∈At C(A t ∪ {r} \ {α}) -C(A t ).
• if ∆C < 0, then cache i e replaces content y e with content o, where (y e , i e ) ∈ arg min (y,i)∈At C(A t ∪ {(o, i)} \ {(y, i)});

• if ∆C ≥ 0, the cache allocation is not updated.

The detailed pseudocode is reported in C.

LocalSwap does not provide worst case guarantees as Greedy, but it asymptotically reaches a locally optimal cache configuration, defined as a configuration whose cost (2) is lower than the cost of all configurations that can be obtained by replacing just one content in one cache. On the contrary, Greedy does not necessarily reach a local optimal state (as we show below in Sect. 4.4). Proposition 4.3. For long enough request sequence LocalSwap converges with probability 1 to a locally optimal cache configuration.

LocalSwap generalizes a similar algorithm proposed in [START_REF] Garetto | Similarity caching: Theory and algorithms[END_REF] for a single cache (called there "greedy") with similar theoretical guarantees. Under the assumption that requests are optimally forwarded, the proof of Proposition 4.3 is essentially the same of [16, Thm. V.3], so we omit it. By clever data structure design, the computational cost of each iteration can be kept O(N O R ).

Remark 1. Note that by cascading Greedy and LocalSwap it is possible to achieve a locally optimal cache configuration whose approximation ratio is guaranteed to be at least 1/2 (i.e., G(A Greedy+LocalSwap ) ≥ 1 2 max A∈I G(A)).

Greedy and LocalSwap in a toy example

This example shows that 1) Greedy does not converge necessarily to a locally optimal cache configuration, and 2) there are both settings where Greedy finds the optimal cache configuration while LocalSwap may not, and settings where LocalSwap finds the optimal cache configuration while Greedy does not.

Consider a scenario with 5 contents

x i for 1 ≤ i ≤ 5. Let us assume that C a (x 2 , x 3 ) = C a (x 3 , x 4 ) = 0, C a (x 1 , x 2 ) = C a (x 4 , x 5 ) = > 0 1 , while C a (x i , x j ) = ∞ otherwise.
We want to solve the content placement problem for a single cache with k = 2 and λ x 3 > λ x 2 = λ x 4 > λ x 1 = λ x 5 . The cost to retrieve the objects from the remote server is h s > 2 . The optimal placement configuration is: {x 2 , x 4 }. Greedy will reach one of the following equivalent sub-optimal configurations {x 3 , x}, with x ∈ {x 1 , x 5 }. LocalSwap, on the contrary, will reach the optimal configuration {x 2 , x 4 } (because it is the unique locally optimal configuration). We observe that the configurations reached by Greedy are not locally optimal: for example if Greedy selects {x 3 , x 1 }, it is convenient to replace x 3 with x 4 .

If we consider two caches 1 and 2 in tandem, each of size k = 1 with requests arriving only to the first cache and retrieval cost equal to h(1, 2) if the object is retrieved from cache 2, and h(1, 2) + h s if it is retrieved by the server. The optimal configurations will maintain a similar structure for h(1, 2) small enough. In particular the optimal configurations will be: {(x 4 , 1), (x 2 , 2)} and {(x 2 , 1), (x 4 , 2)}. Greedy will still reach a state {(x 3 , 1), (x, 2)} with x ∈ {x 1 , x 5 }, while LocalSwap will reach an optimal state. For h(1, 2) large enough the optimal states become {(x 3 , 1), (x, 2)} with x ∈ {x 1 , x 5 } and both previous algorithms will succeed in reaching an optimal solution. At the same time there are settings for which the configurations {(x 3 , 1), (x 1 , 2)} and {(x 3 , 1), (x 5 , 2)} correspond to global minima, the configurations {(x 4 , 1), (x 2 , 2)} and {(x 2 , 1), (x 4 , 2)} correspond to local minima, and Greedy finds one of the first configurations, while Local-Swap may reach one of the second configurations. For example this is the case for h s = 1, h(1, 2) = = 4/9, λ 1 = λ 5 = 1, and λ 2 = λ 4 = 4/3 and any λ 3 > λ 2 .

The Continuous case

When O R is much larger than O, or O is itself very large, it makes sense to study the request space as continuous. Such continuous representation permits us to formulate a simplified optimization problem whose solution well approximates the optimal cost achieved in discrete scenarios with large catalog size.

If the number of objects in the catalog is finite, one could in principle devise a Greedy algorithm also for this case, working exactly as in the discrete case. Indeed the problem (3) can be easily shown to be still submodular even when requests lies over a continuous space. However, one now has to evaluate, for each possible candidate approximizer α to add to the current allocation, complex integrals over the infinite query space. It is not simple to define in general the complexity of such operations but it is evident that previous algorithmic approaches becomes rapidly unfeasible for large set of requests and/or large catalog.

Hereinafter, we will assume that both the request space and the catalog space are continuous.

Preliminary: continuous formulation for a single cache

As a necessary background, we summarize here some results obtained in [START_REF] Garetto | Similarity caching: Theory and algorithms[END_REF] for the case of a single cache with capacity k 1 . Let B r (y 0 ) be the closed ball of radius r around y 0 , i.e., the set of points y such that d(y, y 0 ) ≤ r. The authors of [START_REF] Garetto | Similarity caching: Theory and algorithms[END_REF] proved: Proposition 5.1. Under a homogeneous request process with intensity λ over a bounded set X , any cache state A = {y 1 , . . . , y k 1 }, such that, for some r, the balls B r (y h ) for h = 1, . . . , k 1 are a tessellation of X (i.e., ∪ h B r (y h ) = X and |B r (y i ) ∩ B d (y j )| = 0 for each i and j), is optimal.

Such regular tessellation exists, in all dimensions, under the norm-1 distance, and corresponds to the case in which balls are squares (assuming that k 1 such squares cover exactly the domain X ).

It is then immediate to analytically compute the optimal cost for this case. For example, in a two-dimensional domain (see Fig. 2), requests and the total cost is just C(A) = k 1 c(r). Equation ( 6) provides a simple close-form expression of the approximation cost, but it relies on the assumption that the request space is continuous. To assess the extent of the approximation, we compare it to the cost achieved in the case of a discrete request space, where requests (and catalog objects) are constrained to lie on the points of a L × L square with unitary step and wrap-around conditions.

For some special values of L, namely L = 1+2l(l+1), where l ∈ N , there exists a regular tessellation of the grid with L squares, each comprising L points. Figure 3 provides an example of such regular tessellation in the case l = 2, L = 13. When k 1 = L, the discrete versions of Proposition 5.1 allows us to conclude that storing in the cache the central object of each square is optimal, achieving the per-request approximation cost:

c grid (r) = l i=1 4i γ+1 L (7)
which can be understood by noticing that there are 4i points at hop distance i from the central object. The optimal cost as described by Equation [START_REF] Venugopal | Shadow puppets: Cloud-level accurate AI inference at the speed and economy of edge[END_REF] for these special discrete cases can be compared to the continuous approximation [START_REF] Guo | Foggycache: Cross-device approximate computation reuse[END_REF], where we need to set r = L/2, λ = 1/L. Figure 4 shows the result of this comparison as function of k 1 = L, for different values of γ. We observe that the continuous approximation is very good provided that the number of objects falling in each square is not too small (say larger than a few tens).

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 λ X i . Intuitively, the approximation becomes better and better the more λ x varies smoothly over each Voronoi cell of region i. This in particular occurs when λ x is smooth over the entire domain, and the cache size increases.

Under this approximation, let k i,1 be the number of cache slots devoted to region i (with the constraint that i k i,1 = k 1 ). Then, using standard constrained optimization methods, it is possible to determine the optimal value of k i,1 as function of the local request rate λ X i . Without loss of generality, we can assume that domain X is partitioned into M regions of unitary area, on which the request rate is approximately assumed to be constant and equal to λ i , 1 ≤ i ≤ M .

Then, focusing for simplicity on the two dimensional case when d(x, y)

is the norm-1, and C a (x, y) = d(x, y) γ , each cache slot is used to approximate requests falling in a square of area 1/k i,1 and radius r i = 1/(2k i,1 ). Following ( 6), the approximation cost c i within a square belonging to region i can be easily computed as:

c i (r i ) = 4λ i r γ+2 i γ + 2 = ζλ i k -γ+2 2 i,1 (8)
where ζ 2 (2-γ)/2 /(γ + 2). Hence the total approximation cost in the whole domain, which depends on the vector k of cache slots

k i,1 's, is C(k) = M i=1 k i,1 c i,1 (k i,1
). We select the values k that minimize the expected cost:

minimize k 1,1 ,...,k M,1 ζ M i=1 λ i k -γ/2 i,1 subject to M i=1 k i,1 = k 1 (9)
Employing the standard Lagrange method, one obtains that λ i k

-(γ+2)/2 i,1
equals some unique constant for any region i, which means that k i,1 has to be proportional to λ 2/(γ+2) i

. After some algebra we get:

min C(k) = ζk -γ/2 1 M i=1 λ 2 γ+2 i γ+2 2 . ( 10
)
In the limit of large M , we substitute the sum in [START_REF] Qu | Cooperative caching for multiple bitrate videos in small cell edges[END_REF] with an integral, obtaining:

min C(k) ≈ ζk -γ/2 1 X λ(x) 2 γ+2 dx γ+2 2 . ( 11
)
We observe that, when the distance is the norm-1, this approach from [16] can be extended to higher dimensions computing integrals similar to (6). 2 Under other distances, things are not as simple, but in principle one can determine the best partitioning of the domain into k 1 Voronoi cells 3 V i with center b i , such that

C(A) = i V i C a (x, b i ) dx (12)
is minimum, and store in the cache objects {b i } i . Similarly to [START_REF] Garetto | Similarity caching: Theory and algorithms[END_REF], we prefer to avoid such geometric complications, and stick for simplicity to the norm-1 case.

Chain topology

Here we extend the approach recalled in previous section to a chain network of N caches, where requests arrive at the leaf cache 1, and are possibly forwarded along the chain up to the node providing the best approximizer.

In a chain the cost incurred by request r for object x, served by approximizer

α = (o , j) is C(r, α) = C a (x, o )+h(1, j).
As request originates always at the leaf cache 1, we simplify the notation and denote h(1, j) by h j . We naturally assume h i > h j if i > j. The N -th cache in the chain is the repository, where the approximation cost is negligible. In the following formulas, we recover this situation considering that the last cache has infinite cache size. Let k i,j be the number of cache slots devoted by cache j to region i. Each of these slots is used to approximate requests falling in a square of area 1/k i,j and radius r i,j = 1/(2k i,j ). Hence the cost incurred by requests falling in a square of region i and served by cache j is:

c i,j (r i,j ) = 4 r i,j 0 r i,j -x 0 [(x + y) γ + h j ]λ i dy dx = 4λ i r γ+2 i,j γ + 2 + 2λ i r 2 i,j h j (13)
The cost C i,j incurred by all requests falling in region i and served by cache j, as function of k i,j , reads:

C i,j (k i,j ) = ζλ i k -γ 2 i,j + λ i h j (14)
In general a region i can be served by several caches along the path (every cache for which k i,j > 0). However observe that a single request (i.e., a point of the region) will be always served by one specific cache, cache j * with j * = argmin j C i,j (ties can be neglected). We encode previous property by introducing weights w i,j ∈ [0, 1], where w i,j represents the fraction of region i served exclusively by cache j. Let w j be the vector of {w i,j } i .

We obtain the optimization problem: minimize

w 2 ,...,w N ζk -γ/2 1 M i=1 1 - N j=2 w i,j λ 2 γ+2 i γ+2 2 + M i=1 1 - Z j=2 w i,j w i λ i h 1 + N j=2 ζk -γ/2 j M i=1 w i,j λ 2 γ+2 i γ+2 2 + M i=1 w i,j λ i h j subject to w i,j ≥ 0 ∀j > 1, ∀i N j=2 w i,j ≤ 1 ∀i (15)
where notice that we have separated the contribution of cache 1, and taken as decision variables vectors w j , with j > 1, since w 1 = 1 -N j=2 w j . Moreover, notice that the constraints in [START_REF]Multi-access edge computing[END_REF] are sufficient to guarantee that also the following obvious constraints hold:

w i,j ≤ 1 ∀j > 1, ∀i 0 ≤ w i,1 ≤ 1 ∀i
In this form, ( 15) is a convex minimization problem over a convex domain, thus it has a global minimum. Without loss of generality, let the M regions be sorted in increasing values of λ i . Employing the standard method of Lagrange multipliers, KKT conditions imply that the global optimum is attained when cache 1 handles all most popular regions region i > i * (i.e., w i,1 = 1, i > i * ), plus possibly a piece of region i * (if 0 < w i * ,1 < 1). Cache 1 does not allocate any slot to regions i < i * . Previous result allows us to prove the following interesting property about the structure of the optimal solution: Proposition 5.2. In the case of a chain topology, with requests arriving only at the first cache, the best solution of the continuous-domain, finite-M problem ( 15) is characterized by a set of popularity thresholds

λ * 0 = min{λ i } ≤ λ * 1 ≤ λ * 2 ≤ . . . ≤ λ * N -1 ≤ λ N = max{λ i },
such that cache j approximates all requests falling in regions i with λ * j-1 < λ i < λ * j , plus possibly a portion of a region with λ i = λ * j-1 , and a portion of a region with λ i = λ * j .

Proof. It is sufficient to apply the above property about the regions handled by cache 1, filtering out the requests handled by cache 1, and iteratively applying the same result to the request process forwarded upstream to caches 2, . . . , N .

When the set of popularity values is not finite, it is possible to extend the result in Proposition 5.2, letting M diverge. We partition X into N subdomains X j , j = 1, . . . , N , stacked in vector X , such that cache j handles only requests falling into domain X j , and we seek to minimize:

C(X ) = N j=1   ζk -γ/2 j X j λ(x) 2 γ+2 dx γ+2 2 + h j X j λ(x) dx   (16)
In principle we would like to find the best partitioning:

X * = arg min X C(X )
In this asymptotic case we can restate Proposition 5.2 as follows, providing a simpler and more elegant proof.

Proposition 5.3. In the case of a chain topology with requests arriving only at the first cache, the best partition X * is characterized by the following property: for any i < j, inf X * i λ(x) ≥ sup X * j λ(x). Proof. By contradiction, let us assume that we find two non negligible areas ∆X i ⊆ X * i and ∆X j ⊆ X * j such that: sup

∆X j λ(x) > inf ∆X i λ(x)
Then we can always find two non-negligible areas ∆X i ⊆ ∆X i and ∆X j ⊆ ∆X j such that we jointly have:

∆X i λ(x) 2 2+γ dx = ∆X j λ(x) 2 2+γ dx ( 17
)
and inf

∆X j λ(x) ≥ sup ∆X i λ(x) > 0 ( 18
)
Now let us see what happens if we 'swap' ∆X i with ∆X j , i.e., if we take a new partition X where

X i = (X * i \ ∆X i ) ∪ ∆X j and X j = (X * j \ ∆X j ) ∪ ∆X i . Note that by construction C(X ) = C(X * ) + (h j -h i ) ∆X i λ(x) dx + (h i -h j ) ∆X j λ(x) dx Therefore, since h j > h i , we have C(X ) ≤ C(X * ) if we can show that ∆X j λ(x) dx ≥ ∆X i λ(x) dx.
Denoted with β = 2/(2 + γ) < 1 we have:

∆X j λ(x) dx = ∆X j λ(x) β λ(x) 1-β dx ≥ ( inf ∆X j λ(x)) 1-β ∆X j λ(x) β dx = ( inf ∆X j λ(x)) 1-β ∆X i λ(x) β dx by (17)
≥ (sup

∆X i λ(x)) 1-β ∆X i λ(x) β dx by (18) = ∆X i (sup ∆X i λ(x)) 1-β λ(x) β dx ≥ ∆X i λ(x) 1-β λ(x) β dx = ∆X i λ(x) dx

Extension to equi-depth trees

Previous results obtained for the chain topology can be easily extended to trees with L leaves at the same depth D, where requests arrive only at the leaves and all caches at the same level have the same size. Let h D-j be the (equal) cost to reach the cache at level j starting from a leaf. We assume the spatial arrival rate at leaf to be given by λ (x) = β λ(x), for some constant β > 0, i.e., spatial arrival rates at different caches are identical after rescaling by a constant factor. Moreover arrival processes at different leaves are assumed to be independent. We will call equi-depth tree a cache network with the above characteristics. We naturally assume h i > h j if i > j.

Proposition 5.4. In an equi-depth tree the optimal cost is achieved by replicating the same allocation at each cache of the same level. The allocation to be replicated is the one obtained in the special case of a chain topology (L = 1).

Proof. Suppose to increase the number of nodes in the topology, creating a system of L parallel chain topologies. Each leaf now has an independent path towards a dedicated copy of the root node. By doing so the total cost in the system of parallel chains is surely not larger than the total cost achievable in the original tree, and, in general, it might be smaller (this because we can independently place objects in every chain so as to minimize the cost induced by the requests arriving at the corresponding leaf). On the other hand, the optimal allocation on each chain is the same, since the objective function in ( 15) is linear with respect to parameter β . Therefore, by adopting such equal allocation on each cache of the same level in the original tree, we obtain exactly the same total cost achieved in the system of parallel chains, hence this allocation is optimal.

One crucial assumption of chain topologies (and equi-depth trees) is that requests arrive only at the leaf (leaves). In the next section we discuss what happens when this assumption does not hold, considering the simplest possible case with just two caches.

A tandem network with arrivals at both nodes

In general cache networks that do not belong to the class of equi-depth trees, the simple optimal structure described in Proposition 5.2 is, unfortunately, lost. To see why, it is sufficient to consider the simple case of a tandem network with two identical caches (hereinafter called the leaf and the parent), where the same external arrival process λ(x) of requests arrives at both nodes (see scenario 2 in Figure 7). Now, let us suppose that the cost h to reach the parent from the leaf is large (but it does not need to be disproportionally large). Then the leaf will not find particularly convenient to forward its requests to the parent, unless maybe for objects very close to the ones stored in the parent (whichever they are). On the other hand, the parent has to locally approximate all requests, hence it will need to adequately cover the entire domain X like an isolated cache. As a consequence, we do not expect any clear separation of X into a sub-domain handled by the leaf, and a sub-domain handled by the parent. In particular, the property that we had before, according to which a single cache has to allocate slots to cover a particular region of the domain, does not hold anymore.

A more formal explanation of what happens in this simple case can be provided by the following model. Again, we divide the domain, both at the leaf and at the parent cache, into M regions of unitary area. The request rate over each region is assumed to be constant and we denote it by λ i and βλ i for the leaf and the parent cache, respectively (hence by setting β = 0 we can recover previous case in which requests arrive only at the leaf). Let k i,1 and k i,2 be the number of slots devoted to region i by the leaf and the parent node, respectively. Notice that now both quantities are in general different from zero. The leaf node will forward to the parent the requests falling in a fraction (1 -w i,1 ) of region i, and it is natural to assume that these requests are those falling farther from the locally stored objects, i.e., at a distance larger than r * 1,i = √ w 1,i r 1,i , where r 1,i = 1/(2k i,1 ). Therefore the approximation cost ( 14) is changed to:

C i,1 (k i,1 , w i,1 ) = ζλ i w i,1 γ+2
2 k i,1 -γ 2 . ( 19
)
Requests forwarded to the parent cache will experience an additional movement cost h, plus a local approximation cost at the parent, that we model by assuming that the total area of the subregion forwarded to the parent cache k i,1 2r 2 1,i (1 -w 1,i ) will be served by the k i,2 points at the parent, within squares of radius:

k i,1 r 2 i,1 (1 -w i,1 ) k i,2 = 1 -w i,1 2k i,2 (20)
Moreover, at the parent cache the local requests will generate an approximation cost similar to (14) (with no retrieval cost). The total approximation cost in the network is then:

C(A) = ζ M i=1 λ i w i,1 γ+2
2 k i,1 -γ 2 + ζ M i=1 λ i (β + (1 -w i,1 ) γ+2 2 )k i,2 -γ 2 + h M i=1 λ i (1 -w i,1 ). ( 21
)
This cost should be minimized over {w i,1 } i , {k i,1 } i , and {k i,2 } i . By finding the optimal values for {k i,1 } i and {k i,2 } i given {w i,1 } i , we get

C(w) = ζk -γ 2 1 M i=1 λ 2 2+γ i w i,1 2+γ 2 + ζk -γ 2 2 M i=1 λ 2 2+γ i (β + (1 -w i,1 ) γ+2 2 ) 2 2+γ 2+γ 2 + h M i=1 λ i (1 -w i,1 ). ( 22
)
Note that for β = 0 we recover the cost resulting from [START_REF]Multi-access edge computing[END_REF] in the case of a tandem network. Computing the derivative of the above cost with respect to w i,1 we get:

∂C(w) ∂w i,1 = ζk -γ 2 1 γ + 2 2 M i=1 λ 2 2+γ i w 1,i γ 2 λ 2 2+γ j -ζk -γ 2 2 γ + 2 2 M i=1 λ 2 2+γ i (β + (1 -w 1,i ) γ+2 2 ) 2 2+γ γ 2 × λ 2 2+γ j (1 -w 1,j ) γ 2 (β + (1 -w 1,j ) γ+2 2 ) γ 2+γ -hλ j . (23)
Imposing the optimality conditions, we find that there may be multiple regions with different popularities λ i for which w 1,i * ∈ (0, 1), i.e., for which the leaf forwards part of the requests to the parent. The structure of the solution in Proposition 5.2 might be lost, leading to optimal allocations where both caches handle portions of the same region.

To shed light into this phenomenon, we have further investigated the special case in which λ is uniform over the whole domain. In this case it is convenient to shift over space the two regular tessellations so that the centroids at the leaf and at the parent are as far as possible, as shown in Fig. 5. This allows the leaf to forward the requests farthest from its centroids to the parent, where they are better approximated.

Requests arriving at the leaf are approximated by the leaf in the red portion of the domain, as depicted in Fig. 5, while they are approximated by the parent in the green portion of the domain. Distance z (in Fig. 5) that defines the separation between the two portions can be easily computed (for γ = 1) as z = max{0, (r -h)/2}, where r is the radius of the square of each tessellation (note that if h > r requests are not forwarded from the leaf to the parent). Then one can easily compute the reduction ∆c = 8 3 z 3 in the approximation cost for requests arriving at the leaf, provided by each slot of the second cache, and compute the resulting overall approximation cost (the approach can be generalized to γ = 1, but we omit the details here).

NetDuel: an online dynamic policy

Although in our work we have focused on the static, offline problem of content allocation at similarity caches, we have also devised an online, λunaware dynamic policy NetDuel, which is a networked version of policy z Figure 5: Optimal allocation in the tandem network with uniform arrival process at both nodes. Red areas denote the portion of the domain approximated by red centroids to be stored at the leaf cache. Green areas denote the portion of the domain approximated by green centroids to be stored at the parent cache.

Duel we have proposed in [START_REF] Garetto | Similarity caching: Theory and algorithms[END_REF]. At high-level, it is based on the following idea: each (real) content currently is the cache is paired to a (virtual 4 ) content competing with it. The cumulative saving in the total cost produced by the real and the virtual objects are observed over a suitable time window, and if the saving of the virtual object exceeds the saving of the real one by a sufficient amount, the virtual replaces the real in the cache. Otherwise, at the end of the observation window, the virtual object is discarded, and afterwards the real object will be paired to a new virtual object taken from the arrival process. In contrast to Greedy and LocalSwap, NetDuel does not require information about object arrival rates {λ r } r , and converges more slowly because it needs to estimate such rates from the arrival process itself. On the other hand, it can automatically adapt to dynamic object popularity.

NetDuel achieves an allocation close to the optimal one, suggesting that effective online dynamic policies can be devised for networks of similarity caches, at least under the assumption that each node knows when to forward requests upstream.

7 Numerical experiments

Methodology

We implemented using the C language the Greedy algorithm and the computation of the continuous approximation [START_REF]Multi-access edge computing[END_REF]. To run LocalSwap and NetDuel, instead, we developed an an-hoc event driven simulator, again using the C language, taking as input either a synthetically generated stream of requests, or an actual trace. Our simulator can consider an arbitrary treelike topology, though all of our experiments were performed an a simple tandem network of two nodes. 5

Synthetic arrival process

To test our algorithms, we consider 10000 objects falling on the points of a bi-dimensional L × L grid with L = 100, equipped with the norm-1 metric and the local cost C a (x, y) = d(x, y), i.e., we take (unless otherwise specified) γ = 1. The request process follows a Gaussian distribution, such that 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. To jointly test our continuous approximations, we assume that each grid point i is the center of a small square of area 1, on which λ is assumed to be constant and equal to λ i .

We first consider a simple tandem network with arrivals only at the leaf, and fixed cost h to reach the parent (scenario 1 in Fig. 7). In Fig. 6 we compare the total cost produced by Greedy, LocalSwap, the continuous approximation (the solution of ( 15)) and NetDuel, as function of h, for a larger Gaussian (σ = L/2) or a narrow Gaussian (σ = L/8). We observe that LocalSwap performs better than Greedy, which performs better than NetDuel. The continuous approximation does not necessarily provide a lower bound to discrete algorithms/policy, since it is a different system where the request space is continuous, rather than constrained on the grid points. However, we do observe that the continuous approximation curve gets closer to the curve produced by LocalSwap for σ = L/2 (thick curves), since in this case λ varies more smoothly over the domain.

In Fig. 8 we show the allocations (circles for the parent, triangles for the leaf) produced by the four approaches above in the case σ = L/8 and h = 3, using two different colors for the sub-domains where requests arriving at the user requests user requests h h user requests (scenario 1) (scenario 2)

Figure 7: Simple tandem networks with two identical caches, with arrivals only at the leaf (scenario 1 on the left), or with arrivals at both caches (scenario 2 on the right). Requests forwarded from the leaf to the parent cache incur the additional fixed cost h. leaf are approximated by the leaf or the parent. 6 7 While our algorithms are completely oblivious to the threshold-based solution predicted by the continuous approximation, they achieve, qualitatively, the same cache allocation structure. Differences emerge at the boundary between the area served by the leaf and the area served by the parent, and are more evident for Greedy and NetDuel. Next, we see what happens when the crucial assumption underlying the above structure, namely, the fact that requests arrive only at the leaf, is removed.

Greedy LocalSwap

In Fig. 9 we report, for a larger system with 100000 contents, the allocation produced at the parent by LocalSwap in a tandem network with requests arriving at both nodes (scenario 2 in Fig. 7), showing also with two different colors the regions where requests arriving at the leaf are approximated by the leaf or the parent. We consider both a Gaussian arrival process with σ = L/8 (left plot), and a simple Uniform process (right plot), and fixed h = 3. Notice that the parent cache covers also the central part of the domain, in contrast to Fig. 8. Results produced by LocalSwap suggest that now, for the requests arriving at the leaf, the regions served directly by the leaf and the regions approximated by the parent are intertwined in a complex way. For uniform λ, Fig. 10 shows the accuracy of the continuous approximation based on the shifted regular square tessellations shown in Fig. 5.

Amazon trace

By crawling the Amazon web-store, the authors of [START_REF] Mcauley | Image-based recommendations on styles and substitutes[END_REF] built an image-based dataset of users' preferences for millions of items. Using a neural network pre-trained on ImageNet, each item is embedded into a d-dimensional space, on which Euclidean distance is used as item similarity. We consider as request process the timestamped reviews left by users for the 10000 most popular items belonging to the baby category, with d = 100. The resulting trace, containing about 10.3M requests, is fed into a cache of size 100, with a parent cache of the same size (a tandem network) reachable by paying an additional fixed cost h = 150. The local approximation cost is set equal to the Euclidean distance.

In Fig. 11 we show the allocations produced by LocalSwap in both caches, reporting, for each stored item, the popularity rank (x axes) and the distance from the baricenter (y axes). Across the entire catalog we found no correlation between popularity rank and distance from the baricenter. Nevertheless, we do observe that the leaf cache tends to store items that are either very popular or very close to the baricenter. The resulting total cost is C = 266 (left plot in Fig. 11).

Moreover, by computing the request density within spherical shells at distance d ∈ [ρ, ρ + 1] from the baricenter, we found a decreasing trend in Then G(A) = r max α∈A M r,α , where M r,α ≥ 0 for all r and α. The set function is obviously monotone (i.e., if A ⊂ B, then G(A) ≤ G(B)) and nonnegative and corresponds to the utility of a facility location problem that is known to be submodular (e.g., [START_REF] Krause | Submodular Function Maximization[END_REF], but it is also easy to check directly).

B Pseudocode of Greedy algorithm

After an initial initialization corresponding to the empty allocation (lines 1-3), the algorithm performs K steps (line 4), where K is the total cache capacity in the network. In each step, we consider the addition of any possible approximizer at each cache, i.e., an approximizer not already present in a cache which has not yet been filled up (line 6), searching for the one that minimizes the total cost resulting from the addition of the considered approximizer (line 7). Then we add the found approximizer to the current allocation (lines 14-16), and proceed to the next step.

C Pseudocode of LocalSwap algorithm

We start from a random allocation of objects at the caches (line 1), and perform at most max iter noimprov attempts to improve the current allocation, where max iter noimprov is a parameter of the algorithm, to be Algorithm 1 Greedy Require: cache sizes k i , ∀i ∈ K, arrival rates {λ r } r , ∀r, costs C(r, α), ∀(r, α)

1: A = ∅ Initialize set of approximizers 2: O i = ∅, ∀i ∈ K Initialize set of allocated objects in each cache 3: a i = 0, ∀i ∈ K Initialize number of allocated objects in each cache 4: for i = 1 . . . K do end for

14:

A ⇐ A ∪ (o * , i * )

15:

O i * ⇐ O i * ∪ o * 16:
a i * ⇐ a i * + 1 17: end for 18: return A Final set of approximizers chosen sufficiently large to achieve convergence. In each attempt, we consider a real or emulated request for an object o (line 4), and evaluate what would happen if: i) we evict an object y from a cache i along the forwarding path of o; ii) insert o at cache i in place of y. By considering all possible substitutions as above (line 6), we compute the largest possible negative variation ∆C * in the total network cost (line 8-11) keeping track of the substitution that produces such variation (line 10). If we indeed obtain a negative variation (line 13) (note that ∆C is initialized to zero on line 5), we actually perform the corresponding substitution (line 14).

Algorithm 2 LocalSwap

Require: parameter max iter noimprov, cache sizes {k i } i , arrival rates {λ r } r , ∀r, costs C(r, α), ∀(r, α) 1: Allocate k i distinct random objects in each cache Initialize A 2: iter = 0 3: while iter < max iter noimprov do for all α = (y, i) ∈ A do (y e , i e ) ⇐ (y, i)

Figure 1 :

 1 Figure 1: Application of similarity caching to Mobile Edge Computing.

Proposition 4 . 1 .

 41 The static off-line similarity caching problem in a network (3) is NP-hard.

rFigure 2 :

 2 Figure 2: Perfect tessellation with square cells in a two-dimensional domain, under the norm-1 distance.

Figure 3 :

 3 Figure 3: 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 homogeneous request process.

Figure 4 :

 4 Figure 4: Per-request approximation cost as function of k 1 = L, for different values of γ, under uniform request process. Comparison between continuous request space (lines) and discrete request space (marks).

Figure 6 :

 6 Figure 6: Total cost obtained by Greedy, LocalSwap, continuous approximation and NetDuel in a tandem network with arrivals at the leaf, for σ = L/2 (thick curves) or σ = L/8 (thin curves).

Figure 8 :

 8 Figure 8: Allocations obtained by Greedy, LocalSwap, continuous approximation and NetDuel in the tandem network with σ = L/8, h = 3. Circle marks for the parent cache and triangle marks for the leaf cache.

Figure 9 :

 9 Figure 9: Parent allocation obtained by LocalSwap in a tandem network with arrivals at both nodes. Gaussian traffic (left plot) and Uniform traffic (right plot).

Figure 10 :

 10 Figure 10: Total cost in the tandem network with arrivals at both nodes, λ uniform, as function of h, for different values of γ, according to LocalSwap (points) and continuous approximation (curves).

Figure 11 :

 11 Figure 11: Allocations obtained by LocalSwap in a tandem network with arrivals at the leaf according to Amazon trace. Unconstrained version (left) and constrained version (right).

Figure 12 :

 12 Figure 12: Density of requests of Amazon trace within spherical shells at distance d ∈ [ρ k , ρ k+1 ] from the baricenter.

6 :

 6 for all α = (o, i) : o / ∈ O i , a i < k i do 7:C * = r λ r C(r, A ∪ {α}) cost resulting from addition of α

4 :

 4 generate request for object o according to {λ r } r real or emulated

7 :

 7 ∆C * = C(A ∪ {(o, i)} \ {(y, i)}) -C(A)

Table 1 :

 1 Schematic summary of previous work on similarity caching.

feasible only on small-scale systems. Table 1 offers a schematic summary of previous work.

All costs are assumed to be symmetric.

In the d dimensional case we have c(r) = a d λr γ+d , for an appropriate constant a d .

This task is not hard when the domain X can be exactly partitioned into k1 Voronoi cells of the same shape. Otherwise, for sufficiently large cache sizes, one can neglect border effects and approximately consider k1 Voronoi cells of the same shape covering the entire domain.

The cache stores only metadata of a virtual object, not the object itself. Virtual objects are taken from the arrival process.

The code is available from the authors upon request.

For the continuous approximation, we do not show stored contents, and (border) squarelets are considered as handled exclusively by the parent if wi,2 > wi,1.

On an Intel i7 desktop computer equipped with

8GB of DDR4 RAM, the running time of Greedy, LocalSwap and NetDuel to produce the allocations in Fig.8were, respectively, 3 minutes, 5 minutes and 12 minutes.

ρ, see Fig. 12, which justifies the attempt of 'enforcing' the structure of the optimal solution that we found in chain topologies fed only from the leaf. We do so by constraining the leaf (parent) cache to store only contents at distance from the baricenter smaller (larger) than a given threshold d * . The constrained LocalSwap algorithm obtains, for the best possible d * = 350, a total cost C = 269 (only 1% worse than before), right plot in Fig. 11, suggesting that a simple allocation and forwarding rule based on the distance from the baricenter is close to optimal also in a realistic scenario.

Conclusions and future work

In this paper we have made a first step into the analysis of networks of similarity caches, focusing on the offline problem of static content allocation. Despite the NP-hardness of the problem, effective greedy algorithms can be devised with guaranteed performance, but their implementation become prohibitive as the system size increases. For very large request space/catalog size, we have relaxed the problem to the continuous, obtaining for equi-depth tree topologies an easily implementable solution with a simple structure, which greatly simplifies the related request forwarding problem. The above simple structure is unfortunately lost in more general networks. We have also proposed a first online dynamic policy, NetDuel, whose effectiveness is confirmed by preliminary simulation results. More experiments under both synthetic and real traces could be done to confirm the findings of our preliminary assessment of proposed algorithms and policies.

Future work will focus on: i) the design of practical, scalable algorithms which can deal with similarity caching network having general topology, and large catalog size; ii) the investigation of simple request forwarding strategies for the online setting, in the absence of complete information about which items are stored in upstream caches; iii) the extension of algorithms and policies to the case in which multiple (e.g., the m closest) approximating objects are needed, so as to offer several alternatives to the user; iv) additional numerical experiments under synthetic and real traces.