Sabeur Aridhi
email: sabeur.aridhi@unitn.it

Laurent D'orazio

Mondher Maddouri
email: maddourimondher@yahoo.fr

Engelbert Mephu Nguifo

Cost models for distributed pattern mining in the cloud: application to graph patterns

Recently, distributed pattern mining approaches have become very popular, especially in certain domains such as bioinformatics, chemoinformatics and social networks. In most cases, the distribution of the pattern mining process generates a loss of information in the output results. Reducing this loss may affect the performance of the distributed approach and thus, the monetary cost when using cloud environments. In this context, cost models are needed to help selecting the best parameters of the used approach in order to achieve a better performance especially in the cloud. In this paper, we address the multi-criteria optimization problem of tuning thresholds related to distributed frequent pattern mining in cloud computing environment while optimizing the global monetary cost of storing and querying data in the cloud. To achieve this goal, we design cost models for managing and mining graph data with large scale pattern mining framework over a cloud architecture. We define four objective functions, with respect to the needs of customers. We present an experimental validation of the proposed cost models in the case of distributed subgraph mining in the cloud.

Introduction

Frequent pattern mining is one of the most important concepts in data mining, concerned with finding local structures in the data. It has become an important topic of research with numerous applications in several disciplines ranging from association rule mining [START_REF] Han | Mining frequent patterns by pattern-growth: methodology and implications[END_REF] and graph mining [START_REF] Suryawanshi | Algorithms for frequent subgraph mining[END_REF], to image mining [START_REF] Melendez | Unsupervised texture-based image segmentation through pattern discovery[END_REF] and bioinformatics [START_REF] Maier | Sapa tool: finding protein regions by combination of amino acid composition, scaled profiles, patterns and rules[END_REF]. Generally, these fields exploit the extracted patterns for characterizing and classifying their associated data. For example, in graph mining, patterns are subgraphs extracted from a collection of graphs or a single large graph with a frequency no less than a user-specified support threshold. The discovered patterns are used lately to reveal interesting information hidden in the original data.

Nowadays, the amount of the available data has been exploding. Consequently, several distributed and cloud-based solutions have been proposed for distributed pattern mining from large-scale data. However, the distribution of the pattern mining process generates a loss of information in the output results [START_REF] Aridhi | Density-based data partitioning strategy to approximate large-scale subgraph mining[END_REF]; [START_REF] Riondato | Parma: a parallel randomized algorithm for approximate association rules mining in mapreduce[END_REF].

In [START_REF] Aridhi | Density-based data partitioning strategy to approximate large-scale subgraph mining[END_REF], a cloud-based approach for distributed frequent subgraph mining is presented. The output of the proposed approach is an approximation of the exact solution. In [START_REF] Riondato | Parma: a parallel randomized algorithm for approximate association rules mining in mapreduce[END_REF], PARMA, a parallel technique for mining frequent itemsets and association rules is proposed. The final result of PARMA is an approximation of the exact solution since it mines random subsets of the input dataset. Reducing the loss generated by distributed pattern mining approaches may affect the performance of the distributed approach and thus, the monetary cost when using cloud environments. In this context, cost models are needed to help selecting the best parameters of distributed pattern mining approaches in order to achieve better performance especially in the cloud [START_REF] Kashef | A cost model for hybrid clouds[END_REF]; [START_REF] Nguyen | Cost models for view materialization in the cloud[END_REF].

Several cost models have been developed for estimating costs of distributed data mining applications [START_REF] Ogunde | Improved cost models for agent-based association rule mining in distributed databases[END_REF]; [START_REF] Nguyen | Cost models for view materialization in the cloud[END_REF]. However, these approaches do not deal with distributed pattern mining. In addition, they do not incorporate an optimiser to be able to estimate the costs associated with the distributed pattern mining.

In this paper, we address the multi-criteria optimization problem of tuning thresholds related to distributed frequent pattern mining in cloud computing environments while optimizing the global monetary cost of storing and querying data in the cloud. We propose cost models for managing and mining graph data with large scale pattern mining framework over a cloud architecture. We also define objective functions, with respect to the needs of cloud customers.

The contributions of this paper are as follows:

-We propose cost models for pattern mining over a cloud architecture. We focus on subgraph patterns. -We define four objective functions, with respect to the needs of customers. These needs can be expressed by a financial budget limit, a response time limit or a mining quality limit. -We validate experimentally the proposed cost models and the defined objective functions.

This paper is organized as follows. In the next section, we present the background information and the preliminary notions of our work. In Section 3, we describe our cost models for distributed pattern mining in the cloud. In Section 4, we present the optimization process and the objective functions. In Section 5, we describe our experimental study and we discuss the obtained results. Finally, in Section 6, we present an overview of some related works dealing with cost models for distributed pattern mining in the cloud.

Background

In this section, we present the background information related to pattern mining in the cloud. We first introduce a simple use case that serves as a running example throughout this paper. Then, we describe a typical pricing model in the cloud, illustrated by some of Windows Azure services and Amazon Web Services (AWS).

Running example

In order to illustrate our cost models, we rely on a frequent subgraph mining example. Considering a graph dataset containing a set of community networks of a social network. Nodes of the graph represent people and edges represent interactions between them. Social network analysts need to examine the community networks patterns per day, month, and year. The analysis consists of extraction of frequent subgraph patterns in community networks. It includes queries like "frequent subgraphs that occur in more than 30% of graphs in the database". We suppose that our dataset contains ten million graphs and its size on disk is 100 GB. The query example consists of retrieving community networks patterns that occur in more than 30% of graphs in the database and of producing a query result of 10 GB.

Cloud pricing policies

Cloud Service Providers (CSPs) supply a variety of resources, such as hardware (CPU, storage, networks), development platforms and services with different services and pricing. In addition, they provide services that allow the design of MapReduce-based applications in the cloud such as HDInsight of Windows Azure and Amazon Elastic MapReduce of Amazon Web Services (AWS). In order to have an overview of CSPs pricing policy, the following examples present a simplified version of both HDInsight service offer [START_REF] Inc | Windows azure offer[END_REF] and Amazon Elastic MapReduce (Amazon EMR) service offer Inc (2013a). The objective of this description is indeed not to compare the different providers, but to provide an idea about CSPs pricing offers.

HDInsight offer

HDInsight is a MapReduce service proposed by Windows Azure. It is based on Hadoop. A HDInsight environment consists of a head node, a gateway node and one or more compute nodes. The master node is charged $0.64 per hour and compute nodes are charged $0.32 per hour. The gateway node is free.

According to the HDInsight offer, the costs of five node hadoop cluster (one master node and four compute nodes), is $0.64 + $0.32 • 4 = $1.92 per hour.

We mention that the storage and the bandwidth consumption in HDInsight are billed according to the standard Windows Azure offer [START_REF] Inc | Windows azure offer[END_REF]. Bandwidth consumption is billed with respect to data volume (see Table 1).

TAB. 1: Windows Azure bandwidth prices (output data).

Data volume

Price per month First 5 GB per month free 5 GB-10 TB per month $0.12 per GB 40 TB per month $0.09 per GB 100 TB per month $0.07 per GB 350 TB per month $0.05 per GB

In this model, input data transfers are free, whereas output data transfer cost varies with respect to data volume, with an earned rate when volume increases. When applying this pricing model onto our use case, the cost of bandwidth consumption (query result of 10 GB) is (10 -5) • $0.12 = $0.60.

We mention that Windows Azure Storage provides storage of non-relational data, including storage blob, table and disk. It provides two options for storage: locally and geographically redundant. The locally redundant storage option allows multiple replicas of data within a single sub-region to provide the highest level of durability. The geographically redundant storage option offers an extra level of durability by replicating data between two remote sub-regions.

TAB. 2: Windows Azure storage prices (storage blob).

Price per month Data volume

Geographically redundant storage Locally redundant storage

First 1 TB per month $0,085 per GB $0,068 per GB Next 49 TB per month $0,075 per GB $0,006 per GB Next 450 TB per month $0,06 per GB $0,048 per GB Next 500 TB per month $0,044 per GB $0,0055 per GB Next 4 PB per month $0,41 per GB $0,0051 per GB In this model, the price varies with respect to data volume, with an earned rate when volume increases (see Table 2). In our running example, the monthly storage price of our data (100 GB dataset) with the locally redundant storage option is $0.068 • 100 = $6.8.

Amazon Elastic MapReduce offer

Amazon Elastic MapReduce (Amazon EMR) is a MapReduce web service provided by Amazon Web Service (AWS). Amazon EMR uses Hadoop to distribute and process the data across a resizable cluster of Amazon Elastic Compute Cloud (EC2) instances.

Amazon EMR provides a variety of standard Amazon EC2 instance that can be rent (extra small, small, large and extra large) at various prices, as illustrated in Table 3. We mention that the Amazon EMR price is included in the prices presented in Table 3 For example, the costs of five node hadoop cluster, with small instances, is $0.075 • 5 = $0.375 per hour.

Table 4 presents EC2 bandwidth prices with respect to data volume.

In this model, input data transfers are free, whereas output data transfer cost varies with respect to data volume, with an earned rate when volume increases.

TAB. 4: EC2 bandwidth prices (output data).

Data volume

Price per month First 1 GB per month free 2 GB-10 TB per month $0.12 per GB 40 TB per month $0.09 per GB 100 TB per month $0.07 per GB 350 TB per month $0.05 per GB Finally, AWS Storage provides storage capabilities. Amazon Elastic Block Store (EBS) proposes a fixed price ($0.10 per GB), whereas Amazon S3 (see Table 5) enables an earned rate when volume increases.

TAB. 5: Amazon S3 storage prices.

Data volume Price per month

First 1 TB $0,14 per GB Next 49 TB $0,125 per GB Next 450 TB $0,11 per GB

In our running example, monthly storage price of our data (100 GB dataset) with Amazon EBS is $0,10 • 100 = $10.

Cost models for distributed pattern mining in the cloud

Let C dm be the data management cost and C c be the cost of computing patterns in a distributed environment. We define the total cost C of distributed pattern mining by:

C = C dm +C c .
(1)

Depending on the model used to distribute the computations (i.e. MapReduce or other) and the different parameters within each model, the factors which determine C dm and C c change. In our work, we consider MapReduce-based approaches. Two types of parameters setting are required in this setting: (1) parameters related to the pattern mining process such as the support threshold and the size of the database and (2) parameters related to the MapReduce framework that specify how the MapReduce job should execute the distributed pattern mining process. Let us define some functions that we use to express our cost models.

-Function s(•) returns the size in GB of any dataset, e.g., s(DS) is the size of the dataset DS and s(R) is the size of the result data R, -Function ts(•) returns the storage time of any dataset, e.g., ts(DS) is the storage time of the dataset DS in the cloud and ts(R) is the storage time of the result data R, -Function t map (i, Part i (DS)) returns the runtime taken by the map task to process the i th partition of DS, -Function t reduce (k) returns the runtime taken by the reduce task of the k th reducer.

Data management cost

We define the data management cost C dm as the sum of data transfer cost C t and storage cost C s . Formally, the data management cost is:

C dm = C t +C s .
(2)

Data transfer cost depends on several parameters: the size of the dataset, the size of the results and the pricing model applied by the Cloud Service Providers (CSP). The total data transfer cost C t is the sum of the input data transfer and the output data transfer costs. The input data transfer cost is the product of the CSP's atomic transfer cost c ti of the input data and the total size of input data. The output data transfer cost is the product of the CSP's atomic transfer cost c to of the output data and the total size of result data (s(R)):

