Anicet Beauvais

Ferricrete biochemical degradation on the rainforest-savannas 1 boundary of Central African Republic 2 3

Keywords: Biochemical weathering, Ferricrete, Bauxitization, Termites, Central 62 African Republic 63 1. Introduction

In southeastern Central African Republic the lateritic weathering mantles are 40 capped by two to five meters thick ferricretes, which previously formed under a 41 seasonal tropical climate. The actual humid tropical climatic conditions result in the 42 biophysical disaggregation of the ferricretes everywhere the forest develop that lead to a 43 soil formation composed of ferricrete relicts and ferruginous nodules embedded in a soft 44 bioturbated micro-aggregated clay-ferruginous matrix. The potential effect of the 45 biological activity (e.g., termites) on the soil and vegetation dynamics and therefore on 46 the evolution of the previous consolidated ferricrete is discussed. Following its 47 mechanical disaggregation by the forest tree roots, the ferricrete underwent a chemical 48 degradation under the combined effect of hydration and redox conditions, which result 49 from the biodegradation and oxidation of the organic matter. The transformation of the 50 ferricrete into a soft bioturbated micro-aggregated clay-ferruginous soil matrix implies 51 the hematite dissolution, and the kaolinite transformation into gibbsite, which may 52 characterize a late "bauxitization" (secondary gibbsitization of kaolinite) of previous 53 ferricrete profiles linked to a late Quaternary environmental (climate and vegetation) 54 change. However, the geochemical and mineralogical pattern of the matrix not only 55 reflects the geochemistry of the parental ferricrete but also depends on the physical 56 transfers of quartz and heavy minerals from the lower horizons of the profile. Hence, 57 the use of geochemical indexes such as Ti and/or Zr for mass balance calculations in the 58 lateritic weathering profiles is precluded because these supposedly inert chemical 59 elements are not simply accumulated by in situ chemical weathering process. 60

 1) by comparing the main geochemical outlines of an undisturbed 91 ferricrete profile and a disaggregated ferricrete horizon, and (2) by defining the 92 geochemical differentiation pattern of two disaggregated ferricrete horizons at the top of 93 lateritic weathering profiles profile developed upon different parent rocks. The 94 biophysical and geochemical processes involved in the ferricrete degradation are 95 discussed. In particular, the potential role of the biological activity (e.g., termites) on the 96 degradation processes of previous undisturbed ferricrete profiles is approached. 97 98 2. Field description 99 100

The study area ("Haut Mbomou") is located in southeastern Central African 101 Republic (CAR) (Fig. 1a). The climate is humid seasonal tropical with a dry season 102 from December to February and a mean annual rainfall of 1600 mm (Fig. 1a), a mean 103 annual temperature of 25°C and a mean annual relative humidity of the air of 80%. The 104 southern part of CAR hosts forests belonging to the Congo-Guinean domain (Sillans, 105 1958), where Terminalia superba, Albizia zygia, Triplochiton scleroxylon and Celtis sp. 106 are the main identified species [START_REF] Boulvert | Carte phytogéographique de la République Centrafricaine à 1: 1.000.000. 494 feuille Ouest, feuille[END_REF][START_REF] Beauvais | Paléoclimats et dynamique d'un paysage cuirassé du Centrafrique. 474 Morphologie[END_REF]. 107

The vegetation of the study area is a mosaic of grass savanna interspersed with 108 patches of dense rain forest. About 79.3 % of the total landsurface of the previous 109 mapped area (545 km 2 ) are covered by grass savanna where consolidated ferricrete is 110 outcropping on plateaus and hillslopes, while the rain forest occupies the remaining 111 20.7 % where the ferricrete is disaggregated resulting in the formation of dismantled 112 ferricrete soils [START_REF] Beauvais | Petrological differentiation patterns and geomorphic 487 distribution of ferricretes in Central Africa[END_REF]Fig. 1b). The extension of forest against 113 savanna in the Mbomou area was dated from the Holocene period using C isotopic 114 analyses of organic matter in soils and alluvial sediments [START_REF] Runge | Holocene landscape history and palaeohydrology evidenced by stable carbon 572 isotope  13 C analysis of alluvial sediments in the Mbari valley (5° N/ 23° E), Central 573 African Republic[END_REF] that also 115 characterize a climatic change towards more humidity. A semi-humid forest with Anogeissus leiocarpus and Albizia zygia effectively develops around the highest 117 plateaus (10.6% of the total surface) at a topographic slope gradient change (Fig. 1c), 118 while a Guinean selvage forest with Triplochiton scleroxylon and Celtis sp. occupies 119 relatively incised thalwegs (10.1% of the total surface). A Soudano-Guinean savanna 120 with Daniella oliveri and Terminalia glaucescens alternates with Graminaceae such as 121

Ctenium newtonii and Loudetia annua [START_REF] Sillans | Les savanes de l'Afrique Centrale[END_REF], where ferricrete effectively 122 outcrops on the plateaus [START_REF] Boulvert | Carte phytogéographique de la République Centrafricaine à 1: 1.000.000. 494 feuille Ouest, feuille[END_REF][START_REF] Beauvais | Paléoclimats et dynamique d'un paysage cuirassé du Centrafrique. 474 Morphologie[END_REF]. 123

