Mourtada Benazzouz
email: mbenazzouz@mail.univ-tlemcen.dzismahan

Ismahan Baghli
email: ibaghli@mail.univ-tlemcen.dz

Mohammed Lamine Benomar

Youcef Benmouna

Mohammed Ammar

Amine Baghli

Benomar

Automated Identification of Plasma Cell in Bone Marrow Images

come

I. INTRODUCTION

There are three types of cells in the bone marrow: 1) red cells or erythrocytes are simple, similar and delivering oxygen to the body tissues. 2) platelets, also called thrombocytes, are blood cells whose function is to stop bleeding. 3) leukocytes contain nucleus and cytoplasm are the cells of the immune system that are involved in protecting the body against both infectious disease and foreign invaders. The proportion of counts of distinctive types of white blood cells in the bone marrow, called differential counts, provides precious information to doctors for diagnosis. Enumerate leukocyte is still performed by hematologists, being indispensable in diagnostics in several diseases. In general, leukocytes are usually manually classified in laboratories by using microscopes; this traditional method is very tedious and time consuming. Therefore, an automatic differential counting system is preferred.

In previous works, there are variety methods for segmentation and wbc's classification. We only mention the work of the last ten years. Haralicks techniques are performed by [START_REF] Sabino | A texture approach to leukocyte recognition[END_REF] in order to enhance the characterization of bone marrow images regarding texture information about the leukocyte nucleus and cytoplasm.

In [START_REF] Theera-Umpon | Morphological granulometric features of nucleus in automatic bone marrow white blood cell classification[END_REF], the idea is to investigate information about the nucleus alone, is much easier than the segmentation of the entire cell followed by a classification of WBC with a neural network.

Combining pixel-wise classification with template matching to locate erythrocytes and use a level-set approach in order to get the exact cell contours of leukocyte nucleus and plasma regions as well as erythrocyte regions was presented in [START_REF] Bergen | Segmentation of leukocytes and erythrocytes in blood smear images[END_REF]. [START_REF] Huang | Leukocyte nucleus segmentation and recognition in color blood-smear images[END_REF] after a segmentation of the nucleus, focuses on recognition steps, based on reduction features by principle component analysis (PCA) to obtain suitable features. The genetic algorithm based k-means clustering approach is used to classify the five kinds of leukocyte in the reduced dimensions. In a another paper [START_REF] Dorini | Semiautomatic white blood cell segmentation based on multiscale analysis[END_REF], the authors begin with the nucleus segmentation based the image pre-processing with SMMT (selfdual multiscale morphological toggle has used to ensure the accuracy of two well-known image segmentation techniques, namely, watershed transform and Level-Set methods, then the cytoplasm region is identified with two different schemes, based on granulometric analysis and on morphological transformations. Recently [START_REF] Kasim | Identification of diseased leukocytes cells from blood smear[END_REF] composed an algorithm of markov random filed with k-means and enhancement methods that provides us the segmentation stage truly without luminance and unsuitable stained smear.

Finally, we can also mention the recent work of our research team. The first propose a segmentation scheme using pixel classification based on the fusion of information. The adopted model is guided by the two strategies offered by information fusion, i.e. classifying separately the data from different sources(color spaces) then merging decisions, or combining these data to classify them [START_REF] Benazzouz | Microscopic image segmentation based on pixel classification and dimensionality reduction[END_REF]. The second [START_REF] Baghli | Hybrid framework based on evidence theory for blood cell image segmentation[END_REF] deals with new segmentation framework based on evidence theory, called ESA (Evidential Segmentation Algorithm).

The rest of paper is organized as follows. The next Section precisely describe the proposed WBC segmentation approaches, in Section 3 presents a detailed of characterization of cells. The effectiveness of our framework is verified by a set of experiments in Section 4. Finally, we conclude in Section 5.

II. IMAGE SEGMENTATION

We start an image pre-processing method to separate cells which is an efficient way for detection and classification of leukocytes. We performed multiple tests over color histograms and according number of authors [START_REF] Katz | Image analysis and supervised learning in the automated differentiation of white blood cells from microscopic images, rmit[END_REF], we arrive at the following conclusion: a threshold value of 100 from [0 -255] give an acceptable discrimination between nuclear and non-nuclear pixels. This method leads to image reduction from 1024 × 768 pixels to 200 × 200 pixels; the calculation takes into account the nuclear center, so a square smaller than I can be specified containing the leukocyte.

A. Otsu's thresholding method

Otsu is a nonparametric and unsupervised method of automatic threshold selection for picture segmentation. Otsu is based on a very simple idea: Find the threshold that minimizes the weighted within-class variance. the weighted within-class variance is :

σ 2 w (t) = q 1 (t))σ 2 1 (t) + q 2 (t))σ 2 2 (t) (1)
where the class probabilities are given by:

q(t) = t i=1 P (i) (2)
and the class means is calculated :

µ(t) = l i=t+1 iP (i) q 2 (t) (3)
which t is maximum range of green channel in histogram and p(i) is a probability green value i. All kind of nucleus can be extracted with Otsu method. Figure 2 shows the result.

B. Region Growing

Region Growing can be presented as an algorithm for segmentation of intensity images which is robust, rapid, and free of tuning parameters. The method, however, requires the input of a number of seeds, either individual pixels or regions, which will control the formation of regions into which the image will be segmented [START_REF] Adams | Seeded region growing[END_REF]. The concept like that of other methods by pixel aggregation, is to start with a point that meets a detection criterion and to grow the point in all directions to extend the region.

1) Shape Prior for cytological image segmentation :

For segmentation purposes we define a region of interest as a blob(nucleus region obtained in previous step by otsu), exhibiting a high contrast relative to its local background. The best boundary for the region is a set of connected pixels exhibiting predefined contrast properties.

Since the shape of WBC is always round or oval, we added the circularity index as a second criterion in the region growing algorithm after aggregation of neighboring pixels; i.e. we will test the form obtained at each iteration by comparing it with a of circularity threshold. The major goal of this new criterion is to avoid the algorithm to grow to an area belonging to a neighboring cell that touches or overlaps with our Region of Interest.

Circularity = 1 4π × P 2 A ( 4
)
where P is Perimeter and A is Area [START_REF] Tuset | Shape indices to identify regional differences in otolith morphology of comber, serranus cabrilla (l., 1758)[END_REF]. In the case of a circle, the roundness parameter is minimal and is equal to 1.

In order to do a segmentation assessment, we compare the results obtained by our segmentation scheme with ground-truth The first observation is that the nucleus region is highly satisfactory using the OTSU method : with two examples, the first is oval shaped c 1 and the second is circular c 2 . In the first iterations, we note that the region growing follows properly the shape of the cell. And when there is an overlap of the cells, the criterion of circularity prevents deformation of the cell.

These results are significantly better compared to our previous work in terms of segmentation quality and in terms of time and computing [START_REF] Benazzouz | Microscopic image segmentation based on pixel classification and dimensionality reduction[END_REF], [START_REF] Baghli | Hybrid framework based on evidence theory for blood cell image segmentation[END_REF].

III. CHARACTERIZATION OF PLASMA CELL

In order to identify the plasma cell in the final stage of our work, it is necessary to quantify with attributes. Most work characterizing the WBC consider two types: Texture and Form.

A. Texture attributes

Texture is defined as a spatial repetition of the same pattern in different directions in space. The concept of texture is used to translate a homogeneous appearance of the surface of an object over an image. So the texture is manifested by visual information that can qualitatively describe using the following adjectives: coarse, fine, smooth, mottled, grainy, mottled, regular or irregular.

GLCMs co-occurrence matrices contain the average space of second order. Fourteen indices defined by Haralick [START_REF] Haralick | Textural features for image classification[END_REF] corresponding to descriptive features of textures. After a selection of relevant attributes, we present here only five of these indices:

• Energy: it is a parameter that measures the uniformity of the texture. It reached high values when the distribution of the gray levels is constant or periodic shape.

Energy = i j P 2 d (i, j) (5)
• Homogeneity: when we find the same pair of pixels, this index is high, for example uniform image, texture or periodic in the direction of translation.

Homogeneity = i j P d (i, j) 1 + |i -j| (6)
• Entropy: measures the complexity of the image. When the values of the co-occurrence matrix are almost all the same, the entropy is high. It helps to characterize the degree of granulation of the image.

Entropy = - i j P d (i, j).logP d (i, j) (7)
• Correlation: describes the correlations between the rows and columns of the co-occurrence matrix.

Correlation = (i -µ) (j -µ) P d (i, j) σ x σ x (8)
• Contrast: This parameter measures the local variations, if these variations are significant, so the contrast is high. This parameter is strongly uncorrelated with energy.

Contrast = N g-1 n=0 n 2    N g i=1 N g j=1 P d (i, j)    , |i-j| = n (9)

B. Shape attributes

We used several attributes of shape from the nucleus region of each leukocyte, these attributes have been selected for their ability to define the morphological aspects of the plasma cell:

• nucleocytoplasmic ratio : is the ratio between the number of pixels of the nucleus and the cytoplasm.

• Area : has been determined by counting the total number of pixels nucleus within the wbc.

• Perimeter: was measured by calculating the distance between two successive pixels belonging to the border.

• Compactness: or roundness of a nucleus.

Compactness = P erimeter 2 Area (10)
• Solidity : is the ratio between the effective area and the area of the convex hull.

Solidity = Area ConvexArea (11)
• Eccentricity : this parameter is used to measure the center's shift of nucleus compared the center of the cell. This is an important feature because the plasma cells possess this property.