C t = c ti • s(DS) + c to • s(R).
(3)

As illustrated in equation ( 3), the total data transfer cost is proportional to the total size of input and output data. We notice that most cloud providers such as Windows Azure and Amazon Web Service (AWS) do not charge for input data transfers. Consequently, total data transfer cost C t become:

C t = c to • s(R). (4)
Storage cost depends on parameters such as the size of the dataset, the storage time, the type of data replication (locally redundant storage or globally redundant storage) and the CSP's pricing policy. We assume that the storage period in the cloud is divided into intervals. In each interval, the size of the stored data is fixed. The total storage cost (C s ) is the CSP's fixed price per GB (c CSP s ) multiplied by the size of intial s(DS) and result data s(R), multiplied by the sum of sizes of the initial dataset and the result data, multiplied by their respective storage time during the intervals:

C s = ∑ Intervals c CSP s • (s(DS) + s(R)) • (t end -t start ), (5)
where t start , t end are start and end point of an interval. By combining equations ( 2), ( 3) and ( 5), the total data management cost is:

C dm = ∑ Intervals c CSP s • (s(DS) + s(R)) • (t end -t start ) + c t • (s(DS) + s(R)). (6)
As illustrated in equation ( 6), the data management cost depends essentially on the size of input data and result data. Indeed, it depends on the nature of data under consideration.

Beside the data management cost, it is necessary to study the computing cost on the data. In the context of our work, this computing cost consists of pattern mining cost.

Mining cost

In a cloud environment, mining processes are executed on computing instances {I i } i=1•••n with different performances in terms of number of CPUs, available RAM, etc., and thus, with different costs. Each instance may bear different performances (with respect to its number of CPUs, its available RAM, etc.), and thus different costs.

The cost for renting instance I i is denoted by c(I i ). This cost must be paid at each connection to the cloud. We define the cost of computing patterns by:

C c = n ∑ i=0 c(I i ) • T mining , (7)
where

T mining = (t part + m max j=0 (t map ( j, Part j (DS))) + r max k=0 (t reduce (k)) +CP • t compress ), (8)
where t part is the partitioning time, t map ( j, Part j (DS)) is the time taken by the j th Map task to process the j th partition of DS, t reduce (k) is the time taken by the k th Reduce task, t compress is the compression time of the result files, m is the number of Map tasks, r is the number of Reduce tasks and CP is a binary parameter set to 1 if the output data should be compressed and 0 otherwise. The values of t part , t map ( j, Part j (DS)) and t reduce (k) are estimated experimentally.

Optimization process

In this section, we investigate how the parametrization of the pattern mining approach and of MapReduce framework may impact the mining process performance. In the following, we present four objective functions with respect to the needs and capacity of customers. Such needs include budget limit, response time limit and mining quality limit.

Response time: The idea here is to achieve better performance in terms of response time. Given a predefined financial budget B and a predefined mining quality limit Q, our objective in this scenario is to select the best parameters that minimize the mining process in the cloud:

Ob j 1 =      minimize T mining , C = C dm +C c ≤ B, MiningQuality ≥ Q. (9)
Figure 1 presents the feasible solutions that minimize the response time with respect to financial budget B and a predefined mining quality limit Q. Each point in Figure 1 corresponds to a feasible solution of our objective function without considering constraints defined in equation (9). The red points correspond to solutions that verify our mining quality limit (X axis) and budget limit (Y axis) constraints.

We notice that each point in Figure 1 corresponds to a response time value. The optimal solution in this context is the solution that presents the lower value of the response time. Monetary cost: For a predefined response time limit T and a predefined mining quality limit Q, the objective in this scenario is to select the best parameters that minimize the monetary cost of the mining process in the cloud:

Ob j 2 =      minimize C = C dm +C c , T mining ≤ T, MiningQuality ≥ Q. (10)
Figure 2 presents the set of feasible solutions that minimize the monetary cost with respect to a response time limit T and a predefined mining quality limit Q. In the Figure 2, red points correspond to solutions that verify our mining quality limit (X axis) and response time (Y axis) constraints.

FIG. 2: Minimizing monetary cost under mining quality and response time constraints.

From the set of feasible solutions, we select the optimized solution that presents the lower value of monetary cost.

Mining quality: The goal of this objective function is to achieve the optimized quality of results (the mining quality). Given a predefined response time limit T and a predefined financial budget B, our objective in this scenario is to select the best parameters that maximize the mining quality of the distributed pattern mining method in the cloud:

Ob j 3 =      maximize MiningQuality, T mining ≤ T, C = C dm +C c ≤ B. (11)
We show in Figure 3, the set of feasible solutions that maximize the mining quality with respect to a financial budget B and a predefined response time limit T . Points represented in Figure 3 corresponds to feasible solutions of our objective function without considering the constraints defined in equation ( 11). The red points correspond to solutions that verify our mining quality limit (X axis) and budget limit (Y axis) constraints.

FIG. 3: Maximizing mining quality under monetary cost and response time constraints.

The optimized solution here is the one that presents the higher value of mining quality. In the case of the distributed subgraph mining task, the optimized solution is the one that presents the lower value of LossRate.

Response time vs. monetary cost vs. mining quality tradeoff: Our objective in this scenario is to select the best parameters that offer the best tradeoff between query processing time, mining quality of the distributed pattern mining method and financial cost:

Ob j 4 =          minimize (T mining ,C) and maximize (MiningQuality), T mining ≤ T, C = C dm +C c ≤ B, MiningQuality ≥ Q. (12)
The above presented objective function consists of multi-objective function since more than one objective function to be optimized simultaneously.

Experimental study

In this section, we first describe the experimental data and the overall setup of our preliminary experimentation effort. Then, we present the results we have obtained. We focused our experiments on solving the problem of distributed subgraph mining in the cloud. We adopted FIG. 4: Minimizing response time under monetary cost and loss rate constraints (Budget limit = $0.20 and LossRate limit = 10%).

the Pareto-based multi-objective optimization solution which aim to produce all Pareto optimal solutions. In fact, Pareto optimal solutions are very useful for decision makers who are faced with multiple objectives to make appropriate compromises, tradeoffs or choices.

Experimental setup

All experiments of our approach were carried out using a virtual cluster composed of five virtual machines. Each virtual machine is equipped with a Quad-Core AMD Opteron(TM) processor 6234 2.40 GHz CPU and 4 GB of RAM. All used machines feature Hadoop (version 0.20.2) and operate on Linux Ubuntu.

For our experiments, we have generated our data based on the obtained results from our approach for distributed subgraph mining in the cloud [START_REF] Aridhi | Density-based data partitioning strategy to approximate large-scale subgraph mining[END_REF]. We used results that correspond to the distributed subgraph mining from a dataset of 100, 000 graphs (see [START_REF] Aridhi | Density-based data partitioning strategy to approximate large-scale subgraph mining[END_REF]) to form our set of multi-objective points. For each set of parameters, we noticed the values of our objectives such as the response time (T mining ), the monetary cost (C) and the mining quality. The used parameters include MapReduce parameters and distributed subgraph mining approach parameters such as the support threshold (θ ) and a tolerance rate (τ) [START_REF] Aridhi | Density-based data partitioning strategy to approximate large-scale subgraph mining[END_REF]. Monetary cost values are estimated based on the Windows Azure pricing model [START_REF] Inc | Amazon ec2 offer[END_REF]. We suppose that our experimental environment is close to the large cloud instances provided by Windows Azure. Consequently, we use the corresponding costs to compute the values of the monetary cost C of each experiment using our virtual cluster.

Experimental results

During our experimental study, we examined the four objective functions described in Section 4.

Figure 4 draws the set of feasible solutions that minimize the response time of our distributed subgraph mining approach under monetary cost (C) and mining quality constraints ((LossRate in the case of subgraph patterns) ).

Each solution is represented by two points (a blue square point and a red diamond point). The blue square point corresponds to monetary cost in function of response time. The red diamond point corresponds to the loss rate in function of response time. Thus, the two points representing a solution have the same value of response time. Optimal solutions are determined by selecting solutions that present lower values of response time. For example, with budget limit = $0.20 and loss rate limit = 10% (see Figure 4), we distinguish one optimal solution (surrounded by an ellipse) which allows the lower value of response time. We notice that we can find more than one solution that allows a lower response time value.

In the Figure 5, we present the set of feasible solutions to solve the objective function associated to the monetary cost (Ob j 2 ). As shown in Figure 5, we can identify optimal solutions by selecting the solutions that present lower values of monetary cost in comparison with the set of feasible solutions. For example, with response time limit = 10s and loss rate limit = 30% (see Figure 5), we select one optimal solution (surrounded by an ellipse) which allows the lower value of loss rate.

Figure 6 illustrates the set of feasible solutions that optimize the objective function related to the loss rate of our subgraph mining approach in the cloud (Ob j 3 ). Similarly, feasible solutions are represented by couples of points. A couple of points contains one blue square point and one red diamond point. The blue square point corresponds to response time in function of loss rate. The red diamond point corresponds to the monetary cost in function of loss rate.

We recall that each feasible solution consists of a parametrization of the cloud-based subgraph mining approach. As illustrated in Figure 6, the set of optimal solutions (surrounded by an ellipse) contains more than one optimal solution (six optimal solutions) that minimize the loss rate. Therefore, we have six possible parameterizations of our cloud-based subgraph mining approach.

In order to solve the multi-objective function defined in Section 4, we computed all Pareto optimal solutions from our data (a set of multi-objective points). Table 6 presents the set of -The communication cost estimates: They involve the time needed for the computing agent to travel from the agent zone (AZ) to the data sources. -The local association rule mining costs: They make reference to the time needed for mining association rule locally at each data source. -The results information transfer costs: They make reference to the time needed for the computing agent to travel back to the agent zone with results information concerning each local mining. The overall response time for the distributed association rule mining T would be calculated as follows:

T = t darm + t dki ,
where t darm is the time taken to perform mining in a distributed environment and t dki is the time taken to perform distributed knowledge integration and return the results to the requesting server. The term t darm is defined by:

t darm = t 1 (AZ, i) + n max i=1 t 2 (i) + t 3 (i, AZ)
where the first term is the time taken by the computing agent to travel from the agent zone to data source i. The second term is the maximum of the times taken by the computing agent to mine at all data sources. The third term is the time taken for the agent to travel from the data source back to the agent zone with the results information. The authors discussed the values of t dki according to the number of used data servers and the number of data mining agents.

In [START_REF] Nykiel | Mrshare: sharing across multiple queries in mapreduce[END_REF], the authors propose the MRShare framework that transforms a batch of MapReduce queries into a new batch that will be executed more efficiently, by merging jobs into groups and evaluating each group as a single query. The authors define a cost model for MapReduce that provide a solution that derives the optimal grouping of queries. The total cost of executing a set J of n individual jobs is the sum of the cost T read to read the data, the cost T sort to do the sorting and copying at the map and reduce nodes, and the cost T tr of transferring data between nodes. Thus, the cost in MapReduce is:

T (J) = T read (J) + T sort (J) + T tr (J)
where the values of T read (J), T sort (J) and T tr (J) with grouping of queries are not the same without grouping.

Another attention was carried by [START_REF] Nguyen | Cost models for view materialization in the cloud[END_REF] to data management cost models in cloud environments. In their work, the authors propose new cost models that fit into the pay-as-you-go paradigm of cloud computing. They addressed the multi-criteria optimization problem of selecting a set of materialized views while optimizing the global monetary cost of storing and querying a database in a cloud environment. The total cloud data management cost C is defined by:

C = C c +C s +C t
where C c is the sum of computing costs, C s is the sum of storage costs and C t is the sum of data transfer costs. The proposed cost models complement the existing materialized view cost models with a monetary cost component that is primordial in the cloud [START_REF] Nguyen | Cost models for view materialization in the cloud[END_REF].

In [START_REF] Ogunde | Improved cost models for agent-based association rule mining in distributed databases[END_REF], the authors deal with cost models of classic architectural models used in the development of DDM systems namely, client-server and software agents. However, the proposed cost models in these works do not fit into cloud computing paradigm where the users only pay for the resources they use. In [START_REF] Nguyen | Cost models for view materialization in the cloud[END_REF]; [START_REF] Nykiel | Mrshare: sharing across multiple queries in mapreduce[END_REF], the authors deal with data management and execution aspect of MapReduce framework in a cloud setting. However, they do not include cost models for data mining processes in the top of MapReduce. Moreover, they do not consider monetary costs in the case of cloud-based data mining applications.

To the best of our knowledge, cost models for MapReduce-based pattern mining applications in cloud environments have not been developed.

Conclusion

In this paper, we presented cost models for distributed pattern mining in the cloud. It consists of two levels. The first level is novel cost models for pattern mining in the cloud. We focused the defined cost models on subgraph patterns in cloud computing. The proposed cost models consist of monetary cost components that are primordial in the cloud. The second level consists of the definition of a set of objective functions with respect to the needs and the financial capacity of customers. An experimental study was carried out in the case of cloudbased subgraph mining. It provided a first evaluation of our approach by selecting the optimal solutions that minimize our objectives such as the monetary cost, the response time and the loss rate.

In the future works, we aim to extend the experimental validation of the proposed cost models to a wider-scale experimentation. In this context, additional experiments will be carried out in which we solve the defined objective functions using more methods of solving multiobjective optimization problems. We aim also to run experiments on a variable number of cloud cloud instances, thus, experimenting the effect of primordial elasticity characteristic of the cloud on our cost models.

FIG. 1 :

 1 FIG. 1: Minimizing response time under monetary cost and mining quality constraints.

  FIG.5: Minimizing loss rate under monetary cost and response time constraints (Response time limit = 10s and LossRate limit = 30%).

  .TAB. 3: Amazon EC2 computing prices.

	Type	Virtual cores	RAM	Price per hour
	Small	1	1.7 GB	$0.075
	Medium	1	3.75 GB	$0.15
	Large	2	7.5 GB	$0.30
	Extra large	4	15 GB	$0.60

FIG. 6: Minimizing loss rate under monetary cost and response time constraints (Budget limit = $0.17 and Response time limit = 50).

Pareto optimal solutions that aim to quantify the trade-offs in satisfying the different objectives (response time, monetary cost and mining quality). We notice that the presented optimal solutions in Table 6 may help the parametrization of cloud-based subgraph mining applications. They provide suggestions for the choice of parameters (cloud parameters and mining approach parameters). However, it is suitable to provide one suggestion instead of many. This can be done by ranking optimal solutions based on a user-defined parameter.

We show in Table 6, the details of the Pareto optimal solutions. These details include cloud parameter values and subgraph mining parameter values. The Pareto optimal solutions illustrated in Table 6 aim to quantify the trade-offs in satisfying the different objectives (response time, monetary cost and mining quality).

Related works

Several distributed data mining systems have been proposed [START_REF] Ghoting | Nimble: a toolkit for the implementation of parallel data mining and machine learning algorithms on mapreduce[END_REF]; [START_REF] Chu | Map-Reduce for Machine Learning on Multicore[END_REF]; [START_REF] Riondato | Parma: a parallel randomized algorithm for approximate association rules mining in mapreduce[END_REF]; [START_REF] Foundation | Apache mahout[END_REF]. However, they do not incorporate an optimiser to be able to estimate the costs associated with the various distributed data mining scenarios. Consequently, several cost models have been developed for estimating costs of distributed data mining applications [START_REF] Ogunde | Improved cost models for agent-based association rule mining in distributed databases[END_REF][START_REF] Nguyen | Cost models for view materialization in the cloud[END_REF].

In [START_REF] Ogunde | Improved cost models for agent-based association rule mining in distributed databases[END_REF], the authors present an optimized model for estimating the response time of distributed association rule mining. In this work, three estimates were defined:


Jean Dolbeault
email: dolbeaul@ceremade.dauphine.fr

Giuseppe Toscani
email: giuseppe.toscani@unipv.it

Nonlinear diffusions: extremal properties of Barenblatt profiles, best matching and delays

Keywords: Nonlinear diffusion equations, Source-type solutions, Gagliardo-Nirenberg-Sobolev inequalities, Improved inequalities, Scalings, Second moment, Temperature, Rényi entropy, Best matching Barenblatt profiles, Delay Mathematics Subject Classification (2010) primary: 35K55, 35K65, 35B40; secondary: 46E35, 39B62, 49J40

In this paper, we consider functionals based on moments and nonlinear entropies which have a linear growth in time in case of source-type solutions to the fast diffusion or porous medium equations, that are also known as Barenblatt solutions. As functions of time, these functionals have convexity properties for generic solutions, so that their asymptotic slopes are extremal for Barenblatt profiles. The method relies on scaling properties of the evolution equations and provides a simple and direct proof of sharp Gagliardo-Nirenberg-Sobolev inequalities in scale invariant form. The method also gives refined estimates of the growth of the second moment and, as a consequence, establishes the monotonicity of the delay corresponding to the best matching Barenblatt solution compared to the Barenblatt solution with same initial second moment. Here the notion of best matching is defined in terms of a relative entropy.

Introduction

Consider the nonlinear diffusion equation in R d , d ≥ 1,

∂u ∂t = ∆u p , (1)
with initial datum u(x, t = 0) = u 0 (x) ≥ 0 such that

R d u 0 dx = 1 , Θ(0) = 1 d R d |x| 2 u 0 dx < +∞ . (2)
It is known since the work of A. Friedman and S. Kamin, [START_REF] Friedman | The asymptotic behavior of gas in an n-dimensional porous medium[END_REF], that the large time behavior of the solutions to [START_REF] Barenblatt | On some unsteady motions of a liquid and gas in a porous medium[END_REF] is governed by the source-type Barenblatt solutions U (t, x) := 1

κ t 1/µ d B x κ t 1/µ (3)
where

µ := 2 + d (p -1) , κ := 2 µ p p -1 1/µ
and B is the Barenblatt profile

B (x) :=    C -|x| 2 1/(p-1) + if p > 1 , C + |x| 2 1/(p-1) if p < 1 .
Here (s) + = max{s, 0} and, for p > 1 -2 d , the constant C is chosen so that R d B (x) dx = 1. Solution (3) was found around 1950 by Ya.B. Zel'dovich and A.S. Kompaneets. Later G.I. Barenblatt analyzed the solution representing heat release from a point source for p > 1. See [START_REF] Zel'dovich | Towards a theory of heat conduction with thermal conductivity depending on the temperature. Collection of papers dedicated to 70th birthday of Academician AF Ioffe[END_REF][START_REF] Barenblatt | On some unsteady motions of a liquid and gas in a porous medium[END_REF], and [START_REF] Vázquez | The porous medium equation[END_REF] for more details.

The result of [START_REF] Friedman | The asymptotic behavior of gas in an n-dimensional porous medium[END_REF], subsequently improved in a number of papers like, e.g., [START_REF] Fila | Rate of convergence to Barenblatt profiles for the fast diffusion equation[END_REF], guarantees to various extents that the Barenblatt solution can fruitfully be used to obtain the large-time behavior of all other solutions, departing from an initial value like in [START_REF] Carlen | Hardy-Littlewood-Sobolev inequalities via fast diffusion flows[END_REF]. Precise estimates of the difference in time of basic quantities of the real solution with respect to the source-type one are however difficult to obtain and additional conditions are needed for low values of p > 0.

As main example, let us consider the growth of the second moments of the solution to [START_REF] Barenblatt | On some unsteady motions of a liquid and gas in a porous medium[END_REF], for an initial value satisfying [START_REF] Carlen | Hardy-Littlewood-Sobolev inequalities via fast diffusion flows[END_REF]. For a Barenblatt solution, we easily obtain the exact growth

1 d R d |x| 2 U (t, x) dx = t 2/µ Θ where Θ := κ 2 d R d |x| 2 B (x) dx .
For p > 1 it has been shown in [START_REF] Toscani | A central limit theorem for solutions of the porous medium equation[END_REF] that this time-behaviour is captured by any other solution to (1) satisfying conditions (2) for large times. Further studies published in [START_REF] Dolbeault | Best matching Barenblatt profiles are delayed[END_REF] then revealed that, at least in the fast diffusion range, there is a nondecreasing delay between the propagation in time of the second moments of the source-type solution and the generic solution to [START_REF] Barenblatt | On some unsteady motions of a liquid and gas in a porous medium[END_REF]. We shall give a simple explanation for this fact in Theorem 3, and also show that in the porous medium case p > 1 the delay is nonincreasing.

A way to look at this phenomenon is the following. The second moment of the Barenblatt solution, raised to power µ/2, grows linearly in time. Hence, its first variation in time of Θ (t) µ/2 is constant, while the second variation is equal to zero. To see how the second moment of any other solution to equation [START_REF] Barenblatt | On some unsteady motions of a liquid and gas in a porous medium[END_REF] behaves in time, it comes natural to estimate the time variations of G := Θ µ/2 , where the second moment functional is defined by

Θ(t) := 1 d R d |x| 2 u(t, x) dx .
This analysis will lead to the interesting observation that the second variation of G has a fixed sign, which implies concavity or convexity in t depending on the value of p. Also, since the first variation is invariant with respect to dilations and the solution to ( 1) is asymptotically self-similar, it follows at once that the first variation satisfies a sharp inequality which connects the second moment to its first variation, and optimality is achieved by Barenblatt profiles. This idea can also be applied to the study of the behavior of the derivative of the second moment, as predicted by the nonlinear diffusion. It holds

Θ = 2 E
where, up to a sign, the generalized entropy functional is defined by

E(t) := R d |u(t, x)| p dx .
For the Barenblatt solution (3) one can easily check that E (t) σ grows linearly in time if d (1p) σ = µ. This leads to estimate the time variation of F := E σ . As in the previous case, we will conclude by showing that the second variation in time of F has a negative sign if p < 1, which implies concavity. In this case also, the first variation is invariant with respect to dilations, which implies a sharp inequality of Gagliardo-Nirenberg-Sobolev type, and optimality is again achieved by Barenblatt profiles.

As the results of this paper clearly indicate, looking at functionals of the solution to the nonlinear diffusion(1) which grow linearly in time when evaluated along the source-type solution represent a valid and powerful alternative to the well-known entropy-entropy production method developed in the last two decades to investigate the large-time behavior of the solution by scaling the problem in order to obtain a Fokker-Planck equation with a fixed steady state.

This new way of looking at the problem opens completely new questions, which at the moment seem to be very difficult to deal with. For instance, higher order derivatives in time of the second moment of the solution are easily evaluated in correspondence to Barenblatt solutions, by giving a precise growth, say t -σn , where n is the order of the derivative. Hence, one can think to proceed as for the first two cases, by considering the power of order σ n of the n-th derivative and by checking if there is a sign.