The degradation processes of the ferricrete are investigated on vertical profiles located 124 in the forested transition area between the high plateaus and the bare hillslope (Figs. 1b 125 and 1c), which carry massive or protonodular and protopisolitic ferricretes, respectively, 126 as previously established from a combined geomorphological and petrological study of 127 the main ferricretes in the "Haut-Mbomou" region [START_REF] Beauvais | Petrological differentiation patterns and geomorphic 487 distribution of ferricretes in Central Africa[END_REF]. In the 128 "Haut-Mbomou" area, the moderate epeirogenesis resulted in insufficient river incision 129 and erosion that did not allow a clear differentiation of stepped lateritic 130 paleolandsurfaces (bauxitic and ferruginous) like those characterizing the West African 131 landscapes (Eschenbrenner andGrandin, 1970, Michel, 1973;[START_REF] Grandin | Aplanissements cuirassés et enrichissement des gisements de manganese 530 dans quelques regions d'Afrique de l'Ouest[END_REF]; see also 132 [START_REF] Beauvais | Analysis of 484 poorly stratified lateritic terrains overlying a granitic bedrock in West Africa[END_REF]. The long-term (Cenozoic) climatic change gradient was higher in 133 West Africa than in CAR [START_REF] Tardy | Dérive des continents, Paléoclimats et altérations tropicales[END_REF]. Paleoclimates evolved from humid 134 to dry in West Africa, and from arid to seasonal humid tropical in CAR that led to 135 continuous ferricrete formation during Tertiary [START_REF] Beauvais | Paléoclimats et dynamique d'un paysage cuirassé du Centrafrique. 474 Morphologie[END_REF]Beauvais and Colin, 136 1993;[START_REF] Tardy | Dérive des continents, Paléoclimats et altérations tropicales[END_REF] instead of successive development of bauxite and 137 ferruginous glacis (pediments). However, the high plateaus and hillslopes or low 138 plateaus of the "Haut-Mbomou" could be analogous of the West African intermediary 139 and high glacis landsurfaces, respectively [START_REF] Boulvert | Etude géomorphologique de la République Centrafricaine. Notice 496 explicative de la carte à 1/1 000 000[END_REF].

The "Haut-Mbomou" landscape is also characterized by "mushroom" termite 141 mounds of Cubitermes fungifaber, which are systematically erected on gently sloping 142 surfaces bearing a ferricrete (Fig. 3a), called "lakéré" [START_REF] Sillans | Les savanes de l'Afrique Centrale[END_REF][START_REF] Boulvert | Carte phytogéographique de la République Centrafricaine à 1: 1.000.000. 494 feuille Ouest, feuille[END_REF]. 143 [START_REF] Runge | Bioturbation by termites and late quaternary landscape 575 evolution on the Mbomou plateau of the Central African Republic (CAR)[END_REF] counted five to six hundred termite mounds per hectare for 144 an area of 75,000 km 2 (Mbomou plateau) that imply a denudation rate of 0.1 mm.ha - 145 1 .year -1 corresponding to 0.94 t. ha -1 .year -1 of material removed by termites from the 146 lower weathered horizons (saprolite and mottled clays). This material is therefore 147 available for surface runoff erosion and dispersion over the outcropping ferricretes (Fig. 148 3b) that may favor the forest growth at the expenses of savanna under humid tropical 149 climatic conditions. 150 151

Material and analytical techniques 152 153

The degradation patterns of the ferricrete are studied and analyzed in the 154 uppermost-disaggregated parts (1 to 4.5 m) of two vertical lateritic weathering profiles 155 (Figs. 2c and2d) at Guenekoumba and Finzani in southeastern CAR (Figs. 1a). The two 156 vertical profiles are located in the forest fringe (forested hillslope) between the high 157 plateau and the bare hillslope both bearing undisturbed ferricrete profiles (Fig. 1b). The 158 weathering profile of Guenekoumba is developed on amphibole schist (Beauvais and 159 Colin, 1993) while epimetamorphic schist intruded by granite constitutes the parent 160 rocks of the Finzani weathering profile. Based on geological map, the amphibole schist 161 rocks were observed and collected on outcrops and in riverbeds, while the 162 epimetamorphic schist was deduced by the direct observation of saprolites (Beauvais, 163 1991;[START_REF] Beauvais | Formation and transformation processes of iron duricrust 482 systems in tropical humid environment[END_REF]. A typical disaggregated ferricrete horizon is 164 composed of three main components (Fig. 2b to 2d). A first component corresponds to 165 the disaggregated ferricrete of 1-2 to 3 m thickness, which is often affected by horizontal joints (Fig. 2c and2d), the edges of which being overlain by lamellar 167 goethitic brown secondary deposits. Decimetric and metric fragments and blocks of 168 ferricrete characterize this sub-horizon. The second component is composed of 169 hematitic ferruginous nodules and clasts of ferricrete of size ranging between 1 and 10 170 cm. This sub-horizon can also contain some humus in its uppermost part. The nodules 171 are larger at the top than at the base of the horizon. The third component consists of the 172 bioturbated micro-aggregated clay-ferruginous matrix, in which the nodules and clasts 173 of ferricrete are embedded and the biological activity is highly developed (Fig. 2b). 174

Fifty-three samples and sub-samples were collected between 0 and 4.5 meters 175 (Figs. 2c and2d): thirty-three samples for Guenekoumba (15 ferricrete relicts, 9 nodules 176 and 9 matrices) and twenty samples for Finzani (6 ferricrete relicts, 6 nodules and 7 177 matrices). Subsamples of nodules and matrices were extracted from a same sample. 178 XRD was used to determine the mineral composition of each sample category, i.e., 179 the quantity of quartz, kaolinite, gibbsite, hematite and goethite. Mineral contents were 180 estimated by measuring characteristic intensity of X-ray peak weighted by a calibration 181 coefficient defined for each mineral, using normative calculations [START_REF] Mazaltarim | Géochimie des cuirasses ferrugineuses et bauxitiques de l'Afrique de 546 l[END_REF]. 182

The estimation error ranges from 1 to 3 %. Each sample was therefore defined by five 183 mineralogical variables, corresponding to the estimated contents of kaolinite (Ka), 184 quartz (Q), gibbsite (Gi), goethite (Go), hematite (He), and also by the ratios, RGH 185 equal to 100 * goethite/(goethite + hematite), and RKGi equal to 100 * 186 kaolinite/(gibbsite + kaolinite) as defined by [START_REF] Beauvais | Petrological differentiation patterns and geomorphic 487 distribution of ferricretes in Central Africa[END_REF]. Scanning 187 electron microscopy has been also used to define the crystalline morphology of the main 188 mineral phases for each ferricrete degradation component. 189

Spark emission spectrometry has provided chemical composition for major 190 elements, Si, Al, Fe, Mn, Mg, K, Ti, P. Inductively coupled plasma atomic emission spectrometry (ICP-AES) was used to dose the trace elements, Sr, Ba, V, Ni,Co,Cr,Zn,192 Cu,Sc,Y,Zr,La,Ce,Yb,Nb. 193 Mineralogical and chemical data were statistically analyzed by a principal component 194 analysis (PCA) using StatView F-4.5 (1995) that allowed differentiation of the main 195 geochemical patterns of each sample category. The eigenvectors are first determined with 196 their associated Eigen values from the correlation matrix, followed here by an application of 197 the orthogonal Varimax rotation procedure [START_REF] Lebart | Traitement des données statistiques[END_REF]. The principal components 198 (factorial axes) describe the main differentiation trends in the data set. These independent 199 synthetic variables are characterized by correlation loadings with chemical elements and 200 minerals, as previously applied to tropical soils [START_REF] Litaor | Factor analysis of a lithosequence in the 540 northeastern Samaria steppe (Israel)[END_REF][START_REF] Donkin | Factor analysis of familiar properties of some Natal soils 519 with potential for afforestation[END_REF], 201 bauxitic weathering profiles and ferricretes regional distribution [START_REF] Boski | Trace elements and their relation to the mineral phases in the 492 lateritic bauxites from southeast Guinea-Bissau[END_REF]202 Roquin et al., 1990;[START_REF] Beauvais | Petrological differentiation patterns and geomorphic 487 distribution of ferricretes in Central Africa[END_REF]. Within each factor, the correlation loadings 203 ranging from -0.4 to 0.4 were considered as non-significant regarding to the samples number. The formation processes of undisturbed lateritic weathering profiles (Fig. 2a) were 214 previously studied [START_REF] Beauvais | Formation and transformation processes of iron duricrust 482 systems in tropical humid environment[END_REF][START_REF] Beauvais | Geochemical balance of lateritization processes and climatic 476 signatures in weathering profiles overlain by ferricrete in Central Africa[END_REF]. The present study horizon have the same petrographical fabric as the ferricrete. However, many nodules 218 exhibit peripheral goethite brown rims (Fig. 4a) composed of many thin crystals, which 219 develop perpendicular to the edge of the hematitic core of the nodules (Fig. 4b). Other 220 nodules previously composed of hematite and kaolinite [START_REF] Beauvais | Geochemical balance of lateritization processes and climatic 476 signatures in weathering profiles overlain by ferricrete in Central Africa[END_REF] show gibbsite 221 crystals formed at the expense of the kaolinite (Fig. 5a). Secondary gibbsite crystals of 222 10m size are also observed within vacuolar voids of 20 to 50 m sizes (Fig. 5b). The 223 bioturbated micro-aggregated clay ferruginous matrix is also characterized by the 224 formation of smaller size (2m) gibbsite crystals within the vacuolar and tubular 225 porosity (Fig. 6a and6b). This gibbsite is not inherited but comes from the process of 226 ferricrete transformation, contemporaneously with the secondary gibbsite forming in the 227 kaolinitic saprolite of undisturbed profiles [START_REF] Beauvais | Formation and transformation processes of iron duricrust 482 systems in tropical humid environment[END_REF][START_REF] Beauvais | Geochemical balance of lateritization processes and climatic 476 signatures in weathering profiles overlain by ferricrete in Central Africa[END_REF]. 228

The degradation matrix also contains small size (10 m) quartz gains (Fig. 6c and6d), 229 which may be mechanically transferred from other parts of the profile through the 230 termite activity [START_REF] Eschenbrenner | Contribution des termites à la microagrégation des sols tropicaux. 521[END_REF][START_REF] Tardy | Petrology of laterites and tropoical soils[END_REF][START_REF] Thomas | Geomorphology in the tropics. A study of weathering and denudation in 592 low latitudes[END_REF]. 231 232

Undisturbed versus disaggregated ferricrete profile 233 234

A comparison between a previously studied undisturbed lateritic weathering profile with 235 consolidated ferricrete [START_REF] Beauvais | Formation and transformation processes of iron duricrust 482 systems in tropical humid environment[END_REF] and the disaggregated ferricrete horizon of 236 an adjacent profile in the Guenekoumba site (Figs. 2a,2b and 2c) allows differentiation 237 between the advancing ferruginization and the geochemical degradation of ferricretes. The 238 development of the undisturbed weathering profile is a function of two complementary 239 processes: saprolitization and ferruginization [START_REF] Beauvais | Formation and transformation processes of iron duricrust 482 systems in tropical humid environment[END_REF], during which iron 240 first increases by relative accumulation (saprolitization) and secondly by absolute 241 accumulation that leads to the ferricrete development [START_REF] Beauvais | Geochemical balance of lateritization processes and climatic 476 signatures in weathering profiles overlain by ferricrete in Central Africa[END_REF]. These processes are 242 characterized by analyzing the behavior of Fe against Sc [START_REF] Brown | Robust geochemical indices for redox and 503 weathering on a granitic laterite landscape in Central Uganda[END_REF]. Except for the absolute Fe depletion due to local reduction process in the saprolite, Fe and Sc increase in 244 same proportions (relative Fe accumulation) during the first stage of in situ rock chemical 245 weathering. However, Fe and Sc show a more contrasted behavior during the ferruginization 246 process driven by oxidation processes that lead to the development of the soft nodular and 247 ferricrete horizons by absolute Fe accumulation (Fig. 7a). 248

The ferricrete geochemical degradation first leads to a decrease of Sc compared to 249 the ferricrete of the undisturbed profile, then to a decrease of Fe with approximately 250 constant Sc (Fig. 7a). The nodules of the disaggregated horizon are richer in Fe than the 251 nodules of the soft nodular layer underlying the ferricrete of the undisturbed profile. 252

The first effectively derive from the physical disaggregation and geochemical 253 degradation of the ferricrete, whereas the second are advanced ferruginized forms of 254 mottled clays [START_REF] Tardy | Geochemistry of laterites, stability of Al-goethite, Al-hematite 581 and Fe 3+ -kaolinite in bauxites and ferricretes : an approach to the mechanism of concretion 582 formation[END_REF][START_REF] Nahon | Evolution of iron crust in tropical landscapes[END_REF][START_REF] Nahon | Introduction of the petrology of soils and chemical weathering[END_REF][START_REF] Tardy | Petrology of laterites and tropoical soils[END_REF]. The matrices 255 of the disaggregated ferricrete horizon show less Sc content than the saprolite and the 256 mottled clays of the undisturbed ferricrete profile (Fig. 7a). These matrices are also 257 enriched in Zr and Si (Quartz), and show similar Ti contents as the saprolite and mottled 258 clays of the undisturbed ferricrete profile (Figs. 7b-d). Ti and Zr are not correlated in 259 the undisturbed profile while they co-vary in the disaggregated ferricrete horizon (Fig. 260 7d). They may relatively enrich from the ferricrete degradation or absolutely 261 accumulate by some mechanical transfer from other parts of the profile. 262

A principal component analysis of the geochemical and mineralogical data of the 263 undisturbed and disaggregated profiles yields four factorial axes describing 75.2% of 264 the total variance (Table 1). The first factorial axis (37.3 % of the total variance) 265 discriminates the saprolitization with its residual parent rock mineralogical inheritage 266 (quartz + heavy minerals) from the advancing ferruginization (hematite and goethite) 267 processes (Fig. 8). The second factorial axis (23.6 % of the total variance) characterizes the ferricrete degradation by discriminating the clay-ferruginous matrices from the 269 ferricrete relicts and nodules (Fig. 8). The figure 8 also shows the differentiation of the 270 degradation matrices from the saprolite and mottled clays of the undisturbed ferricrete 271 profile. Compared to the parental ferricretes the degradation matrices are enriched in 272 quartz, gibbsite and heavy minerals and impoverished in iron, hematite and kaolinite. 273

The third factorial axis (7.2 % of the total variance) clearly described the transformation 274 of kaolinite into gibbsite in the undisturbed ferricrete profile [START_REF] Beauvais | Formation and transformation processes of iron duricrust 482 systems in tropical humid environment[END_REF]) 275 but also in the degradation matrices (Table 1 and Figs. 6a-b) that could characterize the 276 late "bauxitization" (i.e., secondary gibbsitization according to [START_REF] Tardy | Petrology of laterites and tropoical soils[END_REF] of the 277 previous ferricrete profiles. This "bauxitization" may result from the development of 278 the forest at the expenses of savanna linked to a more humid climate since the Holocene 279 (7.5 to 7 ka) [START_REF] Runge | Holocene landscape history and palaeohydrology evidenced by stable carbon 572 isotope  13 C analysis of alluvial sediments in the Mbari valley (5° N/ 23° E), Central 573 African Republic[END_REF]. The fourth factorial axis (7.1 % of the total variance) 280 collates Ce, Ba, Sr and La, which reflect some parent rock geochemical inheritance 281 (Table 1). Secondary minerals such as florencite may also form as it was suggested in 282 similar lateritic weathering profiles of Cameroon [START_REF] Braun | Cerium 498 anomalies in lateritic profiles[END_REF]. Cerianite (Ce-283 oxide) was also identified at the bottom of the soft nodular horizon in the undisturbed 284 ferricrete profile of Guenekoumba [START_REF] Beauvais | Formation and transformation processes of iron duricrust 482 systems in tropical humid environment[END_REF]. 285 286

Geochemical differentiation pattern of two disaggregated ferricrete horizons 287 288

The average geochemical and mineralogical compositions of each ferricrete 289 degradation components (ferricrete elements, nodules and soft matrices) are given in the 290 table 2. The degradation components of the Guenekoumba profile are, on the average, 291 less rich in silica, alumina, MgO, and K 2 O but richer in Fe 2 O 3 , Mn 3 O 4 , TiO 2 and P 2 O 5 292 than those of the Finzani profile. These geochemical differences reflect differences of 293 parent rocks, which are also emphasized by differences in V, Cr, Cu, Zn, Y, Ba, La and Ce contents (Table 2). A relatively high amount of K 2 O and Ba has been noted in the 295 Finzani ferricrete relicts as well as some Mg (Table 2) that may indicate a relatively 296 quick ferruginization of saprolite still embedding poorly weathered micas prior to the 297 hardening of the ferricrete [START_REF] Beauvais | Paléoclimats et dynamique d'un paysage cuirassé du Centrafrique. 474 Morphologie[END_REF][START_REF] Beauvais | Geochemical balance of lateritization processes and climatic 476 signatures in weathering profiles overlain by ferricrete in Central Africa[END_REF]. Therefore, the differences of 298 alumina contents may be explained by the accumulation of relict micas and kaolinite 299 higher in the Finzani profile than in the Guenekoumba profile (Table 2). 300

The geochemical differentiation patterns of each sample category (ferricrete relicts, 301 nodules, and matrix) are also deciphered, by applying a Principal Component Analysis 302 (PCA) to the geochemical and mineralogical data that allows definition of three 303 factorial axes accounting for 76.4 % of the total variance (Table . 3). The first factorial 304 axis (44.1 % of the total variance) discriminates the group (ferricrete relicts + the 305 ferruginous nodules) from the embedding clay-ferruginous matrices (Fig. 9). These 306 latter are enriched in quartz (Figs. 6c-d and10a) and heavy minerals (Fig. 10b) and they 307 are propitious to the development of gibbsite (Figs. 6a-b and11a), which results from 308 the late weathering of micas and/or from the desilification and hydration of kaolinite 309 [START_REF] Beauvais | Petrological differentiation patterns and geomorphic 487 distribution of ferricretes in Central Africa[END_REF]. With quartz, the heavy minerals compose the residual 310 mineral phase, which may be relatively enriched by in situ geochemical degradation of 311 ferricrete containing them (Figs. 9 and 10b) or mechanically transferred with the clay-312 silt materials from other parts of the profile through the termite activity (Tardy and 313 Roquin, 1992). The variation of Zr content in matrices at constant Fe (Fig. 11b) may 314 also suggest, at least partially, an absolute input of small size zircon. Hence, the 315 common use of Ti and Zr for mass balance calculations should be considered with much 316 caution. Zircon may also dissolve in the lateritic geosphere [START_REF] Colin | Zircon: an immobile index in soils ?[END_REF]. Mass 317 balance calculations based on geochemical indexes may be applied for non-perturbed 318 weathering horizons [START_REF] Beauvais | Formation and transformation processes of iron duricrust 482 systems in tropical humid environment[END_REF] but they are inappropriate for quantifying the geochemical mass balance transfers in the upper ferruginous horizons 320 that are bioturbated and often rework allochthomous materials [START_REF] Beauvais | Analysis of 484 poorly stratified lateritic terrains overlying a granitic bedrock in West Africa[END_REF]. 321

The geochemical degradation of the ferricrete therefore leads to a release of Fe 2 O 3 , 322 Sr, Ba, V, and Cr, with an accumulation of silica, alumina, Mn 3 O 4 , MgO, K 2 O and TiO 2 323 in the matrices, and also, Ni, Y, Zr, Yb and Nb. The amounts of P 2 O 5 , and Co, Zn, Cu, 324 Sc, La, and Ce remain relatively constant (Table 2). The increasing of magnesium and 325 potassium in the matrices of degradation profiles may reflect the occurrence of poorly 326 weathered micas as phengites that is indicated by the negative loading of the second 327 factorial axis (20.9 % of the total variance). Previous geochemical analyses of saprolite 328 and mottled clays of Guenekoumba undisturbed profile revealed similar Mg and K 329 contents, which related to poorly weathered relict micas optically identified on thin 330 sections [START_REF] Beauvais | Formation and transformation processes of iron duricrust 482 systems in tropical humid environment[END_REF]. The second factorial axis also characterizes the 331 association of goethite with Cu, TiO 2 , Zn, P 2 O 5 , Mn 3 O 4 , and Sc (Table 3), which may 332 indicate the presence of anatase and/or residual ilmenite in the degradation matrices as 333 previously shown in undisturbed weathering profile [START_REF] Beauvais | Formation and transformation processes of iron duricrust 482 systems in tropical humid environment[END_REF]. The 334 factor 2 therefore discriminates the Ti-rich Guenekoumba degradation profile from the 335 Ba-Mg-K rich Finzani degradation profile (Fig. 9) that suggests incomplete micas 336 dissolution in this profile although a part of the kaolinite may derive from their late 337 weathering in the degradation matrices (Table 2). The third factorial axis (11.4 % of the 338 total variance) discriminates La-Sr-Ce-V from Co-Cu-Sc-Ni that reflects some 339 geochemical dependence to the parent rock. 340 341

Factors of the ferricrete biochemical degradation 342 343

The mechanical disaggregation (tree roots effect) and biochemical degradation of 344 the ferricrete result in the loosening of the ferruginous cements and their bioturbation by burrowing animals such as worms and termites. Termites microdivide the mineralogical 346 assemblages and transfer nutrients and clay-silts from the saprolite to the upper 347 ferruginous horizons and the topsoils [START_REF] Eschenbrenner | Contribution des termites à la microagrégation des sols tropicaux. 521[END_REF][START_REF] Eschenbrenner | Les glèbules des sols de Côte d'Ivoire[END_REF]Gleeson and Poulin, 348 1989;[START_REF] Tardy | Geochemistry and evolution of lateritic landscapes[END_REF][START_REF] Thomas | Geomorphology in the tropics. A study of weathering and denudation in 592 low latitudes[END_REF]. Many topsoils of Central Africa are 349 formed, at least in part, from imported material from deeper horizons by termite activity 350 [START_REF] De Heinzelin | Observations sur la génèse de nappe de gravats dans les sols 514 tropicaux[END_REF][START_REF] De Ploey | Stone-lines and clayey-sandy mantles in lower Congo: their formation and 516 the effect of termites[END_REF]. The termite material may be spread at the ground 351 surface by erosion (Fig. 3b) that effectively contributed to the soil restoration and 352 hillslope forestation [START_REF] Mando | Effects of termites on infiltration into 544 crusted soil[END_REF][START_REF] Runge | Bioturbation by termites and late quaternary landscape 575 evolution on the Mbomou plateau of the Central African Republic (CAR)[END_REF], which are further 353 sustained by the nutrients transferred from the bottom to the top of the profiles 354 [START_REF] Miedema | Variability in the growth 550 of Faidherbia albida near Niamey, Niger, Africa : micromorphological aspects of termite 551 activity[END_REF][START_REF] Berner | Global environment, Water, Air, and Geochemical 489 Cycles[END_REF]. The forest biochemically degrades the 355 ferricrete transforming its main mineralogical constituents [START_REF] Tardy | Geochemistry and evolution of lateritic landscapes[END_REF]356 Birkeland, 1999). Notice that many ferruginous "stone lines" of the tropical forest 357 savanna transition areas may result from the combined termite activity and ferricrete 358 biophysical degradation [START_REF] Eschenbrenner | Contribution des termites à la microagrégation des sols tropicaux. 521[END_REF][START_REF] Eschenbrenner | Les glèbules des sols de Côte d'Ivoire[END_REF]. 359

In spite of the lack of specific biogeochemical data, some interesting idea based on 360 field observations may be discussed before to be tested in future investigations. The 361 increasing biological activity generates bioturbation and aeration of the lateritic 362 weathering profiles by creating channels, chambers and pedotubules that improve the 363 hydrological properties of soils (drainage) and the plants development (Humphreys, 364 1994;[START_REF] Mando | Effects of termites on infiltration into 544 crusted soil[END_REF][START_REF] Runge | Bioturbation by termites and late quaternary landscape 575 evolution on the Mbomou plateau of the Central African Republic (CAR)[END_REF]. The digestion of the organic 365 matter by termites modifies the redox conditions of the vadoze zone. In the lateritic 366 profiles evolving under a forest cover the organic matter biodegradation may result in a 367 degassing of a mixture of carbon monoxide and methane. The occurrences of degassing 368 and water at the bottom of 10 to 15 m thick profiles may have a biogeochemical impact 369 on the geochemical and mineralogical patterns of the lateritic weathering profiles.

Although the gases were not analytically identified, they were highly suspected by acid 371 smells owing to the organic matters decomposition, by experimenting burn rope (CO) 372 and observing termite activity (CH 4 ) at the transition between the saturated and 373 unsaturated zone of profiles (10 to 15 meter depth). Carbon monoxide derives from the 374 partial oxidation of organic matter as: 375 376

CH 2 O + 0.5 O = CO + H 2 O
(1) 377 378 Methane result from the biodegradation of organic matter in termites' guts (Berner and 379 Berner, 1996;[START_REF] Mackenzie | Our changing planet. An introduction to earth system science 542 and global environmental change[END_REF] It would be certainly interesting to analytically characterize the organic species in 392 the degradation matrices and in the solutions draining the disaggregated ferricrete 393 profiles as well as to get C isotopic signatures of the organic matters, soil solutions, and 394 gaseous phases. For instance, the measure of 13 C/ 12 C ratios would be useful to distinguish bacterial from non-bacterial sources of methane [START_REF] Conny | The isotopic characterization of methane, non-methane 512 hydrocarbons and formaldehyde in the troposphere[END_REF]. 396 However, the geochemical degradation of the ferricrete including the transformation of 397 its mineralogical constituents may be primarily controlled by the degree of hydration of 398 the profile [START_REF] Tardy | Petrology of laterites and tropoical soils[END_REF], and by the redox conditions change owing to the 399 biodegradation of organic matters producing H + protons [START_REF] Berner | Global environment, Water, Air, and Geochemical 489 Cycles[END_REF]. 400 401

Mineralogical outcomes of the ferricrete biochemical degradation 402 403

The increasing biological dynamics and soil moisture (pore water activity) therefore 404 result in an increase of gibbsite and in a lesser part goethite with respect to kaolinite and 405 hematite. Goethite content does not significantly increase (Table . 1), but hematite is 406 partly dissolved under the combined effect of redox and hydration process. 407

The organic matter biodegradation (reaction 4) and hydration processes may effectively 408 create the conditions of the disruption of the hematite -kaolinite mineral association 409 according to the following reaction: 410 411

Fe 2 O 3 + Si 2 Al 2 O 5 (OH) 4 + CO 2 + CH 4 + O 2 + 4H 2 O + 3H + 412 = 2Al (OH) 3 + FeOOH + 2HCOOH + 2Si(OH) 4 + Fe 3+ (5) 413 414
The released Fe may be exported towards the lower parts of the profiles and 415 reincorporated in a newly formed ferricrete essentially composed of goethtite (Beauvais, 416 1999), according to local redox conditions also favorable to the formation of Ce and 417 Mn-oxhyhydroxydes [START_REF] Beauvais | Formation and transformation processes of iron duricrust 482 systems in tropical humid environment[END_REF]. 418

The matrices and ferruginous nodules of the Guenekoumba profile are a little more 419 gibbsitic but less kaolinitic than those of the Finzani profile (Figs. 10a and11a).

(Fig. 11a) but the same gibbsite quantities. According to [START_REF] Tardy | Petrology of laterites and tropoical soils[END_REF], the 422 transformation of kaolinite into gibssite is limited in quartz-rich matrices, while this 423 transformation is important in matrices impoverished in quartz. But our results show 424 that relatively high quantities of small size quartz in bioturbated matrices do not preclude the transformation of kaolinite into gibbsite . In tropical soils this transformation is driven by high water activity ([H 2 O] = 1) in 427 large pores [START_REF] Tardy | Petrology of laterites and tropoical soils[END_REF]. Gibbsite effectively derives from kaolinite according to 428 desilification and hydration processes that lead to a decrease of kaolinite in the matrices 429 compared with the contents measured in the ferricrete and nodules (Fig. 11a). However 430 in soils with similar physical chemical properties (porosity, water activity and Eh-pH 431 conditions), the presence of silicates as phengites and quartz maintains relatively high 432 amounts of Si, Al, and (Ba, K, Mg) within the matrices (Table 2) that may limit the 433 transformation of kaolinite into gibbsite (Fig. 10a). This is the case of matrices of the 434 Finzani degradation profile (Fig. 11a) where the quantity of poorly weathered micas 435 inherited from the deeper horizons is higher than in the Guenekoumba profile. 436 Therefore, a part of the kaolinite may derive from the late weathering of micas if the 437 water activity in matrix pores is ≤ 0.9; but hematite could remain stable (Trolard and 438 Tardy, 1987). However, it was previously shown that kaolinite deriving from micas is 439 large and well crystallized and could be a mineralogical tracer of the late ferricrete 440 degradation [START_REF] Beauvais | In situ characterization and differentiation of kaolinites 479 in lateritic weathering profiles using infrared microspectoscopy[END_REF]. Both micas and kaolinite may however 441 transform into gibbsite if the water activity > 0.9 [START_REF] Tardy | Petrology of laterites and tropoical soils[END_REF], and the hematite is 442 dissolved and partly transformed into goethite [START_REF] Trolard | The stabilities of gibbsite, boehmite, aluminous goethites and 594 aluminous hematites in bauxites, ferricretes and laterites as a function of water activity, 595 temperature and particle size[END_REF]. 443 444

Conclusion 445

In transitional humid tropical environments between savanna and rainforest, the 447 degradation of ferricrete previously composed of hematite and kaolinite results in the 448 development of a softer material relatively richer in gibbsite and in a lesser part in 449 goethite. The ferricrete degradation horizon is composed of chemically unsaturated 450 ferricrete relicts and ferruginous nodules embedded in a bioturbated micro-aggregated 451 clay ferruginous matrix. This matrix is also enriched in poorly weathered parent 452 minerals such as micas inherited from lower saprolite, and also with small size quartz 453 and heavy minerals, which may be biomechanically transferred by termites from the 454 lower horizons of the lateritic weathering profiles. The nutrient supplies by termites 455 may sustain the forest recrudescence on previous savanna areas implying the 456 biophysical dismantling and the geochemical degradation of the ferricrete. Such an 457 ecosystem may self-organize according to a positive feedback loop in that, the more 458 humid becomes the climate, the faster the forest grows in area enriched in nutrients 459 imported by termites, the more the ferricrete transforms into a micro-aggregated soil, 460 which sustains the forest development and therefore its destructive effect on the 461 ferricrete. The resulting hydration and biological processes lead to the biodegradation 462 and oxidation of organic matters modifying the redox conditions that also trigger the 463 ferricrete degradation. These processes result in the preferential dissolution of hematite, 464 and the transformation of kaolinite into gibbsite provide the moisture (water activity) be 465 sufficient that may also characterize the late "bauxitization" (Holocene) of previous 466 rectangle represents the previous mapped land area [START_REF] Beauvais | Petrological differentiation patterns and geomorphic 487 distribution of ferricretes in Central Africa[END_REF]601 Beauvais, 1999) Table 1. Correlation of chemical elements and minerals with each orthogonal 651 factorial axis defined by the Principal Component Analysis for the undisturbed 652 Factor score 2 Fig. 9 Beauvais, 2008

  204The projection of samples on factor score diagrams highlights the differentiation patterns 205 within and between each samples category, allowing discussion of the geochemical and 206 mineralogical evolution induced by the development of the weathering and ferruginization 207 and/or the ferricrete degradation process.

  is an IRD (UMR 161 CEREGE) contribution, which was 469 previously supported by the research program PIRAT (INSU-CNRS-ORSTOM). Two 470 anonymous reviewers are thanked for their helpful remarks and suggestions. 471

  Figures caption

Figure 4 .Figure 5 .Figure 6 .Figure 7 .Figure 8 .Figure 9 .Figure 10 .Figure 11 .

 4567891011 . (b) Geomorphic distribution of the different forms of ferricrete. The 602 black square is for the location of the disaggregated-ferricrete profile at Guénékoumba. 603 (c) Geomorphological transect across c shown in (b). 604 605 Figure 2. (a) Sketch of a typical undisturbed profile, (b) Macroscopic patterns of the 606 disaggregated ferricrete, (c) and (d) disaggregated ferricrete profiles of Guenekoumba 607 and Finzani, respectively. The grey and black squares represent the analyzed samples. 608 609 Figure 3. (a) Gently sloping surface (bare hillslope) colonized by termite mounds, (b) 610 Detail of the mounds at the transition between the grassy and forested hillslope (the size 611 of the foreground ferricrete block is 0.5-0.6 m). 612 613 Transformation of a red-black hematite-kaolinite nodule into yellow goethite, 614 (a) Polarised optical microscope view, (b) Scanning electron microscope view (Go = 615 goethite crystals developing perpendicular to the nodule edge; kHe = kaolinite-hematite 616 core of the nodule). 617 618 Transformation of kaolinite into gibbsite in a nodule, (a) Polarised optical 619 microscope view. (b) Scanning electron microscope view. (K= kaolinite; G= Gibbsite). 620 621 Scanning electron micrographs of the bioturbated micro-aggregated clay 622 ferruginous matrix. (a) Microcrystalline newly formed gibbsite, (b) detail of (a), (c) 623 relict quartz grain and (d) relict quartz grain with dissolution-crystallization figures. 624 (kHe = kaolinite-hematite; G = gibbsite; Q = quartz). 626 Geochemical comparison between undisturbed ferricrete profile (grey) and 627 the disaggregated ferricrete horizon (black) of Guenekoumba, (a) Fe vs. Sc, (b) Fe vs. 628 Zr, (c) Si vs. Zr, and (d) Ti vs. Zr, (the dashed line represents the relative accumulation 629 and/or depletion of chemical elements). 630 631 Geochemical differentiation pattern of the components in the undisturbed and 632 disaggregated profiles of Guenekoumba by the factor score diagram Fs1 vs. Fs2, (see 633 the table 1 for the factor loadings, and the figure 7 for the labels explanation). (Af = 634 advancing ferruginization; Fd = ferricrete degradation). 635 636 Geochemical differentiation pattern of the degradation components in the 637 disaggregated ferricrete horizons of Guenekoumba (black) and Finzani (grey) by the 638 factor score diagram Fs1 vs. Fs2, (see the table 3 for the factor loadings, and the figure 639 7 for the labels explanation). 640 641 Comparison between each disaggregated ferricrete profile, (a) quartz content 642 vs. ratio RKGi in the degradation matrices (RKGi = 100 * kaolinite / kaolinite + 643 gibbsite), (b) Ti vs. Zr (see Figures 7 and 9 for labels explanation). 644 645 Comparison between the two disaggregated ferricrete profile (a) kaolinite vs. 646 gibbsite contents, (b) Fe vs. Zr (see Figures 7 and 9 for labels explanation) 647 Tables caption 649 650

  Fig.1

  Figure

Table 1 .

 1

	Figure
	a
	% Kaolinite
	0	10		20	30		40
			% Gibbsite
	b
	Fe, μg.g -1
	100	200	300	400	500	600	700
			Zr, μg.g -1
	Fig. 11
		Beauvais, 2008

Table Click here to download Table: Table. 1.doc

 Click

	Location:		Guenekoumba profile				Finzani profile
		_____________________________________ ______________________________________
	Facies:	Ferricrete	Nodules	Matrices	Ferricrete	Nodules	Matrices
	N:	15		9		9		6		6		7
		m	√	m	√	m	√	m	√	m	√	m	√
	SiO 2 wt.% 14.89 3.35 15.17 3.11 32.83 3.15 21.73 3.94 22.75 2.4	37.87 1.52
	Al 2 O 3	19.21 2.44 17.27 1.15 24.53 1.62 23.47 1.63 21.93 2.2	29.67 1.15
	Fe 2 O 3	52.55 4.38 55.6	4.16 27.03 0.91 42.27 4.06 44.2	4.2	17.03 0.67
	Mn 3 O 4	0.06 0.02	0.04 0.01	0.09 0.02	0.02 0.01	0.03 0	0.05 0.02
	MgO	0.03 0.01	0.04 0.01	0.17 0.07	0.23 0.14	0.22 0.02	0.37 0.02
	K 2 O					0.11 0.02	0.61 0.55	0.46 0.06	0.35 0.08
	TiO 2	2.12 0.15	1.89 0.15	2.93 0.14	1.18 0.17	1.25 0.12	2.12 0.12
	P 2 O 5	0.39 0.06	0.38 0.05	0.25 0.04	0.19 0.03	0.19 0.01	0.18 0.02
	LOI	10.11 1.39	9.27 0.95 11.63 1.45 10.65 0.99	9.11 1.02 12.85 0.35
	Sr ppm	39	32	48	9	18	5	34	20	35	7	21	2
	Ba	32	24	51	14	40	7	223 179	157	19	95	12
	V	1369 280	1298	66	634	29	827 202	757	69	344	14
	Ni	47	19	36	6	78	23	35	10	51	6	79	21
	Co	13	5	11	2	13	4	9	8	16	3	20	4
	Cr	340 142	426 117	155	20	403 157	414	79	91	1
	Zn	52	19	50	5	62	16	34	14	40	8	40	8
	Cu	133	64	121	19	116	29	58	9	75	5	89	5
	Sc	42	6	46	6	37	5	36	3	37	1	40	2
	Y	8	2	8	1	23	2	12	2	12	3	31	2
	Zr	341	60	329	27	530	61	337	40	316	26	513	31
	La	47	39	51	12	23	5	34	12	39	6	33	5
	Ce	114	80	99	27	126	20	62	33	65	18	107	11
	Yb	1	0	1	0	3	0	2	0	2	0.5	4	0
	Nb	18	4	19	2	36	3	16	2	14	3	33	4
	% Quartz	1	1	3	3	25	5	3	2	3	1	22	4
	Kaolinite	31	8	27	7	19	9	40	10	44	3	38	5
	Hematite	41	6	45	5	17	1	33	6	37	4	9	1
	Goethite	16	6	14	3	12	1	12	3	8	1	9	1
	Gibbsite	11	6	11	4	27	5	12	4	8	2	22	5
	RHG	72	10	76	6	57	4	73	8	82	3	52	3
	RKGi	72	14	71	14	41	14	76	10	86	4	63	6

Table 2 .

 2

Table Click here to download Table: Table. 2.doc

 Click

	Factorial	 %	Positive loading	Negative loading
	Axis
			Y (0.95) Yb (0.95)	Fe 2 O 3 (0.94)
			Quartz (0.94) SiO 2 (0.92)	Hematite (0.91)
	F1	44.1	Zr (0.91) Nb (0.90)	V (0.78) Cr (0.74)
			Al 2 O 3 (0.82) Gibbsite (0.78)	P 2 O 5 (0.57) Sr (0.40)
			Ni (0.66) MgO (0.62)
			TiO 2 (0.59) Mn 3 O 4 (0.40)
	F2	20.9	Cu (0.75) TiO 2 (0.75)	K 2 O (0.79) Ba (0.77)
			Zn (0.71) P 2 O 5 (0.69)	kaolinite (0.65)
			Mn 3 O 4 (0.67) Goethite (0.63)	MgO (0.60)
			Sc (0.48)
	F3	11.4	Co (0.59) Cu (0.52) Sc (0.40)	Ce (0.78) La (0.75)
			Ni (0.40)	Sr (0.75) V (0.42)

Table 3 .

 3

Table Click here to download Table: Table. 3.doc

 Click

focuses on the uppermost part (ferricrete) of such profiles, which is apparently

disaggregated and degraded under the forest (Fig.2b). The ferruginous nodules of such


Ge Song
email: ge.song@inria.fr

Justine Rochas

Fabrice Huet
email: fabrice.huet@unice.fr

Frédéric Magoulès
email: frederic.magoules@ecp.fr

Solutions for Processing K Nearest Neighbor Joins for Massive Data on MapReduce

Keywords: kNN Join, Data Partition, Hadoop, MapReduce

Given a point p and a set of points S, the kNN operation finds the k closest points to p in S. It is a computational intensive task with a large range of applications such as knowledge discovery or data mining. However, as the volume and the dimension of data increase, only distributed approaches can perform such costly operation in a reasonable time. Recent works have focused on implementing efficient solutions using the MapReduce programming model because it is suitable for large scale data processing. Also, it can easily be executed in a distributed environment. Although these works provide different solutions to the same problem, each one has particular constraints and properties. There is no readily available comparison to help users choose the one most appropriate for their needs. This is the problem we address in this work. Firstly, we show that all kNN implementations go through a common workflow, which we use as a basis for classification. Secondly, we describe precisely the different techniques published so far. And lastly, we provide a set of objective criteria that can be used to make informed decisions.

I. INTRODUCTION

Given a set of query points R and a set of reference points S, a k nearest neighbor join (hereafter kNN) is an operation which, for each point in R, discovers the k nearest neighbors in S. It is frequently used as a classification or clustering method in machine learning or data mining. It can be applied to a large number of fields, such as multimedia [START_REF] Li | Motion-aware knn laplacian for video matting[END_REF] [2], social network [START_REF] Bai | Collaborative personalized top-k processing[END_REF], time series analysis [START_REF] Rafiei | Similarity-based queries for time series data[END_REF] [START_REF] Agrawal | Efficient similarity search in sequence databases[END_REF], bio-information and medical imagery [START_REF] Inthajak | Medical image blob detection with feature stability and knn classification[END_REF] [START_REF] Korn | Fast nearest neighbor search in medical image databases[END_REF].

The basic idea to compute a kNN is to perform a pairwise computation of distance for each element in R and each element in S. The computational complexity of this pairwise calculation is O(|R| × |S|). Then, finding the k nearest neighbors in S for every r in R boils down to sorting the computed distances, and leads to a complexity of at least |S|×log |S|. As the amount of data or their complexity (number of dimensions) increases, this approach becomes impractical. This is why a lot of work has been dedicated to reducing the kNN computational complexity [START_REF] Jagadish | idistance: An adaptive b + -tree based indexing method for nearest neighbor search[END_REF] [START_REF] Böhm | The k-nearest neighbour join: Turbo charging the kdd process[END_REF] [10] [START_REF] Yu | High-dimensional knn joins with incremental updates[END_REF] [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF].

Although a variety of previous work has greatly improved its performance, there are still significant limitations to process kNN on a single machine when the amount of data increases. For large dataset, only distributed and parallel solutions prove to be powerful enough. MapReduce is a flexible and scalable parallel and distributed programming paradigm which is especially designed for data-intensive processing. It was first introduced by Google [START_REF] Dean | Mapreduce: Simplified data processing on large clusters[END_REF] and popularized with the Hadoop [START_REF]Hadoop[END_REF] framework, an open source implementation. MapReduce offers a programming model adapted to large scale data processing, which can easily be distributed. The framework can be installed on commodity hardware and automatically distribute a MapReduce job over a set of machines. Therefore, it seems to be a good target for computing kNN in a distributed way. However, writing an efficient kNN in MapReduce is challenging. First, classical algorithms have to be redesigned to fit the MapReduce programming model. Second, data partition and distribution strategies have to be carefully designed to limit communications and data transfer. In this paper, we review existing implementations of kNN in MapReduce, focusing on different steps involved in a computation. Other surveys about kNN have been conducted, such as [START_REF] Bhatia | Survey of nearest neighbor techniques[END_REF], [START_REF] Jiang | Survey of improving k-nearestneighbor for classification[END_REF]. In [START_REF] Bhatia | Survey of nearest neighbor techniques[END_REF], the authors only focus on centralized solutions to optimize kNN computation whereas we target distributed solutions. In [START_REF] Jiang | Survey of improving k-nearestneighbor for classification[END_REF], the survey is also oriented towards centralized techniques and is based on a theoretical performance analysis. Our approach is much more high level, though we also provide some details about the performance of the works we study. Overall, our contributions are:

• The decomposition of a distributed kNN computation in different steps.

• An analysis of existing techniques for each step based on load balancing, accuracy and complexity.

• A global comparison which can be used to find the most suitable solution for a given use case.

The rest of the paper is organized as follows. Section II introduces the background about kNN and MapReduce. Section III presents the 3 stages of workflow involved in computing kNN on MapReduce. Section IV analyzes existing implementations from the following points of view: load balancing, accuracy and complexity. Finally, Section V concludes this work.

II. CONTEXT

A. k Nearest Neighbors

A nearest neighbors query consists in finding at most k points in a data set S that are the closest to a considered point r, in a dimensional space d. More formal definitions are as follows: given two data sets R and S in R d , and given r and s, two elements, with r ∈ R and s ∈ S, we have: Definition 1: Let d(r, s) be the distance between r and s. The kNN query of r over S, noted kN N (r, S) is the subset

{s i } ⊆ S (|{s i }| = k), which is the k nearest neighbors of r in S, where ∀ s i ∈ kN N (r, S), ∀ s j ∈ S -kN N (r, S), d(r, s i ) ≤ d(r, s j ).
It is easy to extend the previous definition to a set of query points.

Definition 2:

The kNN join of two datasets R and S, kNN(R S) is: kNN(R S)={(r,kNN(r,S)), ∀ r ∈ R} Depending on the use case, it might not be necessary to find the exact solution of a kNN query, and that is why approximate kNN queries have been introduced. The idea is to have the k th approximate neighbor not far from the k th exact one, as shown in the following definition.

Definition 3:

The (1 + )-approximate kNN query for a query point r in a dataset S, AkN N (r, S) is a set of approximate k nearest neighbors of r from S, if the k th furthest result

s k * satisfies s k * ≤ s k ≤ (1 + )s k * ( > 0) where s k is the exact k th nearest neighbor of r in S.
And as with exact kNN, this definition can be extended to an approximate kNN join.

Definition 4:

The (1 + )-approximate kNN join of two datasets R and S, AkNN(R S) is:

AkNN(R S)={(r,AkNN(r,S)), ∀ r ∈ R}
The basic solution to compute kNN adopts a block nested loop approach, which calculates the distance between every object r i in R and s j in S and sorts the results to find the k smallest. This approach is computational intensive, making it unpractical for large or intricate datasets. Two strategies have been proposed to work out this issue.

The first one consists in reducing the number of distances to compute, by avoiding scanning the whole dataset. This strategy focuses on indexing the data through efficient data structures. For example, a one-dimension index structure, the B + -Tree, is used in [START_REF] Jagadish | idistance: An adaptive b + -tree based indexing method for nearest neighbor search[END_REF] to index distances; [START_REF] Böhm | The k-nearest neighbour join: Turbo charging the kdd process[END_REF] adopts a multipage overlapping index structure R-Tree, whose minimum bound is a rectangle (MBR); [START_REF] Ciaccia | M-tree: An efficient access method for similarity search in metric spaces[END_REF] proposes to use a balanced and dynamic M-Tree to organize the dataset; [START_REF] Yu | High-dimensional knn joins with incremental updates[END_REF] introduces a sphere-tree with a sphere-shaped minimum bound to reduce the number of areas to be searched; [START_REF] Andreica | Sequential and mapreduce-based algorithms for constructing an in-place multidimensional quad-tree index for answering fixed-radius nearest neighbor queries[END_REF] presents a multidimensional quadtree in order to be able to handle large amount of data; and [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF] develops a kd-tree which is a clipping partition method to separate the search space.

However, reducing the searched dataset might not be sufficient. For data in large dimension space, computing the distance might be very costly. That is why a second strategy focuses on projecting the high-dimension dataset onto a lowdimension one, while maintaining the locality relationship between data. Representative efforts refer to LSH (Locality-Sensitive Hashing) [START_REF] Datar | Localitysensitive hashing scheme based on p-stable distributions[END_REF] and Space Filling Curve [START_REF] Yao | K nearest neighbor queries and knn-joins in large relational databases (almost) for free[END_REF]. In these cases, the low-dimension data contain much less information than the high-dimension ones because in most cases, the lowdimension data cannot totally fill the high-dimension space. To keep as much information as possible, the trick is to project the high-dimension data multiple times from different perspectives, producing multiple new datasets. For instance, LSH usually provides many space hashing functions. The space filling curve method also usually needs several shifts of data, to reduce the possibilities of errors in the data locality when projecting.

But with the increasing amount of data, these methods can still not handle kNN computation on a single machine efficiently. Experiments in [START_REF] Arefin | Gpu-fs-knn: A software tool for fast and scalable knn computation using gpus[END_REF] suggest using GPUs to significantly improve the performance of distance computation, but this is still not applicable for large datasets that cannot reasonably be processed on a single machine.

Recent papers have focused on providing efficient distributed implementations. Some of them use ad hoc protocols based on well-known distributed architectures [START_REF] Novak | M-chord: A scalable distributed similarity search structure[END_REF], [START_REF] Haghani | Lsh at large -distributed knn search in high dimensions[END_REF]. But most of them use the MapReduce model as it is naturally adapted for distributed computation, like in [START_REF] Stupar | Rankreduce -processing knearest neighbor queries on top of mapreduce[END_REF]- [START_REF] Zhang | Efficient parallel knn joins for large data in mapreduce[END_REF]. In this paper, we focus on the kNN computing systems based on MapReduce, because such systems can scale with the predictable data growth, and also because the framework on which they are based is widespread.

B. MapReduce

MapReduce [START_REF] Dean | Mapreduce: Simplified data processing on large clusters[END_REF] is a parallel programming model that aims at efficiently processing large datasets. This programming model is based on three concepts: (i) representing data as keyvalue pairs, (ii) defining a map function, and (iii) defining a reduce function. The map function takes key-value pairs as an input, and produces zero or more key-value pairs. Outputs with the same key are gathered together (shuffled) so that key-{list of values} pairs are given to reducers. The reduce function processes all the values associated with a given key. This decomposition enables data parallelism as the only dependency between the output of the maps and input of reduces. In practice, the map and reduce functions can be executed on many machines, leading to a naturally distributed computation. The most famous implementation of this model is the Hadoop framework [START_REF]Hadoop[END_REF] which provides a distributed platform for executing MapReduce jobs.

III. WORKFLOW

In this section, we review the methods that have been used to perform kNN join on MapReduce. Overall, they all share the same workflow, comprised of three stages: (i) data preprocessing (ii) data partitioning and organization and (iii) computation of kNN. We will focus on the following works: the initial (basic, not optimized) idea, which we call H-BkNNJ , and its improvements H-BNLJ (Block Nested Loop Join) and H-BRJ (Block Nested R-Tree Join) in [START_REF] Zhang | Efficient parallel knn joins for large data in mapreduce[END_REF], as well as more advanced solutions such as H-zkNNJ (z-value) in [START_REF] Zhang | Efficient parallel knn joins for large data in mapreduce[END_REF], RankReduce (Locality Sensitive Hashing) in [START_REF] Stupar | Rankreduce -processing knearest neighbor queries on top of mapreduce[END_REF] and PGBJ (Voronoi) in [START_REF] Lu | Efficient processing of k nearest neighbor joins using mapreduce[END_REF].

A. Data Preprocessing

The preprocessing stage aims either at processing the initial dataset to reduce its complexity or produces extra information about the data. It is an optional step, as some algorithms can directly work on the initial data, as H-BkNNJ, H-BNLJ and H-BRJ [START_REF] Zhang | Efficient parallel knn joins for large data in mapreduce[END_REF].

For high-dimensional data, the first pre-processing approach projects data onto low-dimensional ones. One way to reduce the complexity and size of the dataset is to use space-filling curves as shown in [START_REF] Yao | K nearest neighbor queries and knn-joins in large relational databases (almost) for free[END_REF]. The solution consists in mapping high-dimensional data to low-dimensional ones while maintaining the locality relationship between each object with high probability (two elements that are close in a high-dimensional space should remain close in the reduced dimensional space). In [START_REF] Zhang | Efficient parallel knn joins for large data in mapreduce[END_REF], the authors compute the z-value of all data from R and S. The z-value of a data is a one dimensional value that is calculated by interleaving the binary representation of the coordinates from MSB (Most Significant Bit) to LSB (Least Significant Bit). However, the ability of z-value to maintain the relative locality between objects in space is not good enough, especially when the dimension is high. Therefore, in practice, several random shifts of the data are generated, and additional z-values are computed, which aims to improve the accuracy at the cost of computation and space.

Another way to reduce the dimension of data is LSH. In RankReduce [START_REF] Stupar | Rankreduce -processing knearest neighbor queries on top of mapreduce[END_REF], high-dimensional data are projected onto low-dimensional ones using Locality Sensitive Hashing (LSH). The idea is to use a group of locality preserving hash functions to map close points from the original data to the same hash value with high probability. The overall performance of LSH depends on parameter tuning [START_REF] Bawa | Lsh forest: Self-tuning indexes for similarity search[END_REF] which depends on the original dataset. Although it is likely for related objects to have the same hash values, in general, one single hash function cannot guarantee a satisfying accuracy. Often, a group of hash functions is required in order to generate multiple hash tables to reduce the number of collisions for distant objects.

In fact, as the quality of the projection is data dependent, both solutions in [START_REF] Zhang | Efficient parallel knn joins for large data in mapreduce[END_REF] and [START_REF] Stupar | Rankreduce -processing knearest neighbor queries on top of mapreduce[END_REF] duplicate the initial dataset and use different parameters for the projection to end up with several projected datasets. The purpose of this duplication is to alleviate information loss from the initial dataset: having multiple projected datasets enable to isolate potential errors. Overall, those solutions are willing to pay the same computation several times on different projected datasets in trade for the complexity of data.

Another approach consists in selecting leaders in the dataset which will drive the subsequent computation. In PGBJ [START_REF] Lu | Efficient processing of k nearest neighbor joins using mapreduce[END_REF], the preprocessing phase tries to identify pivot points (points that correspond more or less to the barycenter of a cluster of points) in the initial dataset which will lead a partition of the dataset. Thus, it is a primary selection before the partitioning stage. In paper [START_REF] Lu | Efficient processing of k nearest neighbor joins using mapreduce[END_REF], three strategies to select the pivots are described. The "Random Selection" strategy generates a set of samples, and calculates the pairwise distance for every point in the samples, and then sums all the distances together. Then, the sample with the biggest summation of distances will be chosen as set of pivots. This strategy provides good results as long as the sample sets are big enough, to maximize the chance to select points in different clusters. The "Farthest Selection" strategy randomly chooses the first pivot. Then, the farthest point to the first pivot will be chosen as the second pivot, and so on until having the desired number of pivots. This strategy ensures that the distance between each selected point is as large as possible, but it is heavier to process than the previous one, as it requires the computing of a lot of distances. Finally, the "K-Means Selection" applies the traditional k-means method on a data sample to update the centroid of a cell as the new pivot each step, until the pivots do not change. With this strategy, the pivots are ensured to be in the middle of a cluster of points, but it is the heaviest strategy as it needs to converge towards the optimal solution. As we will see in the next section, the quality of pivots has an important impact on the quality of the partitioning.

B. Data Partitioning and Organization

First attempts to compute kNN efficiently in sharedmemory focused on particular data organizations, such that the neighbor set can be pruned and neighbor sorting is performed faster. In the most popular methods, data are usually indexed using a tree structure like B + -Tree [START_REF] Jagadish | idistance: An adaptive b + -tree based indexing method for nearest neighbor search[END_REF] or R-Tree [START_REF] Böhm | The k-nearest neighbour join: Turbo charging the kdd process[END_REF]. But as we target big data, shared-memory centric solutions cannot be easily applied to a shared-nothing platform as MapReduce. Instead, the dataset need to be separated into several sets, called partitions, such that, ideally, each partition is independent from others. It is nonetheless possible to use efficient data structures to improve local searching in a partition.

As in any MapReduce computation, the data partition strategy will strongly impact CPU, network communication and disk usage, which in turn will impact the overall processing time [START_REF] Song | A hadoop mapreduce performance prediction method[END_REF] . The key to improve the performance is to preserve spatial locality of objects when decomposing data for tasks [START_REF] Zhou | Data partitioning for parallel spatial join processing[END_REF]. This means making a coarse clustering in order to produce a reduced set of neighbors that are candidates for the final result. Intuitively, the goal is to have a partitioning of data such as an element in a partition of R will have its nearest neighbors in only one partition of S. More precisely, what we want is:

For every partition R i (∪ i R i = R), find a corresponding partition S j (∪ j S j = S), where

kN N (R i S) = kN N (R i S j ), and, kN N (R S) = kN N (R i S j )
which means that, not only it is possible to compute kNN for each element of R i in a single S j , but also the concatenation of the results for all R i is equal to the global kNN join.

In this section, we present two partition methods that enable to separate the dataset into shared-nothing subsets while preserving locality information.

1) Distance Based Partitioning:

The first partitioning method is based on Voronoi diagram, a method to divide the space into disjoint cells. The main property of this method is that every point in a cell is closer to the pivot of this cell than to any other pivot. Because this method relies on the distance metric, it is naturally used to solve neighborhood problems. More formally, the definition of a Voronoi cell is as follow: Definition 5: Given a set of disjoint pivots: P = {p 1 , p 2 , ..., p i , ..., p n }, the Voronoi Cell of p i (0

< i ≤ n) is: ∀ i = j, V C (p i ) = {p d (p, p i ) ≤ d (p, p j )}.
Paper [START_REF] Lu | Efficient processing of k nearest neighbor joins using mapreduce[END_REF] gives a method to partition the dataset R and S using Voronoi diagram. After having identified the pivots in R (as seen in the preprocessing section -III-A), they compute the distance between every point and the pivots, and put the considered point into the cell of the closest pivot. This will naturally give a partitioning of data. Afterwards, they also Fig. 1: Voronoi based partitioning for pivots P i and P j calculate, for each cell of R, the upper (resp. lower) bound of the partition which corresponds to the sphere determined by the furthest (resp. closest) point (in S) from the pivot in the cell of R. Such bounds enable to quickly find the correct partition S j for a given partition R i . This data partitioning principle is shown in Figure 1 where two pivots P i and P j have been chosen from the dataset.

The main problem of this method is that it requires computing the distance of all elements to the pivots. Also, the distribution of the input data might not be known in advance. Hence, the pivots will have to be recomputed if the data changes, which limits dynamicity. Also, there is no guarantee that all cells will have an equal number of elements because of potential data skew. This can have a negative impact on the overall performance because of load balancing issues.

2) Size Based Partitioning: Another type of partitioning method aims at dividing the data into some equal size partitions while preserving their locality information. [START_REF] Zhang | Efficient parallel knn joins for large data in mapreduce[END_REF] proposes a partitioning strategy based on z-value described in the previous section. In order to make every partition of R have a similar number of objects, a sampling is first performed. They claim that the n quantiles (n is equal to the number of partitions) of the sampling data is an unbiased estimation of the boundary point of each partition, with a standard deviation ≤ |R| ( > 0). After having partitioned R this way, the same sampling strategy is applied to S. For each of the boundary points of all R i , the corresponding k th nearest neighbor is identified in S. These points are then used as boundary points of the corresponding S i . As a consequence, the partitions of S are overlapping such that for any given point in R, all the k nearest neighbors can always be found in a single partition of S. An example of z-value based partition is given in Figure 2. This method is likely to produce a substantially equivalent number of objects in each partition.