Eccentricity = √ a 2 + b 2 a ( 12
)
where a and b are the major and minor axis of the ellipse representing the nucleus region.

• Formfactor: it is a dimensionless parameter which changes with surface irregularities.

F ormf actor = 4 × π × Area P erimeter 2 (13)
In the end, each image containing a single WBC, will be characterized with 12 attributes, they will be used to build a classifier cells.

IV. PLASMA CELL IDENTIFICATION

Once the characterization of each image done, and in order to assist in the diagnosis of myeloma, we will now proceed to the recognition of plasma cells (Figure 5).

We designed this classification with the idea of separating leukocytes into two classes: plasma cells and other cells (not plasma cells), ie the output of a classification into image(containing a single WBC ), will be accounted for as plasma cell or as "other" (neutrophils, basophils, eosinophils, monocytes, lymphocytes, megakaryocytes, erythroblasts, proerythroblast, myelocyte, myeloblast, mtamylocyte, prolymphocytes, promonocyte).

In other words, we aimed particularly plasma cell counts from all leukocytes, since this report is a major criterion for diagnosis of myeloma.

We start by building a classifier based on a learning database with 43 white blood cells belonging 27 images. In the purpose of achieving a good training, we took care to eliminate 6 cells, 3 represent segmentation faults, and the 3 others are non-entire cell (located on the edge of the image). A new classifier SVM is designed with 12 input parameters issue from leukocyte characterization step. This classifier is trained on the remaining 37 white blood cells of this base learning (including 15 plasma and 22 non-plasma cells). The classification on the same database of learning led us to recognize the 15 plasma and 22 non-plasma, this is equivalent to saying 100 % of recognition and accuracy rate.

The test database, is made up of 81 spinal cord image after segmentation and characterization, a total of 157 cells is obtained. With the help of an expert, in this case a doctor hematologist, we carried out a labeling of 157 cells that will serve as a test base, we got to annotate 97 plasma and 60 non-plasma cells. After classification, among the 97 plasma cells, 73 were recognized correctly, while 21 dystrophic plasma cells (atypical) and 3 poorly segmented plasma cells were identified as non-plasma; the recognition rate is 75.25 %. Note that this decrease from the results obtained on the learning base is justified primarily by the dystrophic cells, knowing that even the human expert hardly recognize this type of cells. Figure 6 represents images that have been misinterpreted; they would not received to the classifier, or rather should have been eliminating during segmentation. By cons, no false positives were recorded, i.e. 60 cells classified as non-plasma cells really are, this can be considered an advantage because the counting of plasma cells is not impaired.

V. CONCLUSION

In this paper, we have proposed an automated segmentation, characterization and identification of Leukocytes namely plasma cells. The proposed system firstly individuates in the bone marrow image the WBC from the others blood cells, through the method otsu applied to the green channel of the image, obtaining a segmentation of the nucleus. This latter will be used as seed point for the segmentation of the cytoplasm by the region growing. Our second contribution is in the integration of shape constraints into the region growing algorithm to have round or oval cells, and we end up extracting shape and texture indexes in order to classify plasma cells.

Our system is completely automated applicable to varying cell appearance and image quality.

The experimental results are compared with the manual results obtained by hematologists. The proposed method is more reliable and computationally less expensive, but there is a lacuna in in the recognition of distrophiques cells, we will try to correct in future work.

Fig. 1 .

 1 Fig. 1. Segmentation stages

Fig. 2 .

 2 Fig. 2. Otsu's segmentation

Fig. 4 .

 4 Fig. 4. Segmentation results: (a 1 ,a 2 : original cells), (b 1 ,b 2 : nucleus by OTSU), (c 1 ,c 2 : region growing), (d 1 ,d 2 : yellow cytoplasm obtained by subtracting from the two last stages)

  Fig 4 (b 1 ,b 2 ). Region growing is shown in the next line in Fig 4 (c 1 ,c 1 ) :

Fig. 5 .

 5 Fig. 5. Plasma cell examples:(a, b, c) normal, (d) dystrophic

Fig. 6 .

 6 Fig. 6. Example of misfiled images: (a) cell damaged by staggering, (b) badly segmented cell, (c) cell cut on the edge of the image.

TABLE I .

 I

SEGMENTATION ASSESSMENT.

ACKNOWLEDGMENT

We thank Professor Mrs. Nadia Benmansour (Hemobiology service, Tlemcen Hospital) for help and advice during images acquisition, preparation of ground truth images and especially labeling of plasma cells.


Christophe Hurter
email: christophe.hurter@enac.fr

Yohann Brenier
email: yohann.brenier@aviation-civile.gouv.fr

Jason Ducas

Estelle Le Guilcher

CAP: Collaborative Advanced Planning, Trade-off between airspace management and optimized flight performance Demonstration of En-Route reduced airspace congestion through collaborative flight planning

Keywords: trade-off between airspace management air traffic management, collaboration, en-route, collaborative decision making (CDM), collaborative advanced planning (CAP), operations

HAL is

INTRODUCTION

European Air Traffic Management (ATM) mostly relies on strategic, pre-tactical and tactical traffic flow procedures based on post-operation analysis. Applied measures aim at dynamically find the right balance between airlines' demand and available Air Traffic Control (ATC) capacities: what is called the European Demand and Capacity Balancing (DCB) process.

Applying traffic regulations, hence allocating departure slots and generating delays (+ 31% in 2015 compared to 2014 in France) is the widespread measure used to face airspace congestion. As traffic demand (Fig. 1) increases (+2.6% in 2015 vs 2014 in France), some air traffic control sectors are becoming real bottlenecks for which the implementation of daily regulations can no longer be the sole solution to address airspace congestion and induced critical delays for airlines and passengers. With an estimated price of $81 per minute of delay alongside with the recent evolution of European air passenger rights, most of airlines top concern is on-time performance [START_REF] Cook | European airline delay cost reference values[END_REF]. In the framework of the SESAR business trajectory and European airport CDM concepts, collaboration between airlines and Air Navigation Service Providers (ANSPs) has to be the way forward for smarter and innovative solutions towards seamless skies and enhanced passenger experience. DSNA, the French ANSP designed a new approach to better distribute the traffic demand according to the control sector capacities available: The Collaborative Advanced Planning (CAP) process. This CAP process allows ATC flow management units to suggest delay-free flight trajectories and/or cruising levels to airlines operations with the objective to prevent control sectors from congestion and induced delays. This collaborative approach introduces a new pre-tactical flowcentric method for Demand and Capacity Balancing in the European Network.

II. WIDESPREAD EUROPEAN AIR TRAFFIC DEMAND AND CAPACITY BALANCING PROCESS

Each day, between 20.000 and 35.000 commercial and/or instrument flights fly in the European sky. For each of these flights a flight plan is filed by the airlines' operations (or by the crew). This flight plan contains different information like the aircraft identifier (name of the flight), the type of aircraft, the initial planned route, the expected time of departure, the airspeed, etc.

Each European country has its own airspace structure, i.e. airports, routes, way points, terminal procedures that are used by all airspace users (airlines, pilots…). Fig. 2 On a post-operation basis, ATFM (Air Traffic Flow Management) delays generated by these regulations are recorded and used in order to assess the performance of every Area Control Center (ACC) as shown in Fig. 3.

III. STATE OF THE ART

Air Traffic Management was investigated with different perspectives by many previous works. Among existing past publications, two major categories can be outlined: Air Traffic Analysis, where traffic is displayed or analyzed with dedicated tools; and Airspace Management and Usage, where the airspace is restructured depending on the traffic analysis, flight trajectories being generated based on the existing airspace structure. These two categories show how this topic is diverse and versatile. This section provides the details of existing tools or algorithms to support air traffic analysis and airspace management. All of these related works helped ENAC and DSNA build the Collaborative Advanced Planning process.

A. Air Traffic Analysis

The Air Traffic Analysis is achieved with many different tools used to extract data and knowledge from real-time or recorded significant traffic sequences. All of these tools help to better understand the traffic structure and its evolution thanks to different metrics [START_REF] Gianazza | Airspace configuration using air traffic complexity metrics[END_REF] and interaction techniques [START_REF] Hurter | Interactive image-based information visualization for aircraft trajectory analysis[END_REF]. Traffic is analyzed with a flow perspective (flow-centric approach); one can thus better compare the recorded trajectories and look into their temporal evolutions [START_REF] Scheepens | Visualization, selection, and analysis of traffic flows[END_REF]. Traffic flows can also be visually analyzed thanks to simplification techniques like the Edge Bundling one [START_REF] Hurter | Graph bundling by kernel density estimation[END_REF]. The dynamics of traffic flows can be integrated within a dynamic network [START_REF] Hurter | Bundled visualization of dynamicgraph and trail data[END_REF] using schematization techniques for analysis purposes [START_REF] Hurter | An automatic generation of schematic maps to display flight routes for air traffic controllers: structure and color optimization[END_REF]. Traffic flow dynamics can also be extracted with visual analytic [START_REF] Andrienko | Scalable analysis of movement data for extracting and exploring significant places[END_REF] or multiscale techniques [START_REF] Klein | Dynamic multiscale visualization of flight data[END_REF]. Starting from this flow simplification, control sector configurations can be easily monitored [START_REF] Marzuoli | Data visualization techniques for airspace flow modeling[END_REF]. Finally, this flow analysis can provide unexpected information like meteorological parameters (i.e. wind direction) [START_REF] Hurter | Wind parameters extraction from aircraft trajectories[END_REF].

