Christian Darne

Alexandre Desforges

Nawal Berrada

Caroline Fontana

Yves Guichard

Laurent Gaté

Dominique Bégin

François Le Normand

Fabrice Valsaque

Jaafar Ghanbaja

Jérôme Gleize

Brigitte Vigolo

A non-damaging purification method: decoupling the toxicity of multi-walled carbon nanotubes and their associated metal impurities

Multi walled carbon nanotubes (MWCNTs) are purified by a gas-phase method allowing selective removal of the metallic impurities (Fe and Al catalyst residues) while the MWCNTs remain untouched. Contrary to works using standard purification methods, our approach allows to separately study toxicity due to metallic impurities and that of MWCNTs. Both raw and purified MWCNTs are thoroughly characterized by several techniques including transmission electron microscopy, Raman spectroscopy, thermogravimetric analysis, X-ray photoelectron spectroscopy and adsorption volumetry. The results show that the purification method is efficient and the MWCNT characteristics are well controlled. We study the oxidative stress cell response induced by the MWCNT sample after purification. Cytotoxicity and genotoxicicity are investigated using in vitro micronucleus and comet assays. Our results show that the metallic impurities of the used MWCNTs are not involved in the toxic potential of these CNTs. Consequently, these used CVD-produced MWCNTs alone are responsible for the observed toxic response. This presented approach, applied to other source of CNTs, could be useful for determining the involvement of their metallic impurities in the observed toxic response.

Introduction

Carbon nanotubes (CNTs) are promising materials for a variety of applications in nanotechnology, energy conversion, high performance composites and also in the biomedical field. CNTs have been advantageously used for drug delivery, cancer therapy, diagnostic tools, biosensors or tissue engineering [1][START_REF] Beg | Advancement in carbon nanotubes: basics, biomedical applications and toxicity[END_REF][START_REF] Saito | Carbon nanotubes: biomaterial applications[END_REF] . Even if CNTs are incorporated into devices and materials for current practical uses, the question of their toxicity is still under debate. Researchers have shown that CNTs often provoke a toxic response such as pulmonary inflammation, oxidative stress, granuloma or fibrosis [START_REF] Donaldson | Carbon Nanotubes: A Review of Their Properties in Relation to Pulmonary Toxicology and Workplace Safety[END_REF][START_REF] Ferreira | Nanoparticles, nanotechnology and pulmonary nanotoxicology[END_REF][START_REF] Trout | Medical surveillance, exposure registries, and epidemiologic research for workers exposed to nanomaterials[END_REF][START_REF] Bello | Exposure to nanoscale particles and fibers during machining of hybrid advanced composites containing carbon nanotubes[END_REF][START_REF] Morimoto | Inhalation Toxicity Assessment of Carbon-Based Nanoparticles[END_REF][START_REF] Nowack | Occurrence, behavior and effects of nanoparticles in the environment[END_REF] . However, CNTs are a complex material and among the numerous potential parameters, those responsible for the observed toxicity are difficult to identify and the mechanisms involved are far from clear [START_REF] Lanone | Determinants of carbon nanotube toxicity[END_REF][START_REF] Liu | Understanding the Toxicity of Carbon Nanotubes[END_REF][START_REF] Alshehri | Carbon Nanotubes in Biomedical Applications: Factors, Mechanisms, and Remedies of Toxicity[END_REF][START_REF] Hamilton | Effect of MWCNT size, carboxylation, and purification on in vitro and in vivo toxicity, inflammation and lung pathology[END_REF] . The conflicting results in the literature regarding toxicity induced by exposure to CNTs could be explained by the variety of CNTs that exists and their respective behavior, which is strongly dependent on the chemical treatments to which they are subjected. To reach a greater degree of certainty regarding the human health and environmental risks associated with CNTs, standards of well characterized CNTs for which the parameters can be separately modified have to be established [START_REF] Du | Understanding the toxicity of carbon nanotubes in the environment is crucial to the control of nanomaterials in producing and processing and the assessment of health risk for human: A review[END_REF][START_REF] Firme | Toxicity issues in the application of carbon nanotubes to biological systems[END_REF] . CNTs are produced using different methods leading to diverse structures, morphologies, sizes and variable contents of impurities including carbonaceous and metallic by-products [START_REF] Prasek | Methods for carbon nanotubes synthesisreview[END_REF] . Generally, post-synthesis chemical treatments are needed to overcome processing issues of as-produced CNTs. Surface functionalization of CNTs is an important aspect for biomedical applications of CNTs. Grafting functional groups to the CNT surface is normally used to aid their dispersion or to obtain a specific functionality [START_REF] Bianco | Biomedical applications of functionalised carbon nanotubes[END_REF][START_REF] Gilbertson | Toward Tailored Functional Design of Multi-Walled Carbon Nanotubes (MWNTs): Electrochemical and Antimicrobial Activity Enhancement via Oxidation and Selective Reduction[END_REF] . These chemical treatments, usually conducted using strong acids, are reported to dramatically modify the CNT toxic response. For instance, contamination through hydrochloric, nitric or sulfuric acid treatment (creation of carboxylated CNT fragments or halogenated contaminants) can induce toxic effects [START_REF] Wang | Cytotoxicity Screening of Single-Walled Carbon Nanotubes: Detection and Removal of Cytotoxic Contaminants from Carboxylated Carbon Nanotubes[END_REF][START_REF] Koyama | In vivo immunological toxicity in mice of carbon nanotubes with impurities[END_REF] . Elsewhere, CNT toxicity is often reported to be reduced after functionalization [START_REF] Vardharajula | Functionalized carbon nanotubes: biomedical applications[END_REF][START_REF] Figarol | In vitro toxicity of carbon nanotubes, nano-graphite and carbon black, similar impacts of acid functionalization[END_REF][START_REF] Gilbertson | Toward safer multi-walled carbon nanotube design: Establishing a statistical model that relates surface charge and embryonic zebrafish mortality[END_REF][START_REF] Pasquini | Impact of Surface Functionalization on Bacterial Cytotoxicity of Single-Walled Carbon Nanotubes[END_REF][START_REF] Pasquini | Realizing Comparable Oxidative and Cytotoxic Potential of Single-and Multiwalled Carbon Nanotubes through Annealing[END_REF] . Apart from functionalization, purification is another chemical treatment commonly applied to the CNT samples. Standard purification methods as well involve strong acid treatments which are necessary to eliminate the metallic impurities [START_REF] Makama | Recent Developments in Purification of Single Wall Carbon Nanotubes[END_REF][START_REF] Hou | Purification of carbon nanotubes[END_REF] . In order to use purified CNTs for biomedical research, it is crucial that we study their toxic effects since the metal-based catalysts remaining in the CNT samples have been shown to induce their own effects [START_REF] Wang | Effect of different carbon nanotubes on cadmium toxicity to Daphnia magna: The role of catalyst impurities and adsorption capacity[END_REF][START_REF] Shinde | Toxicity mechanism in fetal lung fibroblast cells for multi-walled carbon nanotubes defined by chemical impurities and dispersibility[END_REF][START_REF] Smart | The biocompatibility of carbon nanotubes[END_REF] . Especially, transition metals are normally used for Chemical Vapor Deposition (CVD) processes which produce most available CNTs. [START_REF] Ge | The contributions of metal impurities and tube structure to the toxicity of carbon nanotube materials[END_REF][START_REF] Kagan | Direct and indirect effects of single walled carbon nanotubes on RAW 264.7 macrophages: Role of iron[END_REF] Multi-walled CNTs (MWCNTs) instead of single-walled (SWCNTs) or double-walled CNTs (DWCNTs) are widely chosen for applications since their cost production is lower. The choice of the studied MWCNT sample was dictated by its similarities with the MWCNT industrial samples which are used in commercial products. Indeed, the CNTs produced in large amount are synthesized by using iron as catalyst deposited on an alumina substrate. The particularity of MWCNT samples is that they contain no carbon impurities leading to 'nonprotecting' metal-based particles contrary to SWCNTs and DWCNTs which also often require higher amount of catalyst content to be synthesized. For CVD-produced MWCNTs, the amount of metal-based impurities is usually around 10 wt.%, as in the chosen MWCNT sample. Previous studies have shown that iron impurities and other kinds of nanoparticles contained in CNT samples can themselves lead to toxic effects [START_REF] Ge | The contributions of metal impurities and tube structure to the toxicity of carbon nanotube materials[END_REF][START_REF] Kagan | Direct and indirect effects of single walled carbon nanotubes on RAW 264.7 macrophages: Role of iron[END_REF][START_REF] Aldieri | The Role of Iron Impurities in the Toxic Effects Exerted by Short Multiwalled Carbon Nanotubes (mwcnt) in Murine Alveolar Macrophages[END_REF] . While other studies claim that the metal-based impurities have no effect on toxicity [34][START_REF] Miralles | Multiwalled carbon nanotubes in alfalfa and wheat: toxicology and uptake[END_REF][START_REF] Barillet | Toxicological consequences of TiO2, SiC nanoparticles and multiwalled carbon nanotubes exposure in several mammalian cell types: an in vitro study[END_REF] . A better understanding of human and environmental risk of CNTs requires to better control the factors that can be responsible for the toxic effects. In this study, we were able to investigate separately the toxic effects of metal-based impurities (Fe and Al) independently from those of the used CVD-produced MWCNTs. Such a study was possible thanks to the in-house development of an original and highly selective purification method [START_REF] Mercier | Selective removal of metal impurities from single walled carbon nanotube samples[END_REF] . To the best of our knowledge, the proposed approach which has allowed to decouple toxicity of CNTs and that of their associated metallic impurities, has not been reported yet. Our chemical treatment, which is based on the use of a gas-phase halogen, efficiently eliminates metallic impurities from CNT samples while allowing both the CNT morphology and their structural quality to be preserved. The MWCNTs were purified by heating the powder in a chlorine atmosphere. The purified MWCNTs were then characterized using several techniques (transmission electron microscopy (TEM), Raman spectroscopy, thermogravimetric analysis (TGA), X-ray photoelectron spectroscopy (XPS) and adsorption volumetry) that showed that their characteristics were particularly well preserved. The cytotoxicity and genotoxicicity of raw and purified MWCNTs were then studied using in vitro micronucleus and comet assays. We also studied the cellular oxidative stress after MWCNT treatment.

Materials and methods

Purification

