Éric Fusy

Gregory Kucherov
email: eric.fusy|gregory.kucherov@univ-eiffel.fr

Phase transition in count approximation by Count-Min sketch with conservative updates

Count-Min sketch is a hash-based data structure to represent a dynamically changing associative array of counters. Here we analyse the counting version of Count-Min under a stronger update rule known as conservative update, assuming the uniform distribution of input keys. We show that the accuracy of conservative update strategy undergoes a phase transition, depending on the number of distinct keys in the input as a fraction of the size of the Count-Min array. We prove that below the threshold, the relative error is asymptotically o(1) (as opposed to the regular Count-Min strategy), whereas above the threshold, the relative error is Θ(1). The threshold corresponds to the peelability threshold of random k-uniform hypergraphs. We demonstrate that even for small number of keys, peelability of the underlying hypergraph is a crucial property to ensure the o(1) error. Finally, we provide an experimental evidence that the phase transition does not extend to non-uniform distributions, in particular to the popular Zipf's distribution.

Introduction

Count-Min sketch is a hash-based data structure to represent a dynamically changing associative array a of counters in an approximate way. The array a can be seen as a mapping from some set K of keys to N, where K is drawn from a (large) universe U . The goal is to support point queries about the (approximate) current value of a(p) for a key p. Count-Min is especially suitable for the streaming framework, when counters associated to keys are updated dynamically. That is, updates are (key,value) pairs (p, ) with the meaning that a(p) is updated to a(p) + .

Count-Min sketch was proposed in [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF], see e.g. [START_REF] Cormode | Count-min sketch[END_REF] for a survey. A similar data structure was introduced earlier in [START_REF] Cohen | Spectral bloom filters[END_REF] named Spectral Bloom filter, itself closely related to Counting Bloom filters [START_REF] Fan | Summary cache: a scalable wide-area web cache sharing protocol[END_REF]. The difference between Count-Min sketch and Spectral Bloom filter is marginal: while a Count-Min sketch requires hash functions to have disjoint codomains (rows of Count-Min matrix), a Spectral Bloom filter has all hash functions mapping to the same array, as does the regular Bloom filter. In this paper, we will deal with the Spectral Bloom filter version but will keep the term Count-Min sketch as more common in the literature.

Count-Min sketch supports negative update values provided that at each moment, each counter a(p) remains non-negative (so-called strict turnstile model [START_REF] Liu | Methods for mining frequent items in data streams: an overview[END_REF]). When updates are positive, the Count-Min update algorithm can be modified to a stronger version leading to smaller errors in 1 queries. This modification, introduced in [START_REF] Estan | New directions in traffic measurement and accounting[END_REF] as conservative update, is mentioned [START_REF] Cormode | Count-min sketch[END_REF], without any formal analysis given in those papers. This variant is also discussed in [START_REF] Cohen | Spectral bloom filters[END_REF] under the name minimal increase, where it is claimed that it decreases the probability of a positive error by a factor of the number of hash functions, but no proof is given. We discuss this claim in the concluding part of this paper.

The case of positive updates is widespread in practice. In particular, a very common instance is counting where all update values are 1. This task occurs in different scenarios in network traffic monitoring, as well as other applications related to data stream mining [START_REF] Estan | New directions in traffic measurement and accounting[END_REF]. In bioinformatics, we may want to maintain, on the fly, multiplicities of k-mers (words of length k) occurring in a big dataset [START_REF] Mohamadi | ntcard: a streaming algorithm for cardinality estimation in genomics data[END_REF][START_REF] Behera | Kmerestimate: A streaming algorithm for estimating k-mer counts with optimal space usage[END_REF][START_REF] Shibuya | Set-min Sketch: a Probabilistic Map for Power-Law Distributions with Application to k-mer Annotation[END_REF]. We refer to [START_REF] Einziger | A formal analysis of conservative update based approximate counting[END_REF] for more examples of applications.

While it is easily seen that the error in conservative update can only be smaller than in Count-Min, obtaining more precise bounds is a challenging problem. Count-Min guarantees, with high probability, that the additive error can be bounded by ε a 1 for any ε, where a 1 is the L1-norm of a [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF]. In the counting setting, a 1 is the length of the input stream which can be very large, and therefore this bound provides a weak guarantee in practice, unless the distribution of keys is very skewed and queries are made on frequent keys (heavy hitters) [START_REF] Liu | Methods for mining frequent items in data streams: an overview[END_REF][START_REF] Charikar | Finding frequent items in data streams[END_REF][START_REF] Cormode | Finding frequent items in data streams[END_REF]. It is therefore an important practical question to analyse the improvement provided by the conservative update strategy compared to the original Count-Min sketch.

Probably the first attempt towards this goal was made in [START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF], under assumption that all n k counter combinations are equally likely at each step (n size of the Count-Min array, k number of hash functions) which amounts to assuming uniform distribution on n k input keys. For the regime when the number of distinct keys in the input considerably exceeds the sketch size, it was experimentally observed in [START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF] that frequent keys have essentially no error while the (over)estimate for less frequent keys tends be the same, for given input stream length and sketch size. On the other hand, it was experimentally shown that in that regime, the uniform distribution of keys presents the worst-case scenario producing the largest such estimate and a method was proposed to compute this estimate. Another method for bounding the error proposed in [START_REF] Einziger | A formal analysis of conservative update based approximate counting[END_REF] is based on a simulation of spectral Bloom filters by a hierarchy of ordinary Bloom filters. However, the bounds provided are not explicit but are expressed via a recursive relation based on false positive rates of involved Bloom filters. Recent works [START_REF] Younes Ben Mazziane | A formal analysis of the countmin sketch with conservative updates[END_REF][START_REF] Younes Ben Mazziane | Analyzing Count Min Sketch with Conservative Updates[END_REF] propose formulas for computing error bounds depending on key probabilities assumed independent but not necessarily uniform, in particular leading to an improved precision bounds for detecting heavy hitters.

In this paper, we provide a probabilistic analysis of the conservative update scheme for counting under the assumption of uniform distribution of keys in the input. Our main result is a demonstration that the error in count estimates undergoes a phase transition when the number of distinct keys grows relative to the size of the Count-Min array. We show that the phase transition threshold corresponds to the peelability threshold for random k-uniform hypergraphs. For the subcritical regime, when the number of distinct keys is below the threshold, we show that the relative error for a randomly chosen key tends to 0 asymptotically, with high probability. This contrasts with the regular Count-Min algorithm producing a relative error shown to be at least 1 with constant probability.