Few interaction techniques do exist to manipulate large quantity of aircraft trajectories. FromDady (Fig. 1) shows the first instance of such paradigm [START_REF] Hurter | FromDaDy: Spreading data across views to support iterative exploration of aircraft trajectories[END_REF]. Examples of usages are also provided [START_REF] Hurter | Air traffic analysis[END_REF]. One of the most promising way to allow this kind of interaction with large dataset relies on the so called Pixel Based Techniques [START_REF] Hurter | Image-Based Visualization: Interactive Multidimensional Data Exploration[END_REF].

B. Airspace Management and Usage

Air Space Management [START_REF] Lulli | The European air traffic flow management problem[END_REF] targets many goals: the reduction of flight delay [START_REF] Cook | European airline delay cost reference values[END_REF], traffic optimization [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF] or the satisfaction of the airspace users [START_REF] Dresner | Customer service, customer satisfaction, and corporate perfo[END_REF].

Many techniques exist to model and optimize the airspace with automatic systems [START_REF] Flener | Automatic airspace sectorisation: A survey[END_REF], the use of a predictive model with neural network [START_REF] Gianazza | Forecasting workload and airspace configuration with neural networks and tree search methods[END_REF] or meta heuristics [20] and many others relying on local self-organization [START_REF] Hand | Self-organized traffic flows: a sequential conflict resolution approach[END_REF], [START_REF] Simaiakis | Demonstration of reduced airport congestion through pushback rate control[END_REF] or introducing dynamics in the decision making process [START_REF] Klein | Airspace playbook: Dynamic airspace reallocation coordinated with the national severe weather playbook[END_REF], [START_REF] Ehrmanntraut | Airspace design process for dynamic sectorisation[END_REF], [START_REF] Bloem | Configuring airspace sectors with approximate dynamic programming[END_REF]. Some Methods of dynamic air space configuration have been compared [START_REF] Zelinski | Comparing methods for dynamic airspace configuration[END_REF]. In order to find suitable air space configuration, previous works also investigated a user centered design process [START_REF] Saporito | A participatory design for the visualization of airspace configuration forecasts[END_REF]. While airspace management aims at optimizing the global ATC capacity, generating optimal flight trajectories relies on several parameters like cost effectiveness [START_REF] Bilmoria | FACET: Future ATM concepts evaluation tool[END_REF] or weather conditions [START_REF] Girardet | Generating optimal aircraft trajectories with respect to weather conditions[END_REF].

Collaborative processes were also studied in order to better face adverse conditions [START_REF] Dray | Air Transportation and Multimodal, Collaborative Decision Making during Adverse Events[END_REF], especially in terminal areas [START_REF] Okwir | Collaborative Decision Making (CDM) in Airport Surface: Europe vs usa implementations, challenges and best practices[END_REF].

IV. IMPLICATIONS FOR DESIGN

A. Scenario of current usages

The CAP process was designed using walkthrough methods and ecological interface design [START_REF] Vicente | Ecological interface design: Theoretical foundations[END_REF]. Interviews of the different stakeholders were conducted from flow managers in French ACCs to traffic managers and airlines flight planners in airlines operations control centers (OCCs). These interviews were conducted in April 2015.

In the ACCs, the interviews involved representatives of flow manager teams in Reims, Paris and Marseille ACCs (two people at each time). The outcomes of these interviews paved the way for a stronger involvement at the local ATC for which expertise in airline flight planning processes is expected. The need to change less than a dozen flight plan routes is the major enabler in this approach. Finally flow managers of the 3 involved ACCs were on duty from 6 am to 8 pm local time. On the D day, strategies for flow management had been defined four hours ahead of operations based on the flight plan demand. These strategies involved staff availability, initial flight plan demands, available sector configurations, pretactical measures, regulations and tactical workload transfer.

In the airline operation control center, the organization of the tasks related to flight planning changes from one airline to the others. Depending on who is in charge of making the decision for changing a flight plan, traffic managers, senior flight planners, flight planners and chief of operations were met during these walkthroughs in their premises in London, Manchester and Amsterdam. All five airlines are using the same Computerized Flight Plan Service Providers (CFSP) that automatically computes the routes, the optimal flight levels and costs for a dedicated set of flight, aircraft and crew. On time performance is the first objectives of these airlines as it is directly linked to customer satisfaction [START_REF] Dresner | Customer service, customer satisfaction, and corporate perfo[END_REF]. For each flight, the first flight plan (FPL) is filed and distributed to every ANSP at least six hours before the estimated time of departure. Between the first filing of the FPL and two hours before departure, updates on the route and/or the departure time may be transmitted by airline operations while ANSP are preparing their strategies. If updates on a FPL are communicated later than two hours before departure, the flight is tagged as late updater and subject to more impeding measures. When a flight is delayed because of its flight plan, its route can be modified by the airline operations to try avoiding the congested (and regulated) sectors based on their knowledge of the environment (Fig. 4). The example on the right (Fig. 4) is unrealistic: crew will struggle to descent and then climb again during the cruise phase while it will have highly increased the ATC workload in sectors that are not design to cope with such variable profiles.

B. Observed limits of current usage and improvment perspectives

These uncontrolled FPL changes may be agreed upon when applied to a limited number of flights. But when these changes affect a lot of flights because of penalizing regulation or favorable jet streams [START_REF] Girardet | Generating optimal aircraft trajectories with respect to weather conditions[END_REF], an important part of the initial flight plan demand can shift from initially congested sectors to initially uncongested sectors (Fig. 5). While regulation measures are applied to congested sectors, new regulations might be needed in order to deal with the demand that has shifted: The European network is finally destabilized by such reaction to massively impeding regulations. Local Flow Management Position (FMP) experts have the best knowledge of the traffic structure and are able to identify which flights impede the most on the control sectors capacities. Airline operations are keen to receive any suggestion from a local FMP in order to increase on-time performance while constraining flight performance on a limited number of flights to keep the network stable.

C. Design requirements

As a summary of our observations and current activity analysis, we extracted design guidelines to supports users in their flights operations' management. These requirements are summarized below into the following five categories: Support Asynchronous Communication (AC): since each decision needs to be analyzed beforehand, the operator cannot provide decision making on the fly. This asynchronous communication will leverage the communication flow between operators by providing a history of past events, and using an on the fly chat system.

Collaborative Decision Making (CDM): the need to implement solutions which are compatible with every ACC crossed by any single flight and understandable from an operator, ATC or an airlines perspectives drives us to rely on the CDM principles as already implemented and experienced in the European Airport-CDM concept. These principles mostly rely on the definition of a priority scheme to follow in the decision model for any identified hotspot.

System compatibility with existing regulation process:

European demand and capacity balancing processes have been developed for the last 20 years and are run by more than forty different countries. New introduced concept need to rely on existing processes and especially the regulation process since these regulations are the mean to ensure safety in European ATC sectors. Compatibility with existing working methods: in all complex systems, solutions that proved their efficiency are difficult to integrate in modern technology. Resistance to change and front line operator acceptance are the more important challenges to deal with. Ensuring the compatibility of the CAP with existing robust methods are key for the acceptance of this new process.

Flexible but Synthetic exchange of Information (FSI): exchanging information about flights mostly rely on computerized flight plan data. Since the main principle of the CAP is to offer to the stakeholders enough flexibility to solve together local hotspots with innovative and highly customized solutions, these operators (with an airline background or an ATC background) need to understand each other. FSI is the common vocabulary to be shared between airlines' operators and ACCs to achieve efficient and simple flight plan refiling.

V. OUR IMPLEMENTATION: DESIGN OF THE COLLABORATIVE PLANNING

Based on our design guidelines, the proposed work is entirely operation-oriented. To facilitate its immediate applicability, it is based on flight plan analysis from flow managers and feasibility assessment by airline operators. On the one hand the tradeoff between flight-centric and flowcentric metrics (safety, environment and capacity) provides flow patterns throughout the European network (including flight description, schedules and characteristics). On the other hand, a global picture of the network organization sheds light on the sequenced involvement of each actor: airlines customers and operations departments, flight planning support industries, the European Network Manager, pilots and air traffic controllers. This global knowledge enables to identify the reasons for built up traffic congestions and the involved stakeholders. This process facilitates the collaboration between the right actors at the right time in order to mitigate identified hotspots.

A. Traffic structure

En-Route congested sectors are dealing with several flows that are crossing each other in the same sector. The more impacting flow in terms of constraints on other flows and induced complexity by the numerous ACCs crossed is the BRY-CLM axis (Northbound flow from Fig. 6) where the CAP process was initiated.

B. CAP global design

The global design of the CAP process relies on mutual understanding of front line operators from ACCs and from OCCs. Constraints of both parties are explained to each parties and a presentation of possible exchange timing is extracted: this drives to Collaborative Decision Making in En-Route airspace management. In order to meet ACCs requirements in terms of flight distribution in the available airspace, the initial flight plan demand has to be known. This demand is available when all flight plans have been first filed, for the shortest flights between 6 and 4 hours before their estimated time of departure. Changes on these flight plans may be achieved between 4 hours and 2 hours before the estimated take off time. These requirements defined the timings of Fig. 7.

In order to support AC and FSI, the drafted interface is divided into free text chat boxes and operational data exchange between airlines OCCs and ACCs as shown Fig. 8.

C. Asynchronous Communication