For the CNT synthesis, alumina (particle size: 40-80 mm) was impregnated with the catalyst precursor (Fe(NO3)3, 9H2O) with a loading rate of 20 wt.% in iron. After water evaporation, the solid material was calcined at 350 °C, and finally reduced in situ under hydrogen flow (100 mL min-1) at 400 °C for 1 h to produce the catalyst. Experimentally, a medium temperature (640 °C), a relatively low C2H6-to-H2 molar ratio (60/40), a flow rate of 100 mL/min and a reaction time of 4 h were found to produce almost exclusively MWCNTs (>98%, determined by statistical image analysis) with a yield of 10 g per gram of catalyst. Hydrogen seems to play an important role in limiting the formation of amorphous carbon impurities along with carbon nanotubes [START_REF] Amadou | Synthesis of a carbon nanotube monolith with controlled macroscopic shape[END_REF] .

Potassium permanganate (KMnO4) was provided by VWR Chemicals and hydrochloric acid (HCl, concentration 37 %) and sulfuric acid (H2SO4, concentration 96 %), sodium chloride (NaCl) were purchased from Sigma Aldrich. The raw MWCNTs (r-MWCNT) were purified using a two-step method described in details elsewhere [START_REF] Desforges | Improvement of carbon nanotube stability by high temperature oxygen/chlorine gas treatment[END_REF] . In brief, the MWCNT powder was first heated under chlorine (150 mL/min in N2 as the carrier gas, total pressure 1atm) for 20 min at 500 °C, 600 °C, 650 °C, 700 °C, 800°C and 1100 °C. Chlorine was formed in situ by oxidation of HCl with KMnO4. For environmental and safety reasons, once the treatment has ended, unreacted chlorine was neutralized in 3 successive vials containing a sodium hydroxide solution (17 wt.%) and decomposed in hypochlorite and chloride ions according to the following chemical reaction:

Cl2 + OH - HOCl + Cl - This phenomenon was confirmed by the presence of a yellow characteristic color in the 2 first vials; the last one being colorless. Added to this neutralization and to ensure that no chlorine was released to the atmosphere, a specific and sensitive test was carefully performed during each purification experiment. This test uses potassium iodide (KI) and it is based on the following oxidation-reduction reaction: 2KI + Cl2 2KCl + I2. Appearance of a brown spot due to rapid formation of iodine eventually revealed any trace of chlorine. After the chlorine-based treatment, a hydrochloric acid (4 N) washing step was performed at room temperature for 2 h. After washing (until the pH reached neutrality), filtration and drying, the purified samples were ready for analysis. The MWCNTs purified at 800°C and later used for toxicity analysis are referred to as p-MWCNT. For the TEM and High Resolution TEM (HRTEM) analyses, a drop of the suspension of MWCNTs dispersed by sonication in ethanol was deposited on a holey carbon grid (200 mesh size) and then examined using a JEOL ARM 200F cold FEG apparatus (operating voltage of 80 kV). Typical images are extracted form a batch of at least 25 images taken at different locations on the TEM grid to guarantee a representative description of the MWCNT sample. Their sizes (diameter and length) were evaluated from a statistical analysis on many TEM images. TGA was carried out with a Setaram Setsys evolution 1750 Thermal Gravimetric Analyser. Temperature was increased from room temperature to 900°C at 5 °C/min under dry air (20 mL/min). Raman spectroscopy characterization was performed using a LabRAM HR 800 micro-Raman spectrometer with an incident wavelength of 632.8 nm at a power of 0.25 mW/µm 2 . To guarantee reproducibility, at least three spectra were recorded on different areas for the same sample. For data analysis, for each sample, the ID/IG intensity ratio was calculated from the maximum height of the D and the G band after subtracting a baseline. XPS measurements were recorded using a monochromatic AlKα source and hemispherical detector VSW (pressure 5.10 -9 mbar). For the experiments, the raw and the purified CNTs powder was mixed with KBr powder and then pressed. The Cl/C atomic ratio was determined from the C1s and Cl2p peaks as described in ref. [START_REF] Desforges | Improvement of carbon nanotube stability by high temperature oxygen/chlorine gas treatment[END_REF] . The estimated precision of Cl/C is 0.1 % for the sample treated at 1100°C. For the sample treated at 800°C, detection of chlorine was difficult because it is close to the detection limit of the apparatus, the precision of the Cl/C ratio is probably higher in that case. Adsorption isotherms at 77.3 K were determined using krypton on both raw and purified MWCNTs. Adsorption on the surface of the metallic particles can be neglected compared to that occurring at the surface of CNTs because their amount is relatively low (maximal value for the raw MWCNTs 14.6 wt. %) compared to that of CNTs and their density is from 2 (alumina) to 4 (iron) times greater than that of the MWCNTs. The isotherms were normalized by the amount of carbon content (from TGA) in the samples.

Toxicity experiments

The MWCNT concentrations are expressed in amount of MWCNTs per culture surface (µg of MWCNT/cm 2 ); this unit offers several advantages when we work with insoluble solid materials like the MWCNTs. Indeed, these latter have high tendency to aggregate and sediment on cell and they are rarely homogenously dispersed in the solution. This metering system allows to take into account only 2 criteria: the cell density (number of cells/unit of culture surface) and the concentration (quantity of material/unit of cell culture surface) regardless of the volume or the support used. For the concentration of 7.5 µg/cm 2 , in ROS and cell viability experiments, to ensure that 7.5 µg of MWCNTs are in contact with 5000 cells, we have used a solution at a concentration of 12.75 mg/L of MWCNTs. A solution of 26.24 mg/L of MWCNTs was used for the comet assay and a solution at 16.5 mg/L of MWCNTs for the micronucleus assay. Due to their high aspect ratio (length to diameter), typical of fibers, the choice of which MWCNT concentrations to study was directed by those used for asbestos when investigating induction of genotoxic effects and cell transformation [START_REF] Darne | In vitro comet and micronucleus assays do not predict morphological transforming effects of silica particles in Syrian Hamster Embryo cells[END_REF] . Cell culture. V79 cells (lung fibroblast from Chinese hamster, ATCC, USA, reference CCL-93) were grown in Dulbecco's MEM (DMEM; Invitrogen, France), supplemented with 10 % fetal calf serum (Dutscher, France) and 0.5 % Penicillin/Streptomycin (5000 U-5000 µg/mL, Invitrogen, France). The cell culture was carried out in a humidified chamber at 37 °C with 10 % CO2, as recommended by the distributor. V79 cells were selected for this study as they are one of the cell models recommended in OECD (Organization of Economic Cooperation and Development) guideline n° 487 for use in the in vitro micronucleus assay. MWCNT dispersions. In order to obtain a homogeneous suspension (estimated visually and from optical microscopy, see supporting information Figure S1), the samples were placed in water supplemented with 0.1 wt. % of bovine serum albumin (BSA) and sonicated, in the cup horn of a 400 W Branson Sonifier S-450D (Branson Ultrasonics Corp, Danbury, CT) containing icecold water, for 7 min at 25 % amplitude in a pulse mode (2s on/1s off). 1/50 of the MWCNT suspensions were then added to the cell culture medium (see below). The V79 cells were treated with the prepared dispersions of the CNT samples with concentrations ranging from 0.47 to 7.50 µg/cm 2 . As the metal content of both the raw and the purified MWCNT samples was already known (by TGA), metal-free MWCNT concentrations can be calculated by subtracting the metal content. The concentration could be expressed by the total MWCNT sample amount or the metal-free MWCNT amount in µg per cm 2 of cell culture surface. Free radical generation. Intracellular localization of reactive oxygen species (ROS) was detected with the 5-(and-6)chloromethyl-2'7'-dichlodihydrofluorescein diacetate fluorescence probe (CM-DCFDA, Molecular Probe, Invitrogen).