For the supercritical regime, we show that the average relative error is lower-bounded by a constant (depending on the number of distinct keys), with high probability. We prove this result for k = 2 and conjecture that it holds for arbitrary k as well. We provide computer simulations showing that the expected relative error grows fast after the threshold, with a distribution showing a peculiar multi-modal shape. In particular, keys with small (or zero) error still occur after the threshold, but their fraction quickly decreases when the number of distinct keys grows.

After defining Count-Min sketch and conservative update strategy in Section 2 and introducing hash hypergraphs in Section 3, we formulate the conservative update algorithm (or regular Count-Min, for that matter) in terms of a hypergraph augmented with counters associated to vertices. In Section 4, we state our main results and illustrate them with a series of computer simulations. All technical proofs are provided in a separate Section 5.

In addition, in Section 6, we study a specific family of 2-regular k-hypergraphs that are sparse but not peelable. For such graphs we show that while the relative error of every key is 1 with the regular Count-Min strategy, it is 1/k + o(1) for conservative update. While this result is mainly of theoretical interest, it illustrates that the peelability property is crucial for the error to be asymptotically vanishing. Finally, in Section 7, we turn to non-uniform distributions and provide experimental evidence that for Zipf's distribution, the phase transition in average error does not occur.

Count-Min and Conservative Update

We consider a (counting version of) Count-Min sketch to be an array A of size n of counters initially set to 0, together with hash functions h 1 , . . . , h k mapping keys from a given universe to [1..n]. To count key occurrences in a stream of keys, regular Count-Min proceeds as follows. To process a key p, each of the counters A[h i (p)], 1 ≤ i ≤ k, is incremented by 1. Querying the occurrence number a(p) of a key p returns the estimate âCM (p) = min 1≤i≤k {A[h i (p)]}. It is easily seen that âCM (p) ≥ a(p). A bound on the overestimate of a(p) is given by the following result adapted from [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF].

Theorem 1 ( [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF]) For ε > 0, δ > 0, consider a Count-Min sketch with k = ln( 1 δ ) and size n = k e ε . Then âCM (p) -a(p) ≤ εN with probability at least 1 -δ, where N is the size of the input stream.

While Theorem 1 is useful in some situations, it has a limited utility as it bounds the error with respect to the stream size which can be very large.

Conservative update strengthens Count-Min by increasing only the smallest counters among

A[h i (p)]. Formally, for 1 ≤ i ≤ k, A[h i (p)] is incremented by 1 only if A[h i (p)] = min 1≤j≤k {A[h j (p)]}
and is left unchanged otherwise. The estimate of a(p), denoted âCU (p), is computed as before: âCU (p) = min 1≤i≤k {A[h i (p)]}. It can be seen that âCU (p) ≥ a(p) still holds, and that âCU (p) ≤ âCM (p). The latter follows from the observation that on the same input, an entry of counter array A under conservative update can never get larger than the same entry under Count-Min.

Hash hypergraphs and CU process

With a counter array A[1..n] and hash functions h 1 , ..., h k we associate a k-uniform hash hypergraph H = (V, E) with vertex-set V = {1..n} and edge-set E = {{h 1 (p), ...h k (p)}} for all distinct keys p. Let H k n,m be the set of k-uniform hypergraphs with n vertices and m edges. We assume that the hash hypergraph is a uniformly random Erdős-Rényi hypergraph in H k n,m , which we denote by H k n,m , where m is the number of distinct keys in the input (for k = 2, we use the notation G n,m = H 2 n,m ). Even if this property is not granted by hash functions used in practice, it is a reasonable and commonly used hypothesis to conduct the analysis of sketch algorithms.

Below we show that the behavior of a sketching scheme depends on the properties of the associated hash hypergraph. It is well-known that depending on the m/n ratio, many properties of Erdős-Rényi (hyper)graphs follow a phase transition phenomenon [START_REF] Frieze | Introduction to Random Graphs[END_REF]. For example, the emergence of a giant component, of size O(n), occurs with high probability (hereafter, w.h.p.) at the threshold [START_REF] Luczak | The phase transition in a random hypergraph[END_REF]. Particularly relevant to us is the peelability property. Let H = (V, E) be a hypergraph. The peeling process on H is as follows. We define H 0 = H, and iteratively for i ≥ 0, we define V i to be the set of leaves (vertices of degree 1) or isolated vertices in H i , E i to be the set of edges of H i incident to vertices in V i , and H i+1 to be the hypergraph obtained from H i by deleting the vertices of V i and the edges of E i . A vertex in V i is said to have peeling level i. The process stabilizes from some step I, and the hypergraph H I is called the core of H, which is the largest induced sub-hypergraph whose vertices all have degree at least 2. If H I is empty, then H is called peelable.

m n = 1 k(k-1)
It is known [START_REF] Molloy | Cores in random hypergraphs and boolean formulas[END_REF] that peelability undergoes a phase transition. For k ≥ 3, there exists a positive constant λ k such that, for λ < λ k , the random hypergraph H k n,λn is w.h.p. peelable as n → ∞, while for λ > λ k , the core of H k n,λn has w.h.p. a size concentrated around αn for some α > 0 that depends on λ. The first peelability thresholds are λ 3 ≈ 0.818, λ 4 ≈ 0.772, etc., λ 3 being the largest.

For k = 2, for λ < 1/2, w.h.p. a proportion 1 -o(1) of vertices are in trees of size O(1), (and a proportion o(1) of the vertices are in the core), while for λ ≥ 1/2, the core size is w.h.p. concentrated around αn for α > 0 that depends on λ [START_REF] Pittel | Counting connected graphs inside-out[END_REF].

We note that properties of hash hypergraphs determine the behavior of some other hash-based data structures, such as Cuckoo hash tables [START_REF] Pagh | Cuckoo hashing[END_REF] and Cuckoo filters [START_REF] Fan | Cuckoo filter: Practically better than bloom[END_REF], Minimal Perfect Hash Functions and Static Functions [START_REF] Bohdan S Majewski | A family of perfect hashing methods[END_REF], Invertible Bloom filters [START_REF] Michael | Invertible bloom lookup tables[END_REF], and others. We refer to [START_REF] Walzer | Random hypergraphs for hashing-based data structures[END_REF] for an extended study of relationships between properties of hash hypergraphs and some of those data structures. In particular, peelability is directly relevant to certain constructions of Minimal Perfect Hash Functions as well as to good functioning of Invertible Bloom filters.