With Theorem 1, we shall start by a simplified proof of the isoperimetric inequality for Rényi entropy powers in [START_REF] Savaré | The concavity of Rényi entropy power[END_REF], based on based on the linear growth of the functional F, that is also stated in [START_REF] Carrillo | Renyi entropy and improved equilibration rates to selfsimilarity for nonlinear diffusion equations[END_REF]Theorem 4.4] and emphasize the fact that the method is limited to exponents p ≥ 1 -1 d . Using this inequality, J.A. Carrillo and G. Toscani have been able to establish improved rates of convergence in the non-asymptotic regime of the solutions to [START_REF] Barenblatt | On some unsteady motions of a liquid and gas in a porous medium[END_REF] in [START_REF] Carrillo | Renyi entropy and improved equilibration rates to selfsimilarity for nonlinear diffusion equations[END_REF]Theorem 5.1]. Since Rényi entropy powers are equivalent to relative entropies relative to best matching Barenblatt solutions under appropriate conditions on the second moments as shown in [START_REF] Dolbeault | Fast diffusion equations: matching large time asymptotics by relative entropy methods[END_REF][START_REF] Dolbeault | Improved interpolation inequalities, relative entropy and fast diffusion equations[END_REF], improved rates have to be related with results obtained in rescaled variables in [START_REF] Dolbeault | Improved interpolation inequalities, relative entropy and fast diffusion equations[END_REF], where the scales were defined in terms of second moments. Equivalently, the improved entropy-entropy production inequality of [10, Theorem 1] is similar in nature to the isoperimetric inequality for Rényi entropy powers. As we shall observe in this paper, the isoperimetric inequality for Rényi entropy powers is in fact a Gagliardo-Nirenberg inequality in scale invariant form, which degenerates into Sobolev's inequality in the limit case p = 1 -1 d and explains why it cannot hold true for p < 1 -1 d . The entropy-entropy production inequality of [START_REF] Del Pino | Best constants for Gagliardo-Nirenberg inequalities and applications to nonlinear diffusions[END_REF] is also a Gagliardo-Nirenberg inequality, but not in scale invariant form and it has recently been established in [START_REF] Dolbeault | Stability results for logarithmic Sobolev and Gagliardo-Nirenberg inequalities[END_REF] that the difference between the scale invariant form and the non scale invariant form is enough to account for improved rates of convergence in Fokker-Planck type equations, i.e., in nonlinear diffusions after a convenient rescaling.

Theorem 2 is devoted to a rather simple observation on second moments, which is however at the core of our paper. It is based on the linear growth of the functional G. By introducing the relative entropy with respect to the best matching Barenblatt function, we establish the result of Theorem 3 on delays. This result has been proved in [START_REF] Dolbeault | Best matching Barenblatt profiles are delayed[END_REF] by a much more complicated method, when p < 1. Here we simply rely on the convexity or concavity of t → G(t), depending whether p < 1 or p > 1, and both cases are covered. This analysis also suggests a method to obtain estimates of the delays, that is investigated in Section 5.

Let us conclude this introduction with a brief review of the literature. For considerations on second moment methods in fast diffusion and porous medium equations, we refer to [START_REF] Toscani | A central limit theorem for solutions of the porous medium equation[END_REF][START_REF] Carrillo | Asymptotic complexity in filtration equations[END_REF][START_REF] Dolbeault | Best matching Barenblatt profiles are delayed[END_REF] and references therein. Sharp Gagliardo-Nirenberg-Sobolev inequalities have been studied in [START_REF] Del Pino | Best constants for Gagliardo-Nirenberg inequalities and applications to nonlinear diffusions[END_REF][START_REF] Dolbeault | Improved interpolation inequalities, relative entropy and fast diffusion equations[END_REF][START_REF] Savaré | The concavity of Rényi entropy power[END_REF][START_REF] Dolbeault | Stability results for logarithmic Sobolev and Gagliardo-Nirenberg inequalities[END_REF] from the point of view of the rates of convergence of the solutions to (1) in the intermediate asymptotics regime, and also for obtaining improved convergence rates in the initial regime. A counterpart of such improved rates is the notion of delay which was established in [START_REF] Dolbeault | Best matching Barenblatt profiles are delayed[END_REF] in the fast diffusion regime and will be recovered as a very simple consequence of moment estimates in Theorem 3 and extended to the porous medium case.

Theorems 1 and 2 follow the same line of thought: compute the time evolution of a functional which grows linearly when evaluated in the case of Barenblatt functions and has some concavity or convexity property otherwise. As a main consequence, we provide a proof of some Gagliardo-Nirenberg-Sobolev inequalities which goes along the lines of [START_REF] Carrillo | Asymptotic L 1 -decay of solutions of the porous medium equation to self-similarity[END_REF][START_REF] Del Pino | Best constants for Gagliardo-Nirenberg inequalities and applications to nonlinear diffusions[END_REF][START_REF] Carlen | Hardy-Littlewood-Sobolev inequalities via fast diffusion flows[END_REF] on the one hand, of [START_REF] Savaré | The concavity of Rényi entropy power[END_REF][START_REF] Carrillo | Renyi entropy and improved equilibration rates to selfsimilarity for nonlinear diffusion equations[END_REF][START_REF] Toscani | Rényi Entropies and Nonlinear Diffusion Equations[END_REF] on the other hand, and makes a synthetic link between the two approaches. The first approach is inspired by the entropy functional introduced by J. Ralston and W.I. Newman in [START_REF] Newman | A Lyapunov functional for the evolution of solutions to the porous medium equation to self-similarity[END_REF][START_REF] Ralston | A Lyapunov functional for the evolution of solutions to the porous medium equation to self-similarity[END_REF], also known in the literature as the Tsallis entropy, while the second one is more related with Rényi entropies and connected with information theory inspired by [START_REF] Costa | A new entropy power inequality[END_REF][START_REF] Villani | A short proof of the "concavity of entropy power[END_REF]. The reader interested in further details is invited to refer to [START_REF] Toscani | Rényi Entropies and Nonlinear Diffusion Equations[END_REF] and references therein for a more detailed account.

Notations, main results and consequences

The entropy is defined by

E := R d u p dx
and the Fisher information by

I := R d u |∇v| 2 dx with v = p p -1 u p-1 . If u solves (1), then E = (1 -p) I .
To compute I , we will use the fact that

∂v ∂t = (p -1) v ∆v + |∇v| 2 (4)
and get that F := E σ has a linear growth asymptotically as t → +∞ if

σ = µ d (1 -p) = 1 + 2 1 -p 1 d + p -1 = 2 d 1 1 -p -1 .
This definition is the same as the one of Section 1. The growth is exactly linear in case of Barenblatt profiles, so that E σ-1 I is independent of t if we denote by E , I , F etc. the entropy, the Fisher information, etc. of these Barenblatt profiles.

Theorem 1 Assume that p ≥ 1 -1 d if d > 1 and p > 0 if d = 1. With the above notations, t → F(t) is increasing, (1 -p) F (t) ≤ 0 and lim t→+∞ 1 t F(t) = (1 -p) σ lim t→+∞ E σ-1 I = (1 -p) σ E σ-1 I .
This result has been established in [START_REF] Savaré | The concavity of Rényi entropy power[END_REF]. In this paper we give a slightly simpler proof. The result of Theorem 1 amounts to state that t → F(t) is concave if p < 1 and convex if p > 1, with an asymptotic slope given by (1p) σ E σ-1 I . Moreover, we observe that the inequality

E σ-1 I ≥ E σ-1 I (5)
is equivalent to one of the two following Gagliardo-Nirenberg inequalities:

(i) If 1 -1 d ≤ p < 1, then (5) is equivalent to ∇w θ L 2 (R d ) w 1-θ L q+1 (R d ) ≥ C GN w L 2q (R d ) (6)
where

θ = d q q -1 d + 2 -q (d -2) , 1 < q ≤ d d -2
and equality with optimal constant C GN is achieved by B p-1/2 .

(ii) If p > 1, then ( 5) is equivalent to

∇w θ L 2 (R d ) R d w 2q dx 1-θ 2q ≥ C GN w L q+1 (R d ) (7)
where

θ = d q q -1 d + 2 -q (d -2)
and q takes any value in (0, 1).

In both cases, we relate Gagliardo-Nirenberg inequalities and (5) by

u p-1/2 = w w L 2q (R d )
with q = 1 2 p -1 .

These considerations show that p = 1 -1 d correspond to Sobolev's inequality: 2q = 2 d/(d -2) and θ = 1 if d ≥ 3. This case is therefore the threshold case for the validity of the method. Details will be given in Section 3.

Using the moment

Θ := 1 d R d |x| 2 u dx ,
we can introduce the functional

G := Θ 1-η/2 with η = d (1 -p) .
As a function of t, G also has a linear growth in case of Barenblatt profiles. Again this definition is compatible with the one of Section 1 since

µ 2 = 1 - η 2 .
In the general case, we get that

G = µ H ,
where we define the Rényi entropy power functional H by

H := Θ -η/2 E = Θ d 2 (p-1) E
and observe that the corresponding functional H for Barenblatt profiles is independent of t.

Theorem 2 Assume that p ≥ 1 -2 d . With the above notations, t → G(t) is increasing, (1p) H (t) ≥ 0 and

lim t→+∞ 1 t G(t) = 1 - η 2 lim t→+∞ H = 1 - η 2 H .
The function t → G(t) is convex if p < 1 and concave if p > 1, with an asymptotic slope given by (1η/2) H . Details will be given in Section 4.

We can also consider the relative entropy with respect to the best matching Barenblatt function defined as

F[u] := inf s>0 F[u | U s ]
where U s (x) = U (s, x) = s -d/µ U 1 (s -1/µ x) is defined by [START_REF] Carrillo | Asymptotic L 1 -decay of solutions of the porous medium equation to self-similarity[END_REF]. Here the variable s plays the role of a scaling parameter, and the relative entropy with respect to a given function U is defined by

F[u | U] := 1 p -1 R d u p -U p -p U p-1 u -U dx .
A key observation in [START_REF] Dolbeault | Fast diffusion equations: matching large time asymptotics by relative entropy methods[END_REF] is the fact that

F[u] = F[u | U s ] is achieved by a unique Barenblatt solution which satisfies R d |x| 2 u dx = R d |x| 2 U s dx .
The proof of this fact is a straightforward computation: as a functional of U, F[u | U] is concave and has at most one maximum point. Hence if we write that |U s (x)| p/(p-1) = a(s) + b(s) |x| 2 , then

d ds F[u | U s ] = p p -1 R d a (s) + b (s) |x| 2 (u -U s ) dx . Since R d u dx = R d U s dx = 1
, the term proportional to a does not contribute and the other one vanishes if and only if the moments are equal.

After undoing the change of variables, we get that

s = Θ Θ µ 2 . ( 8
)
With this choice of s, U s is the best matching Barenblatt function in the sense that this Barenblatt function minimizes the relative entropy

F[u | U s ] among all Barenblatt functions (U s ) s>0 .
If u is a solution to (1), for any t ≥ 0, we can define s as a function of t and consider the delay which is defined as

τ (t) := Θ(t) Θ µ 2 -t .
The main result of this paper is that t → τ (t) is monotone.

Theorem 3 Assume that p ≥ 1 -1 d and p = 1. With the above notations, the best matching Barenblatt function of a solution u to (1) satisfying ( 2) is (t, x) → U (t + τ (t), x) and the function t → τ (t) is nondecreasing if p > 1 and nonincreasing if 1 -1 d ≤ p < 1. With s given by ( 8), we notice that the relative entropy with respect to the best matching Barenblatt function is given by