DCFDA derivatives detect a variety of ROS, including hydrogen peroxide, peroxyl radicals and peroxynitrite anions [START_REF] Lebel | Evaluation of the Probe 2',7'-Dichlorofluorescin as an Indicator of Reactive Oxygen Species Formation and Oxidative Stress[END_REF] . 1.5x10 3 V79 cells were treated with 0.47 to 7.50 µg/cm 2 of MWCNTs for 24 h in a 96-well plate (six replicate wells per condition). Following the protocol described by Guichard et al. [START_REF] Guichard | Cytotoxicity and Genotoxicity of Nanosized and Microsized Titanium Dioxide and Iron Oxide Particles in Syrian Hamster Embryo Cells[END_REF] , a sample of nano-size anatase titanium dioxide (TiO2) was used as a positive control (see supporting information Figure S2). At the end of the treatment, the wells were washed with PBS and 50 µL of CM-DCFDA was added to give a final concentration of 5 µM. The plate was then incubated at 37 °C for 30 min. Wells were then washed with PBS and the fluorescence was recorded using a microtiter plate reader (Synergy HT, BioTek) with excitation at 485 nm and emission detection at 530 nm. ROS induction was expressed by the fold change in the measured fluorescence intensity of treated cells relative to the control (cell culture without MWCNTs). Data were expressed as the average of the means ± SEM (standard error). Experiments were repeated three times. Cell viability. Cells (1.5 x10 3 cells/well) were seeded in 48 wells of a 96-well plate for 24 h. The cell cultures were then treated for 24 h in the culture medium without (control) or with MWCNT suspensions at concentrations ranging from 0.47 to 7.5 µg/cm 2 of the cell culture surface (six replicate wells per condition). The remaining 48 wells received the same CNTs suspensions but were not seeded with cells in order to check for possible interactions between formazan reagent and CNTs, at it has been described 40, even if this has not been demonstrated for the WST-1 (Water soluble Tetrazolium, Roche Diagnostics, France) reagent that we used. After treatment, 1/10 (v/v) WST-1 reagent (see also supporting information Figure S3) was added to each well for 3h. The plates were then centrifuged at 4500 rpm for 5 min to eliminate the majority of CNTs and thus avoid interference of the CNTs with the reading. The supernatant was transferred to new 96-well plates and optical density (OD) was recorded at 450 nm and 690 nm with a microtiter plate reader (Synergy HT, BioTek, France). The delta OD (OD450 nm-OD 690 nm) was then calculated. At least three independent experiments were conducted for each condition. In our experiments, the optic density has not significantly decreased in the wells without cells. Genotoxicity. Two types of assay were used to evaluate the genotoxicity of CNTs in V79 cells: the comet assay and the micronucleus assay. Comet assay. The comet assay is a sensitive technique for the detection of DNA damage in eukaryotic cells to identify both single and double strand breaks in alkaline condition (pH>13). The formamidopyrimidine glycosylase (FPG)-modified comet assay was used to evaluate this oxidative DNA damage. The FPG enzyme, a glycosylase, identifies and specifically cuts modified bases such as 8-oxoguanine from DNA, producing apurinic sites that are converted into strand breaks by the associated APendonuclease activity. Therefore, DNA strand breaks detected by the FPG modified comet assay therefore provide a measure of oxidative DNA damage [START_REF] Azqueta | Enhancing the sensitivity of the comet assay as a genotoxicity test, by combining it with bacterial repair enzyme FPG[END_REF] . We followed the procedure from Collins et al. [START_REF] Collins | Serum carotenoids and oxidative DNA damage in human lymphocytes[END_REF] , with minor modifications. In brief, two duplicate comet slides were made for each treatment. One slide was treated with FPG and the other one with the FPG buffer only. The two slides were subsequently treated in a same manner. V79 cells (1x10 5 cells/well) cells were treated for 24 h with the MWCNT samples at concentrations ranging from 0.47 to 7.50 µg/cm2, or with methylmethane sulfonate (MMS, Sigma-Aldrich, France) at 0.25 mM as a positive control, or with the medium alone. Approximately 20,000 cells were mixed in 600 µl of 1 % low melting agarose (LMA, Sigma Aldrich, France) and the mixture was transferred onto a slide pre-coated with normal melting agarose (NMA 1 %, Sigma Aldrich, France). Slides were then immersed in lysis solution (NaCl 2.5 M, Na2EDTA 100 mM, Tris 10 mM with 1 % Triton X-100 and 10 % of fresh DMSO) and kept in the dark for 1 h at 4 °C. The slides were next drained and incubated in the dark for 30 min at 37 °C, in either an enzyme buffer alone or in an FPG (5 U/mL) in enzyme buffer (HEPES 40 mM, KCl 0.1 M, Na2EDTA 0.5 mM, pH 8). The slides were immersed in a cold alkaline solution (NaOH 300 mM, Na2EDTA 1 mM, pH 13) for 20 min. Electrophoresis was then performed in the same buffer at 0.7 V/cm for 40 min to allow the fragments of damaged DNA to migrate towards the anode. The slides were then washed with Tris-HCl 0.4 M for 15 min and stained with propidium iodide (2.5 µg/mL). Slides were examined at 200X magnification under a fluorescence microscope. Images of 100 randomly selected comets were acquired and analysed for each sample (Comet assay IV, Perceptive Instruments, UK) in order to evaluate the % tail DNA used as a measure of DNA damage. The presence of MWCNTs did not interfere with the reading at the concentrations tested. Each experiment was repeated three times independently. In V79 cells, the mean values of the median ± SEM obtained for the positive control (0.25 mM MMS) were 7.4 ± 1.1 and 69.2 ± 2.9, respectively, after 24 h of treatment with or without FPG, respectively. Micronucleus test. V79 cells (2.5x10 4 ) were seeded in Labtek® slides (Nunc A/S, Denmark). After 24 h, the cells were treated with either MWCNTs at concentrations ranging from 0.47 to 7.50 µg/cm 2 or with positive control (0.25 mM MMS), or with medium alone for 24 h (V79 cell doubling time: 14-18 hours). At the end of the treatment, cells were washed with PBS (phosphate buffer saline, Invitrogen, France) and fixed in methanol for 15 min. Slides were washed in PBS, drained and received one droplet of ProLong Gold antifade reagent® with DAPI (Molecular Probe, Invitrogen, France). About 2000 cells were analyzed for the presence of micronuclei (MN) at each concentration. The presence of CNTs did not interfere with the reading. Each assay was repeated three times. Cell proliferation/division was assessed by analysis of the mitotic index (% of mitotic cells, see supporting information Figure S4). Statistics. Results are expressed as means ± SEM (standard error of the mean) from three independent experiments (and six replicates in each). A logarithmic transformation was applied to the biological data. For each assay and for each CNT solution, independently, a mixed linear regression model was applied first to judge the concentration effect, followed by a post hoc test (with Bonferroni correction) to assess the difference between control and concentrations. A second mixed linear model was also applied to measure simultaneously the doseeffect response of both raw and purified CNTs. These two models included a random "experiment" effect to take into account the variability between experiments. Statistical analyses were performed using Stata 14.0 software. The statistical significance threshold was set at 5 %.

Results

Purification of carbon nanotubes

The morphological characteristics of the raw MWCNTs (r-MWCNT) have been determined from TEM analysis. The used MWCNTs have no more than 10 walls and are quite flexible (Figure 2). Their diameter is between 10 and 80 nm and their length varies from several µm to several tens of µm. These MWCNT characteristics were not modified after the purification treatment. The used MWCNTs contain small amount of carbon impurities and in agreement with the synthesis method (see experimental section). From TGA, the metal-based impurity content of r-MWCNT was approximately 14.60 wt. %. These impurities come from the alumina support and iron. From the elemental analysis, the raw MWCNT sample contains 5.0 wt. % of Al and 2.6 wt. % of Fe in agreement with the metal oxide (Fe2O3 and Al2O3) content found by TGA.

The raw MWCNTs (r-MWCNT) were treated with the homedeveloped chlorine-based purification method in order to remove the metallic impurities. Optimization of the purification was achieved by especially varying the temperature of the chlorine treatment. Good control of the impurity content in the CNT samples could be obtained as shown in Figure 1. The purification yield Y is defined as: 100 where and are the metallic content (wt.%) of the purified sample (p-MWCNT) and the raw sample (r-MWCNT) determined by TGA, respectively. At 800°C and above, a metallic impurity content as low as 1.52 wt. % was reached. The purification yield was then about 90 %. Since the MWCNT sample contained a negligible part of carbonaceous impurities (from TEM observations), the raw sample contained 85.40 wt.% of MWCNTs and the purified sample contained 98.48 wt.% of MWCNTs, the rest of the sample being the mineral impurities. In the samples purified at temperatures of 800°C and higher, the remaining metallic impurities were certainly well-protected by a carbon covering (Figure 2a) and inaccessible to chlorine, which prevented their removal. Such impurities, barely observable by TEM, might be inaccessible and would therefore not react with the cells in vitro. In the purified samples (Figure 2b), the MWCNTs did not appear to have been damaged qualitatively; a careful TEM observation of their walls did not reveal any significant increase in the amount of defects. These observations are consistent with the results from Raman spectroscopy (Figure 3). No increase in ID/IG ratios was observed after purification over the whole temperature range investigated. The atomic Cl/C ratio determined by XPS were below 0.1 and around 1.3 % respectively for the MWCNTs purified at 800°C and 1100°C. The chlorine content is therefore quite low for both samples. Standard adsorption volumetry, carried out by using nitrogen as the adsorbent, was used to determine specific surface areas. The well-known BET (Brunauer-Emmett-Teller) method yielded values of 150-160 m 2 /g for both raw [START_REF] Amadou | Synthesis of a carbon nanotube monolith with controlled macroscopic shape[END_REF] and purified MWCNT samples. Further investigations, by using Kr as the adsorbent on p-MWCNT, revealed the presence of uniform surfaces meaning that, after purification, the MWCNTs had a good structural quality. The steps in the Kr isotherms (see supporting information, Figure S5) may be assigned to clean and regular surfaces as adsorption sites have similar adsorption energies for each adsorbed gas layer. When the shape of an isotherm shows one or more steps, the sample surface onto which adsorption occurs has uniform parts [START_REF] Thomy | Two-Dimensional Phase Transitions as Displayed by Adsorption Isotherms[END_REF] . This result is in agreement with the Raman spectroscopy demonstrating that no defects were introduced through application of the purification treatment. For the following part of the work, we study the toxicity effects using the MWCNT sample purified at 800°C.This sample was selected as it did not present any morphological, chemical or structural modifications after purification.

Toxicity

The concentrations used in the prepared dispersions are within the same range as those previously used in our laboratory for toxicity studies on asbestos fibres [START_REF] Darne | In vitro comet and micronucleus assays do not predict morphological transforming effects of silica particles in Syrian Hamster Embryo cells[END_REF] . Here, we have investigated the toxic response of the raw and the purified MWNTs by considering the real carbon nanotubes content. Intracellular ROS detection was performed after exposure to raw and purified MWCNTs. Figure 4 shows the recorded relative fluorescence intensity plotted as a function of the sample concentration (Fig. 4a). In Figure 4b, the MWCNT contents of raw and purified samples were recalculated by subtracting their respective metallic content (as determined by TGA). Both samples were able to induce a ROS production which, as expected, became more significant when sample concentration increased. Results from Figure 4a suggest that p-MWCNT was more reactive than r-MWCNT since the two curves differ significantly (p=0.045). When the ROS production is plotted as a function of the concentration of only the MWCNTs, i.e. without any impurities (Fig. 4b), both MWCNT samples show a similar effect and the curves do not differ significantly. The fit in Figure 4b was derived from the data recorded for the two samples and the reliability factor of 0.86 is satisfactory. Cell viability as the percentage of the control value after 24 h of treatment with r-MWCNT and p-MWCNT is shown as a function of the CNT concentration in Figure 5. The observed decreases in cell viability are dose-dependent and the maximum decreases are 26.4 % and 26.2 % for r-MWCNT and p-MWCNT respectively at a CNT sample concentration of 7.5 µg/cm 2 (Figure 5a). As shown in Figure 5b, variation in cell viability as a function of the metal-free MWCNT concentration can be satisfactorily described the same behaviour (data fit reliability 0.86).

Genotoxicity is an important aspect of cellular toxicity since it can lead mutagenesis or apoptosis of the cells, potentially jeopardizing their expansion and resulting in cancer. In this work both comet and micronucleus (MN) assays, two reliable methods described in ref. [START_REF] Thomy | Two-Dimensional Phase Transitions as Displayed by Adsorption Isotherms[END_REF] have been performed to study the genotoxicity effects of MWCNTs before and after purification. The results of the comet assay are expressed as the percentage of tail DNA for cells exposed to the two samples (r-MWCNT and p-MWCNT) with and without the addition of the enzyme (FPG) (Figures 6a and6b, respectively). Taking into account the measurement error, the comet assay yielded roughly the same results with both MWCNT samples. No significant level of DNA damage was induced by the (raw or purified) MWCNTs themselves with or without FPG. As expected, treatment with FPG led to an increase in the response but without any significant difference from the control, which also presented a higher tail DNA value. As FPG is a bacterial repair enzyme that recognizes and cuts certain modified bases, some base changes not induced by the test compound will also be detected and will generate nonspecific breaks that can be visualized by an increase of the level of breakage in the negative control. Induction of MN in the V79 cells was assessed after 24 h of treatment with raw and purified MWCNTs (Figure 7). For both samples, a significant increase in the number of micronucleated cells is detected, meaning that the MWCNTs show similar genotoxic effects without any influence of the purification treatment.

Discussion

Contrary to other commonly studied particles (asbestos fibres and metallic oxide particles), the non-carbon impurities present in the CNT samples lead to biased results particularly for the comparison between non-purified and purified CNT samples toxicity. Especially, since some CNT samples can contain several tens of weight percent of non-carbon impurities, studying toxicity effects induced by CNTs implies to carefully separate as much as possible the CNT response from that of their impurities. Nevertheless, this aspect is seldom considered even if it directly impacts the dose-effect recorded and its comparison between CNT samples especially for purification investigations.