The connection to hash hypergraphs allows us to reformulate the Count-Min algorithm with conservative updates as a process, which we call CU-process, on a random hypergraph H k n,m , where n, m, k correspond to counter array length, number of distinct keys, and number of hash functions, respectively. Let H = (V, E) be a hypergraph. To each vertex v we associate a counter c v initially set to 0. At each step t ≥ 1, a CU-process on H chooses an edge e = {v 1 , . . . , v k } ∈ E in H, and increments by 1 those c v i which verify c v i = min 1≤j≤k c v j . For t ≥ 0 and v ∈ V , c v (t) will denote the value of the counter c v after t steps, and o e (t) the number of times edge e ∈ E has been drawn in the first t steps. The counter c e (t) of an edge e = {v 1 , . . . , v k } is defined as c e (t) = min 1≤i≤k c v i (t). Clearly, for each t and each e, o e (t) ≤ c e (t). The relative error of e at time t is defined as R e (t) = ce(t)-oe(t) oe(t)

. The following Lemma can be easily proved by induction on t.

Lemma 1 Let H = (V, E) be a hypergraph on which a CU-process is run. At every step t, for each vertex v, there is at least one edge e incident to v such that c e (t) = c v (t).

Observe that, when H is a graph (k = 2), Lemma 1 is equivalent to the property that vertex counters cannot have a strict local maximum, i.e., at every step t, each vertex v has at least one neighbour u such that c u (t) ≥ c v (t).

Phase transition of the relative error 4.1 Main results

Let

H = (V, E) be a hypergraph, |V | = n, |E| = m. Let N ≥ 1.
We consider two closely related models of input to perform the CU-process. In the N -uniform model, the CU process is performed on a random sequence of keys (edges in E) of length N • m, each key being drawn independently and uniformly in E. In the N -balanced model, the CU-process is performed on a random sequence of length N • m, such that each e ∈ E occurs exactly N times, and the order of keys is random. In other words, the sequence of keys on which the CU-process is performed is a random permutation of the multiset made of N copies of each key of E. Clearly, both models are very close, since the number of occurrences of any key in the N -uniform model is concentrated around N (with Gaussian fluctuations of order √ N ) as N gets large. For both models, we use the notation c e of an edge e = (v 1 , . . . , v k ) is always (whatever N ≥ 1) equal to min(deg(v 1 ), . . . , deg(v k ))-1, and is thus always a non-negative integer. For fixed k ≥ 2 and λ > 0, and for a random edge e in H k n,λn , the probability that all k vertices belonging to e have at least one incident edge apart from e converges to a positive constant c(λ, k) = (1 -e -kλ ) k . Therefore, Re is a nonnegative integer whose probability to be non-zero converges to c(λ, k). Thus, Theorem 2 ensures that, for λ < λ k , conservative updates lead to a drastic decrease of the error, from Θ(1) to o(1).