Another similar size based partitioning method can be applied for datasets that are preprocessed with Locality Sensitive Hashing, as illustrated in Figure 3. With this method, the elements of R that are projected to LSH(R), are divided into quasi-equal size partitions using a sampling technique. The same technique can be applied to S and LSH(S).

The strategy of partitioning will impact directly the number of tasks and the amount of computation. Distance based methods aim at dividing the close objects together by preselecting some pivots. Size based methods want to separate objects into equal size zones in which the points are ordered. Regarding the implementation, [START_REF] Lu | Efficient processing of k nearest neighbor joins using mapreduce[END_REF] uses a MapReduce job to

C. Computation

The general idea to compute a kNN, is to (i) calculate the distance between r i and s j for all i and all j, and (ii) sort these distances in ascending order to find out the first k results. In MapReduce, the idea is the same except that what is given to a task must be independent in order to ensure correctness without duplicating the whole dataset. The number of MapReduce jobs used for computing and sorting has an impact on the global performance, given the complexity of the computation performed by each task and the amount of data to exchange between them. The preprocessing and partitioning steps can also affect the number of tasks that are further needed by each MapReduce job. In this section, we review the different strategies used to compute and sort distances efficiently using MapReduce. These different strategies can be divided into two categories: the ones using one round of MapReduce job and the ones using two rounds of MapReduce jobs. Then, those categories can be divided into two subcategories: the ones that do not preprocess and partition data before computation and the ones that implement the preprocessing and partitioning steps. We detail all these strategies in the following.