AC introduces a new paradigm for communication in French operations rooms which is usually done using the phone. To support AC, two basic chat boxes have been offered to the operators during the first trials: a first chat box (Fig. 9) facilitating communication between OCCs and ACCs while the second one is dedicated to DSNA internal negociations. This non interruptive communication paradigm favors the acceptance of this new CAP process. First it is not disturbing operators working on their regulation processes during the initial flight plan demand management. Then it favors constructive exchanges which enable mutual understanding within airline OCCs and ACCs.

D. Flexible but Synthetic exchange of Information

Fruitful collaboration relies on data that are tactically extracted from operational systems (Fig. 10): name of the flight (A/C ID), airports of departure and arrival (ADEP and ADES), Estimated Off Block Time (EOBT) and current filed route. A set of local planning options are defined in order to spread the demand into available sectors instead of concentrating them into upper regulated sectors (Fig. 11). These options are commonly defined by ACCs and OCCs taking into account their actual feasibility in the planning phases (flight plan) but also by the pilots and air traffic controllers during tactical operations. Criteria like existing waypoints, aircraft performance at considered altitudes, usual workload and induced costs in terms of flight time and extra-fuel burn are investigated. Three types of flight planning requests may be implemented: the full level cap (flight is asked not to fly higher than a specified altitude), the anticipated descend, and the free request (flexibility is offered to the operators). In the common agreed framework, level capping a flight to FL340 instead of flying to FL360 or FL380 induces an extra cost of operations of less than $250 and an extra-fuel burn estimated to 100 kilograms of fuel.

E. New Scenario of usages: airline OCCs and ACCs additional meetings

With the five design requirements implemented in the first version of the process (AC, FSI, CDM and compatibilities), the usual working methods and processes can still be run. Whenever real time workload enables running the CAP process, new physical or virtual meetings are schedule to design (Fig. 12), improve or set up tactical collaboration between OCCs and ACCs. Front line operators now integrate daily meeting times through the dedicated web-based interface.

First, the involved ACCs identify a list of hotspots (time and sectors where the demand exceeds the capacity) through the complete BRY-CLM flow. For every hotspot, ACCs identify key flights to remove in order to ease the flow. For each of these key flights, local planning suggestion taken from pre-defined options (Fig. 11) are agreed between ACCs and then communicated to airline OCCs. Then, OCCs assess the feasibility of the route change considering tactical local constraints (fuel, staff availability, crew accessibility…) and inform ACCs on the degree of confidence with which the changes can be achieved. Once a change is done, involved OCCs may confirm that the flight plan has been updated on the web interface while it is transmitted to all stakeholders at the same time.

VI. OPERATIONAL RESULTS OF ACTUAL TRIALS

The Collaborative Advanced Planning process was tested in real operations according to two different objectives. A first three day trial was organized in May 2015 in order to better calibrate the model of this approach for daily collaboration between airlines and air traffic control units. Then with more actors in the loop, the robustness and consistency of the process was assessed during a summer trial in 2015.

A. The investigated flight routes

To validate our software development, we focused on a specific set of flight routes. These flows were interesting since they had usually been the source of numerous delays (95 000 minutes of delay in 2014, part of LFEEFMP delay Fig. 3). Fig. 13 shows the flows being investigated along with their corresponding density over time.

B. May trial: Testing and Calibration of the model

Once the modelling of this collaboration was built, the next step consisted in testing and calibration. A first set of flight planning scenarios in the French airspace was defined: cruising level capping, early descent towards a set of destinations and free requests. This procedure relied on large scale live trials involving pilots and air traffic controllers. The first three-day live trial was organized in May 2015 with the BRY-CLM flow, involving three French area control centers and three partner airlines. Under normal conditions and continuously monitored traffic flows, DSNA audited the Collaborative Advanced Planning process when applied by airlines operations, flow managers, pilots and air traffic controllers. The first live trial enabled to save 5.481 minutes of delay over three days by amending 23 flight plans in a flow of more than 200 daily flights. During these three days, the workload in airline operations, cockpits and behind air traffic controller radar screens was monitored in order to better assess the feasibility of such procedure for a summer long implementation in daily operations. An analysis of what actions could be easily achieved from an operational point of view was conducted. Taken into account these feedbacks, new scenarios were defined and implemented two months later with five airlines in the loop.

C. Summer 2015 trial: outcomes, consistency and robustness checks

In Europe, summer air traffic season starts late April. Traffic increases until mid-July when the shift between business and leisure flight programs operates. Running the CAP process in OCCs and ACCs over a longer period of time from July to September enables to verify its compatibility with the workload and processes that are implemented during high traffic days and weekends. Moreover, a long term assessment of the CAP favors the acceptance of the process by a larger population of FMP staff while requiring a lower involvement of the process design team considering the flexibility of the process.

The summer 2015 trial enabled staff to progressively extend the geographical scope of the process to other flows (RLP, Fig. 6) and challenge the process with unexpected situations like concentration of flights in lower sectors.

From July 7 th to September 13 th 2015, the CAP process was run 62 days over 69. 628 flight plan changes were suggested to the airlines operations. 92% of these requests were implemented by the airline OCCs. The traffic in the considered sectors (5R) increased by 6% during summer 2015 compared to summer 2014 while reducing the delay by 52% during summer 2015 (Fig. 15).

While running the CAP process, the capacity of the ACCs and the OCCs enabled to better estimate the average induced workload on both side of this collaboration. At the same time, it paved the way to more dynamic and safer flight plan demand management. The flight plan demand is now streamlined in the French busiest sectors by acting on less than five FPL for each peak (Fig. 14) rather than delaying hundreds of flights and generating thousands of minutes of delay.

VII. OBSERVATIONS, LESSONS LEARNED AND PERSPECTIVES

ATC is really pleased with this collaboration, showing that the French ANSP can work closely with the airspace users in order to improve the global performance through innovative and collaborative ATFCM methods.

A. Qualitative outcomes

Feedback from involved stakeholders was gathered one month after the end of the summer trials.

1) From the ATC point of view:

The CAP process contributed to a better predictability of the flight plan demand and network stability. DSNA's operators extended the scope of the CAP process to the RLP flow during the summer trial and requested to see the process applied to more flows and more actors.

2) From the airlines point of view:

"The early notification of workload was appreciated, rather than firefighting when a regulation is applied. It was pleased to be part of the operation, and taking this further. The website is very workable and informative, and airlines look forward to the joint initiative being more extensively used over all of France."

"Less fuel was used on days when the procedure was in place as we were not level capping a high percentage of flights. The benefit was also noticed in the other group airlines as they also saw a more stable French network. One other benefit is now due to this trial we have an excellent dialogue with ATC and believe this will bring a lot of future benefits."

"While the trial increases the workload on our busy Ops department, the benefits could be significant to all airlines flying in the French airspace."

"Communication was fine, simple as we like it. For the future this is the way to go, instead of putting in regulations, an active approach from FMP's is required."

The process was appreciated by the airlines which asked to involve more of them in order to get better situation awareness through the French network.

B. Lessons learned

This process demonstrated that daily collaboration between airline operations centers and flow managers in ACCs is feasible and fruitful on a daily basis.

Light was also shed on the need to focus on first line actors' expertise first when trying to improve collaboration in air traffic management processes, rather than defining processes and looking into new support technology.

From an ANSP point of view, it has shown that the need of transparency is essential when it comes to collaboration with several airspace users. During these trials, the participation and CAP involved flights for each airline were monitored and broadcasted to all the other airlines (Fig. 16).

Finally, the more important benefit of the CAP process is the strong improvement of what is called the Common Situation Awareness (CSA) through the European ATM Network. In this way, every involved actor is able to inform other bodies of its current situation and/or participation status as simple as: "busy", "dealing with a flight problem", "dealing with congestion in our sector", "available to help other actors or sometimes competitor airlines".

C. Perspectives

The CAP principle proved its efficiency with its implementation on the BRY-CLM flow. Currently different flows are considered as potential "candidates" for a CAP process:

- Globalization of the process relies on more airlines, more ACCs to join the initiative within an increasing European air traffic.

At the end of the summer 2015 trial, it was decided to continue playing the process. At the beginning of summer 2016, the CAP process is being run in both MANAK-TUPAR and LFMM scenarios. Three more airlines joined the initiative. This research follows a continuous incremental process. The next steps are first to extend the scope of the Collaborative Advanced Planning process in terms of flows and participation (ATC and airlines) and to better support the decision making steps of this process. In parallel, we will focus on framing the En-Route CDM concept from the gathered bottom-up initiatives like the CAP and support its implementation at a European level from both research and operations perspectives. ACKNOWLEDGMENT Christophe Hurter coordinated the academic research of the CAP project. Yohann Brenier is the DSNA CAP project manager, an idea he supported and coordinated while he was in charge of the DSNA summer 2015 plan. Jason Ducas is in charge of the communication around the CAP project. Estelle Le Guilcher ensured the funding and acceptance of the project.

We would like to acknowledge the cooperation and involvement of all the people who contributed and still contribute to this CAP project: Paris, Marseille, Reims, Brest and Bordeaux flow management units for developing the process and running it on a daily basis, the Network Manager Operations Center at Eurocontrol for providing the delay simulations. Special thanks to Céline Tea, Corinne Papier, Jérôme Dufossez, Marie-Laure Faure, Nicolas Roberto, Stéphane Tchertchian, Thierry Durigneux from DSNA who initiated the process, to Martin Djikzeul from KLM, Duncan Philipp from EasyJet, Melanie Whitehead and Ian Pauls from British Airways, Chis Woodland from Thomas Cook Airlines and Fergus Lawless from Ryanair for joining and their contribution to the initiative.