(N ) v = c v (N m) for the resulting counter of v ∈ V , o (
For a given hypergraph H = (V, E) with m edges, we define err

N (H) = 1 m e∈E R (N ) e
the average error over the edges of H. Theorem 2 states that a randomly chosen edge has a small error, but this does not formally exclude that a small fraction of edges may have large errors, possibly yielding err N (H) larger than o(1). However, we believe that this is not the case. From the previous remark, it follows that the error of an edge e = (v 1 , . . . , v k ) is upper-bounded by min(deg(v 1 ), . . . , deg(v k )) -1. Since the expected maximal degree in H k n,λn grows very slowly with n, one can expect that any set of o(n) edges should have a contribution o(1) w.h.p.. This is also supported by experiments given in the next section.

Based on Theorem 2 and the above discussion, we propound that a phase transition occurs for the average error, in the sense that it is o(1) in the subcritical regime λ < λ k , and Θ(1) in the supercritical regime λ > λ k , w.h.p.. Regarding the supercritical regime, we are able to show that this indeed holds for k = 2 in the N -balanced model.

Theorem 3 (supercritical regime, case k = 2) Let λ > 1/2. Then there exists a positive constant f (λ) such that, in the N -balanced model, err N (G n,λn ) ≥ f (λ) w.h.p., as n grows2 .

Our proof of Theorem 3 can be extended to any k ≥ 2 and λ >

1 k(k-1) such that the giant component G = (V , E ) in H k n,λn satisfies w.h.p. |E | -|V | ≥ a n
for some positive constant a. For k = 2, any value λ > 1/2 has this property [START_REF] Pittel | Counting connected graphs inside-out[END_REF], while for k = 3 (respectively, k = 4), the analysis given in [START_REF] Behrisch | Local limit theorems for the giant component of random hypergraphs[END_REF] ensures that this property holds for values of λ strictly above the peelability threshold, namely λ > λ 3 ≈ 0.94 (respectively, λ > λ 4 ≈ 0.98) . Nevertheless, based on simulations presented below, we expect that Theorem 3 holds for k ≥ 3 for all λ > λ k as well, however proving this would then require a different kind of argument.

Simulations

Here we provide several experimental results illustrating the phase transition stated in Theorems 2 and 3. Figure 1 The phase transitions are clearly seen to correspond to the critical threshold 0.5 for k = 2, and, for k ∈ {3, 4}, to the peelability thresholds λ 3 ≈ 0.818, λ 4 ≈ 0.772. Observe that the transition looks sharper for k ≥ 3, which may be explained by the fact that the core size undergoes a discontinuous phase transition for k ≥ 3, as shown in [START_REF] Molloy | Cores in random hypergraphs and boolean formulas[END_REF] (e.g. for k = 3, the fraction of vertices in the core jumps from 0 to about 0.13).

For the supercritical regime, we analysed the concentration around the average shown in Figure 1 by simulating CU-processes on 50 random graphs, for each λ. Figure 2 shows the results. We observe that the concentration tends to become tighter for growing λ. When λ grows beyond the peelability threshold, a fraction of edges with small errors still remains but vanishes quickly: these include edges incident to at least one leaf (these have error 0) and peelable edges (these have error o(1), by arguments to be given in Section 5.3). For intermediate values of λ, the distribution presents several modes: besides the main mode (largest concentration on plots of Figure 3), we observe a few other concentration values which are typically integers. While this phenomenon is still to be analysed, we explain it by the presence in the graphs of certain structural motifs that involve disparities in node degrees. Note that the fraction of values concentrated around the main mode is dominant: for example, for k = 3, λ = 3 (Figure 3d), about 90% of values correspond to the main mode (≈ 3.22). Finally, when λ becomes larger, these "secondary modes" disappear, and the distribution becomes concentrated around a single value. This is consistent with the tighter concentration observed earlier in Figure 2.

Finally, we report on another experiment supporting the conjecture of a positive average error in the supercritical regime. We simulated the CU-process on sparse random non-peelable 3-hypergraphs (i.e. k = 3), namely 2-regular 3-hypergraphs with 2n edges and 3n vertices (n parameter). These are sparsest possible non-peelable 3-hypergraphs, with degree 2 of each vertex. We observed that the average error for such graphs is concentrated around a constant value of ≈ 0.217. Since the core size is linear in the supercritical regime, this experiment provides an evidence of a positive error in the general case. While this remains to be proved in general, in Section 6 we provide a proof for certain families of regular hypergraphs.

(a) k = 2, λ = 1 (b) k = 3, λ = 1 (c) k = 2, λ = 3 (d) k = 3, λ = 3 (e) k = 2, λ = 5 (f) k = 3, λ = 5

Proofs of main results

Theorem 2 relies on properties of random hypergraphs. Case k = 2 corresponds to Erdős-Rényi random graphs G n,λn [START_REF] Erdos | On the evolution of random graphs[END_REF] which have been extensively studied [START_REF] Frieze | Introduction to Random Graphs[END_REF]. In particular, it is well known when λ < 1/2 and n gets large, G n,λn is, w.h.p., a union of small connected components most of which are constant-size trees. That is, a random edge in G n,λn is, w.h.p., in a tree of size O(1). Thus, the proof amounts to showing that, for a fixed tree T and a vertex v ∈ T , we have c

(N )

v /N = 1 + o(1) w.h.p.. We prove this in Section 5.1 for both N -uniform and N -balanced models.

The proof for k ≥ 3, given in Section 5.3, requires more ingredients. An additional difficulty is that, for λ < λ k , a random edge e in H k n,λn may be in the giant component (if λ ∈ ( 1 k(k-1) , λ k )). However, we rely on the fact that the peeling level of e is O(1) w.h.p., and prove that for a vertex v of bounded level, we have c

CU-process on a fixed tree

Analysis in the N -uniform model

Consider a graph G = (V, E), with m edges, on which the CU-process is run, in the N -uniform model. Recall that c v (t) (resp. c e (t)) denotes the value of the counter for v (resp. for e) after t steps, and o e (t) is the number of occurrences e in the first t steps. The aim of this Section is to prove the following result.

Lemma 2 Let T = (V, E) be a tree, on which the CU-process is run, in the N -uniform model. Let m = |E|. Then, for every vertex v of T , there exist absolute positive constants a v , b v such that, for any N ≥ 1 and x > 0, we have

P max t∈[0..N m] |c v (t) -t/m| ≥ x √ N ≤ a v exp(-b v x 2 ).
Lemma 2 implies that, in the N -uniform model, the final counter c We say that a family of events E N M indexed by two parameters N, M ≥ 1, is (N, M )-concentrated if there are absolute constants a, b > 0 such that, for every N, M , we have P(E N M ) ≤ a exp(-bx 2 ), where x = M/ √ N . For f (t) a (possibly random) quantity depending on t ∈ [0..N m], we use the notation f (t) := f (t) -t/m. Thus, to prove Lemma 2, we have to show that for a fixed tree T with m edges on which the N -independent CU-process is run, and for v a vertex of T , the event

{max t∈[0..N m] | c v (t)| ≥ M } is (N, M )-concentrated.
We proceed by induction on the peeling level i of vertices. A vertex v at level 0 is a leaf. Let e be its incident edge. It is easy to see that the counter of v increases exactly at the steps when e is drawn. Hence c v (t) = o e (t) for t ∈ [0..N m]. Doob's martingale maximal inequality combined with Hoeffding's inequality ensure that, for every edge e of T , we have

P(max t∈[0..N m] | o e (t)| ≥ M ) ≤ 2 exp(-2x 2 /m), where x = M/ √ N .
Hence, for any leaf v of T , the event {max t∈

[0..N m] | c v (t)| ≥ M } is (N, M )-concentrated.
Moreover, for v a vertex and e an arbitrary edge incident to v, the fact that c v (t) ≥ o e (t) ensures that the event {min t∈[0..N m] c v (t)) ≤ -M } is (N, M )-concentrated. It thus remains to show that, for vertices of positive levels, the event {max t∈[0..

N m] c v (t) ≥ M } is (N, M )-concentrated.
The following statement will be useful to treat the inductive step.

Proof of Theorem 2 for k = 2

We use the well-known property [START_REF] Erdos | On the evolution of random graphs[END_REF] that, for fixed λ ∈ (0, 1/2), a random edge e in G n,λn is w.h.p. in a tree of size O(1). Precisely, if we let E m n,λ be the event that e belongs to a tree of size at most m, then we have the property that, for every > 0, there exist m and n 0 such that P(E m n,λ ) ≥ 1 -for n ≥ n 0 . By Lemma 4, there exists N 0 (depending on m) such that, in the N -balanced or N -uniform model, for every tree T with at most m edges, and every edge e ∈ T , we have P(R (N ) e ≥ ) ≤ for N ≥ N 0 . Hence, for n ≥ n 0 and N ≥ N 0 , if we perform the CU-process on G n,λn in the N -balanced model (note that the N -balanced model holds separately on every connected component), and draw a random edge e, we have

P(R (N ) e ≥ ) ≤ P(R (N ) e ≥ | E m n,λ ) + P(¬E m n,λ ) ≤ 2 .
This means that R (N ) e

= o(1) w.h.p., when n and N grow. In the N -uniform model, the same argument holds, using the fact that the total number of times edges in T are drawn is concentrated around N m.

Proof of Theorem 2 for k ≥ 3

The proof partly follows the same lines as for k = 2, but requires additional arguments, in particular a suitably extended notion of peelability. A marked hypergraph is a hypergraph H = (V, E) where some of the vertices are marked. The subset of marked vertices is denoted V ∞ . When performing a CU-process on a marked hypergraph, the counters of unmarked vertices are (as usual) initially 0, while the counters at marked vertices are initially (and remain) +∞. When peeling, the marked vertices are not allowed to be peeled (even when they are incident to a unique edge). We define H 0 = H, and iteratively for i ≥ 0, we define V i as the set of non-marked vertices that are leaves or isolated vertices in H i , E i as the set of edges of H i incident to vertices in V i , and H i+1 to be the hypergraph obtained from H i by deleting the vertices in V i and the edges in E i . A vertex in V i is said to have level i. Then H is called peelable if every unmarked vertex is peeled at some step.