Purification treatment: a gentle non-destructive method

Thanks to the purification method that we applied, metal-based impurity particles could be removed from the MWCNT sample while preserving the physical and chemical characteristics of the starting MWCNTs. Raman spectroscopy performed on the samples clearly showed that the D/G ratio did not increase after purification, which means that neither significant CNT damage nor functionalization has occurred by the chlorine-based treatment in agreement with HRTEM images (see supporting information Figure S6). However, as MWCNTs are not highly functionalized Raman spectroscopy might not be sensitive enough to detect any modification in the structure of these samples. Complementary techniques that are more sensitive to MWCNT surface modifications, such as XPS and adsorption volumetry (to date rarely investigated), are required to deeply investigate the state of the MWCNTs, especially after any chemical treatment. Results from XPS showed that p-MWCNT contains a very low Cl content (around 0.1 atomic %).

Metal-based impurities

The raw MWCNT sample was easily purified at a temperature that is quite low compared to temperatures required for the same purification method for other CNT samples whose metal impurities are known to be quite well protected by carbonaceous shells. For arc discharge as-produced single walled carbon nanotubes (SWCNTs), chlorine-based purification conducted at 950°C for 2 h leads to a purification yield of metallic impurities of 65.2 % 39 . Under the same conditions, SWCNTs produced by the chemical vapor deposition (CVD) HiPco process, where the carbon layer covering the metallic particles is known to be thinner, the purification yield reached 87.5 % 37 . The purification yield for double walled carbon nanotubes (DWCNTs) whose impurities are embedded in large carbonaceous particles, was as low as 67 % under the same experimental conditions [START_REF] Desforges | Dramatic enhancement of double-walled carbon nanotube quality through a one-pot tunable purification method[END_REF] . The accessibility of the metallic particles is the main limiting factor to remove them by any chemical treatment. In this work, according to the purification conducted on the MWCNTs, any metallic impurity particles that were not or were only poorly) protected are probably removed from the sample. The negligible amounts of catalyst residues are probably highly protected by carbon layers, and, thus any metallic remaining particles would certainly not interact with cellular material.

Toxic effects

As CNTs are particles with at least one dimension of less than 100 nm [START_REF] Tran | A hypothetical model for predicting the toxicity of high aspect ratio nanoparticles (HARN)[END_REF] , they are classified as High Aspect Ratio Nanomaterials (HARN). Since CNTs can be considered like fibers, their potential adverse effect is an important question which has drawn attention of researchers. Particle and fibre toxicity is often related to the capacity of these materials to induce oxidative stress in cells [START_REF] Fu | Mechanisms of nanotoxicity: Generation of reactive oxygen species[END_REF] . The presence of CNTs, near or inside cells, may lead to ROS production and to an overloading of the cell antioxidant defense system. This phenomenon can induce toxic effects such as alteration of DNA (genotoxic effects) which can ultimately lead to tumor development.

To take into account the question of the toxicity and carcinogenic potential of CNTs, we analyzed the ability of MWCNTs to induce cell cytotoxicity, oxidative stress and genotoxic effects. Added to residual metal catalyst, the other reported parameters which can induce toxic effects are length, rigidity and surface functionalization. Moreover, the observed results also depend on the cell system used. As already discussed, the advantage of the used purification method is that it does not induce any morphological (length) and functionalization of the MWCNTs. Regarding rigidity, this parameter is rarely discussed for in vitro tests. In the works from Palomäki et al. [START_REF] Palomaki | A secretomics analysis reveals major differences in the macrophage responses towards different types of carbon nanotubes[END_REF][START_REF] Palomaki | Long, Needle-like Carbon Nanotubes and Asbestos Activate the NLRP3 Inflammasome through a Similar Mechanism[END_REF] macrophages were treated with both types ("long rigid" and "long tangled") MWCNTs. Higher secretion of interleukin 1-family cytokines was observed for needle-like MWCNTs. Catalan et al. have shown that straight CNTs can be more toxic than flexible CNTs above 50 µg/cm 2 . [START_REF] Catalan | In vitro and in vivo genotoxic effects of straight versus tangled multi-walled carbon nanotubes[END_REF] However, the toxicity induced by flexible CNTs including MWCNTs is as well non negligible. To give an overview of the reported in vitro CNT cytotoxicity, Table 1 gathers some examples of toxicity (cell viability) of many kinds of CNTs. From Table 1, CNT toxicity strongly depends on cellular system used in vitro; for a same CNT sample, in vitro toxicity can be different (see for example NM-403, refs. [START_REF] Jackson | Characterization of Genotoxic Response to 15 Multiwalled Carbon Nanotubes with Variable Physicochemical Properties Including Surface Functionalizations in the FE1-Muta(TM) Mouse Lung Epithelial Cell Line[END_REF][START_REF] Nahle | Single wall and multiwall carbon nanotubes induce different toxicological responses in rat alveolar macrophages[END_REF] ). Among the studied MWCNT samples, our MWCNTs show a significant toxicity. Reactive oxygen species and cell viability. It has been reported that both raw and purified CNTs are able to induce ROS production in V79 cells. The measured stress intensity has been shown to depend on the cell type, with raw MWCNTs inducing an ROS level in V79 cells [START_REF] Darne | Cytotoxicity and Genotoxicity of Panel of Singleand Multiwalled Carbon Nanotubes[END_REF] (also used in this study) similar to that observed here. In the present study, the CNT purification treatment had no effect on cell ROS production (Fig. 4b). This result could be an indication that neither the structure nor the surface of CNTs were modified by the purification method, a conclusion we also drew from the multi-technique characterization we performed. The value of the observed ROS level is difficult to compare to other works since results previously reported are mostly expressed in terms of the mass of the whole nanomaterial sample (i.e including both impurities and CNTs). However, Kagan et al. and Zhou et al, did not notice any difference between raw-and purified SWCNT whereas Pulskamp et al. observed ROS production for raw SWCNTs and the absence of ROS in purified SWCNTs [START_REF] Kagan | Direct and indirect effects of single walled carbon nanotubes on RAW 264.7 macrophages: Role of iron[END_REF][START_REF] Zhou | Multi-walled carbon nanotubes: A cytotoxicity study in relation to functionalization, dose and dispersion[END_REF][START_REF] Pulskamp | Carbon nanotubes show no sign of acute toxicity but induce intracellular reactive oxygen species in dependence on contaminants[END_REF] . These conflicting results that the method used for the CNT purification is determinant since it could in some cases induce CNT surface modifications such as surface functionalization which is known to reduce CNT reactivity [START_REF] Visalli | Toxicological assessment of multi-walled carbon nanotubes on A549 human lung epithelial cells[END_REF] . We have shown that both raw and purified CNTs induce a decrease of cell viability with a similar trend and magnitude (Fig. 5). Our results clearly indicate that cytotoxicity from CNTs is not modified by the purification treatment, and in agreement with other works, that contaminants do not seem to be the main factor explaining CNT toxicity 13,58,59 . In a previous study, similar toxicity study was conducted on a MWCNT sample synthesized by the same method (by Dr. D. Bégin's group). The two MWCNT samples are flexible, they have similar length and diameter, the catalyst nature is also the same, only the catalyst respective content is slightly different. Fe content is of 2.6 and 4.2 wt.% and Al content is of 5 and 7.2 wt.% for the MWCNTs used in this work and the sample used in the work by Darne et al. [START_REF] Darne | Cytotoxicity and Genotoxicity of Panel of Singleand Multiwalled Carbon Nanotubes[END_REF] In that study, MWCNT sample was purified by a standard purification method consisting in a 2-step treatment [START_REF] Gulino | C2H6 as an active carbon source for a large scale synthesis of carbon nanotubes by chemical vapour deposition[END_REF] . The as-produced raw MWCNT powder was first treated with KOH (1 M) at 80°C in order to remove the alumina support. The resulting material was washed several times with distilled water and then treated with a solution of HNO3 (4 M) at 110°C under reflux during 2 h in order to remove the remaining iron particles. The cell viability response had revealed that these purified MWCNTs had a greater toxicity than the raw MWCNTs while in the present study, the response is roughly the same for CNTs before and after the applied purification treatment [START_REF] Darne | Cytotoxicity and Genotoxicity of Panel of Singleand Multiwalled Carbon Nanotubes[END_REF] . This result could be related to the preservation of the CNT walls [START_REF] Requardt | Surface defects reduce carbon nanotube toxicity in vitro[END_REF] through the applied chlorine-based purification method contrary to the standard ones which usually induce chemical and/or morphological modifications through the harsh conditions used for the purification treatment. Carbon nanotube genotoxicity. Finally, we have evaluated the genotoxic effect by the CNTs trough two complementary in vitro tests: the comet assay and the micronucleus assay. The comet assay has been validated as a sensitive method for quantifying DNA strand breaks and evaluating the genotoxic potential of xenobiotics [START_REF] Lee | The use of the single cell gel electrophoresis assay in detecting DNA single strand breaks in lung cells in vitro[END_REF] . The comet assay is a sensitive test for detecting ability of chemicals to generate single-strand and/or doublestrand breaks of DNA [START_REF] Leroy | Evaluation of three methods for the detection of DNA single-strand breaks in human lymphocytes: Alkaline elution, nick translation, and single-cell gel electrophoresis[END_REF] ; here, it modified by using an enzymatic treatment in order to selectively detect DNA damaged by base modification [START_REF] Karlsson | Can the comet assay be used reliably to detect nanoparticleinduced genotoxicity?[END_REF][START_REF] Collins | Drug Safety Evaluation: Methods and Protocols[END_REF] . The in vitro micronucleus assay assesses, in interphasic cells, appearance of micronuclei formed by chromosome breakage events (clastogenic effects) or chromosome losses (aneugenic effects) during nuclear division [START_REF] Fenech | The in vitro micronucleus technique[END_REF] . In agreement with a previous study [START_REF] Darne | Cytotoxicity and Genotoxicity of Panel of Singleand Multiwalled Carbon Nanotubes[END_REF] , for V79 cells, we found that neither raw nor purified MWCNTs induced significant DNA breakage or FPG-sensitive base modification in V79 cells in the comet assay we performed. After 24h of exposure, Cavallo et al. observed similar results in the A549 cells [START_REF] Cavallo | Multi-walled carbon nanotubes induce cytotoxicity and genotoxicity in human lung epithelial cells[END_REF] . Moreover, in the micronucleus assay we performed, CNTs were able to induce some chromosomal disorders. No difference was observed between raw and purified material confirming that the toxicity and the genotoxicity of the CNTs are probably due to the CNT themselves. Sargent et al. studied and also reported this effect in their works and they claimed that "The similarity of carbon nanotubes to microtubules suggests a potential to interact with cellular biomolecules, such as the mitotic spindle" [START_REF] Sargent | Potential pulmonary effects of engineered carbon nanotubes: in vitro genotoxic effects[END_REF] . Such interactions can induce mitotic spindle modifications that lead to micronucleus formation as observed in our work.

Conclusions

In this work, we were able to study the cytotoxic and genotoxic effects of a MWCNT sample by discriminating between the effects of metallic impurities and those of the MWCNTs. Our findings are important since this type of investigation is typically difficult to conduct as physical and chemical characteristics of CNTs are usually modified by the standard purification treatments. However, we have shown that when using our gentle gas phase purification method, the structure and morphology of MWCNTs are not modified. We have shown that Fe and/or Al do not play any role in the in vitro cytotoxicity or genotoxicity of the used MWCNT sample. This approach could be applied to other kinds of CNTs to investigate their own toxic response. However, this study shows that CNTs can induce significant toxic responses, which reinforces the precautionary principle in CNT handling.

Figure 1 .

 1 Figure 1. Impurity content measured by TGA in the samples before and after purification and the corresponding purification yield.

Figure 2 .

 2 Figure 2. Typical TEM bright field micrographs of (a) the raw MWCNT sample and (b) the MWCNT sample purified at 800°C.

Figure 3 .

 3 Figure 3. ID/IG ratios from Raman spectroscopy for the raw (black triangle) and purified MWCNT samples (red square).

Figure 4 .

 4 Figure 4. ROS production after 24 h of treatment of V79 cells with r-MWCNT (black square) and p-MWCNT (red triangle). a): ROS production as a function of the MWCNT sample concentration (including the metal-based impurities) and b): as a function of the MWCNT concentration alone (excluding metal-based impurities). *statistically significant compared to control (p < 5 %).