F[u | U s ] = 1 p -1 R d u p -(U s ) p dx
and it is related with the the Rényi entropy power functional by

H -H = Θ d 2 (p-1) E -Θ d 2 (p-1) E = (p -1) Θ d 2 (p-1) F[u | U s ] .
See Figs. 12. An estimate of the delay t → τ (t) will be given in Section 5.

0 t τ (0) τ (t) τ ∞ = lim s→+∞ τ (s) s Θ µ/2 (s) s (s τ (0))Θ s (s + τ (t))Θ µ/2 µ/2 s s (s + τ ∞ )Θ µ/2
Fast diffusion case + Fig. 1 In the fast diffusion case, the (bold) curve s → G(s) = Θ µ/2 (s) is convex, increasing, and its asymptote is s → (s + τ∞) Θ µ/2 . At any time t ≥ 0, we observe that it crosses the line s → (s + τ (t)) Θ µ/2 = (s -t + 1) Θ µ/2 (t) transversally, so that t → τ (t) is monotone decreasing, unless the solution is itself a Barenblatt solution up to a time shift.

0 s τ (0) τ (t) τ ∞ = lim s→+∞ τ (s) t s (s + τ (0)) Θ µ/2 s Θ µ/2 (s) s (s + τ (t)) Θ µ/2 s (s + τ ∞ ) Θ µ/2
Porous medium case Fig. 2 In the porous medium case, the curve s → Θ µ/2 (s) is still increasing but concave, so that t → τ (t) is monotone increasing, unless the solution is itself a Barenblatt solution up to a time shift.

A direct proof of Gagliardo-Nirenberg inequalities

This section is devoted to the proof of Theorem 1 and also to a proof of Gagliardo-Nirenberg inequalities ( 6) and [START_REF] Costa | A new entropy power inequality[END_REF]. We provide a slightly simplified proof of Lemma 4 below, compared to the existing literature: see [START_REF] Savaré | The concavity of Rényi entropy power[END_REF] and references therein. Some of the key computations will be reused in Section 5.

A preliminary computation

According to [18, Appendix B], we have the following result.

Lemma 4 If u solves (1) with initial datum u(x, t = 0) = u 0 (x) ≥ 0 such that

R d u 0 dx = 1 and 1 d R d |x| 2 u 0 dx < +∞, then v = p p-1 u p-1 solves (4) and I = d dt R d u |∇v| 2 dx = -2 R d u p D 2 v 2 + (p -1) (∆v) 2 dx . (9)

The fast diffusion case

Recall that

E = R d u p dx satisfies E = (1 -p) I with I = R d u |∇v| 2 dx and v = p p-1 u p-1 . Since D 2 v 2 = 1 d (∆v) 2 + D 2 v - 1 d ∆v Id 2
by Lemma 4, we find that F = (E σ ) can be computed as

1 σ (1 -p) E 2-σ (E σ ) = (1 -p) (σ -1) R d u |∇v| 2 dx 2 -2 1 d + p -1 R d u p dx R d u p (∆v) 2 dx -2 R d u p dx R d u p D 2 v - 1 d ∆v Id 2 dx .
Using u ∇v = ∇(u p ), we know that

R d u |∇v| 2 dx = R d ∇(u p ) • ∇v dx = - R d u p ∆v dx
and by the Cauchy-Schwarz inequality,

R d u |∇v| 2 dx 2 ≤ R d u p dx R d u p (∆v) 2 dx .
With the choice

σ = 1 + 2 1 -p 1 d + p -1 = 2 d 1 1 -p -1 , we get that E 2-σ (E σ ) σ (1 -p) 2 =: -R[u]
where the remainder terms have been collected as the sum of two squares:

R[u] R d u p dx = (σ -1) R d u p ∆v -R d u |∇v| 2 dx R d u p dx 2 dx + 2 1 -p R d u p D 2 v - 1 d ∆v Id 2 dx .
Hence we know that

F = (E σ ) is nonincreasing, that is, 1 1 -p E σ-1 E = R d u p dx σ-1 R d u |∇v| 2 dx := J
is nonincreasing. Since J is invariant under scalings as a functional of u, this means that lim

t→∞ J = J
where B is the Barenblatt function such that R d B dx = 1 and J the corresponding value of the functional J. Written for the initial datum u 0 = u, we have shown that J ≥ J .

For any smooth and compactly supported function w, if we write u p-1/2 = w/ w L 2q (R d ) with q = 1/(2 p-1), then the inequality amounts to the Gagliardo-Nirenberg inequality [START_REF] Costa | On solutions to multivariate maximum -entropy problems[END_REF] and equality is achieved by B p-1/2 . More precisely we have shown the following result.

Proposition 5 Assume that 1 < q < d d-2 if d ≥ 3 and q > 1 if d = 1 or d = 2.
With the above notations we have

4 p 2 (p -1) 2 (2 p -1) 2 J -J = ∇w 2 L 2 (R d ) w 2 (1-θ)/θ L q+1 (R d ) w 2/θ L 2q (R d ) -C 2/θ GN = (1 -p) ∞ 0 R[u(t, •)] dt ≥ 0 ,
where u(t, •) denotes the solution to (1) with initial datum u.

Hence we have shown that, as a function of t, F is concave increasing and we have identified its asymptotic slope, which is given by the optimal constant in the Gagliardo-Nirenberg inequality lim t→+∞ J(t) = J = C 2/θ GN .

The porous medium case

The computations are the same. With the same definition (2) as in the fast diffusion case, σ is negative, t → F is convex increasing and the limit of its derivative is achieved among Barenblatt functions. The Gagliardo-Nirenberg inequality now takes the form [START_REF] Costa | A new entropy power inequality[END_REF]. Again equality is achieved by B p-1/2 . Details are left to the reader.

The second moment and the Rényi entropy power functional

This section is devoted to the proof of Theorem 2. Let us consider the subsequent time derivatives of the functional

G := Θ 1-η 2 with η = d (1 -p) = 2 -µ .
It is straightforward to check that

G = µ H with H := Θ -η 2 E
where the Rényi entropy power functional is defined by

H := Θ -η 2 E .
We recall that E = (1p) I. It is straightforward to check that

H 1 -p = Θ -1-η 2 Θ I -d E 2 = d E 2 Θ η 2 +1 (q -1) with q := Θ I d E 2 ≥ 1 because d E 2 = 1 d - R d x • ∇(u p ) dx 2 = 1 d R d x • u ∇v dx 2 ≤ 1 d R d u |x| 2 dx R d u |∇v| 2 dx = Θ I
by the Cauchy-Schwarz inequality. This proves that (1p) H is monotone increasing and from the theory in [START_REF] Del Pino | Best constants for Gagliardo-Nirenberg inequalities and applications to nonlinear diffusions[END_REF], we know that its limit is given by the source-type Barenblatt solutions U p,t defined by [START_REF] Carrillo | Asymptotic L 1 -decay of solutions of the porous medium equation to self-similarity[END_REF]. Since H is also scale invariant, its limit is in fact given by the value of the functional for B , that is lim t→+∞

H(t) = lim t→+∞ Θ(t) d 2 (p-1) E(t) = Θ d 2 (p-1) E =: H
and we get

Θ(t) d 2 (p-1) E(t) ≤ H if p < 1 , Θ(t) d 2 (p-1) E(t) ≥ H if p > 1 . (10)
Taking the logarithm on both sides of inequality [START_REF] Dolbeault | Improved interpolation inequalities, relative entropy and fast diffusion equations[END_REF], and considering that p < 1, we obtain the equivalent inequality

1 1 -p log R d u p dx - d 2 log 1 d R d |x| 2 u dx ≥ log H 1 -p = log E 1 -p - d 2 log Θ
in which we can recognize the well-known inequality for Rényi entropies obtained in [START_REF] Costa | On solutions to multivariate maximum -entropy problems[END_REF][START_REF] Lutwak | Cramér-Rao and moment-entropy inequalities for Renyi entropy and generalized Fisher information[END_REF]. After multiplying by (1p) and taking the exponential, we realize that this is also equivalent to the inequality

F[u | U 1 ] ≥ 0
which is a well-known consequence of Jensen's inequality: see for instance [START_REF] Del Pino | Best constants for Gagliardo-Nirenberg inequalities and applications to nonlinear diffusions[END_REF].

Delays

This section is devoted to delays. At any time t ≥ 0, we consider the best matching Barenblatt solution and the corresponding delay τ (t)

U s(t) (x) = U (s(t), x) , s(t) = t + τ (t)
according to the definitions of Section 2. After proving Theorem 3, we give an estimate of τ (t).

Proof of Theorem 3. With p ≥ 1-1 d , we know that µ > 0. At any time t ≥ 0, let us consider the solution t → u(t, •) to (1). The scale s(t) of the best matching Barenblatt function is determined by [START_REF] Del Pino | Best constants for Gagliardo-Nirenberg inequalities and applications to nonlinear diffusions[END_REF]. By observing that t → Θ µ/2 grows faster (resp. slower) than t

→ t Θ µ/2 if p > 1 (resp. if p < 1), where t → t Θ µ/2
is the rate of growth corresponding to the self-similar Barenblatt function given by (3), we get that t → τ (t) is nondecreasing (resp. nonincreasing) in the porous medium case p > 1 (resp. fast diffusion case p < 1). See Figs. 12.

Next we study a quantitative estimate of delays, which relies on the commutation of the third derivative in t of G. This approach is parallel to the results in [START_REF] Toscani | A concavity property for the reciprocal of Fisher information and its consequences on Costa's EPI[END_REF] in the linear case.

Let us recall that

Θ = 2 E, E = (1 -p) I and J = E σ-1 I is such that 0 ≥ E 2-σ J = (1 -p) (σ -1) I 2 + E I so that I ≤ -(1 -p) (σ -1) I 2 E = - 2 d (1 -η) I 2 E . Hence H 1 -p = Θ -η 2 I -d Θ -η 2 -1 E 2 ≤ d E 3 Θ η 2 +2 η + 2 -3 η q -2 (1 -η) q 2 (11)
according to the computations of Section 4. We observe that H ≤ 0 if p < 1 and H ≥ 0 if p > 1.

Theorem 6 Under the assumptions of Theorem 3, if p > 1 -1 d and p = 1, then the delay satisfies

lim t→+∞ |τ (t) -τ (0)| ≥ |1 -p| Θ(0) 1-d 2 (1-p) 2 H H -H(0) 2 Θ(0) I(0) -d E(0) 2
Proof Assume first that p < 1 and recall that for any t ≥ 0

G (t) ≤ lim t→+∞ G (t) = 1 - η 2 H =: G .
Since G is nonincreasing, we have the estimate

G(t) ≤ G(0) + G (0) t + 1 2 G (0) t 2 ∀ t ≥ 0
so that G(0) + G t -G(t) ≥ (G -G (0)) t -1 2 G (0) t 2 is maximal for t = t := (G -G (0))/G (0). As a consequence, since G(0) = G τ (0) and G(t ) = G t + τ (t ) , we get that

G τ (0) -G τ (t ) = G(0) + G t -G t + τ (t ) ≥ G -G (0) 2 2 G (0) , that is τ (0) -τ (t ) ≥ G -G (0) 2 2 G G (0) = (1 -p) Θ(0) 1+ η 2 2 H H -H(0) 2 Θ(0) I(0) -d E(0) 2 .
We conclude by observing that t → τ (0)τ (t) is nondecreasing.

