Damien Couroussé

Caroline Quéva

Henri-Pierre Charles

Approximate Computing with Runtime Code Generation on Resource-Constrained Embedded Devices

Keywords: approximate, runtime code generation, compilation, code specialization, precision, floating-point, Wireless Sensor Nework

Approximate computing systems aim at slightly reducing the output quality of service, or precision, of a program in order to save computing operations, reduce the execution time and the energy consumption of the system. However, to the best of our knowledge, in all the approximate computing systems presented in the research literature, the implementation of the components that support the approximation is left to the developer.

In this paper, we describe the implementation of a precisionaware computing library that saves the developer from the implementation of approximated functions. Efficient implementations of the approximated functions are achieved with runtime code generation. Our implementation of runtime code generation is fast and memory-lightweight, and its overhead can is amortised in a few executions of the generated code. We illustrate the performance and the lightness of our implementation on the WisMote, a MSP430-based platform with only 16 kB of RAM and 256 kB of flash memory. When the generated code is specialised on one of the input arguments of the approximated function, we achieve a speedup above 7×.

I. INTRODUCTION

Approximate Computing is a powerful emerging concept, currently bringing a lot of interest in research works. As far as we understand it, it covers two issues that share some ideas [START_REF] Han | Approximate computing: An emerging paradigm for energy-efficient design[END_REF]:

(1) how a system can be resilient in the presence of (hardware) errors but still provide correct results, for example when the hardware runs below its lowest supported operating voltage;

(2) how to balance the output precision or Quality of Service of a program in acceptable terms in order to improve its energy and performance efficiency.

In this paper, we address this second issue: we strive for ways to adapt the output precision of a program in acceptable limits in order to improve program performance or energy consumption. The research literature presents a fair amount of papers on this topic. Some works propose tools to analyse the quality output of a program under approximation. ASAC [START_REF] Roy | Asac: Automatic sensitivity analysis for approximate computing[END_REF] performs a sensitivity analysis of a program in order to identify the parts of the program that are the most sensitive to approximation. Green [START_REF] Baek | Green: A framework for supporting energy-conscious programming using controlled approximation[END_REF] is a framework that computes statistical QoS (Quality of Service) guarantees of a program; the program is annotated with approximation annotations by the developer. Chan et al. [START_REF] Chan | Statistical analysis and modeling for error composition in approximate computation circuits[END_REF] perform statistical analysis to determine how the errors propagate in a circuit composed of accurate and approximato modules.

Another approach is to provide to the developer programming paradigms that support approximate computing. Vassiliadis et al. [START_REF] Vassiliadis | A programming model and runtime system for significance-aware energy-efficient computing[END_REF] propose a task-based programming model where the developer describes the significance of program parts and their contribution to the global quality result. The annotations are exploited by the runtime, mainly in loop perforation, to increase program performance w.r.t. result approximation. EnerJ [START_REF] Sampson | Enerj: Approximate data types for safe and general lowpower computation[END_REF] provides specific type annotations to the developer, in order to distinguish between approximate and precise computations. The developer can provide approximate implementations of a program component, but the system also supports approximate-aware hardware.

We hence distinguish between the works than aim to determine the behaviour of a program w.r.t approximation, and the works that provide software developers with tools operating at various levels (compilation, runtime, programming languages) to implement approximate-aware systems. There exists an overlap between these two approximate (pun intended) categories of works, and some works can be classified in these two research domains. However, we observe that in all of these works, the implementation of the component in charge of the approximation is always left to the developer, or to the availability of approximate-aware hardware. In our point of view, this remains a lacking corner-stone in order to build approximate systems.

In this paper, we describe a precision-aware computing library for approximate systems. Our library is lightweight enough to be executed on resource constrained embedded systems. Furthermore, precision awareness is achieved by using runtime code generation in order to reduce the runtime overhead to an acceptable bound. To illustrate our words, we provide performance figures of our precision-aware library on an small computing node typical of the platforms found in Wireless Sensor Networks, fitted with only 16 kB of RAM.

II. RUNTIME CODE SPECIALISATION FOR APPROXIMATE COMPUTING

We present in this section a general description of our approach. Our aim is to provide a precision-aware implementation of the function f , an n-ary function that takes as inputs the n arguments x 1 , . . . , x n , and computes the output y (Equation 1).

y = f (x 1 , . . . , x n ) (1)
The precision-aware implementation of f is described in Equation 2, where p denotes the precision criterion of the function (e.g. number of bits considered in the mantissa of floating-point numbers). In this equation, the notation underlines the fact that the system generates a new implementation of f (f p ) each time a new value of p is set. We could provide an implementation of f that is generic over all the acceptable values of p, but this solution would come at the price of a performance overhead. Instead, our system uses runtime code generation to specialise the implementation of f : the machine code of f p is generated on the fly, at runtime, according to the value of p. The relation with the code generator is described in equation 3, where gen f is a runtime code generator of f .

y = f p (x 1 , . . . , x n ) (2)
f p = gen f (p) (3)
We can go one step further by exploiting runtime code generation to specialise the implementation of f on part or all of its input arguments. It indeed happens often that some program variables (for example configuration values) keep the same constant value during an important part of the execution time. If the function f is specialised on its n -1 input parameters, the code generation is expressed as in equation 4, and the new output value y is computed as in equation 5. We emphasise on the fact that, because of the specialisation, f has a reduced number of arguments (in this case only 1). One intuitively understands that this specialised version is more efficient in terms of execution time and/or energy consumption.

f p,x1,. . . ,xn-1 = gen f (p, x 1 , . . . , x n-1 ) (4)
y = f p,x1,. . . ,xn-1 (x n ) (5)

III. AN APPROXIMATE LIBRARY FOR ARITHMETIC COMPUTING WITH RUNTIME CODE GENERATION

A. Overview

We describe in this section the working principles of our precision-aware library. The library performs the code specialisation of several target functions thanks to runtime code generation, in order to adapt their implementation (in machine code) according to a precision setting, and to the known values of one or several of the input arguments of the functions. The library supports the specialisation of as many approximated functions as required, but we describe the library for the approximated implementation of a function f . We consider the case where the functions supporting approximation are identified a priori, either by the developer or by one of the tools described in the introduction of this paper. The function code generators are added to the library at design time. The code generation system is described below, in section III-B.