Figure 5 .

 5 Figure 5. Percentage of V79 cells after 24 h of treatment with r-MWCNT and p-MWCNT. a) without and b) with normalization of the sample concentration to the MWCNTs. *statistically significant decrease in cell number compared to the control (p < 5%).

Figure 6 .

 6 Figure 6. Comet assay after 24 h of treatment in V79 cells. Percentage of DNA in tail as a function of metal-free r-MWCNT or p-MWCNT concentration without (a) and with FPG (b).

Figure 7 .

 7 Figure 7. Micronucleated V79 cells after 24 h of treatment (~1.7 cell-division cycles for V79 cells) as a function of metal-free raw and purified MWCNT concentration. *statistically significant decrease in cell number compared to control (p < 5 %).

Table 1 .

 1 Comparison of cell viability for different types of CNTs and for the MWCNT sample used in this work. The used cell system and the treatment conditions are also recalled.

	Ref.	CNT type	Catalyst nature and content (% wt.)	Cell type	Viab./Cytotox. assay	Treat. time (h)	Concentration range	Concentration for which cell toxicity > 25 %
	this work	r-MWCNT p-MWCNT	5 Al, 2.6 Fe 1.52 Fe	V79	WST-1	24 24	0.47 -7.5 µg/cm 2 (0.8 -12.75 µg/mL)	7.5 µg/cm 2 (12.75 µg/mL) 7.5 µg/cm 2 (12.75 µg/mL)
	62	MWCNT	Fe	Hek	Neutral Red	24	0.1 -0.4 µg/mL	0.4 µg/mL
		SWCNT	90 C	Alveolar	MTT	6	1.41 -28.25	1.41 µg/cm 2
	63	MWCNT	0.6 Ni	macrophages			µg/cm 2	none
				(Guinea Pig)			1.41 -22.6 µg/cm 2
	64	MWCNT	>95 C	Human T lymphocytes	Trypan blue exclusion	24 40 and 400 µg/mL	none
		SWCNT	2.8 Co, 4.2 Mo					62.5 µg/cm 2 (100 µg/mL)
	56	SWCNT MWCNT	1.3 Co, 1.2 Ni 99.8 C	NR8383	WST-1	24	3.1 -62.5 µg/cm 2 (5 -100 µg/mL)	none none
		MWCNT	1.86 Fe, 0.55 Mo					none
	65	SWCNT	HiPco, 10 Fe	A549	Alamar Blue MTT	24 24	3.125 -800 µg/mL	400 µg/mL 800 µg/mL
					Commasie Blue	24		800 µg/mL
	66	MWCNT	98 C	RLE Rat lung epith.	MTT	24	10 -150 µg/mL	50 µg/mL
				cells
	67	MWCNT	0.18 Fe	A549 BEAS-2B	WST-1	72	25-200 µg/mL	200 µg/mL 200 µg/mL
	68	MWCNT	0.19 Fe, 0.14 S, 0.07 Co, 0.03 Al	RAW 264.7 A549	MTT	24	2.5 -100 µg/mL	25 µg/mL 25 µg/mL
	69	MWCNT-1 MWCNT-2	99 C 99 C	C6 rat glioma cells	MTT	24	25 -400 µg/mL	400 µg/mL none
	31	SWCNT SWCNT	1.1 Cr, 0.7 Fe, 0.3 Mo 9.3 Fe, 4.8 Co, 1.2 Mo	A549	Cell counting kit-8 (Formazan)	24	10 -100 µg/mL	90 µg/mL 20 µg/mL
		MWCNT	Narrow short (NS) 1.19 Ni, 0.85 Fe	THP-1				none
			NS purified (NSp)					none
			Large short (WS) 0.51 Fe, 0.47 Ni					50 µg/mL (15.62 µg/cm 2 )
	13		WS purified (WSp) 0.4 Ni Narrow long (NL) 0.82 Ni NL purified (NLp) 0.46 Ni		Cell titer assay (MTS, Formazan)	24	5 -50 µg/mL (0.32 -15.62 µg/cm 2 )	none none none
			NS, NSp, WS, WSp, NL, NLp	Mice alveolar				none
				macrophages
	70	SWCNT	>60 C, 0.4 Co, 0.15 Mo	A549	N.A.	24	1 -50 µg/mL	50 µg/mL

Table 1 (

 1 continued). Cell viability after treatment with CNTs of different types in comparison with this work. The used cell system and the treatment conditions are also recalled. /cm 2 (25 µg/mL) 113.2 µg/cm 2 (200 µg/mL) 113.2 µg/cm 2 (200 µg/mL) 7.1 µg/cm 2 (12.5 µg/mL) 28.3 µg/cm 2 (50 µg/mL) none 113.2 µg/cm 2 (200 µg/mL) cm 2 of NP specific surface/cm 2 of culture; ** converted concentration in µg/cm[START_REF] Beg | Advancement in carbon nanotubes: basics, biomedical applications and toxicity[END_REF]

	Ref.	CNT type	Catalyst nature and content (% wt.)	Cell type	Viab./Cytotox. assay	Treat. time (h)	Concentration range	Concentration for which cell toxicity > 25 %
	71	MWCNT	purified	BEAS-2B	WST-1	24	24 µg/cm 2	none
		SWCNT MWCNT-8	>90 C >95 C -D:8 nm	V79				none 200 µg/mL
	72	MWCNT-20 MWCNT-50	>95 C -D:20 nm >95 C -D:50 nm		Cell titer assay (MTS, Formazan)	24	50 -200 µg/mL	none none
		SWCNT MWCNT-8	>90 C >95 C -D:8 nm	A549				none none

*

N. Sinha and J. T. W. Yeow, Carbon nanotubes for biomedical applications, IEEE Trans. Nanobiosci.,

2005, 4, 180-195.

Acknowledgements

The authors are grateful to Mrs. L. Marpeaux for technical help and Mrs. A. Remy for the statistical analyses at INRS. The authors thank L. Aranda and P. Franchetti for their valuable help for TGA and Raman spectroscopy, respectively. Mrs. P. Duthuit is thanked for her help for the sample preparation.

Notes and references

Conflicts of interest

There are no conflicts to declare.


Yann Busnel
email: yann.busnel@imt-atlantique.fr

Noël Gillet
email: noel.gillet@imt-atlantique.fr

A Cost-effective and Lightweight Membership Assessment for Large-scale Data Stream

Keywords: data stream, membership query, bloom filter

The membership primitive is a classic and fundamental problem in many use cases. In networking for instance, it is useful to check if a given IP address belongs to a black list or not, in order to allow access to a given server. This has also become a key issue in very large-scale distributed systems, or in massive databases. Formally, from a subset belonging to a very large universe, the problem consists in answering the question "Given any element of the universe, does it belong to a given subset?". Since the access of a perfect oracle answering the question is commonly admitted to be very costly, it is necessary to provide efficient and inexpensive techniques in the context where the elements arrive continuously in a data stream (for example, in network metrology, log analysis, continuous queries in massive databases, etc.). In this paper, we propose a simple but efficient solution to answer membership queries based on a couple of Bloom filters. In a nutshell, the idea is to contact the oracle only if an item is seen for the first time. We use a classical bloom filter to remember an item occurrence. For the next occurrences, we answer the membership query using a second bloom filter, which is dynamically populated only when the database is queried. We provide theoretical bounds on the false positive and negative probabilities and we illustrate through extensive simulations the efficiency of our solution, in comparison with standard solutions such as a classic bloom filter.

I. INTRODUCTION

A basic but fundamental task in computer science is to decide efficiently if a given element belongs to a set or not. In network monitoring for instance, the set can represent a blacklist of IP addresses that are forbidden to access a given server. In real systems, it is required to be able to test the authorization with the lowest delay. In medical informatics, the detection of unknown adverse drug effects (ADE) from electronic health records can be done by checking if a given ADE belong to an existing database of known ADEs. The dynamic aspect of the health data production requires the use of efficient monitoring solutions.

More generally, we want to be able to test the membership to a given set B of items received as a stream. We consider that we have access to an oracle O B , which is able to answer any membership query in an exact manner. An easy solution consists in querying O B for each item of the stream. However, querying O B is typically very costly and resource consuming, This work was partially funded by the French ANR project INSHARE (ANR-15-CE19-0024).

because it is stored remotely or it is a very large database, implying a high latency.

To reduce the querying cost, a classic static solution is to summarize this set beforehand, and to query the perfect oracle only in cases where the summary is not precise enough. The use of a Bloom filter [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF] is a well-known solution to compactly represent a set of items. Without going into details, the idea of a bloom filter is to map every item of B to several locations in a bit array using hash functions. Deciding if a given item belongs to B is done by checking if the corresponding bits in the array are set to 1. A recent survey on bloom filters and their many variations can be found in [START_REF] Tarkoma | Theory and practice of bloom filters for distributed systems[END_REF]. Despite a negative answer gives the guarantee that u i ∈ B, there is a non-zero probability that the Bloom filter answers positively for u i ∈ B, leading to a false positive. If we want to avoid such false positive, we can query O B only if a positive answer occurs, instead of accessing it for each item.