Estimates for p > 1 are very similar, up to signs.

Further estimates can be obtained easily. Let us illustrate our new approach by a result on

q := Θ I d E 2 = 1 + Θ η 2 +1 d E 2 H 1 -p (12)
in the fast diffusion case. We denote by q 0 , Θ 0 ,.. the initial values of q, Θ, etc.

Proposition 7 Assume that 1 -1 d ≤ p < 1. Then for any t ≥ 0, we have q(t) ≤ q 0 Θ(t) q 0 Θ(t) -(q 0 -1) Θ 0 =: q(t) and τ (t) ≤ τ 0 exp t 0 ds s + Θ0 µ E0 -η µ s 0 (q -1) ds t .

Proof Using [START_REF] Dolbeault | Stability results for logarithmic Sobolev and Gagliardo-Nirenberg inequalities[END_REF] and [START_REF] Dolbeault | Best matching Barenblatt profiles are delayed[END_REF], we obtain q ≤ 2 q (1q) E Θ = q (1q) Θ Θ .

We can integrate and get the first estimate.

To obtain the integral estimate for τ , we compute

G G = µ E Θ and 1 1 -p G G = 1 1 -p H H = d E Θ (q -1) ≤ d µ G G (q -1) , so that 1 - G G = G G (G ) 2 ≤ η µ (q -1)
and finally G G ≥ Θ 0 µ E 0 + t -η µ t 0 (q(s) -1) ds .

Using the fact that G(t) = G t+τ (t) , we conclude after one more integration with respect to t and get the second estimate.

Let us conclude this paper by a few remarks.

(i) The quantity q -1 is a measure of the distance to the set of the Barenblatt profiles when p > 1 -1 d : see [START_REF] Dolbeault | Stability results for logarithmic Sobolev and Gagliardo-Nirenberg inequalities[END_REF] for more details. (ii) Improved rates of decay for E and, as a consequence, improved asymptotics for F and G can be achieved by considering the estimates found in [START_REF] Carrillo | Renyi entropy and improved equilibration rates to selfsimilarity for nonlinear diffusion equations[END_REF]. (iii) Alternatively, improved functional inequalities as in [START_REF] Dolbeault | Stability results for logarithmic Sobolev and Gagliardo-Nirenberg inequalities[END_REF] can be used directly to get improved asymptotics for F and G.

Acknowledgements This work has been partially supported by the projects STAB, No-NAP and Kibord (J.D.) of the French National Research Agency (ANR), and by MIUR project "Optimal mass transportation, geometrical and functional inequalities with applications" (G.T.). J.D. thanks the Department of Mathematics of the University of Pavia for inviting him and supporting his visit. c 2014 by the authors. This paper may be reproduced, in its entirety, for non-commercial purposes.

Proof Let us give a simplified proof of this result. Using [START_REF] Barenblatt | On some unsteady motions of a liquid and gas in a porous medium[END_REF] and (4), we can compute

where the last line is given by an integration by parts:

1) Using the elementary identity

2) Since u ∇v = ∇(u p ), an integration by parts gives

Collecting terms establishes (9).


Véronique Cazanau

Y Daële

Jie Hu

Abdelwahid Chen

H Chen

Y Ren

M Cazaunau

V Daële

Y Hu

J Chen

A Mellouki
email: mellouki@cnrs-orleans.fr

Rate coefficients for the reaction of ozone with 2-and 3-carene

Keywords: Ozone, 2-carene, 3-carene, rate coefficients

published or not. The documents may come

Rate coefficients for the reaction of ozone with 2-and 3-carene

INTRODUCTION

It is well recognized that a wide variety of biogenic volatile organic compounds (BVOCs) are emitted into the atmosphere from terrestrial vegetation [1]. Isoprene and monoterpenes are the dominant on a global scale [2]. Once emitted, these BVOCs undergo chemical oxidation through reactions with ozone, OH and NO 3 radicals. The existing literature data shows that OH and NO 3 radicals reactions constitute important atmospheric removal processes of the unsaturated BVOCs during the day and night, respectively [3,4], while the reaction with O 3 could be important both during the day and night [5]. Moreover, ozonolysis of BVOCs is important with respect to production of HO X (OH and HO 2 ) and RO 2 radicals in remote areas and for secondary organic aerosol (SOA) formation [5,6]. The evaluation of the contribution of the ozonolysis as a potential degradation process for BVOCs requires reliable kinetic data in order to evaluate their fate and contribution in the global atmospheric chemistry.

The rate coefficients values for the reaction of O 3 with alkenes depend on the number and identity of alkyl substituents that have both inductive and steric effects. McGillen et al. have developed a structure-activity relationship (SAR) that has been found to perform well for a wide range of open chain alkenes and conjugated dienes [7]. The method was highly parameterized but is not recommended for endocyclic alkenes. The other effects such as ring strain, the asymmetry degree, and conformational constraints have to be taken into account. Hence, experimental data are needed for variety of unsaturated BVOCs in order to improve the existing SAR to enhance the capabilities of the predictive methods to estimate the rate coefficient values for the reactions of ozone with complex organic species.