Fig. 1 .

 1 Fig. 1. This image shows the traffic density over France during one day of recorded trajectories (December 2009). The red dots shows the entry points of the trajectory (e.g. take off or landing).

  explains the different steps that are implemented to ensure smooth operations at hour H when each flight is in contact (radio or digital connection) with one control center at a time. Usually starting between six and two hours before the departure time: -a flight plan is filed by the aircraft operator, sent to a European agency that centralizes all the flight plan for Europe (Eurocontrol/IFPS -Integrated Initial Flight Plan Processing System); -Eurocontrol/ETFMS -Enhanced Tactical Flow Management System -computes the intersection between the route of the flight plans and the airspace structure available in order to provide local Air Navigation Service Providers with the expected traffic load for all control sectors in the European airspace; -local measures for demand and capacity balancing are decided based on the flight plan demand, the expected traffic load of the sectors, the staff available, and weather forecast. This will determine the local control sector capacity; -when the traffic load of a sector exceeds its nominal capacity, a regulation is implemented. A regulation usually spreads the initial flight demand over time. When such regulation is put in place, aircraft operators receive a delay message for the flights supposed to enter in the congested sectors.

Fig. 2 .

 2 Fig.2. This timeline depicts the way ATM is managed in Europe from months before operation until post operation analysis. All steps involve a strong interaction between the ANSPs, the Network Manager and the airlines.

Fig. 3 .

 3 Fig. 3. French ATFM delays in 2014, breakdown by control centers: Bordeaux ACC (LFBB) in blue, Brest ACC (LFRR) in yellow, Paris ACCs (LFFF) in green and brown, Marseille ACC (LFMM) in dark yellow, Reims ACC (LFEE) in Red and approaches.

Fig. 4 .

 4 Fig. 4. Amended flight plans in order to avoid congested sectors. Initial flight plan is in green, refiled flight plan is in red.

Fig. 5 .

 5 Fig. 5. Flight plan demand spread over three flight levels (FL). Concentration at one FL can be noticed from 07 UTC due to favorable jet streams at this altitude. Red line is the maximum capacity of the sector. This extra demand has to be removed in order to ensure safe operations.

Fig. 6 .

 6 Fig. 6. The different air traffic flows crossing Reims (North-East of France) busiest sectors. In orange, the BRY-CLM flow that first motivated the CAP initiative (more than 200 flights a day).

The

  BRY-CLM axis sees around 200 flights a day distributed in long haul flights (departing from South Africa), medium haul flight (coming from North Africa, or South of Europe), short haul flow (departing from South of France). These flights are bound for Paris, Belgium or Holland and the United Kingdoms. The measures mentioned above for demand and capacity balancing are used on this flow on a daily basis.

Fig. 7 .

 7 Fig. 7. CAP timing. The process involves strategic meetings and daily collaboration between the stakeholders that starts 5 hours before the potentially impacted flights leave their parking stand: Estimated Off Block Time (EOBT).

Fig. 8 .

 8 Fig. 8. CAP dsna.fr web-based interface shared in airline operations and ACCs. On the left, shared operational data (flight lists) and on the right free text chat boxes to support AC and FSI.

Fig. 9 .

 9 Fig. 9. Extract of the asynchronous communication between participating airlines and French ACCs (July 2015).

Fig. 10 .

 10 Fig. 10. Flight list shared between OCCs and ACCs. Operational data are completed with specific local constraints to be implemented by the OCCs.

Fig. 11 .

 11 Fig. 11. This vertical view of the airspace structure depicts six predefined flight plan options designed to avoid the HYR and KD sectors.

Fig. 12 .

 12 Fig. 12. This timeline depicts the way ATM is managed in Europe with the introduction of the CAP.

Fig. 13 .

 13 Fig. 13. This figure illustrates the density of flights of the BRY-CLM (blue) and RLP (green) flows. Hourly distribution of these flights can be monitored. Through this point visualization, complexity induced by each flight can be assessed by the flow managers using horizontal and vertical views.

Fig. 14 .

 14 Fig. 14. Evolution of the flight plan demand in HYR sector while the CAP process is run between all stakesholders. Graph demand at the top represents the initial flight plan demand over time when operators started the process. The one below depicts the demand after flight plans where balanced between upper and lower sectors: traffic peaks are mitigated.

Fig. 15 .

 15 Fig. 15. Morning delay (in minutes) evolution during summer 2015 and summer 2014 in Reims busiest sectors.

Fig. 16 .

 16 Fig. 16. Daily flight plan change distribution through involved aircraft operators.

  MANAK-TUPAR: Northbound flow from Spain to the United-Kingdoms; -EYDD: Southwest bound flow from central Europe to Southwest Europe; -LFMM 4th layer: optimizing flight distribution of the Westbound and Eastbound main flows in Marseille airspace.

  VIII. CONCLUSIONThis paper focuses on the design of a new daily Air Traffic Management collaborative process involving ATC actors and airspace users (airlines operations). Already implemented in the French airspace, the Collaborative Advanced Planning (CAP) process enables daily pre-tactical and tactical collaboration between airlines and Air Navigation Service Providers throughout the aviation route network (and not only during adverse events). The effects of Demand and Capacity Balancing are mitigated while meeting the objectives of flightcentric (airline point of view) and flow-centric approaches (ATC point of view): improving flights' on-time performance, reducing ATFM delays in control sectors subject to significant traffic growth. Within the prospect of increasing Common Situation Awareness in Air Traffic Management, this innovative initiative shows that collaboration needs to focus on first line actors' mutual understanding and knowledge while supporting Asynchronous Communication (AC), Collaborative Decision Making (CDM), compatibility with existing working methods and Flexible but Synthetic exchange of Information (FSI) in operational rooms.


Zakaria Gheid
email: §zgheid@esi.dz

Yacine Challal
email: ‡ychallal@esi.dz

Efficient and Privacy-Preserving k-means clustering For Big Data Mining

Keywords: big data, horizontally partitioned data, k-means clustering, privacy, efficiency

Recent advances in sensing and storing technologies have led to big data age where a huge amount of data are distributed across sites to be stored and analysed. Indeed, cluster analysis is one of the data mining tasks that aims to discover patterns and knowledge through different algorithmic techniques such as k-means. Nevertheless, running k-means over distributed big data stores has given rise to serious privacy issues. Accordingly, many proposed works attempted to tackle this concern using cryptographic protocols. However, these cryptographic solutions introduced performance degradation issues in analysis tasks which does not meet big data properties. In this work we propose a novel privacy-preserving k-means algorithm based on a simple yet secure and efficient multiparty additive scheme that is cryptography-free. We designed our solution for horizontally partitioned data. Moreover, we demonstrate that our scheme resists against adversaries passive model.

Introduction

Over the last years, world's generated data have grown in their scope and size, shifting from centralized processing to distributed environments, and leading so to the big data era. Big data is a term used to designate large or complex data sets that are beyond the ability of traditional data processing and methods. The emergence of big data sets have created exciting opportunities to maximize the knowledge available for analysts, researchers and business people, allowing to integrate big data analytics in decision making by uncovering hidden patterns, unknown correlations and other insights.

Moreover, big data analytics is performed throw several advanced data mining techniques such as clustering. This analysis task consists of discovering patterns from a set of data objects, then affecting each object to the closest pattern. Working on automating such a task has produced several methods known as unsupervised learning [START_REF] Hastie | Unsupervised learning[END_REF] such as k-means algorithm [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF]. Indeed, big data clustering is now a keystone requirement for several areas of life like healthcare, social science, business and marketing. For instance, in cancer diagnosis we can take known samples of cancerous and non-cancerous data sets and apply clustering algorithms over patients' medical records (PMR) to identify cancerous data [START_REF] Wang | A comparison of fuzzy and nonfuzzy clustering techniques in cancer diagnosis[END_REF], [START_REF] Girolami | Probability density estimation from optimally condensed data samples[END_REF]. For this, maximizing the number of sample sets by establishing a collaboration between several hospitals may significantly improve the accuracy of the results. Another practical scenario may consist of different telephone companies that need to set up towers in a common region they acquired. The optimum location of these common towers can be found through clustering algorithms so as to maximize the signal strength for each network's users. In social network analysis, clustering users' publications may help in recognizing communities with dense friendships internally and sparse friendships externally. Social network clustering can help in designing marketing plans [START_REF] Mishra | Clustering social networks[END_REF], identifying terrorist cells [START_REF] Krebs | Uncloaking terrorist networks[END_REF] and other useful applications. Hence, putting data sets got from different social networks together should deliver more value to the analysis.

Further, the effective integration of big data mining has given rise to privacy issues surrounding disclosing personal private data during analysis process in distributed environments. In fact, personal opinions, political interests, healthcare records and other private data are being shared between institutions and service providers to improve accuracy of the clustering task.