Following the exact same lines as in the proof of Lemma 2 (induction on the vertex-levels, and a straightforward adaptation of Lemma 3 to hypergraphs) and Lemma 4, we obtain: Lemma 5 Let H = (V, E) be a peelable connected marked hypergraph, on which the CU-process is run, in the N -uniform model. Let m = |E|, and for t ∈ [0..N m], let c v (t) be the value of the counter of v after t steps. Then, for every unmarked vertex v of H, there exist absolute positive constants a v , b v such that, for any N ≥ 1 and x > 0, we have

P max t∈[0..N m] |c v (t) -t/m| ≥ x √ N ≤ a v exp(-b v x 2 ).
In the N -uniform or N -balanced model, for every unmarked vertex v of H, we have c

(N ) v /N = 1 + o(1) w.h.p. as N → ∞.
For H a hypergraph, and for v a vertex of finite level in H, a vertex u ∈ H is called a descendant of v if there is a sequence v 0 = u, v 1 , . . . , v r = v of vertices such that, for each j ∈ [1..r -1], v j and v j+1 are incident to a same edge, and the level of v j+1 is larger than the level of v j .

Lemma 6 For a hypergraph H, and for a vertex v of H of finite level, let D v be the set formed by v and it descendants, and let E v be the set of edges that are incident to at least one vertex from D v . Let H v be the marked hypergraph formed by the edges in E v and their incident vertices, where the marked vertices are those not in D v . Then H v is peelable.

Proof: Let u be a vertex in D v , of level i. If i = 0, then u is a leaf in H. It is also a leaf in H v , and is immediately peeled. Otherwise, except for possibly one incident edge, u has at least one neighbour v e of level smaller than i in every incident edge e (note that v e has to be in D v ). By induction, v e and e are peeled in the peeling process of H v . Hence, u is peeled as well during the peeling process on H v (by induction as well, the level of a vertex in D v is actually the same in H and in H v ).

Remark 1 In a hypergraph H = (V, E), the distance between two vertices u and v is the minimum number of edges to traverse in order to reach v from u. For r ≥ 1 and v ∈ V , the ball B H (v, r) is the set of vertices at distance at most r from v. Clearly, if v is at level i, then every vertex in D v is in B H (v, i), and every vertex of H v is in B(v, i + 1). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lemma 7 (Lemma 3 in [START_REF] Molloy | Cores in random hypergraphs and boolean formulas[END_REF]) Let k ≥ 3, and let λ ∈ (0, λ k ). For every > 0, there exist I( ) and n 0 ( ) such that, for v a random vertex in H k n,λn , the probability that v has level at most I( ) is at least 1 -, for n ≥ n 0 ( ).

Lemma 8 Let H = (V, E) be a hypergraph, and let E be a subset of E. Let V (resp. W ) be the subset of vertices incident to at least one edge from E (resp. incident only to edges in E ). Let H = (V , E ) be the marked hypergraph where the unmarked vertices are those in W . Consider a CU-process on H, with S the sequence of items (each item an edge of H), and for v ∈ V let c v be the final value of the counter of v. Let S be the subsequence of S composed by the items in E . Consider the CU process on H where the sequence of items is S . For v ∈ W , let c v be the final value of the counter of v. Then c v ≥ c v .

Proof: For an assignment f : V → N ∪ {+∞} of initial values to the vertex counters, let c f : V → N ∪ {+∞} be the function giving the final vertex counters after performing the CU-process on an input sequence S. It is easy to check (by induction on the length of S) that the CU-process is monotonous: if f (v) ≤ g(v) for all v ∈ V , then c f (v) ≤ c g (v) for all v ∈ V . Now, if we define f as the function assigning initial value 0 to vertices in W , and initial value +∞ to the other vertices, then c v = c f (v) for all v ∈ W . On the other hand, if f 0 denotes the function assigning initial value 0 to all vertices, then c v = c f 0 (v) for all v ∈ V . Hence, the monotonicity property ensures that c v ≥ c v for all v ∈ W .

We can now conclude the proof of Theorem 2 for k ≥ 3. Let > 0. Let I( ) and n 0 ( ) be as given in Lemma 7. Let s( ) be such that, for a random vertex v ∈ H k n,λn , we have P |B(v, I( ) + 1)| ≤ s( ) ≥ 1 -for all n. The existence of s( ) easily follows from the known property that H n,λn converges to a Galton-Watson branching process for the local topology, see e.g. [START_REF] Dembo | Gibbs measures and phase transitions on sparse random graphs[END_REF]Prop 2.6]. Let v be a random vertex in H n,λn . Let E n, be the event that the level of v is at most I( ), and the number of vertices in H v is at most s( ). Then, using Remark 1 and the union bound, we have P(E n, ) ≥ 1 -2 for n ≥ n 0 ( ). From Lemma 5, there exists N 0 such that, for every marked k-uniform hypergraph H with at most s( ) vertices, and for every unmarked vertex v of H, we have P c (N ) v /N -1 ≥ ≤ for N ≥ N 0 . Let e be a random edge in H k n,λn , and let v be a random vertex of e. Note that v is distributed as a random vertex in H k n,λn . With Lemma 6 and Lemma 8, this implies that, conditioned on E n, , for N ≥ N 0 we have P c (N ) v /N -1 ≥ ≤ in the N -balanced model, and also P(R

(N ) e ≥ ) ≤ (since c (N ) e ≤ c (N )
v ). Since P(¬E n, ) ≤ 2 , we conclude that, for n ≥ n 0 ( ) and N ≥ N 0 , we have P(R

(N ) e ≥ ) ≤ 3 . Hence, in the N -balanced model, R (N ) e = o(1)
w.h.p., when n and N grow. In the N -uniform model, the same argument holds again, using the fact that the number of times an edge in H v is drawn is concentrated around N m, with m the number of edges of H v .

Proof of Theorem 3

The excess of a graph G is exc(G) = |E| -|V |.

Lemma 9 Let G = (V, E) be a graph. Then, for the N -balanced model, we have e∈E R

