Rachid Guerraoui

Anne-Marie Kermarrec

Olivier Ruas

François Taïani

Fingerprinting Big Data: The Case of KNN Graph Construction

Keywords: KNN graphs, fingerprint, similarity graphes KNN, empreinte numérique, similarités

We propose fingerprinting, a new technique that consists in constructing compact, fast-to-compute and privacy-preserving binary representations of datasets. We illustrate the effectiveness of our approach on the emblematic big data problem of K-Nearest-Neighbor (KNN) graph construction and show that fingerprinting can drastically accelerate a large range of existing KNN algorithms, while efficiently obfuscating the original data, with little to no overhead. Our extensive evaluation of the resulting approach (dubbed GoldFinger) on several realistic datasets shows that our approach delivers speedups of up to 78.9% compared to the use of raw data while only incurring a negligible to moderate loss in terms of KNN quality. To convey the practical value of such a scheme, we apply it to item recommendation, and show that the loss in recommendation quality is negligible.

Introduction

Overcoming the machine learning cost barrier

Today's ever growing volumes of data have prompted the development of increasingly powerful learning and analysis platforms [START_REF] Li | Scaling distributed machine learning with the parameter server[END_REF]. Our own experience within a start-up active in this area is that, unfortunately, the cost of running these solutions (whether in a cloud or on dedicated servers) can rapidly become a substantial drag for small businesses. As a result, small companies cannot often expect to recoup the cost of high-end machine-learning techniques running on well-provisioned machines. They have paradoxically more data than they can economically fully exploit.

To overcome this cost barrier we propose a strategy we have called big data fingerprinting. Our approach rapidly reduces the size of data into a compact and efficient binary format that becomes tractable to process on small machines. As an additional benefit, our solution also obfuscates the original clear-text information, at no additional cost. This obfuscation brings useful protection against the privacy risks associated with sensitive data that many organizations must address.

In this paper, we illustrate the potential of our approach on the emblematic problem in big data of K-Nearest-Neighbor (KNN) graph computation.

K-Nearest-Neighbor (KNN) graphs

K-Nearest-Neighbor (KNN) graphs1 play a fundamental role in many big data applications, including search [START_REF] Bai | Gossiping personalized queries[END_REF][START_REF] Bertier | The gossple anonymous social network[END_REF], recommendation [START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF][START_REF] Levandoski | Lars: A location-aware recommender system[END_REF][START_REF] Linden | com recommendations: Itemto-item collaborative filtering[END_REF] and classification [START_REF] Nodarakis | Rapid aknn query processing for fast classification of multidimensional data in the cloud[END_REF]. A KNN graph is a directed graph of entities (e.g., users, documents etc.), in which each entity (or node) is connected to its k most similar counterparts or neighbors, according to a given similarity metric. In many applications, this similarity metric is computed from a second set of entities (termed items) associated with each node in a bipartite graph (often extended with weights, such as ratings or frequencies). For instance, in a movie rating database, nodes are users, and each user is associated with the movies (items) she has already rated [START_REF] Harper | The movielens datasets: History and context[END_REF].

Being able to compute a KNN graph efficiently is crucial in situations that are constrained, either in terms of time or resources. This is the case of real time 2 web applications, such as news recommenders and trending services, that must regularly recompute their suggestions in short intervals on fresh data to remain relevant. This is also the case of privacy-preserving personal assistants executing learning tasks on personal devices with limited resources [START_REF]Snips: The ai platform for voice-enabled devices[END_REF].

Computing an exact KNN graph rapidly becomes intractable on large datasets: under a brute force strategy, a dataset with few thousands of nodes requires tens of billions of similarity computations. Many applications, however, only require a good approximation of the KNN graph [START_REF] Keeton | Lazybase: freshness vs. performance in information management[END_REF][START_REF] Labrinidis | Exploring the tradeoff between performance and data freshness in database-driven web servers[END_REF]. Recent KNN construction algorithms [START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF][START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF] have therefore sought to reduce the number of similarity computations by exploiting a greedy strategy. These approaches start from an initial random graph that is iteratively refined towards an approximate nearest neighbors (ANN) graph. These techniques are among the most efficient to date, but they seem to have reached their limits, and it is now difficult to see how to further reduce the number of comparisons pursuing this paradigm.

Fingerprinting Big Data for space and speed

In this paper, rather than reducing an algorithm's complexity (e.g. by decreasing the number of similarity computations), we propose to pursue an orthogonal strategy that is motivated by the system bottlenecks created by Big Data algorithms: large amounts of data not only stress complex algorithms, they also choke the underlying computation pipelines these algorithms execute on. To avoid these costs, we argue that one should avoid the extensive, and often explicit, representation of Big Data, and work instead on a compact, binary, and fast-to-compute representation (i.e. a fingerprint) of the entities of a dataset.

Instantiated in the context of KNN graph construction, we propose to fingerprint the set of items associated with each node into what we have termed a Single Hash Fingerprint (SHF), a 64-to 8096-bit vector summarizing a node's profile. SHFs are very quick to construct, they protect the privacy of users by hiding the original clear-text information, and provide a sufficient approximation of the similarity between two nodes using extremely cheap bit-wise operations. We use these SHFs to rapidly construct KNN graphs, in an overall approach we have dubbed GoldFinger. GoldFinger is generic and efficient: it can be used to accelerate any KNN graph algorithm relying on Jaccard index, at close to no overhead, and can be tuned to trade space and time for accuracy.

Contributions

In this paper we make the following contributions:

• We propose a formal analysis of GoldFinger's estimation mechanism.

• We formally analyze the privacy protection properties of GoldFinger in terms of k-anonymity and -diversity.

• We extensively evaluate our approach on a range of state-of-the-art KNN graph algorithms such as Locality Sensitive Hashing (LSH), on six representative datasets. We show that GoldFinger is able to deliver speedups of up to 78.9% against existing approaches, while incurring a small loss in terms of quality.

• As a case-study, we use the constructed graphs to produce recommendations, and show that despite the small loss in KNN quality, there is close to no loss in the quality of the derived recommendations.

In the following, we first present the context of our work and our approach (Sec. 2). We then present our evaluation procedure (Sec. 3) and our results (Sec. 4); we report on factors impacting our approach (Sec. 5), before discussing related work (Sec. 6), and concluding (Sec. 7).

Inria 2 Problem, Intuition, and Approach

For ease of exposition, we consider in the following that nodes are users associated with items (e.g. web pages, movies, locations), without loss of generality.

Notations and problem definition

We note U = {u 1 , ..., u n } the set of all users, and I = {i 1 , ..., i m } the set of all items. The subset of items associated with user u (a.k.a. its profile) is noted P u ⊆ I. P u might contain for instance the web pages visited by u, and is generally much smaller than I (the universe of all items). Our objective is to approximate a k-nearest-neighbor (KNN) graph over U (noted G KNN ) according to some similarity functions sim computed over user profiles:

sim : U × U → R (u, v) sim(u, v) = f sim (P u , P v ).
f sim may be any similarity function over sets that is positively correlated with the number of common items between the two sets, and negatively correlated with the total number of items present in both sets. These requirements cover some of the most commonly used similarity functions in KNN graph construction applications, such as cosine or Jaccard's index. We use Jaccard's index in the rest of the paper [START_REF] Van Rijsbergen | Information retrieval[END_REF]. Formally, a KNN graph G KNN connects each user u ∈ U with a set knn(u) of k other users that maximize the similarity function sim(u, -) :

knn(u) ∈ argtop k v∈U \{u} f sim (P u , P v ) (1)
where argtop k returns the set of k-tuples of U \{u} that maximize the similarity function sim(u, -) 3 .

Computing an exact KNN graph is particularly expensive: a brute-force exhaustive search requires O(|U | 2 ) similarity computations. Many scalable approaches therefore seek to construct an approximate KNN graph G KNN , i.e., to find for each user u a neighborhood knn(u) that is as close as possible to an exact KNN neighborhood [START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF][START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF]. The meaning of 'close' depends on the context, but in most applications, a good approximate neighborhood knn(u) is one whose aggregate similarity (its quality) comes close to that of an exact KNN set knn(u).

We capture how well the average similarity of an approximated graph G KNN compares against that of an exact KNN graph G KNN with the average similarity of G KNN :

avg_sim( G KNN ) = E (u,v)∈U 2 : v∈ knn(u) f sim (P u , P v ), (2)
i.e. the average similarity of the edges of G KNN . We then define the quality of The cost of computing Jaccard's index between explicit user profiles is relatively high (a few ms) for average-size profiles. Cost averaged over 4.9 millions computations between randomly generated profiles on a Intel Xeon E5420@2.50GHz.