1) One Round of MapReduce Job: Without preprocessing and partitioning. The basic idea (H-BkNNJ) to compute a kNN with MapReduce is to have every Map task process a pair of R i and S j , and perform a block nested loop on them to calculate the distance between r i ∈ R i and s j ∈ S j , ∀ i and j. Note that, without any smart partitioning strategy, every possible blocks of one partition R i from R and S j from S should be calculated, leading to n 2 tasks totally where n is the Fig. 4: Usual workflow of a kNN computation using MapReduce number of partitions of R and S. The output of the Map task is in the form of (id(r i ), list (id(s j ), d (r i , s j ))). The identifier of r i , named id(r i ), is used as a key and the associated value is a list containing the identifier of s j and the computed distance between r i and s j . A reduce task then processes all computed distances for a given r i , and sorts them in ascending order to output the top k results.

With preprocessing and partitioning. To reduce the number of tasks used to calculate the distances, in other words, to reduce the number of pairs formed by R i and S j , PGBJ [START_REF] Lu | Efficient processing of k nearest neighbor joins using mapreduce[END_REF] uses a preprocessing and distance based partitioning strategy, which ensures that each partition R i has only one corresponding partition S i needed to be searched, which reduces the number of tasks to n. Once the blocks of R i and S i identified, they perform the same calculation as in the H-BkNNJ technique. Because of their data organization, they are able to reduce the number of tasks, greatly improving the performance.