However, such simple approach presents several drawbacks: (1) the communication cost remains important [START_REF] Tarkoma | Theory and practice of bloom filters for distributed systems[END_REF] we must load the whole database beforehand, even if only a subset of B appears in the stream. This could lead to a waste of memory in case of a large database.

A lot of efforts has been done to propose solutions that minimize the false positive probability, that is the probability that an item u ∈ B is considered as belonging to B. For example, several works propose to introduce false negative to reduce the false positive probability [START_REF] Donnet | Retouched bloom filters: allowing networked applications to trade off selected false positives against false negatives[END_REF], [START_REF] Laufer | A generalized bloom filter to secure distributed network applications[END_REF], but they also require to load B entirely. Existing works propose filters that deal with dynamic sets [START_REF] Guo | The dynamic bloom filters[END_REF] and can be use to represent only the items in B seen so far in the stream. However such a naive solution leads to a high communication cost since we have to check for each received item which is not in the filter if it belongs to B or not. a) Contributions: In this paper, we propose an approximate oracle which guarantees a very low false positive probability while keeping a low memory consumption. The idea is to dynamically add discovered items in B to our oracle, avoiding the need to load the whole set. This is done by querying the oracle only if an item is seen for the first time. This idea is especially interesting when the number of distinct items is low.

Unhappily, our solution as in [START_REF] Donnet | Retouched bloom filters: allowing networked applications to trade off selected false positives against false negatives[END_REF], [START_REF] Laufer | A generalized bloom filter to secure distributed network applications[END_REF] may produce false negatives, that is items that belong to B for which the oracle answers negatively. The false negative probability can be parametrized as a trade-off with the false positive probability. However, having no false negative is not a strong requirement in many use cases. In ADE detection use case for instance, a false negative item will imply the monitoring of an already known ADE and thus a small waste of resources. However a false positive item corresponds to an unknown ADE, with a potential sanitary risk, and we definitively want to avoid such error. Other applications in which reducing the number of false positives while introducing false negatives is beneficial are presented in [START_REF] Donnet | Retouched bloom filters: allowing networked applications to trade off selected false positives against false negatives[END_REF], such that file distribution in peer-to-peer systems or resource routing.

b) Road map: After having introduced some backgrounds (Section Section II) and discussed about related works (Section III), we present in Section IV our solution called Dynamic Appending Bloom Filter. In Section V, we give theoretical bounds on the false positive and negative probabilities. In Section VI, we discuss time and communication cost. Finally, we present in Section VII extensive simulations to evaluate our proposal on different distributions. We also evaluate a variation of our solution inspired from the sliding window streaming model.

II. PRELIMINARIES

A. Model

The universe U contains U items and we denote by B the size of the set B ⊆ U. We consider that a stream S of m items is received. Answering a membership query consists, for any item u of S, to determine if u belongs to B.

Let S t = u 1 , . . . , u t be the items received at time t, thus S m = S. The set of distinct items in S t is denoted by D t and we denote by d t the cardinality of D t . Similarly, we define the set Dt = S t ∩ B of cardinality dt as the set of distinct items belonging to B in S t .

B. Membership oracle

A membership oracle O is a compact representation of a set B ⊆ U with access to a primitive O.lookup(u), returning a boolean value for any item u ∈ U. If the oracle is perfect, then O.lookup(u) return true if and only if u ∈ B, for every u ∈ U. Otherwise the oracle is approximate. A false positive is any item u ∈ U such that u ∈ B but O.lookup(u) is true. A false negative is similarly defined as an item u ∈ U such that O.lookup(u) is false for item u ∈ B. Hence the false positive (resp. negative) probability of O is the probability that an item is classified as a false positive (resp. negative).

An important notion is also the false positive rate with is defined as the ratio of the number of items which are false positive, to the total number of items of S which do not belong to B. Intuitively, if we have a false positive probability of f , then on average f m items will be wrongly detected as positives. However, if an item u is a false positive and occurs many times in S, then the false positive rate can drop significantly. Hence having a strong guarantee on the false positive rate is desirable. Similarly, we introduce the notion of false negative rate, which corresponds to the ratio of the number of false negative to the number of item belonging to B in S.

C. Bloom Filter

A bloom filter BF [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF] is an approximate oracle using a bit array A BF of size n and k independent random hash functions {h 1 , . . . , h k }, mapping items from U to an index in [0, n -1] chosen uniformly at random. For each inserted item u ∈ B and every hash function h i , A BF [h i (u)] is set to 1. The membership primitive BF.lookup(u) is easily implemented by returning true if A BF [h i (u)] = 1 for every i ∈ [1, k] and f alse otherwise.

For the purpose of the theoretical proofs, we introduce the notion of masks. The mask H BF (u) of item u is defined as a binary array of size n such that H BF (u)[h i (u)] = 1 for every i, 0 otherwise. The membership query can be solved by doing a bitwise AND operation between H BF (u) and A BF and by checking if the resulting array H BF (u) ∧ A BF = H BF (u). Let H BF (X) = x∈X H BF (x) be the result of a bitwise OR operation over all items in X. With this in mind, we remark that u ∈ B is a false positive if there exists a set X ⊆ B such that H BF (u) ∧ H BF (X) = H BF (u). We say that u collides with X and we denote this event by u ∼ BF X.

It is clear that the false negative probability is equal to 0, since for any item u ∈ S(O) the bits are set to 1 implying that BF.lookup(u) returns true. However the false positive probability is strictly positive if at least one item has been inserted in the filter. Let p(n, k, d) be the false positive probability of such a bloom filter when d ≥ 1 items have been inserted. Since the hash functions are independent and uniform, we can easily deduce the following:

p(n, k, d) = 1 - n 0 (d) n k (1)
where n 0 (d) denotes the number of 0-bits after the insertions of d items. We have n 0 (0) = n and clearly n 0 (d) is a decreasing function. Hence p(n, k, d) is an increasing function in d, for a given n and k. Suppose now that d and k are given. It has been proven in [START_REF] Goel | Small subset queries and bloom filters using ternary associative memories, with applications[END_REF]

that p(n, k, d) ≤ (1 -(1 -1/n) dk+(k-1)/2
) k , which confirms the intuition that the false positive probability increases when n decreases.

III. RELATED WORKS A. Trade-off between false positives and negatives

Solutions already provide a tradeoff between false positive and false negative probabilities [START_REF] Donnet | Retouched bloom filters: allowing networked applications to trade off selected false positives against false negatives[END_REF], [START_REF] Laufer | A generalized bloom filter to secure distributed network applications[END_REF]. The retouched bloom filter proposed in [START_REF] Donnet | Retouched bloom filters: allowing networked applications to trade off selected false positives against false negatives[END_REF] is a classical bloom filter with the additional feature that some bits can be cleared, that is set to 0. By doing this, the false positive probability naturally decreases but at the cost of introducing false negative. To select the bits to clear, the authors suppose that the set of encountered false positive items is known beforehand and they focus the clearing on these items. This assumption is too strong in the context of data streams, where the item distribution is not known a priori. The generalized bloom filter [START_REF] Laufer | A generalized bloom filter to secure distributed network applications[END_REF] is also very similar to the classical bloom filter. There are k 1 hash functions h 1 . . . h k1 and k 2 hash functions g 1 . . . g k2 . When item u is inserted, every bit at position h i (u) is set to 1 and every bit at position g i (u) is set to 0. If h i (u) = g j (u) then the bit is set to 0. This solution introduces false negative but the authors show that the false positive probability depends only on the number of hash functions. However applying this solution in our context would imply the load of the whole database, implying a uselessly large memory consumption.

B. Dynamic oracles

The dynamic bloom filter DBF [START_REF] Guo | The dynamic bloom filters[END_REF] was introduced to represent dynamic sets. At the begin, there is only one BF into which items are inserted. When the occupancy of the BF overreaches a predefined threshold, then a new BF is created in order to receive new items, and so on. This solution is really interesting when ones do not have any idea about the size of the set. However, the use of a simple bloom filter presents better performances if the size of the set is known. Moreover, it has been shown in [START_REF] Negi | Dynamic partition bloom filters: A bounded false positive solution for dynamic set membership (extended abstract)[END_REF] that the false positive probability grows linearly with the size of the dynamic set, for a given amount of memory.

In [START_REF] Negi | Dynamic partition bloom filters: A bounded false positive solution for dynamic set membership (extended abstract)[END_REF], the authors present an oracle to represent a dynamic set with a bounded false positive probability f given as input, independently of the size of the set. This impressive result comes with an important memory cost in memory. Indeed, the total number of bits can theoretically reach O -

kU ln(1-f 1/k )
if the item distribution is uniform. However extensive simulations (not shown in the extended abstract) tends to demonstrate that in practice the solution consumes only slightly more space than DBF, since the distribution in real world data set are more skewed.

C. Adaptivity

Most of the bloom filters variations focus on minimizing the false positive probability or finding a good trade-off between false positive and false negative. However, few works deal with the minimization of the false positive rate. In [START_REF] Mitzenmacher | Adaptive cuckoo filters[END_REF], the authors present the adaptive cuckoo filter, which learns from the answers of the perfect oracle and removes false positive items from the data-structure. Simulations over real datasets show a reduction on the false positive rate in practice. In [START_REF] Bender | Bloom filters, adaptivity, and the dictionary problem[END_REF], the authors use similar techniques to build an adaptive oracle called the broom filters with strong theoretical guarantees. More precisely, they prove that the probability that an item is a false positive (even if S is chosen by an adversary learning from perfect oracle answers) is bounded by a constant < 1. However, these works suppose that the perfect oracle is queried after each positive answers from the filters, which can not fit reasonably in our context.

IV. DYNAMIC APPENDING A. Intuition

Depending on the skewness of item distributions and the length of S, the number of items that belong to B and appear in S can be very low. In such case, using a simple solution such a bloom filter containing the whole set B seems not optimal.

Instead, a natural idea is to append a newly received item u to the filter if u belongs to B. For the same amount of memory, this dynamic version of the bloom filter will naturally provide a better precision for the first items of S, since the number of bits at zero is greater than the one with the naive solution. The counterpart is that this solution implies to query the perfect oracle O B after each item reception, even if u occurs several times in S. To reduce the communication cost, a simple solution could be to remember which item has been seen so far and to query O B only if a new distinct item is received. The communication cost is then reduced from m to d (in the worst case). The communication saving is even more important when the item distribution is skewed. However, remembering exactly which item has been seen could lead to slow solutions, with high memory cost.

We propose a membership oracle called the Dynamic Appending Bloom Filter (DABF). The idea of DABF is based on the use of a pair of Bloom filters, denoted by β and β , significantly smaller in size than the classic solution using a unique static bloom filter. The first bloom filter is used to memorize if an element has already been seen in the past, by gradually populating it online. The second bloom filter is used to determine if an already received element belongs to the considered subset. Thus, the memory cost becomes proportional to the number of distinct items in the stream that belong to the subset. The communication cost is proportional to the number of distinct items in the stream.

B. Algorithm description

We denote by n and n the sizes of the bit arrays of β and β respectively and we use S and S to denote their representative sets. In the following, we present the implementation of the primitive DABF.lookup(u i ) when an item u i is received:

• If β.lookup(u i ) return false, add u i to β and send a membership query to O B . -If O B .lookup(u i ), add u i to β . -In any case, return O B .lookup(u i ). • If β.lookup(u i ), return β .lookup(u i )
Since the filters are populated dynamically, we use notations β t and β to refer to their states after the reception and processing of item u t . S t and S t represent the set of items added respectively to β and β at time t. Initially, S 0 and S 0 are both empty. We define DABF t as the combination of β t and β t .

We do not suppose that both filters use the same set of hash functions but we suppose that every hash function is perfectly random (it draws an index uniformly at random from [1, n]), which is a classic assumption in the literature. We can also use 2-universal random hash functions instead, which are easily implementable and provide strong theoretical guarantees. We denote by k and k the number of hash functions for β and β respectively.

Moreover, the false positive (resp. negative) probability of DABF at time t is denoted by p t (resp. q t ).

C. Extension to the streaming model

We can naturally extend this algorithm to a streaming model in the following manner. Let us denotes by F 0 = β, β and F 1 = β, β two identical DABF's, initially empty. The idea is to fill both filters and to alternately flush them at the end of the window. Let w be the number of items in a window and suppose, for presentation purpose, that m is a multiple of w. Let W i , with i ∈ [0, m/w], be the window including items u iw+1 . . . u (i+1)w . We proceed as follows. For the first w items, we only fill F 0 . Then for any window W i we fill both filters and we use filter F (i-1 mod 2) to answer the membership queries. At the end of the window, we flush filter F (i-1 mod 2) . By doing this, we are able to answer the queries in foreground while maintaining a more up-to-date structure in the background, reducing the impact of the flushing overhead.

V. IMPACT OF THE DYNAMIC

In the case of DABF, the false positive and negative probabilities evolve over time. Indeed the two bloom filters that compose our structure are initially empty and are filled on the fly when items are received. In this section, we provide bounds on p t and q t for an item u received at time t, taking into account that u t is the first occurrence of u or not.

A. First occurrence

In the following, we consider the first occurrence of each distinct item u ∈ D t .

The special case t = 1 is easily treated as follows: since both bloom filters are empty, we get ¬β.lookup(u 1 ) so O B is queried implying that u 1 is correctly classified. In the following, we suppose that t > 1.

Before presenting our main theorem, we show that false negatives can arise when using our oracle.

Proposition 1. Let u ∈ B and suppose that there is a set of items X such that v ∈ B for every v ∈ X and H DABF (u) ∧ H DABF (X) = H DABF (u). Then there is a stream and a time t such that at least one false negative occurs a time t > t.

Proof. Let x = |X|. Consider a stream S such that the x first items correspond to items in X and suppose that u x+1 = u. We deduce that β.lookup(u x+1 ) return true, implying that O B is not queried and u is not added to β . Since X ∩ B = ∅, β is empty, so β .lookup(u x+1 ) returns necessarily f alse, implying that DABF.lookup(u x+1 ) returns f alse.

Our results are summarized by the following theorem.

Theorem 1. Let u be an item received at time t such that no previous occurrence of u has been received.

• If u ∈ B, then q t = p(n, k, |S t-1 |)(1 -p(n , k , |S t-1 |)). • If u ∈ B, then p t = p(n, k, |S t-1 |)p(n , k , |S t-1 |).
Proof. If ¬β.lookup(u), then O B is queried so the false positive or negative probability is 0 in any case.

Let E β denotes the event "β t-1 .lookup(u) returns true", E ¬β (resp. E β ) denotes the event "β t-1 .lookup(u) returns false (resp. true)" and let E ¬DABF (resp. E DABF ) denotes the event "DABF t-1 .lookup(u) returns false (resp. true)".

An item u ∈ B is a false negative if

E β ∧ E ¬β occurs. We have Pr(E β ∧ E ¬β ) = Pr(E β ) • Pr(E ¬β | E β ) = p(n, k, |S t-1 |)(1 -p(n , k , |S t-1 |)). An item u ∈ B is a false positive if E β ∧ E β oc- curs. We have Pr(E β ∧ E β ) = Pr(E β ) • Pr(E β | E β ) = p(n, k, |S t-1 |)p(n , k , |S t-1 |).
This concludes the proof.

The following propositions aim at showing the link between the precision of β and the precision of β . The idea is that if β is more accurate, then more items will be added to β , degrading its precision.

Proposition 2. The number X t of false positive from β at time t is lower bounded by

dt i=1 (1 -(1 -1/n) ki ) k .
Proof. Let X i be an indicator random variable with value 1 if item u i ∈ B is a false positive for β, and value 0 otherwise. The false positive probability is given by (1-n 0 (i)/n) k , where n 0 (i) holds for the number of 0 cells. Hence

E[X i ] = (1 - n 0 (i)/n) k .
Let Y i be the indicator variable set to 1 if cell i is empty. The probability that cell i is empty is given by (1

-1/n) ki , so in expectation we get E[Y i ] = (1 -1/n) ki . Since n 0 (i) = n j=1 Y j , we deduce from the linearity of expectation that E[n 0 (i)] = n(1 -1/n) ki .
Using Jensen inequality, we get that

(1 -E[n 0 (i)]/n) k ≤ E[(1 -n 0 (i)/n) k ] = E[E[X i ]] = E[X i ] = (1 -n 0 (i)/n) k . Let X = dt i=1 X i be the number of false positive from β that belong to B in S t . Then we get X ≥ dt i=1 (1 - E[n 0 (l i )]/n) k ≥ dt i=1 (1 -(1 -1/n) ki ) k . Proposition 3. The false positive probability p t is bounded by p(n , k , dt (1 -(1 -(1 -1/n) k ) k ).
Proof. From Proposition 2, we know that the number of false positive from β is at least

dt i=1 (1-(1-1/n) ki ) k > dt i=1 (1- (1 -1/n) k ) k > dt (1 -(1 -1/n) k ) k . It implies that |S t | = dt -X t ≤ dt -dt (1 -(1 -1/n) k ) k , which concludes the proof.

B. Item repetition

In the previous analysis, we considered the first occurrence of distinct items. However, it is highly probable that an item is seen several times in S, especially if the distribution is heterogeneous. The probabilities are varying from an item to an other, depending on the stream received so far. In the following, we use the notation t u to denote the time at which the first occurrence of u has been seen in S.

Lemma 1. Let F N t ⊆ B be the set of items such that DABF.lookup(u) is false for every u ∈ F N t . Then we have, for any t ≥ t u , for any u ∈ B, u ∈ F N t =⇒ u ∈ F N tu .

Proof. The proof is by contraposition. Suppose that u ∈ B is received at time t u for the first time and DABF tu .lookup(u) is true, implying that u ∈ F N tu . We have two cases:

1) If ¬β tu .lookup(u) then O B is queried and u is added to β . Then u ∈ F N tu and u ∈ F N t , for any t > t u , since β t .lookup(u) will always answers true by definition. 2) If β tu .lookup(u) (i.e., u is a false positive of β tu ), then, as u ∈ F N tu , it implies that β tu .lookup(u) is true. Since the bits are never cleared, we deduce that any further occurrence of u will also be correctly classified. We deduce that u ∈ F N tu implies that u ∈ F N t , for any t ≥ t u . By contraposition, we deduce that u ∈ F N t implies that u ∈ F N tu , for any t ≥ t u , which concludes the proof.

Theorem 2. Let u be an item received at time t such that t u = t.

• If u ∈ B, then q t ≤ q tu . • If u ∈ B, then p t = p(n , k , S t-1 ).
Proof. Consider that u ∈ B is received at time t and the first occurrence of u is received at time t u . Thanks to Lemma 1, we know that any false negative at time t was also a false negative when its first occurrence has occurred. In other words, we have F N t ⊆ F N tu . This implies that Pr(u ∈ F N t ) ≤ Pr(u ∈ F N tu ), leading to the statement.

Consider now that u ∈ B is received at time t. First, it is obvious that the reception of item u implies no modification on β . Moreover, since u has already been seen so far, β.lookup(u) will necessarily return true, implying that the false positive probability of DABF depends only on the false positive probability of β , which is p(n , k , |S t-1 |).

VI. TIME AND COMMUNICATION COMPLEXITY

The reception of each item implies to update our structure and to potentially communicate with the perfect oracle O B . The time complexity only depends on the time required to probe the k bits of each bloom filters bit array. If we suppose that the probing operation is done in constant time, we deduce that the time complexity is O(k).

The communication complexity, measured as the number of time O B is queried, depends on d m , that is the number of distinct items in the stream. However, we remark that any false positive item for β implies that O B is not queried. We deduce that the exact number of communications is

C = d m -N m ,
where N m is the number of false positive produced by β.

We prove the following lower bound on C.

Proposition 4. Let d m be the number of distinct items in S.

The number of communications with O B is at least

d m 1 - kd m n k .
Proof. Let X i the binary random variable with value 1 if item u i ∈ B is a false positive for β, and value 0 otherwise and let

X = di j=1 X j . E[X i ] = i j=1 z(j) n k
where z(j) holds for the number of bits switched from 0 to 1 at time j. From this, we deduce that

E[X] = di j=1 j l=1 z(l) n k ≤ 1 n k di j=1 j l=1 z(l) k ≤ 1 n k di j=1 j l=1 k k ≤ 1 n k di j=1 (jk) k ≤ (d i ) k+1 k n k We deduce that d m -X m ≥ d m -(d m ) k+1 k n k , which
concludes the proof.

VII. PERFORMANCE EVALUATION

c) Performance measures: In our simulations, we measure the precision and the recall of our solution. Formally, let P t ⊆ D t be the set of distinct items in S t for which DABF answers positively. The precision is given by |Pt∩B| |Pt| and the recall is given by |Pt∩B| | Dt| . It is possible that either P t or Dt are empty, implying a division by zero. In such case, the chosen convention is to set the corresponding measure at 1. This can be justified by the fact that if P t (or Dt ) is empty, then it means that we can not misclassified an item. Moreover, we want to specify that an item u is added to P t if DABF answers positively for at least one of its occurrence in S t .

We also present in some simulations the number of communications initiated with O B . Finally we are interested in the false positive and negative rates F P R t and F N R t . Let Nt be the multiset of all items which appear in S t items (with potential repetitions) which do not belong to B. We similarly define Pt for items belonging to B. We define F P t and F N t as the multisets of items in S t which are respectively false positives and false negatives. We define the false positive rate as follows:

F P R = | F P t |/| Nt |, | Nt | > 0 0, | Nt | = 0
We define the false negative rate as follows:

F N R = | F N t |/| Pt |, | Pt | > 0 0, | Pt | = 0 d) General simulation set up: We consider a universe U of size U = 10 4 which consists of integers in range [0, U -1].
The size B = |B| is chosen among the set {10, 100, 1000} and items in B are sampled uniformly at random among U at the beginning of each simulation. In each simulation, we generate 500 streams following a Zipf's law of parameter α ∈ {0.5, 1.0, 2.0, 3.0}. In the simulation descriptions that follow, the item distribution is denoted by zipf-α. The results correspond to the average precision or recall among the 500 runs. e) Bloom filter implementation: The corner stone of our solution is to use classic static bloom filters. To implement these data structures, we have made the following choices.

First, we know from [START_REF] Fan | Summary cache: a scalable wide-area web cache sharing protocol[END_REF] that the false positive probability of a classic static bloom filter of size n that receives d distinct items is minimized when the number of random hash functions is k = n d ln 2. Since n d ln 2 is generally not an integer, a typical choice is to take n d ln 2 as value for k, in order to minimize the computational cost of the hash functions. The number of items added to β corresponds to the number of distinct items d in S. Since we do not make any assumptions on the items distributions, we must assume that d = U = |U| if the stream is large enough. This leads to k = 1 for n < 2U/ ln 2, which is not optimal at early times when the real number of items in β is really low. As a trade-off, we have chosen to set k = n 10 3 ln 2 for β, whatever is the value of n. This setting provides better results for the first items of S. For bloom filter β , a natural upper bound is B so we have set k = n B ln 2 . For every item u, we use a pseudo-random number generator with a seed set at u. Then we generate k random values in range [0, n -1], where n is the size of the corresponding bloom.

As a baseline, we implement a simple solution called 1bf which simply consists in a single bloom filter populated with the whole set B. For the 1bf solution with N bits of memory, we use N B ln 2 hash functions and we also use a pseudorandom number generator for the probes.

A. Single window

In this section, we present simulations with the basic version of DABF, that is without using a sliding window. The generated streams are of size m = 4000 in all simulation.

f) Memory partitioning: In this first simulation, we aim at determining the best way to partition a given amount of memory among our two bloom filters. Let N be the total amount of memory we can afford, then we set n = N • 0.1 • i (for i ∈ [START_REF] Bloom | Space/time trade-offs in hash coding with allowable errors[END_REF][START_REF] Bender | Bloom filters, adaptivity, and the dictionary problem[END_REF]) and n = N -n. In Figure 1, we present the results for a zipf-0.5 distribution, B = 100 and N = 500. The results are similar for others values of B or N .

After only few dozens of items insertions, the precision becomes proportional to the memory given to β, while the opposite can be notice for the recall. This confirms our theoretical analysis on the false positive and negative probability.

g) Impact of the memory: In this simulation, we choose the ratio θ = n/n = 1/9 for the memory partitioning, in order to optimize the precision of our solution. As we argue above, maximizing the precision is fundamental in many use cases. However, this heuristic can be set differently, as a user parameter. We vary the skewness parameter of the Zipf's law and the overall memory N provided to the structure.

We focus on the case B = 100 and we vary the memory N from 1000 to 2000 bits, by step of 200. The results are summarized in Figure 2.

Let first analyse the case α = 0.5. For the precision, DABF is optimal with only 1000 bits of memory. However the recall drops quickly due to the high number of distinct items. The first bloom filter β is indeed saturated with only few decades of items, implying a high number of false negative, which degrades the recall. On the other hand, 1bf is optimal in term of precision with 2000 bits and always produces an optimal recall (as bloom filters avoid false negatives).

In the case α = 2.0 however, the performances of DABF are greatly improved. The precision of our solution is already optimal with N = 1000 and the recall decreases slowly. If we consider the first 1000 items, the recall never goes below 0.9, even with 1000 bits. Please notice that it is possible to opt for a trade-off by choosing a ratio θ = 0.5. This leads to a precision greater than 0.9 while slowing down the recall decrease (cf. Figure 1).

Consider now the case B = 1000, with θ = 1/9 as for case B = 100. The results are summarized in Figure 3. We can notice that the precision is nearly optimal with only N = 4000 bits using DABF , even for zipf-0.5 distribution. As a comparison, the 1bf solution provides a precision of about 0.4 for the same value of N . However, as for the case B = 100, the recall with DABF is quickly decreasing when the distribution is zipf-0.5. Even for N = 10000, the recall drops below 0.7 after less than 1000 insertions. In comparison, 1bf provides a precision above 0.9 for N ≥ 10000 while keeping a perfect recall. In the case α = 2.0 however, our solution clearly outperforms 1bf , with a near perfect precision and a recall of more than 0.89 with only 4000 bits of memory.

B. Sliding window

In order to maintain an up-to-date state of our data structure and to avoid the recall drop, we study the sliding window version. We vary the size of the window from 100 to 1000 by step of 100. We focus our study on the zipf-2.0 distribution, N = 1000 and B = 100. The size of the streams is m = 40000. Here N corresponds to the overall amount of memory, including the two DABF of the sliding window version. The results are summarized in Figure 4.

The top figure presents the precision and recall for different values of the windows size. As baselines, we also present the precision of 1bf and the recall of DABF without using the sliding window mode (nowin). The middle figure represents the communication cost, measured in term of number of communications initiated with O B . Finally the bottom figure represents the false negative rate, depending on the window size, with DABF. The false positive rate is 0 even with a window of size 1000. On the top figure, we observe that the recall is inversely proportional to the size of the window, which makes sense since flushing more often the bloom filters improves their accuracies. This impacts directly the communication cost, as illustrated by the middle figure, which is inversely proportional to the window size. We highlight here that the communications can be easily reduced by querying the oracle if at least one of the filters need to contact him and making the answer available for both filters. The precision with DABF is close to 1 even with a sliding window of 1000 items. As a comparison, 1bf converges to approximately 0.5.

Finally the bottom figure shows that the false negative rate is really stable, whatever is the size of the window. With a window of 1000 bits, the false negative rate is close to 0.2, meaning that 20% of negative answers corresponds to misclassified items that belong to B. But this represent a very small number of distinct items for skewed distributions.

VIII. CONCLUSION AND FURTHER WORKS

We have presented a simple but efficient solution to evaluate the membership of items in a stream to a given set B. The main idea is to summarize only the subset of items in B present in the stream instead of representing the whole set. This leads to a notable space saving in comparison with basic solutions such as a bloom filter. We keep a good precision and recall, especially for skewed distributions.

In the current version of the solution, we are using two bloom filters: one to remember which item has already been seen and a second to summarize the subset of items in B which have been already seen. Especially, as we make no assumption on the items distribution, we must use a large enough amount of memory to handle any scenario. An interesting perspective is to use solutions for representing dynamic sets such as [START_REF] Guo | The dynamic bloom filters[END_REF] or [START_REF] Negi | Dynamic partition bloom filters: A bounded false positive solution for dynamic set membership (extended abstract)[END_REF] and evaluate the interest on the memory consumption in comparison with the use of simple bloom filters. This should be especially promising for the first bloom filter β of DABF .

Fig. 1 .

 1 Fig. 1. Evolution of precision and recall with the variation of ratio n/n . (B = 100, N = 500, α = 0.5)

Fig. 4 .

 4 Fig. 4. Results with the sliding window version (α = 2, N = 1000, B = 100, m = 40000)

  Fig. 2. Impact of the memory with a ratio θ = 1/9 and B = 100.

				Precision and Recall
		0.8 1 0.4 0.6 0.8 1					α=0.5	prec., win=1000 prec. 1bf rec., win=200 rec., win=400 rec., win=600 rec., win=800 rec., win=1000 rec., nowin	α=2.0
	Precision nb com. Recall nb com.	0.2 0.4 0.6 0 0.2 0 8000 0 0.2 0.4 0.6 0.8 1 4000 5000 6000 7000 3000 2000 1000 0 0 1 0.4 0.6 0.8	dabf; N=1000 1bf; N=1000 1bf; N=1200 1bf; N=1400 1bf; N=1600 1bf; N=1800 1bf; N=2000 dabf; N=1000 dabf; N=1200 dabf; N=1400 dabf; N=1600 dabf; N=1800 dabf; N=2000 1bf 30000 35000 500 1000 1500 2000 2500 3000 3500 4000 5000 10000 15000 20000 25000 30000 35000 40000 nb items Communication cost 2bf win=200 2bf win=400 2bf win=600 2bf win=800 2bf win=1000 0 5000 10000 15000 20000 25000 40000 nb items 0 nb items False negative rate 2bf win=200 2bf win=400 2bf win=600 2bf win=800 2bf win=1000	0	1 0.95 0.9 0.85 0.8	dabf; N=1000 1bf; N=1000 1bf; N=1200 1bf; N=1400 1bf; N=1600 1bf; N=1800 1bf; N=2000 dabf; N=1000 dabf; N=1200 dabf; N=1400 dabf; N=1600 dabf; N=1800 dabf; N=2000 1bf 500 1000 1500 2000 2500 3000 3500 4000 nb items
		0.2
		0
		0	5000	10000	15000	20000	25000	30000	35000	40000
							nb items
							α=0.5		α=2.0
		1
		0.8
	Precision	0.2 0.4 0.6							dabf; N=4000 1bf; N=4000 1bf; N=6000 1bf; N=8000 1bf; N=10000 1bf; N=12000	dabf; N=4000 1bf; N=4000 1bf; N=6000 1bf; N=8000 1bf; N=10000 1bf; N=12000
		0
		0.8 1							dabf; N=4000 dabf; N=6000 dabf; N=8000 dabf; N=10000 dabf; N=12000 1bf
	Recall	0.2 0.4 0.6								0.9 0.92 0.94 0.96 0.98	1bf dabf; N=12000 dabf; N=10000 dabf; N=8000 dabf; N=6000 dabf; N=4000
		0
			0	500 1000 1500 2000 2500 3000 3500 4000	500 1000 1500 2000 2500 3000 3500 4000
							nb items		nb items

1 Fig.

3

. Impact of the memory with a ratio θ = 1/9 and B = 1000.