G KNN as quality( G KNN ) = avg_sim( G KNN ) avg_sim(G KNN ) . (3
A quality close to 1 indicates that the approximate neighborhoods have a quality close to that of ideal neighborhoods, and can replace them with little loss in most applications.

With the above notations, we can summarize our problem as follows: for a given dataset (U, I, (P u ) u∈U ) and item-based similarity f sim , we wish to compute an approximate G KNN in the shortest time with the highest overall quality.

Intuition

A large portion of a KNN graph's construction time often comes from computing individual similarity values (up to 90% of the total construction time in some recent approaches [START_REF] Boutet | Being prepared in a sparse world: the case of knn graph construction[END_REF]). This is because computing explicit similarity values on even medium-size profiles can be relatively expensive. For instance, Figure 1 shows the time required to compute Jaccard's index

J(P 1 , P 2 ) = |P 1 ∩ P 2 | |P 1 ∪ P 2 |
between two random user profiles of the same size. The profiles are randomly selected from a universe of 1000 items, and the measures taken on an Intel Xeon E5420@2.50GHz. The cost of computing a single index is relatively high even for medium-size profiles: 2.7 ms for two random profiles of 80 items, a typical profile size of the datasets we have considered. Earlier KNN graph construction approaches have therefore sought to limit the number of similarity computations [START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF][START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF]. They typically adopt a greedy strategy, starting from a random graph, and progressively converging to a better KNN approximation by navigating neighbor-of-neighbor relationships. They only perform a fraction of the similarity computations required by an exhaustive search, show a high memory locality, and are easily parallelizable, but it is now difficult to see how their greedy component could be further improved.

In order to overcome the inherent cost of similarity computations, we therefore propose to target the data on which computations run, rather than the Inria algorithms that drive these computations. This strategy stems from the observation that explicit datastructures (hash tables, arrays) incur substantial costs.

To avoid these costs, we advocate the use of fingerprints, a compact, binary, and fast-to-compute representation of data.

Our intuition is that, with almost no overhead, fingerprints can capture enough of the characteristics of the data to provide a good approximation of similarity values, while drastically reducing the cost of computing these similarities.

GoldFinger and Single Hash Fingerprints

Our approach, dubbed GoldFinger, extracts from each user's profile a Single Hash Fingerprint (SHF for short). An SHF is a pair (B, c) ∈ {0, 1} b × N comprising a bit array B = (β x ) x∈ 0..b-1 of b bits, and an integer c, which records the number of bits set to 1 in B (its L1 norm, which we call the cardinality of B in the following). The SHF of a user's profile P is computed by hashing each item of the profile into the array and setting to 1 the associated bit

β x = 1 if ∃e ∈ P : h(e) = x, 0 otherwise, c = (β x ) x 1
where h() is a uniform hash function from all items to 0..b-1 , and • 1 counts the number of bits set to 1.

Benefits in terms of space and speed

The length b of the bit array B is usually much smaller than the total number of items, causing collisions, and a loss of information. This loss is counterbalanced by the highly efficient approximation SHFs can provide of any set-based similarity. The Jaccard's index of two user profiles P 1 and P 2 can be estimated from their respective SHFs (B 1 , c 1 ) and (B 2 , c 2 ) with

J(P 1 , P 2 ) = B 1 AND B 2 1 c 1 + c 2 -B 1 AND B 2 1 , (4)
where B 1 AND B 2 represents the bitwise AND of the bit-arrays of the two profiles. This formula exploits two observations that hold generally with no or few collisions in the bit arrays (a point we return to below). First, the size of a set of items P can be estimated from the cardinality of its SHF (B P , c p ):

|P | ≈ B P 1 = c p . (5)
Second, the bit array B (P1∩P2) of the intersection of two profiles P 1 ∩ P 2 can be approximated with the bitwise AND of their respective bit-arrays, B 1 and B 2 :

B (P1∩P2) ≈ (B 1 AND B 2 ). (6)
Equation ( 4) combines these two observations along with some simple set algebra (|P

1 ∪ P 2 | = |P 1 | + |P 2 | -|P 1 ∩ P 2 |
) to obtain the final formula. The computation incurred by ( 4) is much faster than on explicit profiles, and is independent of the actual size of the explicit profiles. This is illustrated in Table 1 which shows the computation time of Eq. ( 4) on the same profiles as Figure 1 for SHFs of different lengths (as in Fig. 1, the values are averaged over 4.9 millions computations). For instance, estimating Jaccard's index between two SHFs of 1024 bits (the default in our experiments) takes 0.120 ms, a 23-fold speedup compared to two explicit profiles of 80 items.

The link with Bloom Filters and collisions SHFs can be interpreted as a highly simplified form of Bloom filters, and suffer from errors arising from collisions, as Bloom filters do. However, the two structures serve different purposes: whereas Bloom filters are designed to test whether individual elements belong to a set, SHFs are designed to approximate set similarities (in this example Jaccard's index). Bloom filters often employ multiple hash functions to minimize false positives. By contrast, multiple hash functions increase single-bit collisions, and therefore degrade the approximation provided by SHFs.

2.4 Formal analysis of the Jaccard estimator J(P 1 , P 2 )

For readability in this section, we will generally treat bit arrays (i.e. belonging to {0, 1} n ) as sets of bit positions (belonging to P( 0, b -1 )). We will also note B X the set of bits set to 1 by the (sub)profile P X : B X = h(P X ).

For two given profiles P 1 and P 2 , the distribution of J(P 1 , P 2 ) is governed by how the random hash function h maps the items of P 1 and P 2 unto the bit positions 0, b -1 . The analysis of this random mapping is made simpler if we distinguish between the items that are present in both P 1 and P 2 (P ∩ = P 1 ∩ P 2 ) from those are unique to P 1 (resp. P 2 ), noted P ∆1 = P 1 \ P ∩ (resp. P ∆2 = P 2 \ P ∩ ). These three sets are represented by the three top rectangles of Figure 2.

P ∩ , P ∆1 , and P ∆2 are disjoint by definition, but their bit images B ∩ , B ∆1 , and B ∆2 by h (shown as circles in Figure 2) are typically not, because of collisions.

To analyze these collisions we introduce the following three helping sets:

• B η1 are the bits of B ∆1 (corresponding to items only present in P 1 ) that do not collide with those of B ∩ :

B η1 = B ∆1 \ B ∩ ;
• B η2 is the equivalent for P 2 :

B η2 = B ∆2 \ B ∩ ;
• and B β contains the collisions between B η1 and B η2 : If we note α, η 1 , η 2 , β the sizes of the sets B ∩ , B η1 , B η2 , and B β , respectively, we can express J(P 1 , P 2 ) as

B β = B η1 ∩ B η2 . Inria B ∆1 B ∆2 B ∩ η 1 η 2 β α u P ∆1 P ∩ P ∆2 h h h γ 1 α γ 2
J(P 1 , P 2 ) = α + β α + η 1 + η 2 -β = 2 α + η A + η B u -1, (7)
where u = α + η 1 + η 2 -β is the number of bits set to 1 by either P 1 or P 2 , i.e.

u = |B 1 ∪ B 2 | = B 1 OR B 2 1 .
The distribution of J(P 1 , P 2 ) is determined by the joint distribution of the random values ( u, α, η 1 , η 2 ) when h (shown with dashed arrows in Figure 2) is chosen uniformly randomly among all functions h that map P ∆1 ∪ P ∩ ∪ P ∆2 onto 0, b -1 . (Note that β = α + η 1 + η 2 -u is determined by the four other values, and therefore does not appear in the quadruplet.)

Theorem 1. The probability distribution of ( u, α, η 1 , η 2 ) is given by

P( u, α, η 1 , η 2 |α, γ 1 , γ 2 ) = Card _h( u, α, η 1 , η 2 , α, γ 1 , γ 2 ) b (α+γ1+γ2) , (8)
where

• α, γ 1 , and γ 2 are resp. the sizes of the sets P ∩ , P ∆1 , and P ∆2 introduced earlier;

• Card _h() is the number of hashing functions from As the size of the SHFs decreases, the spread of estimations grows, leading to more frequent misordering of profiles over shorter ranges.

P ∆1 ∪ P ∩ ∪ P ∆2 unto 0, b -1 that produce the quadruplet ( u, α, η 1 , η 2 ), defined by Card _h( u, α, η 1 , η 2 , α, γ 1 , γ 2 ) = b u u α u -α β u -α -β η 1 -β α! α α × ξ(γ 1 , η 1 + α, η 1 ) × ξ(γ 2 , η 2 + α, η 2 ); RR n°9218 0.0 0.2 0.4 0.6 0.8 1.0 J(P1, Px) (Jaccard's index)
• α α denotes Stirling's number of the second type; • and ξ(x, y, z) is the number of functions f : X → Y from a finite set X onto a finite set Y , that are surjective on a subset Z ⊆ Y of Y , with

x = |X|, y = |Y |, z = |Z|, defined by ξ(x, y, z) = z k=0 (-1) k z k (y -k) x .
Proof. The formula for P( u, α, η 1 , η 2 |α, γ 1 , γ 2 ) derives from a counting strategy on the functions from

P ∪ = P ∆1 ∪ P ∩ ∪ P ∆2 unto 0, b -1 : the denominator b (α+γ1+γ2)
is the total number of such functions. The numerator, Card _h(), is the number of functions h that yield precisely the quadruplet ( u, α, η 1 , η 2 ). We obtain Card _h() with a constructive argument. Because P ∩ , P ∆1 and P ∆2 are disjoint, h can be seen as the piece-wise combination of three independent random functions h |P∩ , h |P ∆1 , and h |P ∆2 , where h |X denotes the restriction of h to a set X.

To construct h, we start by choosing B ∪ = h(P ∪ ) within 0, b -1 . As u = |h(P ∪ )|, there are b u such choices. Similar arguments for B ∩ , B β , and B η1 \B ∩ yield that overall the total number of choices for

B ∪ , B ∩ , B β , B η1 \ B ∩ (and B η2 \ B ∩ ) is b u u α u-α β u-α-β η1-β .
(-1) k z k (y -k) x
There are therefore ξ(γ 1 , η 1 + α, η 1 ) functions h |P ∆1 . Similarly there are ξ(γ 2 , η 2 + α, η 2 ) functions h |P ∆2 . The product of the above quantities yields Card _h(), and as a result [START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF].

Combining the formula for P( u, α, η 1 , η 2 |α, γ 1 , γ 2 ) provided by Theorem 1 and Eq. ( 7), we can compute the distribution and moments of the estimator J for any α, γ 1 , γ 2 . For instance, J's mean is equal to

E J(P 1 , P 2 ) = ( u, α, η1, η2) P( u, α, η 1 , η 2 |α, γ 1 , γ 2 ) × 2 α + η A + η B u -1 .
Figure 3 uses this strategy to plot the behavior of the estimator J against the real Jaccard index when comparing a profile, P 1 of 100 items with other profiles P 2 , P 3 , P 4 of varying sizes.

J is biased. For instance when J(P 1 , P 2 ) = 0.25-the right vertical dashed line in the figure-J returns an average value of 0.286. However, this absolute bias has little impact on KNN algorithms, which only need to order nodes correctly, rather than to predict exact similarities. Instead, the spread and overlap of the values returned by J drive its impact on a KNN approximation. This effect is thankfully limited: for instance, if we assume that P 2 belongs to P 1 's exact KNN neighborhood with a similarity of J(P 1 , P 2 ) = 0.25, an algorithm using J might exclude P 2 if it finds another profile P 2 that J wrongly considers as more similar: J(P 1 , P 2 ) < J(P 1 , P 2 ) and J(P 1 , P 2 ) > J(P 1 , P 2 ).

Figure 3 shows this misordering has a very low probability of occurring (less than 2%) when J(P 1 , P 2 ) is lower than 0.17 (left vertical dashed line). This is because J(P 1 , P 2 ) has a 99% probability of being higher than 0.254 (1%-percentile value, shown as a solid horizontal line with a rectangle mark on the y-axis), while P 2 profiles with a real Jaccard's index lower than 0.17 have a 99% probability of being lower than this cut-off value (and this is roughly independent of P 2 's size). This phenomenon is shown in more detail in Figure 4 when P 2 contains 100 items: the error in similarity caused by the use of SHFs to compute J is bounded with high probability by a quantity proportional to the spread of estimated values. When SHFs are large enough compared to the size of the profiles being compared (here with b = 1024 bits), this spread is limited, but it increases as b gets smaller (Figure 5), highlighting a natural trade-off between compactness and accuracy that we will revisit in Section 4.

Privacy guarantees of GoldFinger

The noise introduced by collisions brings additional privacy benefits: collisions obfuscate a user's profile, and thus make it harder to guess this profile from its compacted SHF. This obfuscation can allow users to compute locally their SHF before sending it to some untrusted KNN-construction service.

We characterize the level of protection granted by GoldFinger along two standard measures of privacy, k-anonymity [START_REF] Samarati | Protecting respondents identities in microdata release[END_REF], and -diversity [START_REF] Machanavajjhala | L-diversity: privacy beyond k-anonymity[END_REF]. For this analysis, we assume an honest but curious attacker who wants to discover the profile P u of a particular user u, knowing its corresponding SHF (B u , c u ). We assume the attacker knows the item set I, the user set U and the hash function h. More importantly, for a given bit position x ∈ 0..b -1 , we assume the attacker can compute H x = h -1 (x), the preimage of x by h. How much information does (B u , c u ) leak about the initial profile P u ? This means that having a compacted profile of cardinality c u cannot allow an attacker to distinguish the actual profile which was used to generate (B u , c u ) between the (2 m b ×cu -1) others. We are not considering empty profiles, so every SHF has at least one bit set to one, so SHFs ensure at least (2 m b )-anonymity for the whole dataset.

2.5.1 k-anonymity Definition 1. Consider an obfuscation mechanism obf : X → Y that maps a clear-text input x ∈ X to an obfuscated value in Y. obf () is k-anonymous for x ∈ X , if the observed obfuscated value obf (x) is indistinguishable from that of at least k -1 other explicit input values. Expressed formally, obf () is k-anonymous for x ∈ X iff obf -1 (obf (x)) ≥ k. (9)
The anonymity granted by GoldFinger increases with the size of the item set m = |I|. For instance, one of the datasets we consider, AmazonMovies, has 171,356 items. With 1024-bit SHFs (the typical size we use), GoldFinger provides 2 167 -anonymity, i.e. each compacted profile is indistinguishable from at least 2 167 ≈ 1.87 × 10 50 possible profiles.

-diversity

Although k-anonymity provides a measure of the difficulty to recover the complete profile P u of a user u, it does not cover cases in which an attacker would seek to guess some partial information about u. This type of question is better Inria captured by a second metric, -diversity [START_REF] Machanavajjhala | L-diversity: privacy beyond k-anonymity[END_REF]. The -diversity model ensures that, for a given SHF (B u , c u ), the actual profile P u it was created from is indistinguishable from -1 other profiles {P i } i∈ 1.. -1 , and that these profiles form a well-represented set.

The difference with k-anonymity lies in this notion of well-representedness. In our case it means that we cannot infer any taste from possible profiles: for example in a movie dataset, if all the possible profiles of a given SHF include science-fiction movies, you can infer that the user enjoys science fiction.diversity measures the difficulty of such inferences. Proof. The reasoning is similar to that of k-anonymity. Let x be the index of a bit set to 1. |H x | = m b items are hashed into this bit. Assuming an arbitrary order on items, let us note i x j the j th element of the pre-image H x for each bit x set to 1 in B u . Without loss of generality, we can choose our order so that i x 0 ∈ P u for all x. Consider now the profiles

Q j = ∪ x:Bu[x]=1 {i x j } for j ∈ 1.. m b -1 . By construction (i) P u = Q j for j ≥ 1, (ii) the {Q j } j∈ 1.. m
b -1 are pair-wise disjoint, and (iii) they are all indistinguishable from P u once mapped onto their SHF.

For instance, in the dataset AmazonMovies, using 1024 bit long SHFs, we insure 167-diversity.

Since our hashing is deterministic, we do not have a stronger notion of privacy such as differential privacy [START_REF] Dwork | Differential privacy: A survey of results[END_REF]. It can be easily obtained by inserting random noise to the SHF [START_REF] Alaggan | Blip: Non-interactive differentially-private similarity computation on bloom filters[END_REF].

3 Experimental Setup

Datasets

We use six publicly available datasets (Table 2). We binarize each dataset by only keeping in a user profile P u those items that user u has rated higher than 3.

Movielens

Movielens [START_REF] Harper | The movielens datasets: History and context[END_REF] is a group of anonymous datasets containing movie ratings collected on-line between 1995 and 2015 by GroupLens Research [START_REF] Resnick | Grouplens: an open architecture for collaborative filtering of netnews[END_REF]. The datasets (before binarization) contain movie ratings on a 0.5-5 scale by users who have at least performed 20 ratings. We use 3 versions of the dataset, movielens1M (ml1M), movielens10M (ml10M) and movielens20M (ml20M), containing between 575,281 and 12,195,566 positive ratings (i.e. higher than 3).

AmazonMovies

AmazonMovies [START_REF] Mcauley | From amateurs to connoisseurs: modeling the evolution of user expertise through online reviews[END_REF] (AM) is a dataset of movies reviews from Amazon collected between 1997 and 2012. We restrain our study to users with at least 20 ratings (before binarization) to avoid users with not enough data (this problem, the cold start problem, is generally treated separately [START_REF] Lam | Addressing cold-start problem in recommendation systems[END_REF]). After binarization, the dataset contains 57,430 users; 171,356 items; and 3,263,050 ratings.

DBLP

DBLP [START_REF] Yang | Defining and evaluating network communities based on ground-truth[END_REF] is a dataset of co-authorship from the DBLP computer science bibliography. In this dataset, both the user set and the item set are subsets of the author set. If two authors have published at least one paper together, they are linked, which is expressed in our case by both of them rating each other with a rating of 5. As with AM, we only consider users with at least 20 ratings. The resulting dataset contains 18,889 users, 203,030 items; and 692,752 ratings.

Gowalla

Gowalla [START_REF] Cho | Friendship and mobility: User movement in location-based social networks[END_REF] (GW) is a location-based social network. As DBLP, both user set and item set are subsets of the set of the users of the social network. The undirected friendship link from u to v is represented by u rating v with a 5. As previously, only the users with at least 20 ratings are considered. The resulting dataset contains 20,270 users, 135,540 items; and 1,107,467 ratings.

Baseline algorithms and competitors

We apply GoldFinger to four existing KNN algorithms: Brute Force (as a reference point), NNDescent [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF], Hyrec [START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF] and LSH [START_REF] Indyk | Approximate nearest neighbors: towards removing the curse of dimensionality[END_REF]. We compare the performance and results of each of these algorithms in their native form (native for short) and when accelerated with GoldFinger. For completeness, we also discuss b-bit minwise hashing [START_REF] Li | Theory and applications of b-bit minwise hashing[END_REF], a binary sketching technique proposed to estimate Jaccard's index between sets, albeit in a different context than ours. GoldFinger is orders of magnitude faster than MinHash, whose overhead is prohibitive.

Inria

b-bit minwise hashing (MinHash)

A standard technique to approximate Jaccard's index values between sets is the MinHash [10] algorithm. MinHash creates multiple independent permutations on the IDs of a item universe, and keeps for each profile the item with the smallest ID, after each permutation. The Jaccard's index between two profiles can be estimated by counting the proportion of minimal IDs that are equal in the compacted representation of the two profiles. Although MinHash does not produce a compact binary representation, it was recently extended to keep only the lowest b bits of each minimal element [START_REF] Li | Theory and applications of b-bit minwise hashing[END_REF]. This approach, called b-bit minwise hashing (we call it MinHash for short, even though it is an improvement of the original algorithm), creates very compact binary summaries of profiles, comparable to our SHFs, from which a Jaccard's index can be estimated.

Unfortunately, computing MinHash summaries is extremely costly (as it requires creating a large number of permutations on the entire item set), which renders the approach self-defeating in our context. Table 3 summarizes the time required to load and construct the internal representation of each dataset when using a native (explicit) approach, GoldFinger (using Jenkins' hash function [START_REF] Jenkins | Hash functions[END_REF]), and MinHash. We use 1024 bits for GoldFinger (a typical value), and b = 4 and 256 permutations for BBHM (configuration which provides the best trade-off between time and KNN quality). Whereas GoldFinger is slightly faster than a native approach (as it does not need to create extensive in-memory objects to store the dataset), MinHash is one to 3 orders of magnitude slower than GoldFinger (1692 times slower on AmazonMovies for instance). This kind of overhead makes it impractical for environments with limited resources, and we therefore do not consider MinHash in the rest of our evaluation.

Brute force

The Brute Force algorithm simply computes the similarities between every pair of profiles, performing a constant number of similarity computations equal to n×(n-1) 2

. While this is computationally intensive, this algorithm produces an exact KNN graph.

NNDescent

NNDescent [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF] constructs an approximate KNN graph (or ANN) by relying on a local search and by limiting the number of similarities computations.

NNDescent starts from an initial random graph, which is then iteratively refined to converge to an ANN graph. During each iteration, for each user u, NNDescent compares all the pairs (u i , u j ) among the neighbors of u, and updates the neighborhoods of u i and u j accordingly. NNDescent includes a number of optimizations: it exploits the order on user IDs, and maintains update flags to avoid computing several times the same similarities. It also reverses the current KNN approximation to increase the space search among neighbors. The algorithm stops either when the number of updates during one iteration is below the value δ × k × n, with a fixed δ, or after a fixed number of iterations.

Hyrec

Hyrec [START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF] uses a strategy similar to that of NNDescent, exploiting the fact that a neighbor of a neighbor is likely to be a neighbor. As NNDescent, Hyrec starts with a random graph which is then refined. Hyrec primarily differs from NNDescent in its iteration strategy. At each iteration, for each user u, Hyrec compares all the neighbors' neighbors of u with u, rather than comparing u's neighbors between themselves. Hyrec also does not reverse the current KNN graph. As NNDescent, it stops when the number of changes is below the value δ × k × n, with a fixed δ, or after a fixed number of iterations.

LSH

Locality-Sensitive-Hashing (LSH) [START_REF] Indyk | Approximate nearest neighbors: towards removing the curse of dimensionality[END_REF] reduces the number of similarity computations by hashing each user into several buckets. Neighbors are then selected among users found in the same buckets. To insure that similar users tend to be hashed into the same buckets, LSH uses min-wise independent permutations of the item set as its hash functions, similarly to the MinHash algorithm [START_REF] Broder | On the resemblance and containment of documents[END_REF].

Parameters

We set k to 30 (the neighborhood size). The parameter δ of Hyrec and NNDescent is set to 0.001, and their maximum number of iterations to 30. The number of hash functions for LSH is 10. GoldFinger uses 1024 bits long SHFs computed with Jenkins' hash function [START_REF] Jenkins | Hash functions[END_REF].

Evaluation metrics

We measure the effect of GoldFinger on Brute Force, Hyrec, NNDescent and LSH along two main metrics: (i) their computation time (measured from the start of the algorithm, once the dataset has been prepared), and (ii) the quality of the resulting KNN (Sec. 2.1). When applying GoldFinger to recommendation, we also measure the recall obtained by the recommender. Throughout our experiments, we use a 5-fold cross-validation, and average results on the 5 resulting runs.

Implementation details and hardware

We have implemented Brute Force, Hyrec, NNDescent and LSH (with and without GoldFinger) in Java 1.8. Our experiments run on a 64-bit Linux server with two Intel Xeon E5420@2.50GHz, totaling 8 hardware threads, 32GB of Inria memory, and a HHD of 750GB. Unless stated otherwise, we use all 8 threads. Our code is available online5 .

Evaluation Results

Computation time and KNN quality

The performance of GoldFinger (GolFi ) in terms of execution time and KNN quality is summarized in Overall, GoldFinger delivers the fastest computation times across all datasets, for a small loss in quality ranging from 0.22 (with Brute Force on Gowalla) to Figure 7: KNN quality using a 1024 bits SHF (higher is better). GoldFinger (GolFi) only experiences a small decrease in quality.

an improvement of 0.11 (Hyrec on AmazonMovies). Excluding LSH on Ama-zonMovies, DBLP and Gowalla for the moment, GoldFinger is able to reduce computation time substantially, from 42.1% (NNDescent on ml1M) to 78.9% (Brute Force on ml1M), corresponding to speedups of 1.72 and 4.74 respectively.

GoldFinger only has a limited effect on the execution time of LSH on the AmazonMovies, DBLP and Gowalla datasets. This lack of impact can be explained by the characteristics of LSH and the datasets. LSH must first create user buckets using permutations on the item universe, an operation that is proportional to the number of items. Because AmazonMovies, DBLP and Gowalla are comparatively very sparse (Table 2), the buckets created by LSH tend to contain few users. As a result, the overall computation time is dominated by the bucket creation, and the effect of GoldFinger becomes limited.

In spite of these results, GoldFinger consistently outperforms native LSH on these datasets for instance taking 62s (with Hyrec) instead of 141s with LSH on AmazonMovies (a speedup of ×2.27), for a comparable quality.

Memory and cache accesses

By compacting profiles, GoldFinger reduces the amount of memory needed to process of dataset. To gauge this effect, we use perf6 to profile the memory accesses of GoldFinger. perf uses hardware counters to measure accesses to the cache hierarchy (L1, LLC, and physical memory). To eliminate accesses performed during the dataset preparation, we subtract the values returned by perf when only preparing the dataset from the values obtained on a full execution.

Table 5 summarizes the measures obtained on Brute Force, Hyrec, NNDescent and LSH on ml10M, both without (native) and with GoldFinger (GolFi ). Figure 8: Recommendation quality using a 1024 bits SHF (higher is better). GoldFinger's (GolFi) recall loss is negligible.

We only show L1 accesses for space reasons, since LLC and RAM accesses are negligible in comparison. Except on LSH, GoldFinger significantly reduces the number of L1 cache loads and stores, confirming the benefits of GoldFinger in terms of memory footprint. For LSH, L1 accesses are almost not impacted by GoldFinger. Again, we conjecture this is because memory accesses are dominated by the creation of buckets.

GoldFinger in action: recommendations

We evaluate the applicability of GoldFinger in the context of a concrete application, namely a recommender. Item recommendation is one of the main applications of KNN graphs, and consists in providing every user with a list of items she is likely to rate positively. To do so, we compute for each user u and each item i not known to u that is present in u's KNN neighborhood a score score(u, i), using a weighted average of the ratings given by other users in u's KNN:

score(u, i) = v∈ knn(u) r(u, i) × sim(u, v) v∈ knn(u) sim(u, v)
.

Using the KNN graphs computed for the previous sections, we recommend 30 items to each user in every dataset. Since we use a 5-fold cross validation, we use the 1/5 of each dataset not used in an experiment as our testing set, and consider a recommendation successful if the user has produced a positive rating for the recommended item in the testing set. We evaluate the quality recommendation using recall, i.e. the number of successful recommendations divided by the number of positively rated items hidden in the testing set.

Figure 8 shows the recall of the recommendation made with the native algorithms and with their GoldFinger counterparts on all datasets. These results clearly show that the small drop in quality caused by GoldFinger has no impact on the outcome of the recommender, confirming the practical relevance of GoldFinger.

Sensitivity Analysis

As explained in Section 2, the SHF size determines the number of collisions occurring when computing SHFs, and when intersecting them. It thus affects the obtained KNN quality. Shorter SHFs also deliver higher speedups, resulting in an inherent trade-off between execution time and quality. In this section we focus on ml10M.

Impact on the similarity computation time

SHFs aim at drastically decreasing the cost of individual similarity computations. To assess this effect, Figure 9 shows the average computation time of one similarity computation when using SHFs (Eq. 4), and its corresponding speedup. The measures were obtained by computing with a multithreaded program the similarities between two sets of 5×10 4 users, sampled randomly from ml10M. The first set of users is divided in several parts, one for each thread. On each thread, each user of the part of the first set is compared to every user of the second set. The total time required is divided by the total number of similarities computed, 2.5 × 10 9 , and then averaged over 4 runs. The computation time is linear in the size of the SHF. Computation time spans from 8 nanoseconds to 250 nanoseconds using SHF, against 800 nanoseconds with real profiles. The other datasets show similar results.

Impact on the execution of the algorithm

Figure 10 shows how the overall execution time and the quality of Brute Force and Hyrec evolve when we increase the size of the SHFs. (LSH presents a similar behavior to that of Brute Force, and NNDescent to that of Hyrec.) As expected, larger SHFs cause Brute Force to take longer to compute, while delivering a better KNN quality (Fig. 10a). The overall computation time does not exactly follow that of individual similarity computations (Figure 9a), as the The KNN quality of Hyrec shows a similar trend, increasing with the size of SHFs. The computation time of Hyrec presents however an unexpected pattern: it first decreases when SHFs grow from 64 to 1024 bits, before increasing again from 1024 to 4096 bits (Figure 10b). This difference is due to the different nature of the two approaches. The Brute Force algorithm computes a fixed number of similarities, which is independent of the distribution of similarities between users. By contrast, Hyrec adopts a greedy approach: the number of similarities computed depends on the iterations performed by the algorithm, and these iterations are highly dependent on the distribution of similarity values between pairs of users (what we have termed the similarity topology of the dataset), a phenomenon we return to in the following section.

Impact on estimated similarity values

Figure 11 shows how SHFs tend to distort estimated similarity values between pairs of users in ml10M, when using 1024 (Figure 11a) and 4096 bits (Figure 11b). The x-axis represents the real similarity of a pair of users (u, v) ∈ U 2 , the y-axis represents its similarity obtained with GoldFinger, and the z-axis represents the number of pairs whose real similarity is x and estimated similar- The closer points lay to the diagonal (x = y), the more accurate the estimation of their similarity by GoldFinger. Points over x = y indicate that the SHFs are over-approximating Jaccard's index, while points below correspond to an under-approximation. Figure 11 shows that the size of SHFs strongly influences the accuracy of the Jaccard estimation: while points tend to cluster around x = y with 4096-bits SHFs (Figure 11a), the use of 1024 bits generate collisions that lead GoldFinger to overestimate low similarities (Figure 11b).

To understand why GoldFinger performs well despite this distortion, we analyze more carefully the distribution of pairs in Figure 11a. Most of the pairs (94%) of users have an exact similarity below 0.1. Even with 1024 bits, an overwhelming majority (92%) of these turn out to also have an approximated similarity below 0.1. This confirms our initial intuition (Section 2): two users with low similarity are likely to get a low approximation using GoldFinger.

Although the area [0, 0.1] × [0, 0.1] is where most user pairs can be found, interesting pairs are however not concentrated there. Indeed, the pairs of users present in the KNN (as directed edges) show higher similarities: less than 1% can be found in the area [0, 0.1] × [0, 0.1]. To understand what happens for the rest of the pairs, we focus on the number of total pairs which are at a distance of the diagonal lower than ∆. With SHFs of size 1024, 52% of the pairs are at a distance lower than ∆ = 0.01, 75% for ∆ = 0.02, 94% for ∆ = 0.05 and 99% for ∆ = 0.1, which confirms the theoretical analysis of Section 2.4. This means that a large majority of pairs do not see their similarity changed much by the use of SHFs. The pairs that experience a large variation between their real and their estimated similarity are too few in numbers to have a decisive impact on the quality of the resulting KNN graph.

This explains why the Brute Force algorithm experiments a decrease in execution time along with a small drop in quality with GoldFinger. Hyrec and NNDescent, however, iterate recursively on node neighborhoods, and are therefore more sensitive to the overall distribution of similarity values. The recursive effect is the reason why-somewhat counter-intuitively-Hyrec and NNDe-Inria scent's execution time first decreases as SHFs grow in size (as mentioned earlier, in Fig. 10).

To shed more light on this effect, Figure 12 shows the number of iterations and the corresponding scanrate performed by Hyrec for SHF sizes varying from 64 to 8192 bits. The scanrate is the number of similarity computations executed by Hyrec+GoldFinger divided by the number of comparisons performed by the Brute Force algorithm, n × (n -1)/2. The green horizontal line represents the results when using native Hyrec. As expected, the behavior of the GoldFinger version converges to that of native Hyrec as the size of the SHFs increases. Interestingly, short SHFs (< 1024 bits) cause Hyrec to require more iterations to converge (Fig. 12a), leading to a higher scanrate (Fig. 12b), and hence more similarity computations. When this occurs, the performance gain on individual similarity computations (Figure 9) does not compensate this higher scanrate, explaining the counter-intuitive pattern observed in Figure 10b.

Related work

For very small datasets, KNNs can be solved efficiently using specialized data structures [START_REF] Beygelzimer | Cover trees for nearest neighbor[END_REF][START_REF] Liu | An investigation of practical approximate nearest neighbor algorithms[END_REF][START_REF] Moore | The anchors hierarchy: Using the triangle inequality to survive high dimensional data[END_REF]. For larger datasets, these solutions are more expensive than a brute force approach, and computing an exact KNN efficiently remains an open problem. Most practical approaches therefore compute an approximation of the KNN graph (ANN), as we do.

A first way to accelerate the computation time is to decrease the number of comparisons between users, taking the risk to miss some neighbors. Recursive Lanczos Bisection [START_REF] Chen | Fast approximate knn graph construction for high dimensional data via recursive lanczos bisection[END_REF] for instance computes an ANN graph using a divideand-conquer method. NNDescent [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF] and Hyrec [START_REF] Boutet | Hyrec: leveraging browsers for scalable recommenders[END_REF] rely on local search, i.e. they assume that a neighbor of a neighbor is likely to be a neighbor, and thus drastically decrease the scan rate, delivering substantial speedups. KIFF [START_REF] Boutet | Being prepared in a sparse world: the case of knn graph construction[END_REF] uses the bipartite nature of the dataset to compute similarities only when users share an item. This approach works particularly well on sparse datasets but seems to have more difficulties with denser datasets such as the ones we studied. Locality Sensitive Hashing (LSH) [START_REF] Indyk | Approximate nearest neighbors: towards removing the curse of dimensionality[END_REF] allows fast ANN graph computations by hashing users into buckets. The neighbors are selected only between the users of the same buckets. Several hash functions have been introduced, for different metrics [START_REF] Broder | On the resemblance and containment of documents[END_REF][START_REF] Broder | Syntactic clustering of the web[END_REF][START_REF] Charikar | Similarity estimation techniques from rounding algorithms[END_REF]. All of the above works can be combined with our approachas we have demonstrated in the case of NNDescent, Hyrec, and LSH -and are thus complementary to our contribution.

A second strategy to accelerate a KNN graph's construction consists in compacting users' profiles, in order to obtain a fast approximation of the similarity metric. For instance, a simple way the similarities computation is to limit the size of each user's profile by keeping the least popular items of each profiles [START_REF] Kermarrec | Nobody cares if you liked star wars: KNN graph construction on the cheap[END_REF]. The speed-up is interestering but lower than the one produced by GoldFinger. Instead of sampling based on popularity, minwise hashing [START_REF] Li | Theory and applications of b-bit minwise hashing[END_REF] relies on the same principle as LSH to approximate Jaccard's index by only keeping a small subset of items for each user. It is space efficient but at the expense of a high preprocessing time. An extension of this work consists in hashing each item to 0 or 1 rather than storing its lowest bits [START_REF] Bachrach | Sketching for big data recommender systems using fast pseudo-random fingerprints[END_REF]. This further reduces the memory footprint, but unfortunately maintains a prohibitive preprocessing time.

Similarly to our work, Bin, Heng et al. [START_REF] Cui | Exploring bit-difference for approximate knn search in high-dimensional databases[END_REF] use a bit array to represent profiles. Each feature, which has a continuous score comprised between 0 and 1, is rounded to either 0 or 1, and stored in one bit. This strategy unfortunately does not scale to large item sets (where items play the role of features), which are typical of the datasets we target. Closer to our work, Gorai et al. [START_REF] Gorai | Employing bloom filters for privacy preserving distributed collaborative knn classification[END_REF] use Bloom filters to encode the profiles of the nodes and then estimates Jaccard's index by using a bitwise AND. The use of Bloom filters preserves privacy, but the resulting loss in precision is unfortunately prohibitive. Sketches [START_REF] Charikar | Finding frequent items in data streams[END_REF][START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF][START_REF] Roy | Augmented sketch: Faster and more accurate stream processing[END_REF] are other compacted datastructures, which have been used for instance to find frequent items in data streams [START_REF] Anceaume | Identifying global icebergs in distributed streams[END_REF]. Unfortunately sketches are not optimized for set intersection.

To adapt the KNN graph construction to dynamic data, several metrics and recommendation systems have been proposed that take into account the timestamp of ratings [START_REF] Campos | Simple timebiased knn-based recommendations[END_REF][START_REF] Chen | Terec: A temporal recommender system over tweet stream[END_REF][START_REF] Damaskinos | Capturing the moment: Lightweight similarity computations[END_REF][START_REF] Ding | Time weight collaborative filtering[END_REF][START_REF] Huang | Tencentrec: Real-time stream recommendation in practice[END_REF][START_REF] Lathia | Temporal collaborative filtering with adaptive neighbourhoods[END_REF][START_REF] Liu | Online evolutionary collaborative filtering[END_REF][START_REF] Yang | Scalable collaborative filtering using incremental update and local link prediction[END_REF]. All these approaches remain however computationally intensive.

Privacy has today become a major concern for many information systems which aim to answer queries as accurately as possible while avoiding disclosing any sensible information. Multiple metrics with different semantics have been proposed to characterized privacy protection such as k-anonymity [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF], ldiversity [START_REF] Machanavajjhala | l-diversity: Privacy beyond k-anonymity[END_REF], t-closeness [START_REF] Li | t-closeness: Privacy beyond k-anonymity and l-diversity[END_REF] or differential privacy [START_REF] Dwork | Differential privacy: A survey of results[END_REF]. An increasing number of works currently seek to add those properties to existing machine learning techniques [START_REF] Mcsherry | Differentially private recommender systems: building privacy into the net[END_REF][START_REF] Vu | Efficient algorithms for k-anonymous location privacy in participatory sensing[END_REF]. Blip [START_REF] Alaggan | Blip: Non-interactive differentially-private similarity computation on bloom filters[END_REF] for instance provides differential privacy to users' profiles encoded into Bloom filters by injecting additional noise. By contrast, our approach naturally provides k -anonymity and l -diversity without any alteration of the bit array.

Conclusion

We have proposed fingerprinting, a new technique that consists in constructing compact, fast-to-compute and privacy-preserving representation of datasets. We have illustrated the effectiveness of this idea on KNN graph construction, and proposed GoldFinger, a novel generic mechanism to accelerate the computation of Jaccard's index while protecting users' privacy. GoldFinger exploits Single Hash Fingerprints, a randomized binary summary of the entities of a dataset.

Our extensive evaluation shows that GoldFinger is able to drastically accelerate the construction of KNN graphs against the native versions of prominent KNN construction algorithms such as NNDescent or LSH while incurring a small to moderate loss in quality, and close to no overhead in dataset preparation compared to the state of the art. We have also precisely characterized the privacy protection provided by GoldFinger in terms of k-anonymity and -diversity. These properties are obtained for free.

Figure 1 :

 1 Figure1: The cost of computing Jaccard's index between explicit user profiles is relatively high (a few ms) for average-size profiles. Cost averaged over 4.9 millions computations between randomly generated profiles on a Intel Xeon E5420@2.50GHz.

Figure 2 :

 2 Figure 2: Illustration of the collisions caused by h on two profiles P 1 = P ∆1 ∪ P ∩ and P 2 = P ∆2 ∪ P ∩ . Capital letters (P and B) denote sets, Greek letters denote sizes, and the hat symbol ( ) represent random variables.

Figure 3 :

 3 Figure3: Mean and 1%-99% interquantile of J between a profile P 1 of 100 items, and 3 profiles P 2 , P 3 , P 4 of varying sizes, using SHFs of b = 1024 bits. J is biased, but shows a tight spread of values. As a result the risk of misordering neighbors drops fast with decreasing similarity.

Figure 4 :Figure 5 :

 45 Figure 4: Distribution of estimation when the real Jaccard indices with P 1 equal 0.25 and 0.17 (represented in bins of 0.0025). |P 1 | = |P 2 | = |P 2 | = 100 items, b = 1024 bits. When P 2 's real similarity with P 1 drops below 0.17, the risk of misordering P 2 and P 2 drops below 2%.

Inria

  Let us note ξ(x, y, z) the number of functions f : X → Y from a finite set X onto a finite set Y , that are surjective on a subset Z ⊆ Y of Y , with x = |X|, y = |Y |, z = |Z|. Using an inclusion-exclusion argument we have ξ(x, y, z) = z k=0

Theorem 2 .

 2 GoldFinger ensures (2 m b ×cu )-anonymity for a given SHF (B u , c u ) of length b, and cardinality c u , where m = |I| is the size of the item set.Proof. Let x be the index of a bit set to 1. Let H x = h -1 (x) the set of all the items which are hashed by h to x, it is on average of size m b with a uniformly random hashing function. Thus P(H x ) (the powerset of H x , sometimes noted {0, 1} Hx ), whose cardinality is 2 m b , is the set of all possible sub-profiles that will set the bit x to 1. All of these sub-profiles are indistinguishable once hashed, hashing ensures (2 m b )-anonymity for this bit. For every bit set to one, there are 2 m b possible set of items, leading to a (2 m b ) cu -anonymity, since all pre-images (H x ) x are pair-wise disjoint.

Definition 2 .|Q| ≥ - 1 . ( 10 ) 3 .

 21103 Consider an obfuscation mechanism obf : P(I) → Y that maps a set of items P ⊆ I to an obfuscated value in Y. obf () is -anonymous for P ⊆ I, if the observed obfuscated value obf (P ) is indistinguishable from that of at least -1 other explicit profiles Q = {P i } i∈ 1.. -1 that are pair-wise disjoint: ∀P 1 , P 2 ∈ Q : P 1 ∩P 2 = ∅. Expressed formally 4 , obf () is -anonymous for P ⊆ I iff max Q⊆obf -1 (obf (P ))\{P }: ∀P1,P2∈Q:P1∩P2=∅ Theorem For a given SHF (B u , c u ) of length b and cardinality c u , SHF ensures ( m b )-diversity for (B u , c u ).

Figure 6 :

 6 Figure 6: Execution time using a 1024 bits SHF (lower is better). GoldFinger (GolFi) outperforms Brute Force, Hyrec and NNDescent in their native version on the four datasets.

Figure 9 :

 9 Figure 9: Effect of the size of the SHF on the similarity computation time, on ml10M. The computation time is roughly proportional to the size of SHFs.

Figure 10 :

 10 Figure 10: Relation between the execution time and the quality in function of the size of SHF.

Figure 11 :

 11 Figure 11: Heatmaps similarities on ml10M. The distortion of the similarity decreases when the size of SHF augments.

Figure 12 :

 12 Figure12: Effect of compression on the convergence of Hyrec on ml10M. GoldFinger converges to the native approach when the size of SHF augments.

Table 1 :

 1 Effect of SHFs on computation time of Jaccard's index, compared to Fig.1(80 items).

	SHF length (bits) Comp. Time (ms) Speedup |P | = 80
	64	0.011	253
	256	0.032	84
	1024	0.120	23
	4096	0.469	6

  Once these supporting sets have been chosen, we pick h |P∩ , h |P ∆1 , and h |P ∆2 . h |P∩ is a surjection from P ∩ to B ∩ . There are α! α α such surjections, where

α α is Stirling's number of the second type.

h |P ∆1 maps P ∆1 onto B ∪ , but only needs to be surjective on B ∆1 \ B ∩ = B η1 . In addition, h |P ∆1 only maps elements unto B ∆1 ⊆ B η1 ∪ B ∩ , whose cardinal is η 1 + α.

Table 2 :

 2 Description of the datasets used in our experiments

	Dataset	Users	Items Scale Ratings > 3	|Pu|	|P i | Density
	movielens1M (ml1M) [25]	6,038	3,533	1-5	575,281 95.28 162.83	2.697%
	movielens10M (ml10M) [25]	69,816	10,472	0.5-5	5,885,448 84.30 562.02	0.805%
	movielens20M (ml20M) [25] 138,362	22,884	0.5-5	12,195,566 88.14 532.93	0.385%
	AmazonMovies (AM) [43]	57,430 171,356	1-5	3,263,050 56,82	19.04	0.033%
	DBLP [53]	18,889 203,030	5	692,752 36.67	3.41	0.018%
	Gowalla (GW) [17]	20,270 135,540	5	1,107,467 54.64	8.17	0.040%

Table 3 :

 3 Preparation time of each dataset for the native approach, b-bit minwise hashing (MinHash) & GoldFinger.

	Dataset Native MinHash	GoldFinger speedup (×)
	ml1M	0.37s	6.24s	0.31s	20.1
	ml10M	3.90s	203s	3.24s	62.7
	ml20M	8.71s	820s	7.06s	116.1
	AM	3.40s	3250s	1.92s	1692.7
	DBLP	0.42s	944s	0.29s	3255.2
	GW	0.47s	594s	0.40s	1485.0

Table 4 :

 4 Computation time and KNN quality with native algorithms (nat.) and GoldFinger (GolFi).

				comp. time (s)	KNN quality
			algo	nat. GolFi gain%	nat. GolFi loss
		ml1M	Brute Force 19.0 Hyrec 14.4 NNDescent 19.0	4.0 4.4 11.0	78.9 69.4 42.1	1.00 0.98 1.00	0.93 0.07 0.92 0.06 0.93 0.07
			LSH	9.5	3.0	68.4	0.98	0.92 0.06
		ml10M	Brute Force 2028 Hyrec 314 NNDescent 374 LSH 689	606 110 147 255	70.1 65.0 60.7 63.0	1.00 0.96 1.00 0.99	0.94 0.06 0.90 0.06 0.93 0.07 0.94 0.06
	datasets	ml20M AM	Brute Force 8393 2616 Hyrec 842 289 NNDescent 919 383 LSH 2859 1060 Brute Force 1862 435 Hyrec 235 62 NNDescent 324 91	68.8 65.7 58.3 62.9 76.6 73.6 71.9	1.00 0.95 0.99 0.99 1.00 0.82 0.98	0.92 0.08 0.88 0.07 0.92 0.07 0.93 0.06 0.96 0.04 0.93 -0.11 0.95 0.03
			LSH	144	141	2.1	0.98	0.96 0.02
		DBLP	Brute Force 100 Hyrec 46 NNDescent 31	46 27 24	54.0 41.3 22.6	1.0 0.86 0.98	0.82 0.18 0.81 0.05 0.82 0.16
			LSH	40	38	2.6	0.87	0.86 0.01
		Gowalla	Brute Force 160 Hyrec 39 NNDescent 45 LSH 30	54 22 26 27	66.3 43.6 42.2 3.7	1.0 0.95 1.0 0.87	0.78 0.22 0.78 0.17 0.79 0.21 0.82 0.05

GoldFinger yields the shortest computation times across all datasets (in bold), yielding gains (gain) of up to 78.9% against native algorithms. The loss in quality at worst moderate, ranging from 0.22 to an improvement of 0.11.

Table 4 .

 4 The columns marked nat. indicate the results with the native algorithms, while those marked GolFi contain those with GoldFinger. The columns in italics show the gain in computation time brought by GoldFinger (gain % ), and the loss in quality (loss). The fastest time for each dataset is shown in bold. Excluding LSH for space reasons, the same results are shown graphically in Figures 6 (time) and 7 (quality).

Table 5 :

 5 L1 stores and L1 loads with the native algorithms (nat.) and GoldFinger (GolFi) on ml10M.

					L1 stores (×10 12 )	L1 loads (×10 12 )
				algo	nat. GolFi gain%	nat. GolFi gain%
				Brute Force 2.82	0.34	87.9	8.26	1.08	86.9
				Hyrec	0.35	0.08	77.1	1.14	0.28	75.4
				NNDescent 0.57	0.16	71.9	1.93	0.59	69.4
				LSH	0.84	0.85 -1.19	2.96	2.90	2.03
	GoldFinger drastically reduces the number of L1 accesses, yielding reductions (gain) ranging
	from 67.2% to 87.7%.
		0.3
	recom. recall	0.0 0.1 0.2	Br ut eF or ce H yr ec	N N D es ce nt native GolFi

Note that the problem of computing a complete KNN graph (which we address in this paper) is related but different from that of answering a sequence of KNN queries.

Real time is meant in the sense of web real-time, i.e. the proactive push of information to on-line users.RR n°9218

In other words, argtop k generalizes the concept of argument of the maximum (usually noted argmax) to the k top values of a function over a finite discrete set.RR n°9218

RR n°9218

This definition, adapted to our context, differs slightly from that of the original paper, but leads in practice to the same result.RR n°9218

https://gitlab.inria.fr/oruas/SamplingKNN RR n°9218

https://perf.wiki.kernel.org/index.php/Main_Page Inria

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399


Mickaël Pruvost

Wilbert J Smit

Cécile Monteux

Philippe Poulin

Annie Colin
email: annie.colin@espci.fr

Microporous electrostrictive materials for vibrational energy harvesting

Keywords: polymers, electrostriction, vibrational energy harvesting, electrostrictive material, capacitive sensors

We present electrostrictive materials with excellent properties for vibrational energy harvesting applications. The developed materials consist of a porous carbon black composite, which is processed using water-in-oil emulsions. In combination with an insulating layer, the investigated structures exhibit a high effective relative dielectric permittivity (up to 182 at 100 Hz) with very low effective conductivity (down to 2.53 10 -8 S m -1 ). They can generate electrical energy in response to mechanical vibrations with a power density of 0.38 W m -3 under an applied bias electric field of 32V. They display figures or merit for energy harvesting applications well above reference polymer materials in the field, including fluorinated co-and ter-polymers synthetized by heavy chemical processes. The production process of the present materials is based on non hazardous and low-cost chemicals. The soft dielectric materials are highly flexible (Young's modulus of ~1 MPa) making them also suited for highly sensitive capacitive sensors.

Introduction:

The Internet of Things (IoT) is a new and fast growing concept which aims at connecting everyday physical objects into the Internet without any human interaction [START_REF] Gubbi | Internet of Things (IoT): A vision, architectural elements, and future directions[END_REF][START_REF] Xia | Internet of Things[END_REF]. The IoT requires the usage of numerous wireless sensors. Providing the electrical energy to run these wireless sensors is of major concern. Use of batteries with limited lifetime is a severe constraint. To overcome this problem, several environmental energy sources such as thermal, solar, salinity gradients, vibrations can be used to fulfil energy demands [START_REF] Brogioli | Extracting Renewable Energy from a Salinity Difference Using a Capacitor[END_REF][START_REF] Janssen | Boosting Capacitive Blue-Energy and Desalination Devices with Waste Heat[END_REF][START_REF] Dutoit | Design considerations for mems-scale piezoelectric mechanical vibration energy harvesters[END_REF]. It could thus make sensors, MEMS, communicating devices, etc. self-sufficient in energy supply and as-such highly increase their life time. A promising method to resolve this challenge is to harvest mechanical energy from the ambient environment and convert it into electrical power. An apparently convenient method consists in using piezoelectric materials. The most efficient piezoelectric ceramics can produce up to 0.2-30 mW cm -1 [START_REF] Sodano | A Review of Power Harvesting from Vibration Using Piezoelectric Materials[END_REF][START_REF] Anton | A review of power harvesting using piezoelectric materials (2003-2006[END_REF][START_REF] Yan | Giant piezoelectric voltage coefficient in grain-oriented modified PbTiO3 material[END_REF][START_REF] Fan | Flexible Nanogenerators for Energy Harvesting and Self-Powered Electronics[END_REF]. However, these materials are stiff and brittle which limits 2 their implementation in embedded applications [START_REF] Guillon | Tensile fracture of soft and hard PZT[END_REF]. Triboelectric nanogenerators have recently demonstrated volume power densities up to 0.49 W cm -3 [START_REF] Wang | Triboelectric nanogenerators as new energy technology and self-powered sensors -Principles, problems and perspectives[END_REF][START_REF] Nguyen | Effect of humidity and pressure on the triboelectric nanogenerator[END_REF]. However, their performances are largely affected by the environment such as humidity [START_REF] Nguyen | Effect of humidity and pressure on the triboelectric nanogenerator[END_REF]. Moreover, their low durability as a result of two materials in physical friction is still a limiting factor [START_REF] Wang | Triboelectric nanogenerators as new energy technology and self-powered sensors -Principles, problems and perspectives[END_REF]. A more recent approach consists in using electrostrictive polymers to convert energy from mechanical vibrations [START_REF] Jaaoh | Enhanced strain response and energy harvesting capabilities of electrostrictive polyurethane composites filled with conducting polyaniline[END_REF][START_REF] Yin | A comprehensive investigation of poly(vinylidene fluoride-trifluoroethylene-chlorofluoroethylene) terpolymer nanocomposites with carbon black for electrostrictive applications[END_REF][START_REF] Luna | Giant Electrostrictive Response and Piezoresistivity of Emulsion Templated Nanocomposites[END_REF][START_REF] Luna | Giant Permittivity Polymer Nanocomposites Obtained by Curing a Direct Emulsion[END_REF][START_REF] Yuan | Graphene liquid crystal retarded percolation for new high-k materials[END_REF][START_REF] Li | Enhanced electromechanical properties in all-polymer percolative composites[END_REF][START_REF] Yin | Mechanical energy harvesting via a plasticizer-modified electrostrictive polymer[END_REF].

These polymers have high dielectric permittivity and are used as the dielectric layer inside variable capacitors. Capacitance variations in response to mechanical variations are enhanced by changes of dielectric permittivity of the electrostrictive polymers. This principle can be used to convert mechanical energy of vibrations into electrical energy. The interest in electrostrictive polymers is rapidly growing because polymer-based high-permittivity materials are flexible, low cost, and easily tunable, which makes them good candidates for IoT applications. A recent approach for obtaining high permittivity electrostrictive polymers is the use of polymers loaded with conductive nanoparticles [START_REF] Luna | Giant Electrostrictive Response and Piezoresistivity of Emulsion Templated Nanocomposites[END_REF][START_REF] Luna | Giant Permittivity Polymer Nanocomposites Obtained by Curing a Direct Emulsion[END_REF][START_REF] Yuan | Graphene liquid crystal retarded percolation for new high-k materials[END_REF][START_REF] Li | Enhanced electromechanical properties in all-polymer percolative composites[END_REF][START_REF] Yin | Mechanical energy harvesting via a plasticizer-modified electrostrictive polymer[END_REF]. These composite materials exhibit a large increase of dielectric permittivity in the vicinity of their percolation threshold but suffer from a weakness due to the substantial increase of losses near and above percolation [START_REF] Yin | Mechanical energy harvesting via a plasticizer-modified electrostrictive polymer[END_REF][START_REF] Parant | Flowing suspensions of carbon black with high electronic conductivity for flow applications: Comparison between carbons black and exhibition of specific aggregation of carbon particles[END_REF].

To overcome these limitations, we design a new bilayer structure based on a microporous dielectric layer associated with a thin insulating layer of polydimethyl siloxane (PDMS). Porous flexible materials of which the internal pores are covered with carbon black particles are prepared using a water-in-oil emulsion. This new composite possesses a high dielectric permittivity along with a very low conductivity. We show that the fabrication of the microporous dielectric layer using a water-in-oil emulsion provides a fine control of the location of the conductive inclusions.

The latter remain confined in the emulsions droplets. The micropores significantly deform upon compression resulting in a large change of the dielectric permittivity [START_REF] Jones | Particle shape effects on the effective permittivity of anisotropic or isotropic media consisting of aligned or randomly oriented ellipsoidal particles[END_REF]. As such, the porous dielectric material can be used in a variable-capacitance engine to harvest mechanical energy [START_REF] Boisseau | Electrostatic Conversion for Vibration Energy Harvesting[END_REF].The energy harvesting performance can be improved by combining the porous dielectric with a thin insulating layer of PDMS. This reduces the conductivity of the system, and allows an increase of the filler concentration above the percolation threshold in the high permittivity layer.

The electrostrictive properties of the material can be finely tuned by varying the concentration of conductive particles. The presented bilayer structures exhibit high effective relative dielectric permittivity (up to 182 at 100 Hz) with a very low effective conductivity (down to 2.53⋅10 -8 S m - 1 ). They can generate electrical energy in response to mechanical vibrations with a power density of 0.4 W cm -3 . The efficiency of electrostrictive materials for actual energy harvesting applications can be assessed by their so-called Figure of Merit (FoM). FoM of the present materials exceeds the previous-best electrostrictive materials based on mixtures of fluorinated terpolymers and carbon black particles by a factor 1.7, and by almost four orders magnitude more conventional composites made of polyurethane and carbon black particles. They have also a low cost considering the components they are made of. In addition, considering their large flexibility (Young's modulus of about 1MPa) and sensitivity of dielectric properties, the presented materials are well suited for capacitive sensors with high sensitivity.

Experimental details:

Material synthesis:

The emulsion consists of an aqueous solution of carbon black droplets dispersed in a matrix of PDMS and a curing agent. We used the following procedure (FIG. 1). The water phase is prepared by mixing 5 g of arabic gum (Sigma Aldrich) and 95 g of deionized water. The desired concentration of carbon black powder (Alfa Aesar) is added and the mixture is tip sonicated during 1 hour at 400 W to homogeneously disperse the carbon black (CB) particles [START_REF] Parant | Flowing suspensions of carbon black with high electronic conductivity for flow applications: Comparison between carbons black and exhibition of specific aggregation of carbon particles[END_REF]. The oil phase is prepared by mixing PDMS (Dow Corning), the curing agent (Dow Corning, 10% in weight with respect to the PDMS phase), and the surfactant lauryl PEG-8 dimethicone (Silube J208-812, Siltech, 5.0 wt% of the final mixture). The emulsion is prepared by progressively adding the carbon black solution to the oil phase under manual stirring up to a mass ratio of water:oil=1:1. The mean droplet size depends on the viscosity of the continuous phase and ranges between 10-30 m. The water-in-oil emulsion loaded with carbon black particles is spread with a stencil that has a depth of 500 µm on a plastic surface with a diameter of 24 mm. A second plastic surface is placed on the spread emulsion such that the emulsion remains confined between two flat surfaces. Solid materials are obtained by curing the PDMS polymer without evaporation in a warm water bowl (90°C) for 4 hours. The relative humidity in these conditions is 100%.

Then, the solid material layer is removed from the two plastic surfaces and dried in an oven for 1 hour at 150°C. As PDMS is permeable to water vapor, droplets from carbon black solution dried and leave a structure with spherical-shaped pores covered by carbon black particles (FIG. 2).

4

Curing and drying are critical stages which strongly influence the final morphology of the porous composite.

Isolating layer deposition:

To decrease the dielectric losses, the microporous materials are combined with a thin insulating layer of PDMS. The insulating layer is spin coated on conductive aluminum substrates with a diameter of 24 mm. For the spin-coating, 3 g of PDMS with a curing agent (10% in weight with respect to the PDMS phase) is deposited at rest on an aluminum substrate. Then a spin-coater is used at 8000 rpm for 60 s at an acceleration of 1000 rpm s -1 to obtain a thickness of the PDMS layer of 5 m. The aluminum substrate covered by the PDMS layer is then soft baked at 100 ºC for 30 minutes to cure the PDMS. The thickness of the layer is measured by a mechanical profilometer (Dektak 150) after scratching the surface.

FIG.2: Electron microscope picture of a cross-cut of a porous porous carbon black composite. FIG.1: Scheme of the preparation of the microporous materials with pores covered by carbon black particles. (a) Preparation of the oil phase by mixing PDMS, curing agent, and surfactant. (b) Preparation of the water phase by mixing water and arabic gum. (c) Dispersion of black carbon powder in water phase. (d) Dispersion of water phase inside the oil phase. (e) Spreading of the emulsion between two surfaces and immersion in a water bowl. (f) The PDMS in the emulsion is cured by increasing the temperature of water. (g) Evaporation of the water by increasing the temperature outside the water bath. (h) Finally, a

porous and dried composite is obtained.

Determination of the dielectric properties

We measure the electrical conductivity and dielectric permittivity of the samples between two metallic disc electrodes in the frequency range of 10-10 6 Hz under an applied voltage of 1 V using an impedance analyzer (Bio-Logic Impedance Analyser, MTZ-35). A calibration procedure removing the contribution of the polarization of the electrodes is used to determine the dielectric permittivity and the conductivity of the sample as a function of frequency [START_REF] Luna | Giant Permittivity Polymer Nanocomposites Obtained by Curing a Direct Emulsion[END_REF]. All the experiments are performed at room temperature.

Determination of the electromechanical performances

To determine the electrostrictive properties of the composites we use the experimental setup illustrated in FIG. 3, which consists of a piezoelectric actuator (Physik Instrumente P-842.30) driven by a function generator (Keysight 33611A Waveform Generator) that applies a sinusoidal mechanical strain at a frequency of 100 Hz. The sample is placed between two electrodes: the top electrode is connected to the piezo actuator and moves at the same frequency as the actuator, the bottom electrode is fixed to the sample holder and does not move. As such, a modulated strain is applied along the thickness of the material. The strain is controlled by a computer linked to a function generator which controls the stroke of the actuator. An electric field is applied to the composite along the height (3-direction in FIG. 3) by a DC generator. To measure the current and generated power, a load resistance (R) is connected in series with the sample. The voltage U R over the resistance is recorded by an oscilloscope (Keysight InfiniiVision 1000 X) and the current is determined using the Ohm's law (I=U R /R l ).

R i R l 6
The Young's modulus of the composites is measured using a tensile tester (Instron Model 4505). The initial dimensions (width and thickness) are measured before mounting the sample between the fixed and moving jaws. The force-displacement responses are acquired for each sample at a displacement rate of 0.067 mm s -1 . The tests ended when the specimens fractured. The Young's modulus is determined by measuring the slope of stress-strain curves in the elastic domain.

The composite material is modeled by a parallel RC circuit (see FIG. 3b). The observed current is composed of two parts: a leakage current I dc and a harvested current I h induced by compression-decompression cycles of the composite. According to the model developed by Guyomar et al [START_REF] Lallart | Evaluation of energy harvesting performance of electrostrictive polymer and carbon-filled terpolymer composites[END_REF][START_REF] Cottinet | Modeling and experimentation on an electrostrictive polymer composite for energy harvesting[END_REF], for a sinusoidal strain the current through a load resistance Rl is given by (see supporting information)

(EQ. 1)
Here, A is the area of the sample, Y is the Young's modulus, is the apparent electrostrictive coefficient [START_REF] Luna | Giant Electrostrictive Response and Piezoresistivity of Emulsion Templated Nanocomposites[END_REF], is the applied bias electric field ( , S is the sinusoidal strain amplitude equaling the displacement induced by the piezo actuator (24 µm) divided by two times the material thickness, is the relative dielectric permittivity, is the vacuum permittivity, d is the material thickness, and is the angular frequency of the applied strain. Hence, a linear relation between and is obtained for a constant strain, frequency, and load resistance. As a result, the product can be easily estimated from the slope of the I-E dc curves. The apparent electrostrictive coefficient is calculated by division of the Young's modulus Y.

3 Results:

Polymer-carbon black composites:

The dielectric properties of the polymer/carbon black composite, without insulating layer, are first studied at rest. The load fraction of carbon black particles inside composites is varied while keeping the oil:water ratio constant. FIG. 4 shows the electrical conductivity, dielectric permittivity, and loss tangent ( , with the electrical conductivity) as a function of the frequency for different carbon black particle concentrations.

7

Both conductivity and dielectric permittivity increase as a function of CB concentration. The percolation threshold is reached for a weight fraction of 6%. Below the percolation threshold, the conductivity is frequency dependent and arises from dielectric losses due to bound charges. In the meantime, the dielectric permittivity remains constant for the full range of investigated frequencies. Above the percolation threshold, and at low frequencies, the conductivity is constant because essentially due to the transport of free charges brought by the carbon black particles. By contrast, the dielectric permittivity presents frequency dependence and is enhanced by the interfacial polarization of the carbon black particles. In the high filler concentration regimes, the values of conductivity (above 10 -6 S m -1 ) make the materials unsuitable for vibrational energy harvesting.

Bilayer polymer-carbon black composites:

The high conductivity (free charges carriers and dielectric loss) of the carbon black composites is a drawback for energy harvesting applications [START_REF] Cottinet | Modeling and experimentation on an electrostrictive polymer composite for energy harvesting[END_REF]. Indeed, such applications do not allow any leakage for yielding a positive energy conversion. In this paper, we propose an original approach for keeping high values of effective dielectric permittivity and low values of conductivity by associating a thin insulating layer to the high permittivity layer. This layer has low dielectric losses and no free charge carriers. It acts as a blocking layer and prevents leaks of the capacitors (FIG. 5). The electrical equivalent circuit for a bilayer material is a junction of two RC circuits in series.

The expressions for the effective dielectric properties of the bilayer structure are given in the supporting information. The effective conductivity and dielectric constant of the bilayer structure depend on the thicknesses and dielectric properties of both layers. The blocking layer 2 is a cured PDMS layer ( and 10 -13 S m -1 in the range 10-10 6 Hz at 25°C) of thickness 5 m. The high permittivity layer 1 is the porous carbon black material layer of variable thickness depending on carbon black concentration (see Table 1). For comparison, we investigate the dielectric properties of the electrostrictive composites at rest with and without insulating layer. FIG. 6 shows the relative dielectric permittivity, electrical conductivity, and loss tangent at 100 Hz as a function of the carbon black concentration. First, we consider the electrostrictive composites without insulating layer. At carbon black concentrations below the percolation threshold (~5 wt%), the dielectric permittivity has a nearly constant value of ~10 with an electric conductivity of ~1 nS m -1 . Above the percolation threshold, the dielectric permittivity rapidly increases to 550 at 6 wt%. However, the electrical conductivity also increases by a factor of 10 3 , leading to a loss tangent above 1. A further addition of conductive carbon black particles enhances the interfacial polarization, which leads to an increase in permittivity but also leads to further increase of the electrical conductivity to 0.6 mS m -1 at ~8 wt%. Such a high conductivity does not allow the efficient use of the materials as a dielectric layer in variable capacitors.

The effective dielectric properties of the electrostrictive composites with an insulating layer are very different at carbon black concentrations above the percolation threshold. The PDMS layer limits the electric conductivity below 1-10 nS m -1 . The insulating layer also leads to a decrease of the effective dielectric permittivity to 157 and 182 for the 8 and 10 wt% black carbon weight fractions, respectively. However, the obtained dielectric loss tangents are very low with 1.5⋅10 -2 and 2.5⋅10 -2 for the 8 and 10 wt% carbon black systems, respectively, making them well suited for energy harvesting applications. Theoretical calculations of the conductivity (see supporting information) predict values slightly lower than the ones found experimentally, probably as a result of small holes and defects in the insulating PDMS layer.

Electromechanical performances and power harvested estimation:

We now investigate the performance of the bilayer composites for energy harvesting purposes.

First, the electromechanical performances are assessed by calculating the figure of merit (FoM) proposed by Guyomar et al. [START_REF] Lallart | Evaluation of energy harvesting performance of electrostrictive polymer and carbon-filled terpolymer composites[END_REF][START_REF] Cottinet | Modeling and experimentation on an electrostrictive polymer composite for energy harvesting[END_REF]:

(EQ.2) 10
The FoM depends only on materials properties ( , Y, and aims at comparing electromechanical performances of materials without any external parameters such as geometry and measurement details. Three compositions (6, 8, and 10 wt%) are used for performances comparisons (Table 2). Properties of the materials are reported in Table 2. FoM, and Y are measured using the methods described in the experimental section.

Determination of the harvested power:

Next, we examine the power generation properties of the bilayer composites by discharge over a load resistance R l . As shown in FIG. 8, the voltage drop over the resistance U r and the instantaneous harvested power are monitored as a function of time. The average harvested power per cycle is calculated using

(EQ. 3)
where T is the period of the cycle. The theoretical harvested power is given by (see supporting information) , (EQ. 4)

where .

FIG. 9 shows the value of the theoretical and experimental power harvestable as a function of the load resistance. Best values are obtaining for a load resistance of about 1 M for both materials, which corresponds to the resistance with optimal power production ( ). Good agreement is observed between the experimental data and theoretical powers. In addition, the increase in FoM by a factor 5 between 8 CB wt% and 10 CB wt% leads to an increase in harvested power by a factor 6.

Efficiency:

FIG. 9: Harvested power of the composites with 8 CB wt% (green) and 10 CB wt% (pink) with insulating layer as a function of the load resistance. Squares are experimental data and lines are theoretical predictions using EQ. 7.

The strain frequency is 100 Hz and the applied voltage over the composite V dc = 32 V.

12 To get a positive energy balance, the dissipated power must be smaller than the harvested power.

The dissipated power for maintaining a polarization of the composite is given by [START_REF] Cottinet | Modeling and experimentation on an electrostrictive polymer composite for energy harvesting[END_REF]: , (EQ. 5)

where is the internal leak resistance, is the load resistance values, and is the applied voltage difference. The internal leak resistance is calculated by R i = with the data from Table 2. The electrical energy gain is calculated by considering the ratio of power harvestable to electrical polarization losses for a bias voltage of V dc = 32 V and a load resistance of R l =1 MΩ.

Discussions:

The use of an insulating layer limits the electric conductivity below 1-10 nS m -1 and allows us to use our materials for energy harvesting. Data given in Table 3 show that the energy balance is largely positive for both materials. The power produced by the mechanical-electrical conversion for the 8 wt% composite is 1.74 times higher than the power dissipated to polarize it and the net power harvestable is around 0.17 W m -3 . We can see that increasing the CB wt% enables to increase the net harvested power by almost a factor 4, i.e. up to 0.38 W m -3 . This is a consequence of the increase of permittivity of the material at 10 wt%. But at the same time, the conductivity of the 10 wt% composite is 1.9 higher than that of the 8 wt% composite which has a conductivity of 1.30⋅10 -8 S m -1 ; leading to a net decrease in the energy balance, but to an increased overall power production. These excellent performances can be explained by the porous structure of the materials and insulating properties of the thin polymer layer. As a result, the electric field required to polarize the material is decreased, which is crucial for vibrational energy harvesting applications.

13 FIG. 7 presents the FoM of materials from the literature, and of composites developed in this work. The values of the FOM are enhanced by increasing the filler concentration. For 10 wt% CB, the FoM is equal to 5.06⋅10 -8 This result exceeds the previous-best electrostrictive materials based on a of Polyvinylidene fluoride (PVDF) terpolymers and carbon black by a factor 1.7. In addition, it outperforms in term of process and material cost and toxicity [START_REF] Jones | Particle shape effects on the effective permittivity of anisotropic or isotropic media consisting of aligned or randomly oriented ellipsoidal particles[END_REF][START_REF] Boisseau | Electrostatic Conversion for Vibration Energy Harvesting[END_REF]. Increasing the FoM is a key point for increasing the power harvestable as we show below. Besides, their low Young's modulus compared to PVDF polymers (~ GPa) could enlarge the scope of applications using low stress vibrations.

Conclusions:

We presented microporous electrostrictive composites with improved properties for vibrational energy harvesting. These systems are made of carbon black particles dispersed in a porous PDMS matrix. An inverted emulsion templating approach provides a fine control of the location of the particles which is a key factor to achieve high permittivity and low losses. A thin insulating layer was added to limit further the losses. The resulting structure possesses a very large effective FIG. 7: Comparison of the electromechanical performances at 100 Hz using the figure of merit (FoM) proposed by Guyomar et al. [START_REF] Lallart | Evaluation of energy harvesting performance of electrostrictive polymer and carbon-filled terpolymer composites[END_REF][START_REF] Cottinet | Modeling and experimentation on an electrostrictive polymer composite for energy harvesting[END_REF]. Thick lines have the same FOM. Black spots refer to materials from the literature [START_REF] Lallart | Evaluation of energy harvesting performance of electrostrictive polymer and carbon-filled terpolymer composites[END_REF][START_REF] Cottinet | Modeling and experimentation on an electrostrictive polymer composite for energy harvesting[END_REF].

14 relative dielectric permittivity of 182 at 100 Hz in combination with a very low loss tangent of 2.5⋅10 -2 . We succeeded in evaluating the energy scavenging abilities of these composites. More than 300 nW has been harvested with the 10 wt% carbon black composites which leads to a power density of 0.4 W cm -3 . The present materials exhibits a figure of merit as high as 5.06⋅10 -8 which is 1.7 times higher than the best reference fluorinated polymers and 3350 times higher than pure polyurethane [START_REF] Jones | Particle shape effects on the effective permittivity of anisotropic or isotropic media consisting of aligned or randomly oriented ellipsoidal particles[END_REF]. The low cost process and low toxicity make the carbon black bilayer composites very promising materials for vibrational energy harvesting. The power harvested with our materials is good enough to provide a significant boost to the battery life of ultra-low power devices. For example, the Phoenix processor [START_REF] Hanson | A Low-Voltage Processor for Sensing Applications With Picowatt Standby Mode[END_REF][START_REF] Jayakumar | Powering the internet of things[END_REF] has a sleep power consumption of only 30 pW and 200 nW in active mode which makes our materials suitable for this application. In addition, these carbon black bilayer composites, with excellent dielectric properties, could find potential applications as low cost flexible capacitors sensors in the printed electronics industry.

5 Supporting information

Effective dielectric properties of a stacked bilayer

The effective relative dielectric permittivity and conductance of two stacked dielectric layers are calculated by [START_REF]Dielectric relaxation in biological systems: physical principles, methods, and applications[END_REF] with .

Here, is the thickness of layer 1, is the thickness of layer 2. and are the dielectric constant and conductivity of layer , respectively, and is the vacuum permittivity.

Theoretical derivation of the harvested current

Here, we expose a theoretical derivation of the harvested current for a pure electrostrictive material (i.e. no piezoelectric behaviour). We depart from the differential equation for the harvested current as derived by Lallart et al. [START_REF] Jones | Particle shape effects on the effective permittivity of anisotropic or isotropic media consisting of aligned or randomly oriented ellipsoidal particles[END_REF] for a small strain : where is an integration constant, which we set to zero as is finite. This leaves us with the following integral:

For a sinusoidal strain with amplitude S and angular frequency ω, i.e. , the harvested current becomes .

By applying integration by parts twice we get . 17

We now insert the definitions for and and obtain

Derivation of the harvested power

The average harvested power of a cycle can be obtained by calculating where is the period of the cycle.

Inserting the above derived expression for , we obtain .

5

 5

FIG. 3 :

 3 FIG.3: Schematic of the experimental setup (a) and the equivalent electric circuit (b).

FIG. 4

 4 FIG. 4 : a) Evolution of the dielectric permittivity (a), conductivity (b) and loss tangent (c) as a function of the frequency for various CB particle concentrations. 3.0 wt % (black squares), 4.0 wt % (red circles), 6.0 wt% (purple top triangles), 8.0 wt% (green down triangles) , 10 wt% (pink left triangles)Phase fractions are fixed: oil:water = 1:1

1 FIG. 6 :

 16 FIG. 6: Effective dielectric properties at 100 Hz of the porous carbon black layer (red circles), bilayer polymer-carbon black composites (black squares), and theoretical predictions of the latter (open black triangles), as a function of carbon black concentration.

FIG. 8 :

 8 FIG. 8: The voltage difference (a) and instantaneous power (b) across a load resistance of 1 MΩfor a 100 Hz sinusoidal strain. The applied bias voltage over the bilayer composite with 8 wt% carbon black is 32 V.

, 16 For

 16

Table 1 :

 1 Properties of the carbon black (CB) composites.

	FIG. 5: Equivalent electric circuits for the porous black carbon (a) and the
	bilayer (b) composite.	and d i are the dielectric permittivity, the
	conductivity, and the thickness of the layer i, respectively.
	3	31	500
	4	42	510
	6	64	510
	8	87	750
	10	110	800

% CB CB (g L -1 ) Thickness (µm)

Table 2 :

 2 Materials properties

	% CB	Oil fraction	CB (g L -1 )	Thickness (µm)	Surface (m²)	M* Y	Y (MPa) (m 2 V -2 )
	6.0	0.5	6.4⋅10 1	5,1⋅10 2	1.1⋅10 -3 2.2⋅10 -10 1,38	1,60⋅10 -16
	8.0	0.5	8,7⋅10 1	7.5⋅10 2	6.2⋅10 -4	1.5⋅10 -9	1,40	1,07⋅10 -15
	10.0	0.5	1.1⋅10 2	8.0⋅10 2	1.0⋅10 -3	3.6⋅10 -9	1,61	8,46⋅10 -15

Table 3 :

 3 Efficiency of the bilayer composites for different carbon black concentrations.

	% CB Harvested power (W)	Power loss (W)	Net power production (µW)	Electrical gain factor
	8.00	0.20	0.12	0.08	1.74
	10.0	1.3	1.0	0.3	1.31

Acknowledgements: We acknowledge financial support from the following organisms and projects: Université de recherche Paris Sciences et Lettres, the Université Pierre et Marie Curie, ANR Project ANR-12-NANO-0002 ELENA, and ANR in the Cluster of Excellence AMADEUS.