In RankReduce [START_REF] Stupar | Rankreduce -processing knearest neighbor queries on top of mapreduce[END_REF] 1 , the authors first preprocess and partition data into buckets using LSH. Their Map function computes the distance of all points in the partition, and then sorts the local distances to output the local k nearest neighbors for each point in the partition, together with their distance in form of (id(r i ), list (id(s j ), d (r i , s j ))). These key-value pairs are then pulled by Reducers where they are sorted and issued as final results.

Overall, the main limitation of these approaches is that the number of values to be sorted in the reduce phase can be extremely large, up to |S|, if the pre-processing and partitioning have not significantly reduced the set of candidate points. This greatly limits the applicability of such approach.

2) Two Rounds of MapReduce Jobs: Without preprocessing and partitioning. To overcome the previously described limitation, multiple successive MapReduce jobs are required. The idea is to have the first job output the top k for each pair (R i , S j ). Then, the second job is used to merge all the top k values for a given r i and to perform the merging and sorting of all local top k values (instead of all values), producing the final global top k. Such approach is used in H-BNLJ [START_REF] Zhang | Efficient parallel knn joins for large data in mapreduce[END_REF] and greatly improves sorting time.

With preprocessing and partitioning. A last possibility is based on the z-value preprocessing. In H-zkNNJ [START_REF] Zhang | Efficient parallel knn joins for large data in mapreduce[END_REF] the authors propose to generate several shifted copies of R and S (to improve the accuracy), and to determine the bounds of the partitions of R i and the corresponding S i in a preprocessing MapReduce job. So here, the preprocessing and partitioning step is completely integrated in MapReduce. Then, the first MapReduce round of computation takes the partitions R i and S i previously determined, and computes the candidate neighbor set, named C i (r), for ∀r i ∈ R i , which contains k local nearest objects immediately before r i and k objects after r i (2k objects totally). The second MapReduce round decides the exact result ∀r i ∈ R from the candidate neighbor set kN N (r, C i (r)). So in total, three MapReduce jobs are launched, and among them, two are actually devoted to the kNN computation. As the number of points that are in the candidate neighbor set is small, thanks to the drastic partitioning (itself due to a drastic preprocessing), the cost of computation and communication is extremely reduced.