In the present work, we have measured the rate coefficients for the reaction of O 3 with 2-carene (3,7,7-

Laminar flow reactor:

The laminar flow reactor has been described in details previously [9].

Briefly, the flow reactor consists of a vertical 100-cm-long Pyrex glass tube with 10 cm i.d. and a 110-cm-long movable mixing plunger with 1.2 cm i.d.. With the 2.8 L min -1 "ozone flow" through the injector and the 1.8 L min -1 "carene flow" through the reactor tube, the reaction time was varied in the range of 17-55 s by adjusting the position of the mixing plunger relatively to the sampling point at the bottom of the reactor (30-90 cm). In our experimental conditions with the total flow rate of 4.6 L min -1 (the flow velocity, Ve~1.57 cm s -1 ), the flow reactor was characterized by a Reynolds number of ~107 and a Knudsen number of 6.6 × 10 -17 , corresponding to a laminar and viscous flow. Experiments were performed at T = 296 ± 1 K, P = 760 ± 0.5 Torr and relative humidity ≤1%. Ozone was produced by passing the controlled mixture of synthetic air and nitrogen through a UV Pen-ray lamp. Its concentration was measured at the outlet of the reactor by an UV absorption ozone monitor (France Environment 41M; Horiba APOA-360). Carene was premixed with nitrogen (typically ~0.05%) in a 10 L glass bulb at a total pressure of 800-1000 Torr. The flow from the bulb was controlled by a calibrated mass flow controller to determine the carene concentration in the flow reactor. Additional calibration was conducted for the glass bulbs by means of dynamic dilution which agreed with the calibration conducted in the simulation chamber within ~5% uncertainty. Since the carene concentrations were not measured directly during experiments, an uncertainty of 10% was used for data evaluation.

Instruments

PTR-TOF: PTR-TOF was running under E/N 137 Td (10 Multipath FTIR: It consists of Bruker Vertex 70 FTIR spectrometer equipped with DigiTect high sensitivity detector DLATGS (D301/B) system and coupled to a white-type mirror system in the chamber resulting of an optical path of 302.6 meters. The reactants and products were monitored in the spectral range 8.000-350 cm -1 . Samples were averaged from 250 scans which typically took 3 minutes. The concentration of ozone was quantified by comparison with reference ozone spectra at the wavelength range 900-1070 cm -1 .

Kinetic measurements

The rate coefficients for the reaction of O 3 with 2-and 3-carene were determined by the absolute and relative methods using the three reactors described above.

Absolute method: Experiments were carried out under pseudo-first-order conditions with

[carene] 0 ≫ [O 3 ] 0 or conversely. In the case of carene in excess (performed in SC and in the flow reactor), the temporal profiles of [O 3 ] is given by:

    ' 33 0 OO kt t e   (1)             3 0 33 0 3 O ln ' or ln O ' ln O O t t k t k t         (2)     3 0,O where ' ( carene ) carene ' i k f k k    (3)
where i k represents the rate coefficients for the reaction of ozone with 2-and 3-carene, as a function of the concentration of carene (  

( carene ) f
), and 0,carene ' k is the first-order ozone decay rate in the absence of carene. i k , the bimolecular rate coefficient for the ozonolysis of carene, is obtained from the slope of the plot

0,carene ' ' kk  vs. [carene].
In the case of O 3 in excess (performed in HELIOS), one species among cyclohexane, 1,3,5trimethylbenzene (TMB) and 2-butanol was employed to scavenge OH radicals produced by reactions of O 3 with carene. The rate coefficients ( i k ) are derived from the Eq. ( 4):

3 3 0,carene ' ([O ]) [O ] ' i k f k k    (4)
where ' k and Relative method: Experiments were performed both in SC and in HELIOS. Relative rate coefficients for the reactions of ozone with 2-and 3-carene were determined by comparing their rates of decay with that of a reference compound (cyclohexene in the present work) whose

reaction rate coefficients (k ref ) is well established.         00 0,carene 0,cyclohexene carene cyclohexene ln ' ln ' carene cyclohexene i ref tt k k t k t k                             (5)
where 0 ' k is the first-order decay rate of carene or cyclohexene in the absence of ozone and t is the reaction time. Since ozonolysis of carene generates OH radicals that may lead to much faster decay of the reactants, OH scavenger was injected simultaneously to scavenge more than 90% of

[OH].
Note that in some experiments (i.e. 3CAR-6BR and 2CAR-5BR), excess ozone was injected in one addition, in which case that absolute and relative rates were simultaneously derived from the data sets.

RESULTS

Absolute rate measurements

For experiments performed in the flow reactor and in SC, the initial concentrations of carene and ozone were in the range of 0.9-12.1 × 10 13 and 1.0-3.0 × 10 12 molecule cm -3 , respectively. The use of large excess of carene over ozone enables to make secondary ozone reactions such as ozone with OH and HO 2 radicals negligible (k(OH+O 3 )= 7.3× 10 -14 ; k(HO 2 +O 3 )= 2.0× 10 -15 cm 3 molecule -1 s -1 [START_REF]Task Group on Atmospheric Chemical Kinetic Data Evaluation[END_REF]). The experimental conditions and the results obtained are summarized in Table 1. Typical data sets of pseudo first order rate coefficients are plotted in Figure 1. 41M or APOA-360 ozone monitors were respectively utilized for 2-carene and 3-carene experiments in the flow reactor since they showed no interference with corresponding carene in the absence of ozone. However, negative readings were observed at the end of reactions on 41M or APOA-360 ozone monitors respectively for 2-and 3-carene experiments performed in SC (Suppl. Fig. 2). In the case of 3-carene, the negative readings (up to "-19" ppbv) showed significant correlation with the concentration of consumed ozone (i.e. consumed 3-carene), inferring that the products of reaction between ozone and 3-carene in the absence of OH scavenger caused the interference. Thereby, the ozone concentration profiles have been corrected from the "negative" contribution from the products that related to the consumption of ozone.

Note that the interference was expected to be minor in the flow reactor since the reaction was limited by residence time for a maximum of 55 s. However, a possible overestimation of pseudo first order rate coefficients due to the negative interferences cannot be excluded.

The first order rate coefficients of ozone loss in the absence of any organic reagents were typically (8 ± 4) × 10 -4 s -1 and (2.0 ± 0.9) × 10 -5 s -1 for the flow reactor and SC, respectively. The pseudo first order rate coefficients derived from the decay of ozone in the presence or 2-and 3carene carried out in the flow reactor might be subject to diffusion processes. The diffusion coefficient in air (D O3-Air ) was estimated to be 0.164 cm 2 s -1 at 293 K [START_REF] Massman | [END_REF]. The plug-flow approximation where

with ' Meas k is the measured pseudo first order rate coefficient (in s -1 ), R is the inner radius of the flow reactor (in cm) and D O3-Air is the diffusion coefficient of ozone in air (in cm 2 s -1 ) can be applied to the experimental system for ' Meas k ≤ 9.84×10 -3 s -1 and the concentration of ozone was homogeneous all over the flow section. For ' Meas k ≥ 9.84×10 -3 s -1 , the measured pseudo first order rates have been corrected for radial diffusion using the formula: has not been corrected [9].

  2 ' 1 ' ' Meas eff Meas k D k e k V    
For experiments performed in HELIOS, the initial concentrations of carene were in the range of 1.6-6.9 × 10 11 molecule cm -3 , while the concentrations of ozone were typically 2.4-10.0 × 10 12 molecule cm -3 (Table 2 & Suppl. Table 1).

To make sure that carene was removed solely by reaction with ozone, experiments were carried out, in the presence of sufficient concentrations of cyclohexane, TMB or 2-butanol to scavenge most of the OH radicals produced from the ozonolysis of carene, i.e.,

    0 0 Scav 10 carene OH Scav OH carene k k      (7)
The parent peak of m/z 137.13 was usually used for calculating the concentration of carene, while the fragment peak of m/z 81.07 was used when available (Fig. 2b and Table 2). Cyclohexane, 2butanol or TMB have been used as OH scavengers (Suppl. Table 1). Since TMB reacts with OH at a rate comparable to that of carene, relatively low concentration of TMB compared to that of 2butanol and cyclohexane was added to the chemical system to scavenge OH. However, several "products" peaks were observed on PTR-TOF spectra when O 3 and TMB were present in HELIOS, which might originate from some side reaction occurring in the drift tube or other phenomena. Among those peaks, significant isobaric peak of m/z 137.10 (C 9 H 13 O + ) can affect the evaluation of carene decay using m/z 137.13 (Suppl. Fig. 3). Taking advantage of the high-massresolution feature of PTR-TOF, the concentration of carene (m/z 137.13) was obtained using appropriate multi-peak separation method. Its decay rate showed no difference from that of fragment peak at m/z 81.07 (Fig. 2b).

Cyclohexane was preferred for PTR-TOF measurement because its proton affinity is lower than that of water molecule, which makes it undetectable. There was only k' available derived from m/z 137.13 because cyclohexanone, a product of reaction between cyclohexane and OH, shared the fragment peak of m/z 81.07 with carene. Similarly, the k' derived from the decay of m/z 81.07 in the presence of cyclohexene as a reference has been excluded because interference from cyclohexene at m/z 81.07 made them overestimated. Unsurprisingly, k', i.e.

 

3 O Carene 3 O k  
showed great linearity with either TMB, 2-butanol or cyclohexane as a scavenger. Since we have no reason to decline the data sets derived either from m/z 137.13 or m/z 81.07, the k was extracted from all data (in units of 10 -17 cm 3 molecule -1 s -1 ): k(O 3 +3-carene) = 3.7 ± 0.2; k(O 3 +2carene) = 23.9 ± 1.3.

Relative rate measurements

The decay rates of 2-and 3-carene and cyclohexene in the absence of ozone were determined before initiating the reaction. The initial concentration of carene and cyclohexene were in the range of 580-4800 ppbv (SC) and 6.7-30 ppbv (HELIOS). Their decays were monitored by the PTR-TOF at a time resolution of 15 to 60 s at protonated m/z 137.13 and m/z 83.09. The m/z 83.09 and m/z 137.13 were found to interfere with isobaric peaks of m/z 83.05 (C 5 H 7 O + ) and m/z 137.10 (C 9 H 13 O + ), respectively (Suppl. Fig. 4). Those isobaric peaks might originate from the products of the reactions between carene/cyclohexene and ozone or their fragments. Manually Gauss peak fits (SC) or PTR-data analyzer (HELIOS) [12] were applied on the high-resolution (3000-4000 / mm  ) mass spectra to obtain the peak intensities of m/z 137.13 and m/z 83.09.

Figure 3 shows examples of experimental plots derived from the analysis of a relative rate measurement for the reactions of ozone with 2-and 3-carene, respectively. As expected, straight lines with a zero intercept were obtained, showing in all cases a good linearity.

    0 ln t A f A      ,     0 0 2 f t f t f A A         resulted in an uncertainty ~7%.
The rate coefficients of the reactions of ozone with 2-and 3-carene obtained using the relative rate method, are summarized in Table 3. 91%-95% of OH radicals were scavenged during the experiments.

The measured rate coefficients ratios were placed on an absolute basis using the k(O 3 +cyclohexene) = 7.9 ×10 -17 cm 3 molecule -1 s -1 at 296 K [START_REF] Calvert | The Mechanisms of Atmospheric Oxidation of the Alkenes[END_REF][START_REF] Atkinson | [END_REF]. The final rate coefficients values were derived by averaging the data from different experiments with error limits that encompass the extremes of σ error of the individual determinations and do not include systematic errors and uncertainties of the reference rate coefficients which could be as high as 25%.

In addition, k(O 3 +cyclohexene) was determined simultaneously during Exp. 3CAR-6BR and 2CAR-5BR (Table 4). The obtained rate coefficient of (7.4 ± 0.5) x 10 -17 cm 3 molecule -1 s -1 at 295 ± 2 K is in good agreement with literatures [START_REF] Atkinson | [END_REF][15][16].

DISCUSSION

The rate coefficients obtained in the present work using three different facilities (the flow reactor, SC and HELIOS) are compared with the existing data in the literature in Table 5.

Recommendations from IUPAC [START_REF]Task Group on Atmospheric Chemical Kinetic Data Evaluation[END_REF] are also included for comparison. k(O 3 +2-carene) values measured with the absolute and relative rate methods in our laboratory are in good agreement with each other and with the only available experimental results from Atkinson, et al. [17] where both absolute and relative rate methods were used.

On the other hand, the rate coefficients for reaction of ozone with 3-carene obtained from the flow reactor is ~30% higher than those using other methods. This would be partially explained by the interferences of O 3 monitor. Additionally, limited by the vapor pressure of 3-carene, its concentration in the flow reactor could not exceed 11.3 ×10 13 molecule cm -3 under our experimental conditions. In this case, the k' was only ~5.5 times higher than the typical wall loss rate, which made the extracted slope of k' against [3-carene] of great uncertainties. The rate coefficients reported by Grimsrud, et al. [18] for a series of terpenes are higher than those of subsequent studies. In a more recent study from Atkinson, et al. [17], the presence of reactive impurities in the 3-carene sample used was reported (3% sabinene and/or β-pinene and 2.9% limonene), such that the measured absolute rate by monitoring the decay rate of O 3 in the presence of excess 3-carene was believed to be overestimated by up to about 20%. In the present study, the stated purity of 3-carene was ≥ 98.5% (more details in supplementary), and the impurities at this level would not significantly affect our absolute and relative rates. Witter, et al. [19] reported k(O 3 +3-carene) = 5.6 × 10 -17 cm 3 molecule -1 s -1 using relative method in a flow reactor. It is ~50% higher than the other values, for which the reason is unknown.

Eventually, we present updated rate coefficients values for reactions of ozone with 2-and 3carene by averaging the values reported in this study and from Atkinson, et al. [17]: k(O 3 +2carene) = 23.9 ± 1.0 and k(O 3 +3-carene) = 3.8 ± 0.2 (in units of × 10 -17 cm 3 molecule -1 s -1 ) at 296 ± 2 K. For 3-carene, only the results derived from AM-SC, AM-HELIOS, RM-HELIOS in this study and RM in Atkinson, et al. [17] are used.

In terms of the structure-activity relationships (SAR), 2-and 3-carene have a moiety as 2,2dimethyl-2-pentene. No kinetic data of 2,2-dimethyl-2-pentene was available for comparison to date, and it was expected to be in the range of that of 2-methyl-2-pentene (43.0 × 10 -17 cm 3 molecule -1 s -1 ) and 2,4,4-trimethyl-2-pentene (13.2 × 10 -17 cm 3 molecule -1 s -1 ) because of the variable steric effect dependent on the number of 4-methyl substitutes [20]. Therefore, with rate coefficient of 2.4 × 10 -16 cm 3 molecule -1 s -1 , the bicyclic structure of 2-carene is empirically speculated to be strain-free and show no additional steric effect. On the other hand, 3-carene reacts much slower with ozone even compared with 2,4,4-trimethyl-2-pentene, inferring additional steric effects induced by its specific structures. The additional steric effects arise from mainly two hypothesis: (1) the conformational constraints of a C6-ring system containing two sp 2 hybridized carbons could inhibit reaction with ozone; (2) the bridgehead carbon out of the plane of the six membered ring like α-pinene and camphene cause additional steric effect [21]. The initial ozone attack on 2-and 3-carene gives an energy-rich primary ozonide (POZ), which promptly decomposes to two excited carbonyl substituted Criegee intermediates (CIs). Syn-and disubstituted CIs mainly decompose to form OH radicals through vinyl hydroperoxide channel in conjunction with a number of β-oxo alkyl radicals. The OH yields for reaction of ozone with 2and 3-carene were reported to be 0.81 ± 0.11 and 0.86 ± 0.11 respectively [22]. The high OH yields can be rationalized by the existence of β-vinyl hydrogen. The further chemistry of the βoxo alkyl radicals originated from ozonolysis of 3-carene may form a number of reported multifunctional organic products containing hydroxyl, carbonyl and acid functionalities and also acetone and formaldehyde ( [START_REF]Task Group on Atmospheric Chemical Kinetic Data Evaluation[END_REF] and cited refs.). Anti-conformer of CIs cannot isomerize to synconformer owing to the high energy barrier (over 20 kcal mol -1 [5]) and predominantly react with H 2 O under atmospheric conditions, leading to formation of caronaldehyde and H 2 O 2 , or carononic acid. Some support for this comes from the significant yield of H 2 O 2 for ozonolysis of 2-carene performed close to 100% RH [23] and increasing yield of 3-caronaldehyde for ozonolysis of 3-carene with increasing humidity [24]. Additionally, secondary ozonide has been observed for ozonolysis of 3-carene [25]. , where k(OH+2-butanol) = 8.7 × 10 -12 cm 3 molecule -1 s -1 [START_REF]Task Group on Atmospheric Chemical Kinetic Data Evaluation[END_REF], k(OH+2-carene) = 8.0 × 10 -11 cm 3 molecule -1 s -1 [START_REF] Calvert | The Mechanisms of Atmospheric Oxidation of the Alkenes[END_REF], k(OH+3-carene) = 8.8 × 10 -11 cm 3 molecule -1 s -1 [START_REF] Calvert | The Mechanisms of Atmospheric Oxidation of the Alkenes[END_REF], k(OH+cyclohexene) = 6.77 × 10 -11 cm 3 molecule -1 s -1 [START_REF] Calvert | The Mechanisms of Atmospheric Oxidation of the Alkenes[END_REF]. (c) Excessive concentration of 2-butanol completely consumed primary ions and thereby caused non-linear responses of carene and cyclohexene so that the obtained i ref k k was not included for the average. (d) Placed on an absolute basis using k(O 3 +cyclohexene) = 7.9 × 10 -17 cm 3 molecule -1 s -1 [START_REF] Atkinson | [END_REF]. k 295K = 7.9 × 10 -17 (a) [START_REF] Atkinson | [END_REF] k 298K = (8.5 ± 0.8) × 10 -17 (a) [15] k 295K = (7.05 ± 0.11) × 10 -17 (a)

CONCLUSION

[16] (a) cm 3 molecule -1 s -1 . (a) (× 10 -17 cm 3 molecule -1 s -1 ) (b) Placed on an absolute basis using k(O 3 +cyclohexene) = 7.9 × 10 -17 cm 3 molecule -1 s -1 [START_REF] Atkinson | [END_REF]. (c) Placed on an absolute basis using k(O 3 +α-pinene) = 9.3 × 10 -17 cm 3 molecule -1 s -1 [START_REF]Task Group on Atmospheric Chemical Kinetic Data Evaluation[END_REF]. (d) Placed on an absolute basis using k(O 3 +2-methylbut-2-ene) = 3.92 ×10 -16 cm 3 molecule -1 s -1 [START_REF]Task Group on Atmospheric Chemical Kinetic Data Evaluation[END_REF].

  trimethyl-bicyclo[4.1.0]hept-2-ene) and 3-carene(3,7,7-trimethyl-bicyclo[4.1.0]hept-3-3-carene are two important BVOC species characterized with an α-methyl-substituted endocyclic olefinic bond. The absolute and relative rate coefficients have been measured in three complementary experimental systems: two atmospheric simulation chambers and a laminar flow reactor. The kinetic measurements of 2-and 3-carene have been performed previously only a few times, most of which were conducted decades ago. The kinetic data obtained in this work are compared with the previous studies and discussed in terms of the atmospheric implications. Three complementary experimental systems have been used during this work: 7300 L simulation chamber (SC): Absolute and relative rate coefficients were measured using the ICARE-7300 L Teflon chamber[8]. Experiments were performed in Pressure ~ 760 torr of air at Temperature = 295 ± 1 K with a relative humidity of ~5%. Reagents that are liquids under ambient conditions were introduced into the chamber by placing a known volume in a glass-made bubbler which was then flushed by purified air (gently heated when necessary). The concentration of carene was monitored by a commercial Proton-Transfer-Reaction Time-of-Flight (PTR-TOF, Ionicon). Ozone was produced using a silent discharge in O 2 and its concentration was measured by UV absorption (Horiba, APOA-360). Two fans installed into the chamber ensured rapid mixing of reactants. Temperature and relative humidity data were continuously recorded by a combined sensor placed in the chamber. To prevent contamination from outside air, a flow of purified air was added continuously during all experiments to keep the chamber slightly above atmospheric pressure and to compensate for sampling flows of various instruments connected to the chamber. 90000 L simulation chamber (HELIOS): newly constructed at ICARE-CNRS, made from teflon and in the shape of truncated hemisphere with a surface to volume ratio of 1.2 m -1 . Absolute rates were measured in excess of ozone over carene. Experiments were performed in Pressure ~ 743-754 torr of air at Temperature = 293-305 K with a relative humidity of ~ 0.4% (dew point = -45 °C, [H 2 O] ~2.5 × 10 15 molecule cm -3 ). The operation procedures, including VOCs and O 3 injection, flow compensation, etc., are similar to those in 7300L simulation chamber. While ozone was monitored by either APOA-360 or in-situ Fourier transform infrared spectrometer (FTIR, Vertex 70, Bruker, optical length = 302.6 m), carene was monitored by PTR-TOF. Two fans installed into the chamber ensured rapid mixing of reactants.

  rates of carenes in the presence or absence of ozone, respectively. i k , as a function of the concentration of ozone ( O 3 ]. The decay of 2-and 3-carene and cyclohexene were monitored by PTR-TOF.

   derived from experimental data from both the flow reactor and simulation chamber are plotted against the concentration of carene in Figure2ato obtain the absolute rate coefficients, k i . It is worth noting that significant uncertainties for the pseudo first order rate coefficients measured at low concentration in the flow reactor was caused by the comparable 0 ' k . The rate coefficients are determined (in units of 10 -17 cm 3 molecule -1 s -1 ): k(O 3 +3-carene) = 4.9 ± 0.8 (flow reactor), = 3.5 ± 0.2 (SC); k(O 3 +2-carene) = 24.7 ± 2.5 (flow reactor).

  where D eff is the effective diffusion coefficient, preferred to D O3-Air . The correction factor applied to ' Meas k in the present work ranged from 1×10 -2 s -1 ) which indicated that axial diffusion can be considered negligible in our experimental conditions and therefore, 'Meas k

2-and 3 -

 3 Carene are expected to be removed from the troposphere through reactions with the main atmospheric oxidants (OH, NO 3 and O 3 ). The available kinetic data on the reactions of OH and NO 3 and the ones determined in the present work on O 3 enable to estimate the atmospheric lifetimes for 2-and 3-carene. Using tropospheric [OH]  2 × 10 6 molecule cm -3 (12-h average), [NO 3 ]  2 × 10 8 molecule cm -3 (12-h average, [4]) and [O 3 ]  10 12 molecule cm -3 (24-h average), the tropospheric lifetimes (τ = 1/k[X] with X = OH, NO 3 and O 3 ) with respect to reactions of carenes with OH (k(2-carene) = 8 × 10 -11 and k(3-carene) = 8.8 × 10 -11 in units of cm 3 molecule -1 s -1 [13]), NO 3 (k(2-carene) = 2 × 10 -11 and k(3-carene) = 9.1 × 10 -12 in units of cm 3 molecule -1 s -1 [10]) and O 3 (k(2-carene) = 2.4 × 10 -16 and k(3-carene) = 3.7 × 10-17 , in units of cm 3 molecule -1 s -1 , this work) are estimated to be in the range of few minutes to few hours. Ozone reactions might be important during day and night while OH and NO 3 reactions may be of importance during the daytime and nighttime, respectively. The very short atmospheric lifetimes indicate that 2-and 3carene will be oxidized near their emission sources to form other atmospheric organic components and radicals.

Figure 1 :

 1 Figure 1: Reaction of ozone with (a) 2-carene and (b) 3-carene: examples of pseudo-first order plots at 296 ± 2 K and 293 ± 2 K obtained from experiments in the flow reactor.

Figure 2 :

 2 Figure 2: Pseudo-first order constants as function of concentration of carene (a) from flow reactor and SC or ozone (b) from HELIOS. The pseudo-first order constants for 2-carene timed 1/3 for clearness.

Figure 3 :

 3 Figure 3: The decay rates of 2-carene (circle) and 3-carene (square) relative to that of cyclohexene in the presence of ozone and excess of 2-butanol.

[

Table 1 :

 1 Initial conditions and results obtained from the absolute measurements of rate coefficients for the recations of ozone with 2-and 3-carene at 295 ± 3 K and 760 ± 1 torr in the flow reactor and in SC.

		T (K)	[carene] (×10 13 molecule cm -3 )	'1 k  	(×10 -2 s -1 )
	2-carene	296	1.0	0.16±0.08
		295	2.4	0.60±0.12
		295	4.7	1.17±0.11
		297	7.2	1.69±0.14
		297	11.6	2.79±0.64
		296±2	k = (24.7 ± 2.5) × 10 -17 cm 3 molecule -1 s -1 (Flow reactor)
	3-carene	295	1.2	0.12±0.09
		293	1.8	0.14±0.12
		293	2.9	0.14±0.12
		294	5.0	0.25±0.07
		294	8.2	0.41±0.13
		294	11.3	0.55±0.10
		293±2	k = (4.9 ± 0.8) × 10 -17 cm 3 molecule -1 s -1 (Flow reactor)
		295	0.9	0.06±0.01
		295	2.5	0.09±0.01
		295	3.3	0.13±0.01
		295	4.5	0.16±0.01
		295	6.2	0.22±0.01
		295	6.9	0.25±0.01
		295	10.3	0.34±0.01
		295±1	k = (3.5 ± 0.2) × 10 -17 cm 3 molecule -1 s -1 (SC)

Table 3 :

 3 Summary of the experimental conditions and the results from the relative rate study of reaction of ozone with 2-and 3-carene in the presence of an excess of 2-butanol.

			Exp.				[carene] (×10 11 ) (a)	[cyclohexene] (×10 11 ) (a)	[2-butanol] (×10 13 ) (a)	k k	' '	scav reac	(b)	k	i	k	ref
									2-carene
	2CAR-SC				180	430	890			19	3.03 ± 0.21
								230	930	890			10	3.34 ± 0.57
											Average	3.06 ± 0.27
									k = (24.2 ± 2.2) × 10 -17 cm 3 molecule -1 s -1 (d)
	2CAR-5BR				1.6	7.2	10			14	2.83 ± 1.4
									k = (22.4 ± 1.4) × 10 -17 cm 3 molecule -1 s -1 (a)
									3-carene
	3CAR-6BR				2.4	7.2	10			12	0.44 ± 0.01
	3CAR-7BR				7.1	7.2	16			12	0.52 ± 0.09
											Average	0.48 ±0.04
									k = (3.8 ± 0.3) × 10 -17 cm 3 molecule -1 s -1 (a)
	(a) (in units of molecule cm -3 ) .
	(b)	k k	reac ' ' scav		OH k	,2		 00     ,1 0 ,3 OH 2-Butanol cyclohexene OH k carene k 

Table 4 :

 4 Pseudo first order rate coefficients for reaction of ozone with cyclohexene and obtained rate coefficient in comparison with literatures.

Table 5 :

 5 Rate coefficients values obtained in this work and from the literature for the reactions of ozone with 2-and 3-carene.

		3 O k (a)	T (K)	Method	Reference
		24.7 ± 2.5	296 ± 2	AM-FR	This study
		23.9 ± 1.3	293-305	AM-HELIOS	This study
	2-carene	23.2 ± 3.0	296 ± 2	AM-SC	[17]
		24.2 ± 2.2	296 ± 2	RM-SC, Scav. = 2-butanol, Ref. = cyclohexene (b)	This study
				RM-HELIOS,
		22.4 ± 1.4 (f)	293 ± 1	Scav. = 2-butanol,	This study
				Ref. = cyclohexene (b)
		25.2 ± 2.7	296 ± 2	RM, Scav. = cyclohexane, Ref. = α-pinene (c)	[17]
		24 ± 14	298		[10]
		4.9 ± 0.8	293 ± 2	AM-FR	This study
		3.5 ± 0.2	295 ± 1	AM-SC	This study
	3-carene	3.7 ± 0.2	296 ± 3	AM-HELIOS	This study
		12	295 ± 1	AM-FR	[18]
		5.20 ± 0.56	296 ± 2	AM-SC	[17]
				RM-HELIOS,
		3.8 ± 0.3	296 ± 2	Scav. = 2-butanol,	This study
				Ref. = cyclohexene (b)
		4.05 ± 0.43	296 ± 2	RM, Scav. = cyclohexane, Ref. = α-pinene (c)	[17]
		5.60 ± 0.95	295 ± 0.5	RM, Scav. = m-xylene, Ref. = 2-methylbut-2-ene (d)	[19]
		4.8 ± 2.9	298		[10]
	AM=Absolute rate; RM=Relative rate; FR=Flow Reactor; SC=Simulation Chamber.

Acknowledgments

Labex Voltaire (ANR-10-LABX-100-01), Region Centre (France) through Formul'Air project, ANR (13-BS06-0002-01, COGNAC) and the EU-Eurochamp-2 (E2-2013-02-27-0086) projects for support.