From the perspective of research, many proposed works attempted to reach a partial privacy protection by adding some noise before sharing data [START_REF] Kargupta | On the privacy preserving properties of random data perturbation techniques[END_REF], [START_REF] Bunn | Secure two-party k-means clustering[END_REF], [START_REF] Stanley | Privacy preserving clustering by data transformation[END_REF]. However, the minimum error rate raised by the added noise is intolerable for applications needing a high accuracy level, such as healthcare. From another side other works have implemented homomorphic encryption schemes or oblivious transfert protocols [START_REF] Naor | Oblivious transfer and polynomial evaluation[END_REF] in order to securely share personal data for clustering. Nevertheless, these latter security measurements had inevitably result in serious degradation of performance especially for big data sets [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model[END_REF], [START_REF] Lu | Toward efficient and privacy-preserving computing in big data era[END_REF].

In this work, we propose an efficient k-means protocol that aims to ensure total privacy protection under a given security model without using any cryptographic scheme. The contribution of this work can be summarized as follows

•

We present (Π-sum): a privacy-preserving and efficient multiparty additive scheme based on the famous Clifton's secure sum [START_REF] Clifton | Tools for privacy preserving distributed data mining[END_REF] and modified so as to escape the "maximum" barrier assumpted by [START_REF] Clifton | Tools for privacy preserving distributed data mining[END_REF].

•

We sketch (sk-means): a secure implementation of the k-means algorithm over horizontally partionned data and based on Π-sum.

•

We evaluate the security of our proposals using the real/ideal standard paradigm [START_REF] Canetti | Security and composition of multiparty cryptographic protocols[END_REF] and we proof their performance efficiency compared to other methods through different experimental tests.

The rest of the paper is organized as follows. In section 2 we present preliminaries and notations used to introduce our proposals. In section 3 we highlight the privacy concern in k-means process and we present two privacy-peserving protocols in order to efficiently tackle this issue. In section 4 we give a formal security proof of our solution using the real/ideal paradigm and we devote section 5 to the performance analysis through different experiments. We give a literature survey of related works in section 6 and we conclude by summarizing the contributions this work.

Preliminaries & terminology

In this section we introduce preliminaries and notations used later to implement and analyse our proposal.

k-means clustering algorithm

Recall that data clustering is a task of data mining that consists of partitioning a collection of data sets into separated groups called clusters in a way that maximizes the similarity of the objects in each cluster. Euclidian distance and cosine similarity [START_REF] Strehl | Impact of similarity measures on web-page clustering[END_REF] are some metrics used to evaluate similarity between objects in a cluster. K-means [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF] is one of the most widely used algorithm [START_REF] Anil | Data clustering: 50 years beyond k-means[END_REF] to produce automatically k clusters from a collection of data sets in a simple way. A brief description of k-means implementation is presented in Algorithm1. Assign each data entity to the closest cluster center c i .

4:

Replace each cluster center c i by the mean of the cluster i. 5: until cluster centers do not change.

Big data properties

Big data mining requires additional constraints than traditional data mining tasks in order to better handle its main characteristics, which are illustred in Figure 1.

High volume.

Big data is a great amount of datasets. Thus, using a method which performs a privacy-preserving clustering without inducing a high computation cost is a keystone requirement. 2.2.3. High variety. Big data stores involve data sets of different sizes that originate from several sources. So, we need to address this variety in the big data clustering analysis.

Data distribution model

In a distributed environment, a data store is splitted over sites into multiple units called fragments. data fragmentation can be done in three ways, namely, horizontal, vertical and mixed distributions [START_REF] Navathe | A mixed fragmentation methodology for initial distributed database design[END_REF]. Let S be a set of k data objects (d 1 , ..., d k ) each of which has n attributes (a 1 , ..., a n ) Definition 1. A horizontal distribution produces fragments S i of m i (m i < k) data objetcs each of which has n attributes (a 1 , ..., a n ). Each fragment S i can be get by the selection operation (σ) of the relational algebra using a criterion c i as σ ci (S). Definition 2. A vertical distribution of S produces fragments S i of k data objects (d i 1 , ..., d i k ) having a subset of the n original attributes. Each S i can be get by the projection operation (π) of the relational algebra using a subset of attributes a i (1 ≤ i ≤ n) such as π a1,a2,...,am(m≤n) (S). Definition 3. A mixed distribution of S is obtained using a horizontal distribution followd by a vertical distribution or a vertical destribution followed be a horizontal distribution. Using the precedent examples we can define it in the relational algebra as σ ci (π a1,a2,...,am(m≤n) (S)) or π a1,a2,...,am(m≤n) (σ ci (s)).

In this work, we will propose security for the horizontal distribution model.

Multiparty computation

Let us consider a set of participants that want to jointly compute the value of a public function f relying on their private data. Let P 1 ,...,P n denote the participants and v 1 ,...,v n their private data respectively. We call MPC model the running process of f (v 1 , ..., v n ) [START_REF] Lindell | Secure multiparty computation for privacy-preserving data mining[END_REF]. Let Π denote a multiparty protocol executed by n participants (P 1 ,...,P n ) in order to evaluate the function f and let v denote the set of inputs (v 1 , ..., v n ). We consider n as security parameter and we will give security proof relying on the assumption: n > 2.

Notation 1. Let view Π X (v,n) i denote the set of messages get by the party P i∈{1,...,n} during the execution X of Π on the set of inputs v and security parameter n.

Notation 2. Let out Π X (v,n) i denote the output of the party P i∈{1,...,n} by the execution X of the protocol Π on the set of inputs v and security parameter n. Let out Π X (v,n) denote the global output of all collaborating parties from the same execution of Π, where

out Π X (v, n) = ∪ n i=1 out Π X (v, n) i
In next section, we introduce a novel privacy-preserving clustering protocol built on a secure multiparty additive scheme. We will use these MPC notations later, to prove the security of our proposal.

A novel efficient and privacy-preserving kmeans clustering

Privacy issue in k-means algorithm

In a horizontal distributed environment (see Definition1), sites wanting to participate in a k-means clustering task need to collaborate (see task 4, Algorithm 1) in order to compute means of the clusters that may involve data objects from different sites. Assume a cluster i includes n data objects {d 1 , ..., d n } originating from m sites {P 1 , ..., P m }.

To get the mean of the cluster i (which will be the novel cluster center c i ), participants need to evaluate the following computation

c i = m j=1 ( di∈Pj d i ) m j=1 card(i, j) (1)
where card(i, j) denotes the number of data objetcs originating from the participant P j . This collaborative computation requires from participants to send their sum of data objects (numerator) as well as their cardinalities (denominator) to each other, which may cause a privacy breach when it comes to private data such as medical records. Thus, to preserve privacy in a horizontal distributed k-means execution we will present a privacy-preserving protocol that securely assesses this mean computation (equation ( 1)) based on a simple multiparty additive scheme.

sk-means: a privacy-preserving and efficient kmeans protocol for horizontally partitioned data

Throughout the litterature survey we present later in this paper, only few works ave targeted horizontally partitioned data. Contrary to precedent works [START_REF] Samet | Privacy preserving k-means clustering in multi-party environment[END_REF] that aim to secure the whole fraction (see equation 1), The main idea of our scheme consists of splitting the calcution of each cluster mean into two sum operations (numerator and denominator). Thus, we reduce the need for secure multiparty mean computation to the need for secure multiparty sum. This reduction will induce a high level of efficiency that copes with big data properties. Let us assume m participants {P 1 , ..., P m } in a k-means clustering task, each of which has n i(1≤i≤m) data objects. Let sum(i, j) denote the sum of data objects involved in the cluster i and originating from P j and let card(i, j) denote the number of these data objects. Using the secure mutiparty addition primitive named Π-sum and detailed in section 3. Assign each data object to the closest cluster center c i (Performed by each P j locally).

4:

for (i = 1; i ≤ k; i + +) do 5:

sum 1 ← Π-sum (sum(i, 1), ..., sum(i, m))

6:
sum 2 ← Π-sum (card(i, 1), ..., card(i, m))

7: c i ← sum1 sum2 . 8:
end for 9:

Sharing the novel k cluster centers {c 1 , ...c k }. 10: until cluster centers do not change.

Π-sum: a privacy-preserving and efficient multiparty additive scheme

In what follows we present Π-sum, a privacy-preserving and efficient multiparty sum protocol, which is free from cryptographic operations. Π-sum is built on the secure sum protocol proposed by Clifton et al. [START_REF] Clifton | Tools for privacy preserving distributed data mining[END_REF], working in the same security model that we explore in the next section and having less restrictions on data inputs in order to cope with big data high variety. Assume m parties (P 1 ,...,P m ) having respectively (v 1 ,...,v m ) private values and wanting to evaluate

v = m i=1 v i (2)
Assuming no collusion, Clifton's secure sum [START_REF] Clifton | Tools for privacy preserving distributed data mining[END_REF] operates by hiding v1 with a random number r chosen uniformely from the range [0.

.n] by P 1 , then, sending (r + v 1 mod n)

to P 2 , which adds v 2 and sends the result to P 3 and so on until the end. The protocol could work only under the assumption given in [START_REF] Clifton | Tools for privacy preserving distributed data mining[END_REF] that the value v is known to be in the range [0..n]. This is a hard restriction for big data stores that may involve uncontrollable values. Through Πsum that we present in Algorithm 3, we show that sending a number r randomly chosen from R is sufficient for securing this type of scheme and we prove its security in the next section.

Algorithm 3: Π-sum (v 1 ,...,v m ),
S i ← S i-1 + v i 6:
P i shares S i with P i+1 7: end for 8: P m shares S m with P 1

Step 3 by P 1 9: S 1 ← S m + (v 1 -r) 10: return S 1 in broadcast.

Security analysis

In this section we prove the security of our scheme in a given security model according to the real/ideal simulation paradigm [START_REF] Canetti | Security and composition of multiparty cryptographic protocols[END_REF].

Adversarial model