D. Summary

So far, we have studied the different ways to go through a kNN computation from a workflow point of view with three main steps. The first step focuses on data preprocessing, either for selecting pivots for each partition or for projecting data from high dimension to low dimension. The second step is in charge of data partitioning and organization in the partitions using distance based method or size based method. The last step of the workflow is to actually compute the kNN in one or two MapReduce jobs. Figure 4 summarizes the workflow we have gone through in this section and the techniques that are associated with each step.

IV. ANALYSIS

A. Load Balance

In a MapReduce job, the completion time of the Map phase and the Reduce phase depends on the longest-running task. This makes load balancing particularly important. In this sense, the partitioning strategy should ensure that the processing time of each task is roughly the same, so as to achieve the optimal overall performance. In our context, each task is used to calculate the pairwise distance of < r i , s i > in the partition

∀ i = j, |R i | × |S i | = |R j | × |S j |.
This is hard to ensure in practice. It is however possible to obtain a sub-optimal solution in the following situation. Since S i is the set of possible nearest neighbors for the elements in R i , then:

∀ i = j, if |R i | = |R j | or |S i | = |S j |, then |R i | × |S i | ≈ |R j | × |S j |
That is to say, if the number of objects in each partition of R is equivalent, then the sum of the number of k nearest neighbors of all objects in each partition can be considered approximately equivalent, and vice versa.