(N ) e ≥ 1 2 exc(G).
Proof: During the CU process, each time an edge is drawn, the counter of at least one of its extremities is increased by 1. Hence v∈V c

(N ) v ≥ N |E|. Hence, with the notation R (N ) v := c (N ) v /N -1, we have v∈V R (N ) v
≥ exc(G). Now, by Lemma 1, for each v ∈ V , there exists an edge

e v incident to v such that c (N ) ev = c (N ) v
(if several incident edges have this property, an arbitrary one is chosen). Hence, v∈V R (N ) ev ≥ exc(G). Note that, in this sum, every edge occurs at most twice (since it has two extremities), thus e∈E R (N ) e ≥ 1 2 exc(G). For λ > 1/2, it is known [START_REF] Pittel | Counting connected graphs inside-out[END_REF]Theorem 6] that there is an explicit constant f (λ) > 0 such that the excess of the giant component G = (V , E ) of G n,λn is concentrated around f (λ)n, with fluctuations of order √ n. Thus, exc(G ) ≥ 1 2 f (λ)n w.h.p. as n → ∞. Hence, by Lemma 9, w.h.p. as n → ∞ (and for any N ≥ 1), we have

err N (G n,λn ) ≥ 1 λn e∈E R (N ) e ≥ 1 2λn exc(G ) ≥ 1 4λ f (λ) =: f (λ).
6 Analysis for some non-peelable hypergraphs

Analysing the asymptotic behaviour of the relative error of the CU-process on arbitrary hypergraphs seems to be a challenging task, even if we restrict ourselves to N -uniform and N -balanced models, as we do in this paper. Based on simulations, we expect that, for a fixed connected k-hypergraph H = (V, E), and for v ∈ V , we have c

(N ) v /N = C v + o(1) w.h.p. as N → ∞, for an explicit constant C v ∈ [1, deg(v)]. Since the number of increments at each step lies in [1..k], constants C v must verify 1 ≤ 1 |E| v∈V C v ≤ k, where 1 |E| v∈V C v
can be seen as the average number of increments at a step. If H is peelable, then Lemma 5 implies that this concentration holds, with C v = 1. We expect that, if no vertex of H is peelable, and if H is "sufficiently homogeneous", then the constants C v should be all equal to the same constant C > 1, and thus the relative error R (N ) e of every edge is concentrated around C -1 > 0 w.h.p. as N → ∞. This, in particular, is supported by an experiment reported at the end of Section 4.2.

In this Section, we show that this is the case for a family of regular hypergraphs which are very sparse (O( |V |) edges) but have a high order (an edge contains O( |V |) vertices). The dual of a hypergraph H is the hypergraph H where the roles of vertices and edges are interchanged: the vertices of H are the edges of H, and the edges of H are the vertices of H so that an edge of H corresponding to a vertex v of H contains those vertices that correspond to edges incident to v in H. We consider here the hypergraph K n dual to the complete graph K n .

Lemma 10 Consider any CU-process on K n = (V, E). At each step t, let minedges(t) be the set of edges of E whose counter c e (t) is minimal over all edges. We have |minedges(t)| ≥ 2. Let e be the edge selected at time t. Then, at time t, e is the only edge whose counter increases (by 1), except when e ∈ minedges(t) and |minedges(t)| = 2, in which case the counter of the other edge in minedges(t) also increases (by 1).

Proof: Every vertex v ∈ V has degree 2. Considering a vertex v of minimal counter, its two incident edges thus have to be in minedges(t), therefore |minedges(t)| ≥ 2.

Let e be the chosen edge at time t. Clearly, c e increases (by 1). Moreover, for every edge e such that c e (t) = c e (t), c e does not increase. Let now e be such that c e (t) = c e (t), but there exists an edge e / ∈ {e, e } with c e (t) ≤ c e (t). Let v = e ∩ e . By Lemma 1, we must have c v (t) = c e (t). Since v is not incident to e, its counter does not increase, and neither does the counter of e . If there does not exist e / ∈ {e, e } with c e (t) ≤ c e (t), then we must be in the situation where e ∈ minedges(t) and |minedges(t)| = 2. Let v = e ∩ e . Then, by Lemma 1, we have c v (t) = c e (t) = c e (t), and any vertex v = v must satisfy c v (t) > c v (t) (since v has at least one incident edge different from e, e ). Thus, the counter of v increases, and the counter of e also increases. Proof: Consider a CU-process performed on K n = (V, E). At each step t, let p(t) = min(c v (t), v ∈ V ) = min(c e (t), e ∈ E), and let q(t) = max(c e (t), e ∈ E). It easily follows from Lemma 10 that e∈E c e (t) = t + p(t). Therefore, (n -1)p(t) ≤ t ≤ (n -1)q(t), so that t n-1 ∈ [p(t), q(t)]. We now consider the CU process on K n in the N -uniform model. Let e 1 , e 2 be two edges in E, and let M ≥ 1. For t ∈ [0..N n], the event that c e

[0,N n] | o e (t)| ≥ M is (N, M )- concentrated. Hence, the event {max t∈[0,N n] (c e 2 (t) -c e 1 (t)) ≥ M } is (N, M )-concentrated. This implies that P(c e 2 (N n) -c e 1 (N n) ≥ N 2/3 ) = O(e -bN 1/3
) for some b > 0, and (by the union bound) that P(q(N n) -p(N n) ≥ N 2/3 ) = O(e -bN 1/3 ) for some b > 0. Note that N n n-1 ∈ [p(N n), q(N n)], and for every edge e ∈ E we have c e

(N n) ∈ [p(N n), q(N n)]. Therefore, P(|c e (N n) -N n n-1 | ≥ N 2/3 ) = O(e -bN 1/3 ). Hence, in the N -uniform model we have R (N ) e -1 n-1 = O(N -1/3 ) = o( 1
) w.h.p. as N → ∞. In the N -balanced model, by the same argument as in Lemma 5.1.2, we have

P(|c (N ) e -N n n-1 | ≥ N 2/3 ) = O(N n/2 e -bN 1/3 ); hence, R (N ) e -1 n-1 = O(N -1/3 ) = o(1) w.h.p. as N → ∞.
Note that with regular Count-Min, the relative error of every edge is 1 + o(1) (exactly 1 in the N -balanced model), since all vertices have degree 2. The statement and proof of Theorem 4 easily extend to dual complete hypergraphs as follows. Let K n,r be the complete r-uniform hypergraph on n vertices (for n ≥ r ≥ 2), and consider a CU-process on K n,r in the N -uniform (resp. N -balanced) model. Then the counter of each vertex v ∈ K n,r satisfies c