Figure 1 illustrates the working principle of our library. Our main concern is to reduce the runtime overhead incurred by code generation: to do so, the specialised functions are stored in a software-managed code cache in order to pay off the cost of runtime code generation. If the specialised code for function f is found in the code cache, it is executed immediately, avoiding the cost of a new runtime code generation. If the specialised code for function f is not found in the code cache, a new code is generated, stored in the code cache, and then executed.

B. deGoal: runtime code generation for embedded devices

Runtime code generation is achieved with deGoal, a tool for embedding runtime code generators, called compilettes, in applications [START_REF] Charles | deGoal a Tool to Embed Dynamic Code Generators into Applications[END_REF]. Compilettes can be understood as ad hoc runtime code generators specialised to generate the binary (machine) code of a software component. The implementation of the target component is known before runtime, and as a consequence, runtime code generation is fast and code generators present a limited memory footprint. At runtime, when target data for code specialisation are known, the compilette is executed and creates a specialised binary code using the knowledge of the data. The produced binary code is then used the same way as any other function.

IV. PERFORMANCE EVALUATION A. Experimental setup

We use the WisMote platform from Arago Systems [START_REF]Wismote platform[END_REF], which is representative of a low power system with limited memory resources and limited power computation, often used as a node in a Wireless Sensor Network. The WisMote uses the 16-bit MSP430F5437 micro-controller from Texas Instrument, fitted with 256 kB of flash and 16 kB of RAM. We use the open source operating system Contiki version 2.7, and the code is compiled with the gcc toolchain in version 4.7 provided for TinyOS [START_REF]Tinyos (tinyprod) Debian Development Repository[END_REF]. The clock frequency of the CPU is set to 2.45 MHz, and to measure execution time, we configure an internal timer of the CPU at its maximum frequency (2.45 MHz/4). Hence our execution time measurements have a precision of 4 CPU cycles.

All the performance evaluations consider the floating-point multiplication routine. Our reference is the implementation provided in the libfp library that comes with the platform gcc toolchain. The implementation of the specialised version generated in our library is optimised using a polynomial root approximation method known as Horner scheme [START_REF] Aracil | Software acceleration of floating-point multiplication using runtime code generation[END_REF]. This method allows for a variable number of precision bits used in the mantissa of the floating-point numbers, and for the specialisation of one of the multiplication operands.

B. Performance metrics

We use two performance metrics representative of the execution cost of our implementation: the speedup, and the overhead recovery. These metrics are based on three performance measurements: t ref , t gen , t spec that respectively denote the execution times of the reference implementation, of the runtime code generator, and of the specialised function.

The speedup represents the acceleration factor of our implementation as compared to the reference implementation. It is the ratio between execution cost of the generic application and the specialised application (Equation 6):

speedup = t ref t spec (6)
The overhead recovery, denoted N , represents the number of executions of the specialised code that are necessary to amortise the cost of code generation (Equation 7).

N = t gen t ref -t spec (7)

C. Performance figures

The multiplication routine is generated with a variable precision p that denotes the number of bits of the mantissa of the floating-point numbers taken into account. For 32-bit floating-point values, the mantissa is represented on 24 bits (with one implicit bit). Hence, we vary the precision p in the range [1; 24].

The evaluation uses, for each value of p, of 4000 floatingpoint multiplications of two sets of randomly-picked operands. Three special values are always included in our sets of input values: 2.0, which has an empty mantissa; 3.3333333, which has an half-set floating-point mantissa; and 3.9999998, which has a full-set mantissa. In the case where we perform code specialisation on the value of the first multiplication operand, these values will respectively correspond to the shortest, average and longest code generation time because the code generation time is proportional to the number of bits set to 1 in the mantissa.

1) Variable precision, no value specialisation: We first describe the performance figures obtained where the multiplication routine is specialised over the precision p only (Figure 2). The performance improvement is modest as compared to the reference implementation. With an equivalent precision (p = 24), the speedup is close to 1. This explains why the corresponding values of the overhead recovery are high: considering the minor performance improvements, it requires a high number of executions of the specialised code to amortise the cost of code generation. However, with a lower precision, our specialised version executes faster, up to more than 2× when p < 6; the overhead recovery is also acceptable, smaller than 10 for p < 13.

2) Variable precision, value specialisation on one of the operands: In this case the runtime library also specialises the multiplication function over one of the operands. Hence, the multiplication function y = f (a, b) is specialised as follows. The code generator specialises the function f over the value of a: f a = gen(a). The result of the multiplication is then obtained from the execution of y = f a (b). The performance achieved is illustrated in Figure 3.

As compared to the previous case, the value specialisation on one of the operands brings a considerable performance improvement. With the precision as our reference implementation in the libfp (p = 24), our implementation is 7× faster in average, up to 11× for particular specialisation values. Even in the worst case, the speedup is still above 6× faster than the reference implementation. When the precision is lowered, the speedup is even better. The median speedup is around 8× for p < 17.

The overhead recovery is variable, depending on the precision setting. This is explained by the fact that the multiplication of the mantissa is unrolled according to the contents of the mantissa of the specialisation value. For p = 24, the overhead recovery is always below 5, which means that the cost of runtime code generation is paid-off as soon as the specialised code is executed 5 times. With a lower precision setting, the overhead recovery is even better: the code specialisation is amortised in 3 executions only when p < 10.

V. CONCLUSION

We have presented a precision-aware library for arithmetic computing, suitable even for constrained embedded devices with low computing power and memory resources. The performance figures presented in this paper illustrate that our implementation presents a low runtime overhead, and that it can bring interesting performance improvements as soon as some data are known to keep the same values for a few iterations of the computation. Future works will establish a bridge with higher-level tools that tackle approximation at the semantic level of a program. precision (ARTEMIS/ECSEL Joint Undertaking, supported by the European Commission and French Public Authorities).

Fig. 1 .

 1 Fig. 1. Overview of the code generation system embedded in the runtime library

Fig. 2 .Fig. 3 .

 23 Fig. 2. Performance results of our implementation of the floating-point multiplication, specialised over the values of the bit precision only.

ACKNOWLEDGMENTS

This work has been partly funded by the Artemis AR-ROWHEAD project under grant agreement number 332987


Antoine Rebecq
email: antoine.rebecq@insee.fr

Extension sampling designs for big networks -Application to Twitter

With the rise of big data, more and more attention is paid to statistical network analysis. However, exact computation of many statistics of interest (such as clustering or centrality) is of prohibitive cost for big graphs. A way to solve this problem is to use statistical estimators instead of exact ones. A broad literature on model-based estimation exists, but these estimates cannot be used for quick computation of statistics of interest. Therefore, design-based estimates relying on sampling methods were developed specifically for use on graph populations. Reference libraries for statistical network analysis now implement variations of sampling designs.