So an efficient partitioning should try to enforce either (1)

|R i | = |R j | or (2) |S i | = |S j |.
In [START_REF] Zhang | Efficient parallel knn joins for large data in mapreduce[END_REF], the authors give a short proof which shows that the worst-case complexity for (1) is equal to:

O (|R i | × log |S i |) = O |R| n × log |S| (1)
and for choice (2), the worst-case complexity is equal to:

O (|R i | × log |S i |) = O |R| × log |S| n ( 2
)
where n is the number of partitions. Since n |S|, the optimal partitioning is achieved when

|R i | = |R j |.

B. Accuracy

Usually, the lack of accuracy is the direct consequence of techniques such as z-values and LSH used in the preprocessing step. In [START_REF] Zhang | Efficient parallel knn joins for large data in mapreduce[END_REF] (H-zkNNJ), the authors show that when the dimension of the data increases, the quality of the results tends to decrease. This can be counterbalanced by increasing the number of random shifts applied to the data, thereby increasing the size of the resulting dataset. Experiments show that three shifts of the initial dataset (in dimension 15) are sufficient to achieve a good approximation (less than 10% of errors shown in the experiences), while controlling the computation time. A similar result can be obtained with LSH by increasing the number of hash functions used. However, when using space filling curves, the distance from the optimal solution (the true kNN) is often bounded, which is not the case for LSH, as explained in [START_REF] Liao | High dimensional similarity search with space filling curves[END_REF].