Non-uniform distributions

An interesting and natural question is whether the phase transition phenomenon holds for nonuniform distributions as well. This question is of practical importance, as in many practical situations keys are not distributed uniformly. In particular, Zipfian distributions often occur in various applications and are a common test case for Count-Min sketches [START_REF] Cormode | Summarizing and mining skewed data streams[END_REF][START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF][START_REF] Einziger | A formal analysis of conservative update based approximate counting[END_REF][START_REF] Chen | Precise error estimation for sketch-based flow measurement[END_REF][START_REF] Younes Ben Mazziane | A formal analysis of the countmin sketch with conservative updates[END_REF].

In Zipf's distributions, key probabilities in descending order are proportional to 1/i β , where i is the rank of the key and β ≥ 0 is the skewness parameter. Note that for β = 0, Zipf's distribution reduces to the uniform one. It is therefore a natural question whether the phase transition occurs for Zipf's distributions with β > 0.

One may hypothesize that the answer to the question should be positive, as under Zipf's distribution, frequent keys tend to have no error, as it has been observed in earlier papers [START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF][START_REF] Younes Ben Mazziane | A formal analysis of the countmin sketch with conservative updates[END_REF][START_REF] Younes Ben Mazziane | Analyzing Count Min Sketch with Conservative Updates[END_REF]. On the other hand, keys of the tail of the distribution have fairly similar frequencies, and therefore might show the same behavior as for the uniform case.

However, this hypothesis does not hold. Figure 4 shows the behavior of the average error for Zipf's distributions with β ∈ {0.2, 0.5, 0.7, 0.9} vs. the uniform distribution (β = 0). The average error is defined here as the average error of all keys weighted by their frequencies3 , i.e. ). In other words, err N (H) is the expected error of a randomly drawn key from the entire input stream of length mN (taking into account multiplicities).

We observe that the phase transition behavior vanishes for β > 0. It turns out that even in the subcritical regime, frequent elements, while having no error themselves, heavily affect the error of certain rare elements, which raises the resulting average error. In the supercritical regime (λ > 1 in Figure 4) the opposite happens: the uniform distribution shows the largest average error. This is because an increasingly large fraction of the keys (those in the core of the associated hypergraph) contribute to the error, while for skewed distributions, frequent keys tend to have no error, and thus the larger β (with frequent keys becoming more predominant) the smaller the average error. Note that this is in accordance with the observation of [START_REF] Bianchi | Modeling conservative updates in multi-hash approximate count sketches[END_REF] that the estimates for the uniform distribution majorate the estimates of infrequent keys for skewed distributions.

Concluding remarks

We presented an analysis of conservative update strategy for Count-Min sketch under the assumption of uniform distribution of keys in the input stream. Our results show that the behaviour of the sketch heavily depends on the properties of the underlying hash hypergraph. Assuming that hash functions are k-wise independent, the error produced by the sketch follows two different regimes depending on the density of the underlying hypergraph, that is the number of distinct keys relative to the size of the sketch. When this ratio is below the threshold, the conservative update strategy produces a o(1) relative error when the input stream and the number of distinct keys both grow, while the regular Count-Min produces a positive constant error. This gap formally demonstrates that conservative update achieves a substantial improvement over regular Count-Min.

We showed that the above-mentioned threshold corresponds to the peelability threshold for k-uniform random hypergraphs. One practical implication of this is that the best memory usage is obtained with three hash functions, due to the fact that λ 3 is maximum among all λ k , and therefore k = 3 leads to the minimum number of counters needed to deal with a given number of distinct keys.

In [START_REF] Cohen | Spectral bloom filters[END_REF] it is claimed, without proof, that the rate of positive errors of conservative update is k times smaller than that of regular Count-Min. This claim does not appear to be true. Note that Count-Min does not err on a key represented in the sketch if and only if the corresponding edge of the hypergraph includes a leaf (vertex of degree 1), while the conservative update can return an exact answer even for an edge without leaves. However, this latter event depends on the relative frequencies of keys and therefore on the specific distribution of keys and the input length. On the other hand, our experiments with uniformly distributed keys show that this event is relatively rare, and the rate of positive error for Count-Min and conservative update are essentially the same.

One important assumption of our analysis is the uniform distribution of keys in the input. We presented an experimental evidence that for skewed distributions, in particular for Zipf's distribution, the phase transition disappears when the skewness parameter grows. Therefore, the uniform distribution presents the smallest error in the subcritical regime. The situation is the opposite in the supercritical regime when the number of distinct keys is large compared to the number of counters: here the uniform distribution presents the largest average error. As mentioned earlier, for Zipf's distribution, frequent keys have essentially no error, whereas in the supercritical regime, low frequency keys have all similar overestimates. This reveals another type of phase transition in error approximation for Zipf's distribution, occurring between frequent and infrequent elements. Quantifying this transition is an interesting open question directly related to the accurate detection of heavy hitters in streams.

  N ) e = o e (N m) for the resulting number of occurrences of e ∈ E, c (N ) e = c e (N m) for the resulting counter of e ∈ E, and R (N ) e = R e (N m) = (c error of e. In the N -balanced model, since each key e ∈ E occurs N times, we have R (N ) e = (c (N ) e -N )/N . Our main result is the following. Theorem 2 (subcritical regime) Let k ≥ 2, and let λ < λ k , where λ 2 = 1/2, and for k ≥ 3, λ k is the peelability threshold as defined in Section 3. Consider a CU-process on a random hypergraph H k n,λn under either N -uniform or N -balanced model, and consider the relative error R (N ) e of a random edge in H k n,λn . Then R (N ) e = o(1) w.h.p., as both n and N grow 1 . Note that with the regular Count-Min algorithm (see Section 2), in the N -balanced model, the counter value of a node v is c(N) v = N •deg(v), and the relative error R(N)

4 Figure 1 :

 41 Figure 1: Average relative error as a function of λ = m/n for regular Count-Min (red) and conservative update (blue), for k ∈ {2, 3, 4}.

3 Figure 2 :

 32 Figure 2: Concentration of the average error as a function of λ = m/n, for k ∈ {2, 3}.

Figure 3

 3 Figure3where each point corresponds to an edge, and the edges are randomly ordered along the x-axis. Each plot corresponds to an individual random graph.When λ grows beyond the peelability threshold, a fraction of edges with small errors still remains but vanishes quickly: these include edges incident to at least one leaf (these have error 0) and peelable edges (these have error o(1), by arguments to be given in Section 5.3). For intermediate values of λ, the distribution presents several modes: besides the main mode (largest concentration on plots of Figure3), we observe a few other concentration values which are typically integers. While this phenomenon is still to be analysed, we explain it by the presence in the graphs of certain structural motifs that involve disparities in node degrees. Note that the fraction of values concentrated around the main mode is dominant: for example, for k = 3, λ = 3 (Figure3d), about 90% of values correspond to the main mode (≈ 3.22). Finally, when λ becomes larger, these "secondary modes" disappear, and the distribution becomes concentrated around a single value. This is consistent with the tighter concentration observed earlier in Figure2.Finally, we report on another experiment supporting the conjecture of a positive average error in the supercritical regime. We simulated the CU-process on sparse random non-peelable 3-hypergraphs (i.e. k = 3), namely 2-regular 3-hypergraphs with 2n edges and 3n vertices (n parameter). These are sparsest possible non-peelable 3-hypergraphs, with degree 2 of each vertex. We observed that the average error for such graphs is concentrated around a constant value of ≈ 0.217. Since the core size is linear in the supercritical regime, this experiment provides an evidence of a positive error in the general case. While this remains to be proved in general, in Section 6 we provide a proof for certain families of regular hypergraphs.

Figure 3 :

 3 Figure 3: Distribution of relative errors of individual edges shown in a random order along x-axis.

  = 1 + o(1) w.h.p. as N → ∞, where the o(1) term does not depend on the size of the giant component.

v

  v of T is concentrated around N , with (sub-)Gaussian fluctuations of order √ N . The same holds for the final counter c ) of every edge e = (u, v) of T . On the other hand, the number o e (N m) of times e is chosen follows a binomial distribution Bin(N m, 1/m). Then, it is also concentrated around N , with Gaussian fluctuations of order √ N . This implies that R (N ) e = O(1/ √ N ) = o(1) w.h.p. as N gets large.