In this paper, we test some sampling designs used by official statistics institutes to estimate quantities when characteristics of interest on the population can be modeled as networks. These sampling methods can be described as "extension" sampling designs. Unit selection happens in two phases: in the first phase, simple design such as Bernoulli sampling are used, and in the second phase, some units are selected among those that are somehow linked to the units in the first-phase sample.

We test these methods on Twitter data because its size and structure typically match the structure of big social networks for which such methods would be very useful. Also, statistics on the Twitter graph are used in many papers in computer and social science.

Introduction 1.Problem

With more and more businesses and public administrations producing larger raw datasets every day, statistical analysis of so-called "big data" has risen. Consenquently, more research in computer science and statistics have focused on methods to tackle such problems. However, a significant part of datasets that fall under the general "big data" framework are actually graphs. Graphspecific data analysis has applications in domains as diverse as social networks, biology, finance, etc. Since the rise of the web, statistical literature for networks has been growing rapidly, especially in the field of model-based estimation. In the past 20 years, models such as Barabasi-Albert ( [START_REF] Barabási | Emergence of scaling in random networks[END_REF]), Watts-Strogatz ( [START_REF] Duncan | Collective dynamics of 'smallworld'networks[END_REF]), stochastic block models ( [START_REF] Nowicki | Estimation and prediction for stochastic blockstructures[END_REF]) and many others have induced huge progress in understanding probabilities and statistics for various cases of networks. Yet, model-based estimation is sometimes inconvenient. First, models cannot possibly perform well on all statistics of real-life graphs. Second, model-based estimation obviously requires a fine tuned choice of model before being able to produce statistics. Finally, even when a specific model exists and is fit for a specific graph, computation can be cumbersome. This is a motivation for developping design-based estimates, which have received little attention from a purely statistical point of view. One of the most efficient tools for statistical graph analysis, snap -which has a very convenient Python interface ( [START_REF] Leskovec | .py: SNAP for Python, a general purpose network analysis and graph mining tool in Python[END_REF]), uses sampling methods to compute various statistics of interest ( [START_REF] Leskovec | Sampling from large graphs[END_REF]).

Also, some research in computer and social science specifically focus on social networks. A large part of this literature analyses published content, and not estimates regarding quantification or qualification of accounts engaged in the analyzed content. On Twitter, this means the focus is more on tweets than on who tweets. Most recent analysis and inference based on Twitter data used the Streaming API ( [START_REF] Burnap | 140 characters to victory?: Using twitter to predict the uk 2015 general election[END_REF]). Tweets matching a research criterion were collected in real time for a few days, and then analyzed. Many studies perform sentiment analysis on the harvested tweets. Some studies try to unravel political sentiment based on their Twitter data ( [START_REF] Conover | Political polarization on twitter[END_REF], [START_REF] Tumasjan | Predicting elections with twitter: What 140 characters reveal about political sentiment[END_REF]), for example to try and predict election outcomes. Very recently, election prediction based on Twitter data was proven not more accurate than traditional quota sampling, when trying to predict the outcome of the UK 2015 general election ( [START_REF] Burnap | 140 characters to victory?: Using twitter to predict the uk 2015 general election[END_REF]). Other topics are very diverse and include for example stock market prediction ( [START_REF] Bollen | Twitter mood predicts the stock market[END_REF]). Non-academic studies based on tweets data are also numerous. Most are made by market research companies, often to measure "engagement" by users to a brand. However, such analyses are based on biased estimates.

First, the Streaming API is often preferred by researchers over the Rest API. The Streaming API provides tweets in real-time matching a certain query, thus allowing collection of a huge amount of data. However, when the data size exceeds a certain threshold, only a fraction of tweets are output, but Twitter does not disclose the sampling design used to select these tweets. The Rest API allows the collection of a much more limited number of tweets, but the selection is made by account and not by a query on tweets. A statistical analysis using the Rest API is thus much closer to the survey sampling paradigm. In fact, it is possible to derive unbiased estimators using the Rest API.

Using the Streaming API to perform a global analysis on Twitter user (or a fortiori if estimates are to be extrapolated to a larger population, such as in the case of the prediction of election outcomes) can lead to unbalanced profiles of users. When the selection is made by tweets, users tweeting much less about a certain subject have a much lower probability of being selected than users who tweet a lot about the same subject. This is even more telling when socalled "bots" (automated accounts set up to regularly write tweets about a pre-defined subject) account for a non-negligible fraction of the total tweets ( [START_REF] Ferrara | The rise of social bots[END_REF]). When selection is made using a search query, it is very difficult to assess the selection probability, and when not all the tweets are output a large number of probabilities can be equal to 0. As Mutafaraj et al. noticed ([21]), in many cases the users that precisley have a low selection probability account for the greater variability in estimates. Sloan studies precisely these difference in user profiles used in Twitter-based estimations ( [START_REF] Sloan | Knowing the tweeters: Deriving sociologically relevant demographics from twitter[END_REF]).

The goal of our work is to perform an estimate of the number of accounts tweeting on a specific subject, focusing on the accounts behind the tweets instead of the tweets themselves. We chose to work on the release of the trailer of the movie "Star Wars : the Force awakens" that occurred on October 19, 2015. According to Twitter Reverb data, this event generated 390 000 tweets in less than 3 hours (http://reverb.guru/view/597295533668271595).

This study is meant to be a proof of concept for further study. Regarding specific analysis on social networks, we think our analysis could be used joinlty with analyses based on tweets to shed a new light on the structure data structure. For example, in the case of election prediction, it could be used to balance selection probabilities that are naturally skewed away from people who're less likely to participate in Internet debates (which, unfortunately, is correlated to political opinions). In any other marketing context, this method could be used to weigh tweets according to methods extending the "generalized weights share method" such as proposed by Rivers ([25], [START_REF] Lavallée | Estimation par la méthode généralisée du partage des poids: Le cas du couplage d'enregistrements[END_REF]). More generally, understanding how different sampling schemes behave on a huge graph that exhibits many of the particular properties of web and social graphs (see for example 1.2) could help us understand the benefits and disadvantages of these schemes. Estimation by sampling could be used to improve computation time and precision for descriptive statistics or even machine learning algorithms on graphs.