In multiparty computation, there are two main types of adversaries, namely, passive and active, according to the allowed behaviours of their corrupted participants in the computation [START_REF] Lindell | Secure multiparty computation for privacy-preserving data mining[END_REF]. In this work we give security proof against passive adversaries. 4.1.1. Passive adversary. (Also called semi-honest) In this model of adversary, corrupted parties follow the protocol specifications but they are allowed to learn information from the messages they receive during the execution of the protocol.

4.1.2. Active adversary. (Also called malicious) For this model, there are no suppositions on the behaviour of corrupted parties and they are allowed to randomly deviate from the protocol according to the adversary's instructions.

Security model

In this subsection we introduce the real/ideal simlation paradigm [START_REF] Canetti | Security and composition of multiparty cryptographic protocols[END_REF]. Let Π denote a mutipaty protocol executed by m participants (P 1 ,...,P m ) in order to evaluate a function f . Let B denote the class of adversary that may corrupt participants in Π such as B ∈ {active, passive}. Let R and L denote respectively the real and the ideal executions of Π on the set of inputs v and security parameter m.

During a real execution (R) we consider the presence of an adversary denoted A that behaves according to the class B while corrupting a set of participants P i(1≤i≤m) . At the end of R, uncorrupted parties output whatever was specified in Π and the corrupted P i outputs any random functions of their view Π R (v,m) i . During an ideal execution (L) we consider the presence of a trusted incorruptible party denoted T , which receives the set of inputs v from all participants in order to evaluate the function f in the presence of an adversary denoted S. We assume S corrupts the same P i as the adversary A of the correspondant real execution, and behaves according to the same class B before sending inputs to T . By the end of L, uncorrupted participants output what was received from T and the corrupted P i output any random functions of their view Π L (v,m) i . Definition 4. Let Π and f be as above. We consider Π a secure multiparty protocol if for any real adversary A having a class B and attacks the protocol Π, there exists an adversary S in the ideal execution having the same class B and that can emulate any effect achieved by A. Let d ≡ denote the distribution equality. We formalize this security definition as follows

{out Π R (v, m)} d ≡ {out Π L (v, m)} (3)

Real/ideal proof

In what follows we give simulations for real and ideal execution to prove the security of Π-sum prtocol. Then, we deduce the security of sk-means protocol.

Π-sum security proof.

Theorem 1. Assume m (m > 2) participants (P 1 ,...,P m ) having respectively (v 1 ,...,v m ) private values and assuming no collusion. Then, Π-sum (v 1 ,...,v m ) is a secure MPC protocol in the presesence of a passive adversary.

Proof. We consider restricting the adversarial class (B) to passive adversary and that is allowed to corrupt one participant at a time since no collusion is assumed. Let A, S and T be as above. Let Π denote Π-sum protocol and v denote the set of inputs (v 1 ,...,v m ) where v i(1≤i≤m) ∈ R n . In this adversarial model (passive) the simulation is trivial, since any corrupted P i(1≤i≤m) is assumed following Π.

Assume A corrupts a P i(1≤i≤m) , then, S will just handle P i 's input and sends it to T , thereby, completing the simulation. By the end, T performs the sum computation of all received inputs and sends back the result to each participant. The security proof of this simulation relies on four different cases as follows • Case 1: P 1 is corrupted. In this case the views of P 1 are described as follows

view Π R (v, m) 1 = {r, v 1 , v, S 1 , S m } (4) view Π L (v, m) 1 = {r, v 1 , v} (5)
Since we defined the security parameter m > 2, we have according to Π (Algorithm 3)

S m = S m-1 + v m (6)
So, S m will not reveal any information for P 1 since it involves at least two unknowns (S m-1 and v m ). Likewise, S 1 will not involve additional information than the random value r. Then, we can reduce (4) as follows

view Π R (v, m) 1 = {r, v 1 , v} (7)
Thus, according to ( 5) and ( 7), we can deduce

{out Π R (v, m)} d ≡ {out Π L (v, m)} (8)
• Case 2: P 2 is corrupted. In this case the views of P 2 are described as follows

view Π R (v, m) 2 = {v 2 , v, S 1 , S 2 } (9) view Π L (v, m) 2 = {v 2 , v} (10)
As S 1 involves the random value r, then

v = S m -S 1 + v 1 (11)
But, since we define the security parameter m > 2, S 1 will be useless for P 2 to disclose v 1 because (11) will involve at least two unknowns (S m /

∈{1,2}

and v 1 ). Consequently, S 2 will not involve additional information for P 2 . Then, we can reduce [START_REF] Stanley | Privacy preserving clustering by data transformation[END_REF] as follows

view Π R (v, m) 2 = {v 2 , v} (12)
Thus according to [START_REF] Naor | Oblivious transfer and polynomial evaluation[END_REF] and ( 12) we can deduce the same (8).

• Case 3: P m is corrupted. Then, we describe the views of P m as follows

view Π R (v, m) m = {v m , v, S m , S m-1 } (13) view Π L (v, m) m = {v m , v} (14)
But since we defined security parameter m > 2, S m-1 will be other than S 1 , then v = S m -S 1 + v 1 will not reveal any information for S m since S 1 and v 1 are two unknowns. Consequently, S m as well as S m-1 will not include additional information for P m . Thus, we can reduce [START_REF] Clifton | Tools for privacy preserving distributed data mining[END_REF] from S m and S m-1 , then, we deduce the same (8).

• Case 4: P i(2<i<m) is corrupted. In this case the views of P i are described as follows

view Π R (v, m) i = {v i , v, S i , S i-1 } (15) view Π L (v, m) i = {v i , v} (16)
With the same reasoning logic as case 3, we can reduce (15) from S i and S i-1 in ordr to deduce the same [START_REF] Bunn | Secure two-party k-means clustering[END_REF].

Throughout these possible corruption cases, we have proved that any information that can be output (learned) by a corrupted participant P i(1≤i≤m) in a real execution of Π-sum can also be output (learned) in ideal execution according to the passive adversarial model.

Note 1. Notice that we have not considered outputs of uncorrupted parties during the security proof of the diferent cases, because they are never affected in the passive adversarial model.

sk-means security proof.

Corollary 1. Assume m (m > 2) participants (P 1 ,...,P m ) in a multiparty clustering task and assuming no collusion. Then, running sk-means is a secure MPC in the presence of a passive adversary.

Proof. As the call to Π-sum is the only multiparty task within sk-means (see Algorithm 2), we can deduce the security of sk-means relying on Theorem 1 proved above.

Performance evaluation

In this section we will demonstrate the efficiency of our propsed sk-means protocol thus, its suitability for big data mining.

Simulation model and scenarios