Theorem 4

 4 For any fixed n ≥ 2, in the N -uniform model (resp. in the N -balanced model), the counter of each vertex v ∈ K n satisfies c (N ) v /N = n/(n -1) + o(1) w.h.p. as N → ∞. Hence, the relative error R (N ) e of each edge e in K n satisfies R (N ) e = 1/(n -1) + o(1) w.h.p. as N → ∞.

  = n/(n -r + 1) + o(1) w.h.p as N → ∞, hence the relative error R (N ) e of any edge e ∈ K n,r satisfies R (N ) e = r-1 n-r+1 + o(1) w.h.p. as N → ∞. For regular Count-Min, the relative error is r -1 + o(1) (exactly r -1 in the N -balanced model), since every vertex in K n,r has degree r.

Figure 4 :

 4 Figure 4: Average error as a function of λ = m/n, for Zipf's distributions with β ∈ {0.0, 0.2, 0.5, 0.7, 0.9}. Plots obtained for n = 1000, k = 3, N = 50, 000.

  1 (t) ≥ c e 2 (t) + M implies the event that o e 1 (t) -o e 1 (t ) ≥ o e 2 (t) -o e 1 (t ) + M for some t ∈ [0..t] (indeed, letting t be the last time before t where c e 1 = c e 2 , Lemma 10 ensures that all times in [t ..t -1] where c e 1 increases are due to chosing e 1 ), which is the same as the event that o e 1 (t) -o e 1 (t ) ≥ o e 2 (t) -o e 1 (t ) + M for some t ∈ [0..t], with the notation of Section 5.1.1. Therefore, the event that c e 2 (t) -c e 1 (t) ≥ M for some t ∈ [0..N n] implies the event that max(| o e 1 (t)|, | o e 2 (t)|) ≥ M/4 for some t ∈ [0..N n]. With the terminology of Section 5.1.1, for every e ∈ E, the event max t∈

Formally, for any > 0, there exists M such that P(R(N ) e ≤ ) ≥ 1 -if n ≥ M and N ≥ M .

Formally, for any > 0, there exists M such that P(errN (Gn,m) ≥ f (λ)) ≥ 1 -if N ≥ 1 and n ≥ M .

This definition is natural for non-uniform distributions, as the error for a frequent key should have a larger contribution. Note that it is consistent with the definition of Section

[START_REF] Younes Ben Mazziane | A formal analysis of the countmin sketch with conservative updates[END_REF].1 in the N -balanced case, and in the Nuniform case it presents a negligible difference when N gets large.

Acknowledgments We thank Djamal Bellazougui who first pointed out to us the conservative update strategy.

 Lemma 3Let G be a graph on which a CU-process is run. Let v be a vertex of G, with v 1 , . . . , v h+1 its neighbours one of which (say v h+1 ) is distinguished, and with e denoting the edge {v, v h+1 }. For t ∈ [0..N m], let d v (t) = max(c v 1 (t), . . . , c v h (t)). Consider the event E N M that there exists t ∈ [0..N m] such that c v (t) ≥ d v (t) + M , and the event

The crucial point is that, in the interval [t ..t 0 ], any step where c v increases occurs when e is chosen (indeed, when c v (t) > max(c v 1 (t), . . . , c v h (t)), choosing an edge {v,

and assume Lemma 2 holds for all vertices of level smaller than i. Let v be a vertex of level i, for which we want to prove that the event {max t∈

All neighbours v 1 , . . . , v h+1 of v have level at most i -1, except for one, say v h+1 , with its level in {i -1, i, i + 1} (respectively corresponding to T i having one vertex, two vertices, or at least three vertices).

Let e be the edge between v and v h+1 . Let E N M be the event that c v (t) ≥ M for some t ∈ [0..N m]. If this holds, then one of the two events

holds. Since these events are (N, M )-concentrated, we conclude (using the union bound) that the event {max t∈[0..N m] c v (t) ≥ M } is also (N, M )-concentrated, which concludes the proof of Lemma 2.

Analysis in the N -balanced model

Lemma 4 Let T be a tree, on which the CU-process is performed, in the N -balanced model. Then, for every edge e of T , we have R Proof: Note that the N -balanced model is just the N -uniform model conditioned on all edges occurring exactly N times, which happens with probability Θ(n -m/2 ) if T has m edges. Let u be an extremity of e. By Lemma 2, there exists a positive constant b such that, in the N -uniform model,