Here, we test two different methods of sampling adapted to graph populations. These two methods are in fact extensions of simple sampling designs. Each of these methods yield unbiased estimates. Theoretically, the precision of the estimates can be spectacularly improved with these extension designs. However, their practical use can be limited by our ability to collect the data on the graph. In this paper, no inference is made on any population outside the set of Twitter users (ie the vertices of the Twitter Graph).

Twitter's graph

In computer science, Twitter's graph is said to show both "information network" and "social network" properties (see for instance [START_REF] Myers | Information network or social network?: the structure of the twitter follow graph[END_REF]) :

• The degree distributions (both inbound and outbound) are heavy-tailed, resembling a power law distribution

• The average path length between two users is short Thus, in the context of model-based estimation, the Twitter graph should be modelized by both a scale-free network (Barabási-Albert, [START_REF] Barabási | Emergence of scaling in random networks[END_REF]) and a small-world network (Watts-Strogatz, [

z k = 1{k ∈ U , y k ≥ 1} N C = #{k ∈ U , y k ≥ 1} n C = #{k ∈ s, y k ≥ 1} = number of people in s who tweeted about Star Wars T (Y ) = k∈U y k
We also use graph-specific notations to make some formulas clearer

V = set of vertices (= U ) E ij =

set of edges linking vertices i and j

The goal is to estimate N C = T (Z), the number of users who have tweeted about the Star Wars trailer during the time span of the study.

Sampling designs 2.1 Notations

Notations for ensembles and networks :

s 0 = initial sample C = i r i =
sub-population of units bearing the characteristic of interest s c = s ∩ C s = total sample i.e. s 0 inflated with units of C that can be reached

s ri = s ∩ r i C k = ∀k ∈ s, C k = 1{k ∈ C} δ = Graph
geodesic distance between two units in the network

r 0 i = {k, δ(k, r i )}, "side" of r i s 0 = i r 0 i = {k ∈ s, δ(k, s C ) = 1}
s ex = elements which are neither in a network nor a side = {k ∈ s, δ(k, s C ) ≥ 2}

In this article, s 0 is selected using stratified Bernoulli sampling.

Bernoulli sampling

Poisson sampling consists in selecting in the sample s each unit k ∈ U with a Bernoulli experiment of parameter π k , the first-order inclusion probability of unit k:

∀k ∈ U, P(k ∈ s) = π k
Second-order inclusion probabilities thus have a very simple expression:

∀k = l ∈ U, π kl = P(k, l ∈ s) = π k π l
Bernoulli sampling is Poisson sampling with equal probabilities (∀k ∈ U , π k = p). Bernoulli sampling design is the most simple design that can be used and thus gives very simple formulae for estimators and variance estimators. One can refer to Särndal ([26]) for a more detailed presentation of Poisson and Bernoulli sampling. For the rest of this article, we'll use Bernoulli sampling as the primary sampling design on which we'll base other more complicated (and more efficient in terms of precision) designs: a stratified design, an adaptive design and a one-stage snowball design. We write: p = selection probability for each unit in the frame (each twitter user)

q = 1 -p
Poisson sampling is seldom used in survey sampling (at least in national statistics institutes), because it yields samples of variable size (#s is a random variable). A variable size can be problematic when collecting data is costly (in most surveys by official statistics institutes, interviewers set up meetings with selected individuals either by phone or face-to-face). In our present case, it doesn't matter because the final goal is to use adaptive or snowball sampling, which will eventually yield a random final sample size. More, the cost of data collection is uniform across all units. We thus chose Poisson designs over simple random sampling, because the expressions for adaptive estimation and Rao-Blackwell estimates are much simpler.

On Twitter, users are assigned an id, ranging from 1 to N ≈ 3.3•10 9 . Some of the ids in this range are not assigned, but every new user is given an id greater than the last. In result, when selecting a Poisson sample using the ids in [[1, N ]], part of the ids selected (≈ 30%) will not correspond to any Twitter user. Our sample is thus selected in a set greater than the population. Moreover, we are interested in only people who are active on twitter, i.e. users who tweeted in the last month. There are two reasons for which we consider these units: first we have a population margin to calibrate on (see 3.4) and second, it is the scope that is generally considered when stats on Twitter's users are discussed for business purposes.

Consequently, our frame over-covers our scope. But as out-of-scope units are perfectly identified, the over-coverage can be treated very simply (see [START_REF] Sautory | Les enjeux méthodologiques liés à l'usage de bases de sondage imparfaites[END_REF]) by using the restriction to a domain of the usual estimators. Based on the Horvitz-Thompson, two strategies can be used:

If the total population on the domain U d is unknown, we use Hájek estimators:

T (Y ) d = k∈U y kd ŷd = k∈U y kd k∈U z kd
where:

y kd = y k • 1{k ∈ U d } z kd = 1{k ∈ U d }
In our case, we know the total of the population on the domain N d (see paragraph 3.4), so it is preferable to use:

T (Y ) d = k∈U d y k (1) ŷd = k∈U d y k N d (2)
Using estimator 1, all the estimators will work just like a restriction of the sample data frame on the scope. From now on, all the estimators are implicitly restricted to the scope domain unless stated otherwise.

The fact that some of the units sampled are finally out of scope leads to a final true sample size that can vary, which is another argument for not using fixed-size sampling design. For the simple Bernoulli design, our initial expected sample size (i.e. not taking the scope restriction into account) is 20000:

p = 20000 3300000000 ≈ 6.1 • 10 -6

Stratified Bernoulli sampling

A usual way to improve the precision of the estimates is to stratify the population. We write:

U = U 1 ⊕ U 2
and draw two independant samples in U h , h = 1, 2 (in our case, two Bernoulli samples). With this design, the variance of the estimators write:

V( T ) = h f h (S 2 h )
If strata are wisely selected, they should be homogeneous so that the S 2 h are much reduced in comparison to the S 2 which determines the variance of the Horvitz-Thompson estimator under the simple Bernoulli design (see paragraph 4.1). Here, we try to estimate a proportion (alternatively a sub-population size), so we have:

f h (S 2 h ) = (1 - n h N h ) N h N h -1 p h (1 -p h ) n h
The goal is thus to constitute strata where the probability of tweeting about the "Star Wars : The force awakens" trailer is more or less equal among users.

We divide the population of twitter users into two strata:

1. The users who follow the official Star Wars account ("@starwars") (1654874 followers as of October, 21, 2015)

2. The users who don't

We use Bernoulli sampling on each stratum independantly, but with different inclusion probabilities, so that users who follow the official Star Wars account are "over-represented" in the final sample. By doing this, we hope to increase n C the number of units who tweeted about Star Wars in s, as users who follow the official Star Wars account are more likely to be interested in tweeting about the new trailer. Descriptive statistics on the stratified Bernoulli design are shown in table 1.

In order to be able to compare the precision of the stratified design with the simple Bernoulli, we keep an expected final sample size of n = n 1 + n 2 = 20000. But we have to think about how to allocate these 20000 units between the two strata. We choose (again, in expected sample sizes):

1. 9700 units in stratum 1 2. 10300 units in stratum 2 which corresponds to a Neyman allocation ( [START_REF] Neyman | On the two different aspects of the representative method: the method of stratified sampling and the method of purposive selection[END_REF]) supposing that approximately half of the people who tweeted were following the official @starwars account and that each person who tweeted about "The force awakens" did it three times: n sw1 = 50000 n sw2 = 50000 which gives:

p 1 = 3.3% p 2 = 0.15%
and then, the Neyman allocation writes:

N 1 S 1 + N 2 S 2 ≈ 46290 + 49500 = 95790
(3)

n 1 = n N 1 S 1 N 1 S 1 + N 2 S 2
≈ 9700 (4)

n 2 = n N 2 S 2 N 1 S 1 + N 2 S 2 ≈ 10300 (5)
The quantities in equations 4 and 5 are approximations, but this does not matter much, as it is well known that the Neyman optimum is flat (see for example [START_REF] Merly | L'algorithme curios pour l'optimisation du plan de sondage en fonction de la non-réponse[END_REF] for an illustration). Thus, even if the approximated allocation is slightly shifted from the optimal one, the variance of the Horvitz-Thompson estimator will still be very close from the optimal variance.

One stage snowball sampling

For a vertex i, let's denote:

B i = {i} ∪ {j ∈ V, E ji = ∅} A i = {i} ∪ {j ∈ V, E ij = ∅} B i
is called the set of vertices adjacent before i, and A i the set of vertices adjacent after i. In the case of Twitter's graph, B i is the set of the users following user i and A i is the set of users followed by user i.

The snowball design consists in selecting:

s = A(s 0 )
Contrary to adaptive sampling (see paragraph 2.5), the sample is enhanced with the friends of every user k ∈ s 0 , even if k / ∈ C. In this design, we also do not care about symmetric relationships. Another difference with the adaptive design is that we cannot remove out-of-scope units prior to the sample enhancement, as out-of-scope units may have in-scope units in their friends. Figures 1, 2 and 3 describe the snowball sampling design.

As decribed in in paragraph 1.2 and in [START_REF] Myers | Information network or social network?: the structure of the twitter follow graph[END_REF], Twitter's graph is highly central and clustered. Thus, the number of reachable units via the edges of the units is s 0 is huge. Mean number of friends for every unit is estimated from the stratified sample to be approximately 75 for units in stratum 2 and a little more than 400 for units in stratum 1. In order to obtain final samples s of comparable sizes, we base the snowball design on a smaller stratified Bernoulli sample of expected size 1000 units, with an allocation proportional to the Neyman described in paragraph 2.3 :

p S1 = 485 1654874 ≈ 2.9 • 10 -4 p S2 = 515 33000000 ≈ 1.6 • 10 -8
The final sample size is 159957, which is much higher than we expected, probably due to the large tail distribution of the degree for units of stratum 1. This definition of one-stage snowball sampling can easily be generalized to nstage snowball sampling by including in the sample all units that have a shorter path than n to any unit in s 0 . n-stage snowball sampling, although fairly simple to implement, can lead to very complex estimators for n ≥ 2 (see [START_REF] Kolaczyk | Statistical analysis of network data[END_REF] for a more general discussion). But even more problematic in our case is that we saw in paragraph 1.2 that the average path length for the Twitter is very small (≈ 4.5). A precise analysis of characteristics of Twitter's graph ( [START_REF] Myers | Information network or social network?: the structure of the twitter follow graph[END_REF]) even shows that the distribution of path length is somewhat platykurtic. Thus, selecting a nsnowball sample could lead to huge sample sizes, reaching almost every units for very small values of n. For these reasons, we limit ourselves to one-stage snowball sampling (see 3.2).

Stratified adaptive cluster sampling

In our problem, the population is made of the vertices of a graph bearing a dummy characteristic. One modality of the characteristic is supposed to be rather rare in the population, and the units bearing it should be more likely to be linked to one another. In other terms, we suppose that users who follow people who tweet about Star Wars have a higher propensity of also tweeting about Star Wars.

Adaptive cluster sampling (first described in [START_REF] Steven K Thompson | Adaptive cluster sampling[END_REF]) consists in enhancing the initial sample s 0 with all units for which y > 0 (i.e who tweeted about the Star Wars Trailer) among the units who are connected to the units of s 0 . As all units of interest who are connected with to a unit in s 0 will be added to the final sample s, adaptive sampling is a particular case cluster sampling, the clusters being the networks of units having tweeted about the Star Wars trailer. Units of s 0 who didn't tweet about Star Wars won't have any other unit from their network added to the sample, but they can be seen as a 1-unit cluster.

Once a person who tweeted about star wars is found in the initial sample s 0 , many more can be discovered, which resembles the gameplay of the famous "minesweeper" videogame, and is often depicted as so in the literature (see figure 4).

The Twitter network is a directed graph. Let us consider a unit i ∈ s 0 , y i = 1. Following the logic of adaptive sampling explained in the previous paragraph, we should look for units who also tweeted about "The force awakens" by searching the friends and followers of i, and if such units were found, look for other units among the friends and followers of these units and so on till the entire network is discovered. But if we did this, the inclusion probabilities for any unit k ∈ s would not only depend on the units of k's network but also on other units with edges leading to k. This typically cannot be estimated from sample data ( [START_REF] Steven K Thompson | Adaptive sampling in graphs[END_REF]), as there is no reason that any of these unit be included in the sample. Thus, we only select units who show symmetric relationships with units in s 0 or in their networks.

For huge networks, we could expect the final sample size to be much greater than the initial sample size, especially if the network is highly clustered (which is the case of Twitter's graph, see paragraph 1.2). However, the fact that Twitter's graph is directed imposes us to only look for symmetric relationship, which will limit the size of the networks s ri added to s 0 . Finally, in addition to the s ri , we also include in s units who have symmetric relationships to units in s C , but who are not in C themselves. These units are called the "sides" s 0 of the networks s r . These units can be described as: {k ∈ s, δ(k, C) = 1}. In general, the sides of the networks also contain valuable information and should be included in the estimations to improve precision (see [START_REF] Deville | échantillonnage de réseaux, une relecture de s.k thompson avec une nouvelle présentation et quelques nouveautés[END_REF] and [START_REF] Deville | échantillonnage adaptatif[END_REF]). In our case, we'll rely on the Bernoulli stratified design of paragraph 2.3 to select s 0 : the final design is thus stratified adaptive cluster sampling ( [START_REF] Steven K Thompson | Stratified adaptive cluster sampling[END_REF]). Estimators for this design are developped in paragraph 3.3.

Estimates

Horvitz-Thompsom estimator

For the simple designs, the privileged estimator is Horvitz and Thompson's ( [START_REF] Daniel | A generalization of sampling without replacement from a finite universe[END_REF]), which weighs the observations with the inverse of the inclusion probabilities:

T (Y ) HT = k∈s y k π k ŷHT = 1 N k∈s y k π k
For the Bernoulli design, it simply writes:

T (Y ) 1 = 1 p k∈s y k NC1 = n C p
For the stratified Bernoulli, we get:

T (Y ) 2 = s∩U d1 y k p 1 + s∩U d2 y k p 2 NC2 = N 1 n 1 n C1 + N -N 1 n 2 n C2
3.2 One stage snowball sampling

Horvitz-Thompson estimator

Estimation is developped in Frank ( [START_REF] Frank | Survey sampling in graphs[END_REF]). The Horvitz-Thompson estimator writes:

T (Y ) 3 = k∈s y i 1 -π(B i ) NC3 = k∈s z i 1 -π(B i )
where π(B i ) = P(B i ⊂ s), the probability that no unit of B i is included in s. As the sampling design for s 0 is stratified Bernoulli (in particular, the event of belonging or not to s is independant for each unit of U ):

π(B i ) = k∈Bi (1 -P(k ∈ s)) (6)
= q #(Bi∩U1) S1

• q

#(Bi∩U2) S2 (7)
As stated in paragraph 6, the computation of this probability does not use any particular knowledge of the shape of the graph.

Just like the classic Horvitz-Thompson estimator, the estimator for the onestage snowball sampling is linear homogeneous, with weights

d i = 1 1 -π(B i ) .
This property will be particularly useful for calibration on margins (3.4).

Rao-Blackwell estimator

In the case of one-stage snowball sampling, [START_REF] Frank | Survey sampling in graphs[END_REF] shows that a Rao-Blackwell type estimator can be written in closed-form:

N * C3 = k∈s y k π k     1 - L⊂s (-1) #L π({k} ∪ B(L ∪ s)) L⊂s (-1) #L π(B(L ∪ s)     (8)
where the summation is done over all the subsamples L of s.

This Rao-Blackwell estimator is unbiased and as long as selection probabilities are not ill-defined (meaning that ∀k ∈ U, π(B k ) < 1), it performs better than the Horvitz-Thompson [START_REF] Deville | échantillonnage de réseaux, une relecture de s.k thompson avec une nouvelle présentation et quelques nouveautés[END_REF]. However, there are 2 #s -1 terms in each of two sums in equation 8. Computing each term of the sums implies computing the exclusion probabilities for as many B k , which means at least knowing their sizes. This is extremely costly in time, and in our particular case in number of calls to the Twitter API. Thus, we prefer using NC3 over N * C3 .

Estimators for adaptive sampling

Horvitz-Thompson

As explained in 2.5, the adaptive sample is selected using only units who have symmetric relationships (so that the graph induced by a unit k ∈ s 0 ∩ C can be considered undirected).

T (Y ) 4 = K k=1 y * k J k π gk NC4 = K k=1 n * Ck J k π gk
where k = networks in the population , y * k is the total of Y in the network k, n * Ck the number of people with y k ≥ 1 in the network k, J k = 1{k ∈ C} (ie intersection with sample) and π gk is the probability that the initial sample intersects network k:

π gk = 1 -(1 -p k ) ng
where n g = #{k ∈ g}.

Hansen-Hurwitz

Other design-unbiased estimators can be used. For example, Hansen-Hurvitz -like ( [START_REF] Morris | On the theory of sampling from finite populations[END_REF]) estimators in this case would write:

T (Y ) HH = h=1,2 1 p h N h n=1 y i f i m i
where m i is the number of units in the network that includes unit i and f i is the number of units from that network included in the initial sample. This re-writes:

T (Y ) HH = h=1,2 n h i=1 w i p h
where the sum is over the elements of s 0 ∩ U h and with w i the the average of y in the network r i , which would give:

NHH = h=1,2 1 p h n h i=1 n Ci

Rao-Blackwell

In the case of adaptive sampling, it is very common to use the Rao-Blackwell estimator. This means using the conditional design P(s|s 0 ) (see for example [START_REF] Deville | échantillonnage adaptatif[END_REF] or [START_REF] Steven K Thompson | Adaptive web sampling[END_REF] for more details on exhaustivity in sampling). In most cases, computing the Rao-Blackwell is computationally intensive and is achieved using Markov-Chain Monte-Carlo ( [START_REF] Steven K Thompson | Adaptive web sampling[END_REF]). However, with Bernoulli stratified sampling it is possible to derive a closed form of the Rao-Blackwell ( [START_REF] Deville | échantillonnage de réseaux, une relecture de s.k thompson avec une nouvelle présentation et quelques nouveautés[END_REF]). Following [START_REF] Deville | échantillonnage adaptatif[END_REF] and [START_REF] Steven K Thompson | Adaptive sampling in graphs[END_REF], we write:

T (Y ) RB = k∈sex y k π k + k∈s 0 y k + k∈sr Y r π r
where Y r = k∈r y k denotes is the total of the variable of interest y in the network r. In our case, this leads to:

NC5 = s 0 1{yk ≥ 1} + sr n r π r = n 0 + K k=1 n r 1 -(1 -p) nr with n 0 = #s 0 .
The Rao-Blackwell for the Hansen-Hurvitz estimator also has a simple closed form that can be found in [START_REF] Deville | échantillonnage adaptatif[END_REF].

Calibration on margins

The calibration estimator

Let us denote X a matrix of J auxiliary variables:

∀j ∈ [[1, J]], X j = (X j1 . . . X jn )
whose values can be computed at least for all units of s. Let's suppose we also know the totals of these auxiliary variables on the population: T (X j ) = k∈U X jk .

We write T (X j ) the total of the j-th auxiliary variable and T (X) the column vector of all the J totals T (X) = (T (X 1 ) . . . T (X J )).

In the general case, there is no reason that the estimated totals T (X) jπ using the Horvitz-Thompson weights match the actual totals T (X j ). For two main reasons, one may want to use a linear homogeneous estimator that is calibrated on some auxiliary variables. First, often in official statistics, a single set of weights is used to compute estimated totals for many variables. Thus, it is often required that these weights are calibrated on some margins for sake of consistency. For example, X = 1 is often chosen as a calibration variable so that the size of the population N is estimated with no variance. Other typical calibration variables include sizes of subpopulations divided in sex and age groups so that the demographic structure of estimates is similar to the demographic structure of the population or quantitative variables linked to revenuewhich is a main parameter of interest in most sociological studies, etc. Second, when estimating a variable Y using the calibrated weights w k , the precision of the estimator will be increased if Y is correlated to one or more of the auxiliary variables X j (see 4.4). This is the most interesting feature of calibration in the context of this study.

Let us write: X s the n × j matrix of the values of the auxiliary variables and w a set of weights of a linear homogeneous estimator. Calibration on margins X 1 . . . X j consists in a searching a linear homogeneous estimator such that :

X s w = T (X) (9)
supposing, of course, that this system has at least one solution. In general, when this linear systems has solutions, their number is infinite. To choose among these solutions, we look for weights w k that are the closest to the Horvitz-Thompson weights d k wih respect to some distance G. Finally, finding the calibrated weights is equivalent to solving a linear optimization problem ( [START_REF] Deville | Calibration estimators in survey sampling[END_REF]):

   min w k k∈s d k G( w k d k ) under constraint: X s w = T (X)
Property 1 (Approximately Design Unbiasedness (ADU)). The calibration estimator is approximately degin-unbiased. Its bias tends to 0 as N → +∞

The Horvitz-Thompson estimator is the most used estimator in survey sampling. One of its key properties is that it is design-unbiased. The calibration estimator, being the closest linear Godambe-class estimator with respect to a certain distance to the Horvitz to ensure the calibration equation ( 9), we can expect it to be also unbiased under some conditions. In fact, the property holds asymptotically, i.e. when N goes with n to infinity (precise definition of the superpopulation model used to prove this asymptotic property is detailed in Isaki-Fuller, [START_REF] Cary | Survey design under the regression superpopulation model[END_REF]).

Margins used for Twitter

For the calibration of our estimators NC , we use the following margins (i.e the columns of matrix X):

• N = Total number of accounts who tweeted in the last month (quantitative):

• T (Y ) =Total number of tweets about "Star Wars : The Force Awakens" between 10/25, 7:48 PM EST and 10/25, 10:48 PM EST (quantitative): 390000

• Number of verified accounts1

• Structure of users in sample in terms of number of followers Many other margins could be added to the calibration process. Improvement in terms of variance of NC is achieved as long as the margin X j correlates to N C and the calibration algorithm has a solution. Other calibration margins could include the number of (active) verified users, the number of tweets about "Star Wars: The Force awakens" per hour, etc. The geographical origin of the tweets is another variable that might strongly correlate to N C . Twitter does dispose of such a variable, but it is seldom available. Imputation is not worth considering for this particular variable, because the number of accounts for which the variable can be used is very low. However, we could use Time Zones as a proxy for geographical origin, as the Time Zones are disclosed for every account. In general, in order to facilitate sampling estimates, Twitter could release calibration margins on a few characteristics.

Finally, we could calibrate on variables accounting for the graph structure, which probably correlate highly with N C as well as a lot of other characteristics of interest of Twitter's graph. This could be achieved by finding a method for calibration on non-linear totals (see 6.2). which can be estimated by:

Variance and precision estimation

V( T (Y )) 1 = k∈s (1 -p)y k p 2
Once n (which is random) has been drawn, it is common to work with the variance conditional to the sample size ( [START_REF] Tillé | Théorie des sondages[END_REF]). This gives:

V( T (Y )) 2 = V( T (Y ) | #s = n) 1 = 1 -n N n Σ(Y )
For stratified Bernoulli, the total variance is the sum of the variance of the two independant designs in the strata. If the strata are well built, the dispersions Σ(Y ) will be lower among each strata than in the total population, yielding a lower variance for the Horvitz-Thompson estimator.

Snowball sampling

An unbiased estimator of the variance of the Horvitz-Thompson estimator is given in [START_REF] Daniel | A generalization of sampling without replacement from a finite universe[END_REF]. One can easily rewrite the general case formula in the case of snowball sampling:

V( NC3 ) = i∈s j∈s z i z j π(B i ∪ B j ) γ ij (10)
where:

γ ij = π(B i ∪ B j ) -π(B i )π(B j ) [1 -π(B i )][1 -π(B j )] (11)
The probabilities in [START_REF] Frank | Survey sampling in graphs[END_REF] are theoretically easily computed using the formula (6). However, practically, it means browsing the whole set of vertices B(s), which can be huge for highly central and/or clustered graphs (see 5.2). This variance estimator is thus potentially highly instensive in time and computation power. In the case of the Twitter graph, this means a high number of calls to the API, which is unfortunately limited in number of calls. For too big sample sizes, we might have trouble computing the estimation.

Adaptive designs

Horvitz-Thompson

We use the variance estimator proposed by Särndal ([26]):

V( NC4 ) = K k=1 K k =1 y k y k π gkk π gkk π gk π gk - 1
where:

π gkk = 1 -π gk -π gk + (1 -p) n gk +n gk
Computing this variance estimator only requires the sizes of each network, which can be stored during the data collection process. In terms of number of calls, the variance estimator is thus much less demanding than the variance estimator in the case of the one-stage snowball (4.2).

Rao-Blackwell

Although the Bernoulli scheme conveniently yields a closed-form Rao-Blackwell estimation, it's not the case for the variance estimator. We have:

V( NC3 ) = V( NC4 ) + E( NC3 -NC4 ) 2
The second term can be estimated without bias by selecting m samples. An unbiased estimator for V( NC4 ) then writes:

V( NC4 ) = V( NC3 ) - 1 m -1 m i=1 ( NC4i -N C3 )
Of course, this method increases the number of calls needed to the graph API. In the case of Star Wars, we were already unable to get to the end of s 0 (see 5.2). If we'd had to generate several samples to estimate the variance of the estimation, it would obviously have been even harder.

Adjustment for calibration

Following [START_REF] Deville | Calibration estimators in survey sampling[END_REF], the variance for a calibrated Horvitz-Thompson for total Y writes:

Vc ( T (Y )) = k∈s l∈s ∆ kl π kl (g k d k e k )(g l d l e l )
where: w k are the weights of the calibrated estimator, d k the weights of the non-calibrated estimator, g k = w k d k and e k = y k -b x k , residuals of the weighted regression (weights: d k ) of Y on X 1 . . . X j . . . X J in s.

We recognize the general form of the Horvitz-Thompson estimator of variance (see [START_REF] Daniel | A generalization of sampling without replacement from a finite universe[END_REF]) which is used to construct variance estimators of paragraphs 4.1, 4.2 and 4.3, applied to the linear variable g k e k . This means that V( NCi ), i = 1...5 can be easily computed by re-using the formulae from 4.1, 4.2 and 4.3, and replacing the z k by g k • e k .

Results

Estimates

The variance of all estimators used in this paper is bounded by O( 1 n ). It is thus always possible to reduce variance by increasing the sample size. In order to compare the sampling designs for their respective merits in reducing the variance of the estimation, we define the design effect Deff as:

Def f = V( Ŷdesign ) V( Ŷdesign ) = V( Ŷdesign ) (1 -n N Σ(Y ) 2 ) with: Σ(Y ) = 1 N -1 k∈U (y k -ȳ) 2
which compares the variance of the estimator to the variance of the estimator under a simple random sampling design of same size. The Deff is greater than 1 for designs that yield worse precision than the simple design (typically cluster or two-degree sampling), and lesser than 1 for designs that are more precise (typically stratified designs). Of course, real variance is impossible to compute, so the Deff can be estimated by: We can also note that the mean number of tweets about Star Wars according to the one-stage snowball sampling design is 1.18 ± 0.07. This low number suggests that automatic accounts are responsible for a very small amount, if any, of the total number of tweets on this subject ([9]).

Def f = V( Ŷdesign ) V( ŶSAS ) = V( Ŷdesign ) (1 -n N σ(Y ) 2 ) with: σ(Y ) = 1 n -1 k∈s (y k -ȳ)

Size of the extensions

It is important to note that the final sample size is random, just like for any clustererd sampling design with non-constant sizes of clusters. When a unit is selected in s 0 , there is no way to know in advance what the size of the clusters (networks) that includes it will be. Therefore, the final sample size #s can be highly variable. In the case of adaptive sampling, the subject studied featured highly clustered networks of Star Wars fans. This led to a very large number of users reached by the adaptive procedure. Due to the limits in number of calls imposed by the Twitter API, we were not able to finish collecting the stratified adaptive sample in less than a month. In order to prevent such issues, we could imagine sampling designs adjusting the selection probabilities as the collection of the units of s 0 goes along. Sampling design and estimation with such sampling designs is one of the future developments of our research we consider on this subject (see section 6.2).

Snowball sampling is unlikely prone to the same flaw, as number of units in final sample depends on the degree distribution. This distribution is often known a priori, and well modeled by a power law for all web and social networks graphs. Contrary to adaptive sampling, we are guaranteed that the extension will be complete after only one browse of the list of users followed by the units in s 0 .

Conclusion and future work 6.1 Summary

This paper describes a design-based statistical method to estimate linear quantities on Twitter's graph based on users rather than queries. The method relies on sampling theory and in particular on developments of sampling theory for graphs. We tried two so-called "extension" designs: snowball sampling and adaptive sampling, which were first designed in official statistics to measure rare characteristics on a given population. We use them to try and measure the number of accounts having tweeted about the trailer of the Star Wars movie on the day of its release. Despite the event generating 390000 tweets in approximately 3 hours, the users responsible for these tweets are rare among the 1 billion Twitter users. Despite being unable to get through the whole adaptive sample because of the number of calls allowed by the Twitter API, the stratified snowball proved rather precise. Variance estimators were also computed, although they required a much higher number of calls.

Future work

More specific adaptive designs As we saw in paragraph 5.2, in the case of adaptive sampling, the final sample size can be huge if units bearing the characteristic of interest are highly clustered. In order to avoid being unable to collect the whole sample in this case, it might be useful to introduce a second-degree sampling design to select only a part of each network k ∈ [ [1, K]]. Estimation using such designs has been studied by Thompson ( [START_REF] Steven K Thompson | Adaptive web sampling[END_REF]).

Design effects

The results obtained proved the extension sampling designs to be efficient methods to measure rare quantities with decent accuracy. Though the design effects shown in table 1 are smaller than 1, they are very similar to those of the stratified sampling design. In other terms, these extension sampling designs seem successful as a way to reach rare individuals ; however, in general, it appears that neither snowball nor adaptive sampling are generic methods that can help reduce variance by extending any sampling design. In other terms, variance for snowball and adaptive sampling cannot by bounded by something lower than O( 1 n ), which is the order of magnitude of the variance of the Horvitz-Thompson estimator under a simple random sampling design. It is also interesting to note that we used an opportunity stratification, thus such performance cannot be guaranteed in general, even for networks presenting characteristics similar to the Twitter graph.

Our future work on this aspect consists in studying correlations for different models commonly used in model-based estimation. This will hopefully lead to specifications determining cases when exstension designs are worth using.

Estimation of graph totals Finally, in this article, we only dealt with linear estimators of totals and means. Estimation of totals of higher order are possible under the snowball and the adaptive sampling design. Such variables can include degree, clustering, centrality, etc. Following and idea developped by Dell et al. ( [START_REF] Dell | Mise en oeuvre du calcul de variance par linéarisation[END_REF], [START_REF] Lesage | Calage non linéaire[END_REF]), we will also try calibration on such totals when they are known.

  35]) Let's denote : U = population of interest = vertices of the graph N = #U = population size n = sample size y k = number of times user k tweeted about the Star Wars trailer

Figure 1 :

 1 Figure 1: Population U

Figure 2 :

 2 Figure 2: Sample s 0 .

Figure 3 :

 3 Figure 3: Addition of 1-stage snowball A(s 0 )

Figure 4 :

 4 Figure 4: Adaptive stratified cluster sampling, figure from[START_REF] Steven K Thompson | Stratified adaptive cluster sampling[END_REF]

4. 1

 1 Simple designsV( T (Y )) = k∈U (1 -p)y k p

Table 1 :

 1 Estimates and characteristics for three different sampling designs

	2

https://support.twitter.com/articles/119135