In order to prove the efficiency of the sk-means protocol (Algorithm 2) based on Π-sum (Algorithm 3) we will evaluate the impact of big data volume (number of data objects) and big data variety (size and source of data objects) on sk-means running time and we compare it to the most recent secret sharing-based protocol for horizontally data distribution proposed by Patel et al. [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model[END_REF]. We have avoided to test protocols based on oblivious transfer and homomorphic encryption because of their inadequacy for big data analytics as was reported by different works [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model[END_REF], [START_REF] Lu | Toward efficient and privacy-preserving computing in big data era[END_REF]. For experimental purpose and without loss of generality, we will simulate the computation of only one cluster mean rather than simulating the hole sk-means clustering process.

We assume a cluster i involves m data objects (d 1 ,...,d m ) each of which has the size of n attributes and originating all from s participant sites. For simplicity reason we assume each site has m s data entities involved in the cluster i. We perform three experiments, namely, E1, E2 and E3 in order to evaluate respectively the impact of: a) the number of data objects (m), b) the number of collaborative sites (s) and In figure 2 we plot results of E1, E2 and E3 besides the running time of a native k-means clustering process (without any security measurments) as a reference time. We plot results of comparison with the protocol proposed by Patel [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model[END_REF] in figure 4 and we give more detailed results in table 1 and table 2.

Regarding the evaluation environment, we make each experiment on the same data sets through a simulator built in Python and executed in an Intel i5-2557M CPU running at 1.70 GHz and having a 4 GB of RAM. We stress that despite the low communication cost of our proposal, we are not considering communication costs in comparison.

Results and discussion

Results of E 1 .

In E 1 we attempted to test the impact of big data volume on running time of sk-means compared to the standard k-means. For this, we fixed s and n parameters to 10 and 20 respectively and we vary the number of data entities (m) in the range [100,10000]. Results that are shown in table 1 and illustrated in figure 2a reveal the efficiency of sk-means with an almost constant distance from k-means running time. The overhead rate induced by 2c are showing the efficiency of sk-means with a stable and not significant computation overhead compared to the native k-means.

5.2.4. sk-means vs. Patel et al. [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model[END_REF]. We have compared sk-means running time to the recent privacy-preserving kmeans protocol proposed by Patel et al. [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model[END_REF]. We took data sets of the same size that considered in the evaluation presented in [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model[END_REF] under the assumption that each data attribute is coded in one byte, i.e. each data object requires n bytes. We make comparaison of the computation overhead rate of the two protocols with respect to the native k-means protocol. We note that we have taken evaluation performance of the protocol [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model[END_REF] when executed under the passive adversarial model as reported by Patel et al. [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model using zero knowledge proof[END_REF]. Results that are shown in table 2 and illustrated in figure 4 reveal the high level of efficiency provided by sk-means. We observe that for small data objects, sk-means protocol outperforms [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model[END_REF] by a magnitude of (12×), this outperformance increases with the increase of the size of data objects until reaching (36×). We note that the stable rate of sk-means overhead is due to its independance from the size of data objects, which has been proved through E 2 .

Related works

Privacy preserving data mining methods had been surveyed in different works, we cite as examples Verykos et al. [START_REF] Vassilios S Verykios | State-of-the-art in privacy preserving data mining[END_REF], Vaidya et al. [START_REF] Vaidya | A survey of privacy-preserving methods across vertically partitioned data[END_REF], Aggrawal et al. [START_REF] Charu | A general survey of privacypreserving data mining models and algorithms[END_REF] and a more recent one given by Meskine et al. [START_REF] Meskine | Privacy preserving k-means clustering: a survey research[END_REF]. In this state-of-the art section, we make focus on the privacy protection in the data clustering task performed across k-means algorithm in a distributed environment.

From a literature survey we observe that all proposed works could be classified according to their privacy level into two categories: those proposing a partial privacy protection and others achieving a complete privacy protection.

The first category proceeds by introducing a noise to the shared data [START_REF] Kargupta | On the privacy preserving properties of random data perturbation techniques[END_REF], then, clusters the noisy data with a minimum error rate. Works of Bunn et al. [START_REF] Bunn | Secure two-party k-means clustering[END_REF] and Oliveira et al. [START_REF] Stanley | Privacy preserving clustering by data transformation[END_REF] present some contributions that fall in this category. Even these methods do not induce computation overhead, they are compromising privacy with the trustworthiness of the result. Such a compromise is unacceptable for applications where a complete accuracy or a complete privacy are critical.

The second category attain a complete privacy using three main tools that consist of: oblivious transfer protocols [START_REF] Naor | Oblivious transfer and polynomial evaluation[END_REF], homomorphic cryptosystems and secure sharing schemes. The two first techniques have been largely implemented because of the high level of security they provide.

Vaidya et al. [START_REF] Vaidya | Privacy-preserving k-means clustering over vertically partitioned data[END_REF] gave the first common cited work in which they attempted to secure vertical data distributions. For this, they implemented the secure permutation of Du et al. [START_REF] Du | Privacy-preserving cooperative statistical analysis[END_REF], the Yao's evaluation circuit [START_REF] Yao | How to generate and exchange secrets[END_REF], besides some homomorphic encryption schemes. This pile of primitives resulted in a high computation cost and reduced the scalability of this method for big data sets. Jha et al. [START_REF] Jha | Privacy preserving clustering[END_REF] proposed two protocols for vertically partitioned data based on oblivious polynomial evaluation [START_REF] Naor | Oblivious transfer and polynomial evaluation[END_REF] and homomorphic encryption schemes. Each of these techniques has a high communication and computation cost when executed on large datasets [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model[END_REF], [START_REF] Meskine | Privacy preserving k-means clustering: a survey research[END_REF], in addition, they operate only on two parties and can not be extended for multiple participants. Contrary to precedent works, Jaganhatan et al. [START_REF] Jagannathan | Privacy-preserving distributed k-means clustering over arbitrarily partitioned data[END_REF] targeted mixed partitioned data by using the Yao's circuit and the secure scalar product [START_REF] Goethals | On private scalar product computation for privacy-preserving data mining[END_REF]. Because they used these security subroutines expensively [START_REF] Meskine | Privacy preserving k-means clustering: a survey research[END_REF] their method seems to be impractical for big data sets. Bunn et al. [START_REF] Bunn | Secure two-party k-means clustering[END_REF] proposed a more efficient protocol for mixed data distributions. Yet, they implement some time expensive operations such as the Paillier cryptosystems [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. Samet et al. [START_REF] Samet | Privacy preserving k-means clustering in multi-party environment[END_REF] proposed two protocols for both vertically and horizontally data distributions. They implement a secure multi-party addition primitive and present an application example for two or more parties. Nonetheless, we can simply demonstrate that any multiparty addition scheme is unsecure for two-party execution because of the bijective property of the addition (a participant secret can be got from the result by subtracting the local value).

Furthermore, few solutions have been proposed based on secure sharing paradigm. Doganay et al. [START_REF] Mahir Can Doganay | Distributed privacy preserving k-means clustering with additive secret sharing[END_REF], Upmanyu et al. [START_REF] Upmanyu | Efficient privacy preserving k-means clustering[END_REF] and Jinwala et al. [START_REF] Neha | Privacy preserving using distributed k means clustering for arbitrarily partitioned data[END_REF] are almost the only works that belong to this category. They proposed different protocols based on some secure sharing schemes in order to preserve privacy under a semi-honest model of adversaries. Recently, Patel et al. [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model[END_REF] proposed a privacy protection that resists to malicious adversaries based on the shamir's secret sharing scheme [START_REF] Shamir | How to share a secret[END_REF].

By summarizing we can deduce the lack of techniques that can provide a complete privacy while remaining efficient to cope with big data properties. It has been proved [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model[END_REF], [START_REF] Lu | Toward efficient and privacy-preserving computing in big data era[END_REF] that encryption-based techniques are not suitable for big data sets while the secret sharing schemes are more promising for mining large datasets because of their low and efficient computation and communication costs [START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model[END_REF].

In this paper we presented a simple, efficient and privacy-preserving k-means protocol based on a multiparty additive scheme. We targeted horizontally partitioned data under the passive adversarial model and we tackle the problem of big data high requirements in an efficient way.

Conclusion

In this paper we proposed sk-means: a novel efficient and privacy-preserving protocol for k-means clustering founded heaviliy on a secure and simple multiparty additive protocol named Π-sum. Through different evaluations we proved the security of sk-means and Π-sum as well as their simplicity and efficiency compared to other propositions. These preliminary results demonstrate that our solution suites better to big data properties and scales to large data sets as shown in experimental tests where we demonstrate that performance (computation overheades) of our solution is independent from data entity sizes and the induced computation overhead does not exceed the ratio of (1.0x) of the native kmeans, yet providing privacy-preserving of cluster centers computation.

Algorithm 1 :

 1 k-means clustering 1: Randomly select k cluster centers {c 1 , ...c k } . 2: repeat 3:

Figure 1 .

 1 Figure 1. Big data main characteristics: volume, variety and velocity 2.2.2. High velocity. Big data are subjected to a high velocity stream of input and output queries which requires in some contexts real time interactions. Thus, introducing privacy preserving mechanisms should not induce unaffordable computation overhead.

Figure 2 .Figure 3 .

 23 Figure 2. Impact of (m), (S) and (n) parameters on the running time of sk-means protocol compared to the native k-means execution

  3, we present sk-means, a secure k-means protocol implemented in Algorithm 2.

	Algorithm 2: sk-means, a privacy-preserving and ef-
	ficient k-means protocol
	Variables:

k: number of clusters m: number of participants i: the cluster index sum(i, j): sum of data objects of P j involved in the cluster i card(i, j): number of data objects of P j involved in the cluster i 1: Randomly select k cluster centers {c 1 , ...c k }. 2: repeat 3:

  a privacy-preserving and efficient multiparty addition Input : v i : the private value of P i , v i(1≤i≤m) ∈ R n m: the number of participant parties S i : the secret of P i r: random variable ∈ R n generated by P 1 Output: v = Generates a random r ∈ R n 2: S 1 ← r 3: P 1 shares S 1 with P 2 Step 2 by ∪ m i=2 P i 4: for i = 2 to m -1 do

	Step 1 by P 1	k i=1 vi
	1: 5:

Table 1 .

 1 EXPERIMENTAL EVALUATION RESULTS

	Data entities number (m)	100	1000	5000	10000
	with s=10 and n=20
	k-means running time (second)	0.0016	0.017	0.081	0.157
	sk-means running time (second)	0.0017	0.018	0.082	0.159
	Ratio	1.06	1.06	1.01	1.01
	Number of sites (S)	20	150	200	250
	with m=10000 and n=20
	k-means running time (second)	0.17	0.17	0.17	0.17
	sk-means running time (second)	0.170	0.173	0.177	0.177
	Ratio	1	1.01	1.04	1.04
	Dimension of data entities (n)	50	100	500	5000
	with s= 10 and m=1000
	k-means running time (second)	0.016	0.017	0.018	0.026
	sk-means running time (second)	0.017	0.018	0.019	0.028
	Ratio	1.06	1.06	1.06	1.07

Table 2 .

 2 Results of E 2 . Through E 2 we have evaluated the impact of big data variety in data sources on running time of k-means and sk-means. To do this, we varied the number of participant sites (s) in the range[START_REF] Patel | Privacy preserving distributed k-means clustering in malicious model using zero knowledge proof[END_REF]600] and we fixed m and n to 10000 and 20 respectively. Results that are presented in table 1 and illustrated in figure2breveal the efficiency of sk-means with an almost constant distance from k-means. Augmenting s has no effect on sk-means running time because in the Π-sum protocol, random number (r) is generated once only by the participant P 1 . The augmentation in sk-means running time observed is due to running environment and it is not significant, hence, the overhead rate induced by sk-means is still stable in the neiberhood of (1.0x) × (k-means running time).5.2.3.Results of E 3 . In E 3 we aimed to evaluate the impact of big data variety in objects' size. We fixed m and s to 1000 and 10 respectiveley and we have varied the size of data objects (n) in the range[50,10000]. Results shown in table 1 and illustrated in figure

	Data size (Kb)	2	25	82
	S Patel [11] computation overhead (%)	77.26	226.23	229.05
	sk-means computation overhead (%)	6.25	6.25	6.25
	sk-means remains stable in the neiberhood of (1.0x) × (k-
	means running time).
	5.2.2.

RUNNING TIME PERCENTAGE INCREASE WITH RESPECT TO K-MEANS