C. Complexity

Computational complexity is often used to describe the execution time of an algorithm. When computing kNN with MapReduce, additional factors strongly impact the execution time:

(1) The number of MapReduce jobs: Starting a job (whether in Hadoop [START_REF] Jiang | The performance of mapreduce: An in-depth study[END_REF] or any other platform) requires some initialization steps such as allocating resources and copying data. Those steps can be very time consuming.

(2) The number of Map tasks and Reduce tasks used to calculate kNN(R i S): The larger this number is, the more information is exchanged through the network during the Shuffle phase. Moreover, scheduling a task also incurs an overhead.

(3) The number of distances to compute and to sort for each object r i : Sorting is a dominating operation, so the number of elements to be sorted also impacts computation time.

The basic method H-BkNNJ only uses one MapReduce job, and requires n 2 Map tasks to calculate the distances where n is the number of partitions. The complexity of sorting all distances for one r i in R is |S| × log |S|. Since S is usually a large dataset, this method quickly becomes impracticable.

To overcome this limitation, H-BNLJ or H-BRJ [START_REF] Zhang | Efficient parallel knn joins for large data in mapreduce[END_REF] uses 2 MapReduce jobs, again with n 2 Map tasks to compute the distances. However, using of a second job significantly reduces the complexity of sorting to |n • k| × log |n • k|, where n is the number of partitions and k is the number of nearest neighbors queried.

PGBJ [START_REF] Lu | Efficient processing of k nearest neighbor joins using mapreduce[END_REF] performs a pre-processing phase followed by 2 MapReduce jobs. This method also only uses n Map tasks to calculate the distances. Overall, the sorting complexity is reduced to

|S i | × log |S i |.
H-zkNNJ [START_REF] Zhang | Efficient parallel knn joins for large data in mapreduce[END_REF] also begins by a pre-processing phase and uses in total 3 MapReduce jobs in exchange for taking only n

D. Wrap up

Although the workflow for computing kNN on MapReduce is the same for all existing solutions, the guarantees offered by each of them vary a lot. As load balancing is a key point to shrink completion time, one should carefully choose the partitioning method to achieve this goal. Also, the accuracy of the computing system is crucial: exact results really needed? If not, then one might trade accuracy for efficiency, by using data transformation techniques before the actual computation. Complexity of the global system should also be taken into account for particular needs, although it is often related to the accuracy: an exact system is usually more complex than an approximate one. Finally, none of the systems really offers a way to handle data updates. This is due to the specific partitioning performed before computing. Indeed, an efficient partitioning is adapted to a particular dataset, and might not be adapted to another. Table I is a summary table of the systems we have examined and their main characteristics.

V. EXPERIMENTAL EVALUATION

To validate our analysis, we performed an experimental evaluation of the algorithms we have described in the previous sections. We computed the 20 nearest neighbors (20-NN) of a two dimension geographical dataset on a 20 nodes Hadoop Cluster (dual core with 8 GB of RAM). For each implemented algorithm, we first determined experimentally the optimal parameters (shown in Figure ) and show only the best results measured. Figure 5-left shows the completion time of H-BNLJ, RankReduce, PGBJ and H-zkNNJ, for dataset R and S that both went from 0.5 × 10 5 to 16 × 10 5 records (R = S at each step). H-BkNNJ could not be executed in reasonable time for big dataset. The execution time of H-BNLJ increases exponentially, making it impracticable for the dataset which contains more than 2×10 5 records. The three other algorithms compete fairly up to the biggest dataset considered, but PGBJ is much slower than the other two. This is expected since it gives an exact result whereas RankReduce and H-zkNNJ are only approximate. Nevertheless, PGBJ greatly improves over the exact algorithm H-BNLJ. Overall, RankReduce and H-zkNNJ are the fastest algorithms to find the approximate nearest neighbors in MapReduce. We also studied their accuracy as shown in Figure 5-right. For small dataset, they both have a good accuracy (97% for RankReduce vs 93% for H-zkNNJ). However, as the dataset grows, the accuracy of H-zkNNJ decreases to 86%. Because when the dataset grows, the deviation of the estimation will become bigger. But for LSH, when the density of data becomes larger, the chance that the neighbor data being sent to one bucket will increase, that's the reason the accuracy of LSH becomes better when the number of data increases. This highlights the trade-off between fastness and accuracy for approximate methods.

VI. CONCLUSION

In this paper, we have studied the existing systems to perform the kNN operation in the context of MapReduce. We have first approached this problem from a workflow point of view. We have pointed out that all solutions follow three main steps to compute kNN over MapReduce, namely the pre-processing of data, the partitioning and the actual computation. We have listed and explained the different algorithms which could be chosen for each step, and developed their pros and cons. In a second stage, we have further analyzed existing systems by reviewing their main properties, in terms of load balancing, accuracy of the computation, and overall complexity. Above all, this paper can be seen as a guideline to help selecting the most appropriate method to perform the kNN join operation on MapReduce for a particular use case.

VII. ACKNOWLEDGMENT

Fig. 2 :Fig. 3 :

 23 Fig. 2: z-value based partitioning

Fig. 5 :

 5 Fig. 5: Completion time and accuracy of knn mapreduce algorithms

TABLE I :

 I Summary table of kNN computing systems with MapReduce < R i , S i >. Thus, the number of distances that needs to be calculated is|R i | × |S i |.If all tasks have to compute the same number of distances, they should have a roughly equivalent duration. Hence, the optimal partition strategy should make:

Although RankReduce only compute kNN for a single query, it is easy to extend it to a full kNN join

The authors would like to thank Léa El Beze for her work on the experimentation. Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr)