Tyssandier Viviane

Choubert Georges

Grolier Pascal

Borel Patrick

Carotenoids, mostly the xanthophylls, exchange between plasma lipoproteins

Keywords: lipoprotein, transfer, -carotene, lycopene, lutein, xanthophyll, trout, human

Carotenoids are exclusively transported by lipoproteins and in vitro studies suggest that they might protect these particles against oxidation. Yet, little is known on the factors that govern the distribution of these micronutrients among lipoproteins. The objective was to assess whether carotenoids exchange between lipoproteinsand the factors involved. In a first experiment different group of trouts were fed for 5 days with either a carotenoid-free diet or diets containing a single 80 mg pure carotenoid/kg feed.

Lipoproteins were separated by ultracentrifugation and carotenoid-rich HDL were incubated for 2 h at 37°C with carotenoid-free VLDL, and vice versa. After incubation, lipoproteins were re-separated and carotenoids were quantified to measure the transfer.

The same experiments were done in the presence of cholesteryl ester transfer protein (CETP) and lecithin cholesterol acyltransferase (LCAT) inhibitors. In a second experiment the exchange was measured between human VLDL and HDL. In trout, incubation of carotenoid-rich HDL with carotenoid-free VLDL resulted in the appearance of carotenoids in VLDL, and inversely. The higher the hydrophobicity of a carotenoid, the lower its proportion in HDL after incubation. CETP and LCAT inhibitors significantly increased the proportion of carotenoids in HDL after incubation.

Results obtained with human lipoproteins showed that the xanthophyll lutein transferred between lipoproteins, but could not show any carotenes (-carotene, -carotene and lycopene) transfer. We conclude that carotenoids, chiefly the xanthophylls, exchange between lipoproteins. The transfer depends on plasma factor(s) sensitive to CETP and/or LCAT inhibitors.

Introduction

Epidemiological studies consistently associate diets rich in fruit and vegetables with a reduced risk of chronic diseases [START_REF] Lampe | Health effects of vegetables and fruit: assessing mechanisms of action in human experimental studies[END_REF]. Among the components suspected to explain this effect, the lipid-soluble plant pigment carotenoids, whose antioxidant properties have been clearly demonstrated [START_REF] Krinsky | Mechanism of action of biological antioxidants[END_REF], are likely to play an important role [START_REF] Rock | Carotenoids: biology and treatment[END_REF][START_REF] Ziegler | A review of epidemiologic evidence that carotenoids reduce the risk of cancer[END_REF][START_REF] Giovannucci | Tomatoes, tomato-based products, lycopene, and cancer: Review of the epidemiologic literature[END_REF][START_REF] Klipsteingrobusch | Serum carotenoids and atherosclerosis -The Rotterdam Study[END_REF][START_REF] Snodderly | Evidence for protection against age-related macular degeneration by carotenoids and antioxidant vitamins[END_REF].

Carotenoids are transported in human plasma exclusively by lipoproteins [START_REF] Parker | Absorption, metabolism, and transport of carotenoids[END_REF][START_REF] Faure | Carotenoids: 1.Metabolism and physiology[END_REF].

Chylomicrons are responsible for the transport of carotenoids from the intestinal mucosa to the bloodstream, via the lymphatics, and then to the liver. VLDL and LDL are apparently responsible for the transport of carotenoids from the liver to peripheral tissues. The role of HDL in carotenoid transport is unknown. The relative distribution of carotenoids among lipoproteins has been reported [START_REF] Romanchik | Distributions of carotenoids and alpha-tocopherol among lipoproteins do not change when human plasma is incubated in vitro[END_REF][START_REF] Clevidence | Association of carotenoids with human plasma lipoproteins[END_REF]. Hydrocarbon carotenoids (carotene, -carotene and lycopene), are mainly recovered in LDL (58-73%), monohydroxy carotenoids (mainly -cryptoxanthin) are distributed almost equally between LDL and HDL (about 40% in each class), and dihydroxy carotenoids (lutein and zeaxanthin), are found predominantly in HDL (53%). These micronutrients might participate in the protection of lipoproteins against oxidation [START_REF] Gaziano | Supplementation with beta-carotene in vivo and in vitro does not inhibit low density lipoprotein oxidation[END_REF][START_REF] Oshima | Supplementation with carotenoids inhibits singlet oxygen-mediated oxidation of human plasma low-density lipoprotein[END_REF][START_REF] Carpenter | The carotenoids beta-carotene, canthaxanthin and zeaxanthin inhibit macrophage-mediated LDL oxidation[END_REF][START_REF] Dugas | Dietary supplementation with beta-carotene, but not with lycopene, inhibits endothelial cell-mediated oxidation of low-density lipoprotein[END_REF][START_REF] Panasenko | Interaction of peroxynitrite with carotenoids in human low density lipoproteins[END_REF], and thus might prevent the development of atherosclerosis [START_REF] Klipsteingrobusch | Serum carotenoids and atherosclerosis -The Rotterdam Study[END_REF][START_REF] Gerster | Potential role beta-carotene in the prevention of cardiovascular disease[END_REF][START_REF] Gey | Increased risk of cardiovascular disease at suboptimal plasma concentrations of essential antioxidants: an epidemiological update with special attention to carotene and vitamin C[END_REF][START_REF] Gaziano | The role of beta-carotene in the prevention of cardiovascular disease[END_REF][START_REF] Kritchevsky | beta-carotene, carotenoids and the prevention of coronary heart disease[END_REF][START_REF] Arab | Lycopene and cardiovascular disease[END_REF].

The transfer/exchange of lipids and vitamin E between lipoproteins has been extensively studied [START_REF] Bruce | Plasma lipid transfer proteins, high-density lipoproteins, and reverse cholesterol transport[END_REF][START_REF] Guyard-Dangremont | Phospholipid and cholesteryl ester transfer activities in plasma from 14 vertebrate species. Relation to atherogenesis susceptibility[END_REF][START_REF] Kostner | Human plasma phospholipid transfer protein accelerates exchange transfer of alpha-tocopherol between lipoproteins and cells[END_REF]. On the contrary the exchange of carotenoids among lipoproteins has not been investigated in depth. Although postprandial studies have suggested that some -carotene can be transferred from chylomicrons to HDL [START_REF] Traber | -Carotene transport in human lipoproteins. Comparisons with -tocopherol[END_REF], only three studies have been dedicated to study the transfer of carotenoids between other lipoprotein fractions. One has been done with insect lipophorins [START_REF] Tsuchida | Lipid transfer particle catalyzes transfer of carotenoids between lipophorins of bombyx mori[END_REF], one with unilamellar vesicles as model of lipoproteins [START_REF] Massey | Kinetics of transfer of -tocopherol between model and native plasma lipoproteins[END_REF], and one with human lipoproteins [START_REF] Romanchik | Distributions of carotenoids and alpha-tocopherol among lipoproteins do not change when human plasma is incubated in vitro[END_REF]. The results were contradictory. Indeed, the team of Maekawa [START_REF] Tsuchida | Lipid transfer particle catalyzes transfer of carotenoids between lipophorins of bombyx mori[END_REF] found a transfer, while the two other teams did not. These different results, which probably depend on the model used, do not lead to any definite conclusion on the ability of carotenoids to exchange between human lipoproteins. Thus we have decided to re-assess this very important aspect of carotenoid transport.

Materials, Subjects and Methods

Animals and diets

A total of 80 immature rainbow trouts (Oncorhynchus mykiss Walbaum) of both sexes, with a mean weight of 200g, were used as experimental animals. The fishes were obtained from the INRA experimental fish farm of Donzacq (France), and kept in freshwater tanks at 17  1°C during the experimental period. The following protocol complied with the Guide for the Care and Use of Laboratory animals. After an adaptation period (15 days), while fishes received a commercial fish diet (Trouw, Fontaine les Vervins, France), 6 groups of 10 trouts, were fed diets containing similar amount (80 mg carotenoid/kg feed) of single pure (>95%) carotenoids during 5 days.

The carotenoids were either all-trans astaxanthin, or canthaxanthin, or zeaxanthin, or cryptoxanthin, or -carotene, or lycopene (Roche Vitamines France, Neuilly-sur-Seine, France). During the same period, a group (20 trouts) received the same diet free of carotenoids. Feed distribution was withheld from fishes19 hours before they were killed by stunning. Blood was withdrawn in the caudal vein and plasma was immediately prepared on EDTA (Sigma, Saint Louis, USA) by centrifugation (910 g, 4°C, 15 min).

After centrifugation, 10 µl/mL of a solution of sucrose (60%) and EDTA (10%) was added to preserve plasma lipoproteins. The plasma was stored under nitrogen at -20 °C until analysis.

Isolation of trout lipoproteins

Trout lipoproteins were isolated by ultracentrifugation (Kontron T2070, Zurich, Switzerland) (200000g for 22 hours, at 15°C) in a Swinging TST 41.14 rotor [START_REF] Chapman | A density gradient ultracentrifugal procedure for the isolation of the major lipoprotein classes from human serum[END_REF].

Discontinuous six-step density gradients were prepared with NaBr solutions (Sigma, Saint Louis, USA). Successive densities were, from the top to the bottom of the tube :

1.006 g/mL (1.1 mL) ; 1.019 g/mL (2.5 mL) ; 1.063 g/mL (3.5 mL) ; 1.210 g/mL (2.5 mL) ; 1.310 g/mL (1 mL plasma adjusted to this density with solid NaBr) and 1.386 g/mL (0.8 mL). Each density solution was controlled with a density meter (Digital Density Meter DMA 40, Anton Paar, Austria). After ultracentrifugation, lipoprotein fractions were removed; 1.7 mL for VLDL (d<1.015 g/mL); 2.1 mL for LDL (1.015<d<1.085 g/mL); 3.2 mL for HDL (1.085<d<1.21 g/mL) and 2.6 mL for Vitellogenin (1.21<d<1.31 g/mL). Immediately after the separation, VLDL and HDL were used to study the transfer of carotenoids (see below). The other lipoprotein fractions were stored under nitrogen, at -80°C, until analysis.

Humans

In order to study the transfer of carotenoids between human lipoproteins, we recruited two young (18 y < age < 35 y), non obese (BMI<30) male volunteers. These volunteers were chosen among a sample of 79 subjects who were enrolled in a previous study [START_REF] Borel | Low and high responders to pharmacological doses of beta-carotene: proportion in the population, mechanisms involved and consequences on beta-carotene metabolism[END_REF]. One had a relatively high plasma carotenoid status (sum of -carotene + lycopene + lutein + zeaxanthin + -cryptoxanthin + -carotene = 2.5 mol/L), the other had a relatively low plasma carotenoid status (sum = 0.8 mol/L). Blood withdrawal was approved by the regional committee on human experimentation of the regional university hospital in Clermont-Ferrand (France). The two volunteers, who gave informed consent, were apparently healthy according to clinical examination and disease history. Their fasting plasma lipid parameters (total cholesterol and total triacylglycerols) were in the normal range, suggesting that they had a normal lipid metabolism.

Isolation of human lipoproteins.

Human lipoproteins were separated by using a discontinuous KBr gradient (Sigma, Saint Louis, USA), subjected to ultracentrifugation (200 000g for 24 hours, at 10°C) in a Swinging TST 41.14 rotor [START_REF] Borel | Postprandial chylomicron and plasma vitamin E responses in healthy older subjects compared with younger ones[END_REF][START_REF] Dubois | Effects of moderate amounts of emulsified dietary fat on postprandial lipemia and lipoproteins in normolipidemic adults[END_REF]. The successive densities of the discontinuous six-step density gradient were, from the top to the bottom of the tube :

1.006 g/mL (1 mL) ; 1.019 g/mL (2.5 mL) ; 1.040 g/mL (2.5 mL) ; 1.063 g/mL (2.5 mL) ; 1.21 g/mL (2 mL plasma adjusted to this density with solid KBr) and 1.34 g/mL (1 mL). After ultracentrifugation, lipoprotein fractions were removed; 2.5 mL for VLDL (0.96<d<1.006 g/mL), 5 mL for LDL (1.03<d<1.063 g/mL) and 2.5mL for HDL (1.063<d<1.21 g/mL). Immediately after the separation, VLDL and HDL were used to study the transfer of carotenoids (see below). The others lipoprotein fractions were stored at -80°C, under nitrogen, until analysis.

Purity of lipoprotein fractions

The purity of the lipoprotein fractions was checked by using polyacrylamide gel electrophoresis (method adapted from Babin [START_REF] Babin | Apolipoproteins and the association of egg yolk proteins with plasma high density lipoproteins after ovulation and follicular atresia in the rainbow trout (Salmo gairdneri)[END_REF]). Gels were made with a stacking gel at 2.5 % (pH 6.8). The running gel was a linear gradient of 2.5-16% polyacrylamide adjusted to pH 8.8 with 1M tris(hydroxy-methyl)aminomethane (Tris) buffer. An aliquot of lipoproteins (which provided 35 to 40 µg proteins) was applied to each well and electrophoresis was carried out at 150 V for 10 h in a Tris/borate buffer (0.09M Tris / 0.08 M Boric acid / 3mM EDTA: 3mM NaN 3, pH 8.35). After migration, lipoproteins were revealed with Coomassie Blue R250 (0.025%) (Sigma, Saint Louis, USA). Results showed that lipoprotein fractions were apparently pure (no detectable LDL and HDL band in the VLDL fraction and no detectable VLDL and LDL band in the HDL fraction).

Protocol to study the transfer of carotenoids between lipoproteins

The transfer was studied by incubating carotenoid-rich lipoproteins (either HDL or VLDL) with carotenoid-poor lipoproteins (either VLDL or HDL). Carotenoid-rich lipoproteins were either lipoproteins coming from trouts who were fed diets containing carotenoids, or lipoproteins coming from the human subject with a high plasma carotenoid status. Carotenoid-poor lipoproteins were either lipoproteins coming from trouts who were fed diets without carotenoids, or lipoproteins coming from the human subject with a low plasma carotenoid status. Immediately after separation of lipoproteins, 550 µL carotenoid-rich VLDL and 550 µL carotenoid-poor HDL (and inversely) were incubated together in the dark, and stirred at 37°C, under nitrogen, for 2h in presence of antioxidants: ascorbic acid (200 mmol/L) (Prolabo, Lyon, France) and pyrogallol (200 mmol/L) (Sigma, Saint Quentin Fallavier, France). A control experiment had previously shown that this combination of antioxidants preserve > 90% carotenoids during incubation. The same experiments were done with LCAT (lecithin cholesterol acyltransferase) inhibitors [START_REF] Harris | LCAT inhibitors interfere with the enzymatic determination of cholesterol and triglycerides[END_REF]: 5,5' dithio-bis (2-nitrobenzoïc acid) (2 mmol/L) and p-chloromercuriphenyl sulfonic acid (2 mmol/L) (Sigma, Saint Quentin Fallavier, France) and a CETP (cholesteryl ester transfer protein) inhibitor [START_REF] Jeong | CETP inhibitory activity of ceramides, isolated from the gorgonian Acabaria Undulata[END_REF]: N,Ndimethylsphingosine (0.1 mmol/L) (Sigma, Saint Quentin Fallavier, France). After incubation, VLDL and HDL were reseparated by ultracentrifugation as described above.

Carotenoids were measured in the lipoprotein fractions before and after incubation.

Carotenoid measurement

Plasma and lipoprotein carotenoids were extracted twice with ethanol and hexane, sample/ethanol/hexane (1:1:2, by vol). Echinenone (Roche Vitamines France, Neuilly-sur-Seine, France) was used as internal standard. Carotenoids were quantified by reverse-phase HPLC on a Kontron apparatus (Zurich, Switzerland) with detection at 450 nm. Carotenoids were separated using two columns set in series [START_REF] Borel | Low and high responders to pharmacological doses of beta-carotene: proportion in the population, mechanisms involved and consequences on beta-carotene metabolism[END_REF]: a Nucleosyl C18, 150  4.6 mm, 3 µm followed by a Vydac C18, 250  4.6 nm (Interchim, Montluçon, France). The mobile phase was a mixture of acetonitrile/methanol/dichloromethane/water (70:15:10:5, by vol). Quantification was conducted using the Kontron MT 2 software, by comparing peak areas to those of standard solutions of carotenoids. Echinenone allowed to calculate and overall recovery yield 75-100%.

Statistical analysis

Results are expressed as means  SEM. The repartition of the different carotenoids between trout VLDL and HDL after incubation was compared by analysis of variance (ANOVA). When a significant difference was detected (P<0.05), means were compared using the post-hoc Tukey / Kramer's test. The repartition of carotenoids between human VLDL and HDL before and after incubation was compared by the Student's t-test (P<0.05).

Results

Distribution of carotenoids among trout and human lipoproteins

The distribution of carotenoids among trout and human lipoproteins is shown in Figure 1. Note that after supplementation with 80 mg lycopene/kg feed for 5 days, no lycopene was detected in trout lipoproteins. In the trout, the higher proportion of carotenoids was found in the HDL fraction, whereas in humans it was found in the LDL fraction. There was a relationship between the percentage of carotenoids in certain lipoprotein classes and carotenoid hydrophobicity. Indeed, the higher the hydrophobicity of a carotenoid (as estimated by the octanol-water partition coefficient of the molecule:

Log P [START_REF] Cooper | Evaluation of the potential for olestra to affect the availability of dietary phytochemicals[END_REF]), the lower was its percentage in the HDL fraction (r 2 =0.742, P=0.061 for trout HDL and r 2 =0.957, P=0.001 for human HDL). There was also a strong relationship between the percentage of carotenoids in human LDL and carotenoid hydrophobicity (r 2 =0.970, P=0.001).

Exchange of carotenoids between trout lipoproteins

Figure 2 shows the distribution of carotenoids among trout lipoproteins after incubation of a lipoprotein class rich in carotenoids (either VLDL or HDL) with a lipoprotein class free of carotenoids (either HDL or VLDL). Note that the repartitions obtained after incubation of carotenoid-rich VLDL with HDL which contained no carotenoids were the same than those obtained after incubation of carotenoid-rich HDL with VLDL which contained no carotenoids. There was no relationship between the percentage of carotenoids found in VLDL or HDL after incubation, and either the molecular weight or the melting point of carotenoids. Conversely, there was a high significant relationship (r 2 =0.939, P=0.007) between the percentage of carotenoid found in VLDL or HDL and carotenoid hydrophobicity (Log P). The percentage of astaxanthin in VLDL was significantly (P < 0.05) lower than that of the other carotenoids. On the other hand, the percentage of canthaxanthin and zeaxanthin in VLDL were not significantly different, but they were significantly lower than that of -cryptoxanthin and -carotene. Finally, no significant difference was found between the distribution of cryptoxanthin and -carotene among VLDL and HDL after incubation.

Effect of CETP and LCAT inhibitors on the transfer of carotenoids between trout lipoproteins

The exchange of carotenoids between trout VLDL and HDL, in presence of CETP and LCAT inhibitors, was studied for three carotenoids: astaxanthin, zeaxanthin and -carotene (Figure 3). The presence of inhibitors changed the repartition of carotenoids between VLDL and HDL after incubation. The inhibitors reduced the percentage of carotenoids recovered in the VLDL fraction and consequently increased the percentage of carotenoids in the HDL fraction (compare Figure 2 and Figure 3). In the presence of LCAT and CETP inhibitors astaxanthin and zeaxanthin were recovered almost exclusively in HDL, while a significant proportion of -carotene (27%) was recovered in VLDL.

Exchange of carotenoids between human lipoproteins

Figure 4 shows the repartition of several carotenoids between human carotenoidrich HDL and carotenoid-poor VLDL before (left column) and after (right column) incubation of the two lipoprotein classes with each other for 2 h at 37°C. There was a significantly higher proportion of lutein in VLDL after incubation (+12%). There was a higher proportion of the other carotenoids in VLDL after incubation (around 4% increase), but this was not significant.

Figure 5 shows the results obtained when carotenoid-rich VLDL were incubated with carotenoid-poor HDL. As observed in Figure 4, there was a transfer of lutein from the lutein-richest lipoprotein (VLDL in that case) to the lutein-poorest lipoprotein (HDL). The percentage transferred was equivalent to that observed in Figure 4 (+14%), but it was not significant due to the higher variability of the measurements.

Discussion

The choice of trout lipoproteins as a model to study the transfer of carotenoids between lipoproteins was dictated by four reasons. First, as we wanted to be able to detect a transfer, even very low, and as we wanted to compare the transfer of different carotenoids without possible interactions between carotenoids [START_REF] Van Den Berg | Carotenoid interactions[END_REF], it was essential to use acceptor lipoproteins without carotenoids and donor lipoproteins with only one class of carotenoid. Such lipoproteins cannot be obtained in humans. Indeed, this would have required the consumption of fruit and vegetable free diets for several weeks/months, followed by the consumption of purified carotenoids for several weeks. Second, we wanted to test a variety of carotenoids to assess whether there is a relationship between characteristic physical properties of carotenoids and their transfer. This was also not feasible in humans because not all carotenoids are allowed as diet additives. Third, we wanted to work with lipoproteins that had naturally incorporated carotenoids. Thus we did not want to incorporate carotenoids by using organic solvents. Indeed, it is highly probable that such an incorporation would not lead to a natural distribution of carotenoids between the core and the surface of lipoproteins [START_REF] Borel | Carotenoids in biological emulsions: solubility, surface-to-core distribution, and release from lipid droplets[END_REF]. Finally, despite the large evolutionary distance between trout and human, major elements of the structure of their plasma lipoproteins are shared [START_REF] Chapman | Distribution and characterization of the serum lipoproteins and their apoproteins in the rainbow trout (Salmo gairdnerii)[END_REF][START_REF] Babin | Plasma lipoproteins in fish[END_REF] and trout, as human, displayed substantial CETP and phospholipid transfer protein (PLTP) activities [START_REF] Guyard-Dangremont | Phospholipid and cholesteryl ester transfer activities in plasma from 14 vertebrate species. Relation to atherogenesis susceptibility[END_REF].

The results obtained with trout lipoproteins demonstrate for the first time that a carotene (-carotene) as well as several xanthophylls (astaxanthin, canthaxanthin, lutein, and -cryptoxanthin) can transfer between vertebrate lipoproteins. They also demonstrate that the transfer is bi-directional, from HDL to VLDL, and vice versa. The fact that the proportion of carotenoid found in each lipoprotein class after exchange was similar suggests that there was an apparent equilibrium after 2 h incubation, and thus that all the carotenoids were transferred within the 2 h. The fact that the repartition of carotenoid after exchange was related to carotenoid hydrophobicity suggests that carotenoids distribute as a function of their relative solubility in the different lipid classes which constitute the lipoproteins. This hypothesis elegantly explain the relationship observed between carotenoid hydrophobicity and carotenoid proportion in trout and human HDL and in human LDL (see Figure 1 results).

Results obtained with human lipoproteins demonstrated a transfer for the xanthophyll (lutein) but not for the carotenes (-carotene, -carotene and lycopene). This result is in concordance with those obtained in the trout which showed that the xanthophylls were better transferred than the carotenes. This difference between the xanthophylls and the carotenes, with regard to the transfer, also explains the discrepancy between a result found with an insect model [START_REF] Tsuchida | Lipid transfer particle catalyzes transfer of carotenoids between lipophorins of bombyx mori[END_REF], i.e. a transfer of carotenoid was measured, and a result found with an unilamellar vesicle model [START_REF] Massey | Kinetics of transfer of -tocopherol between model and native plasma lipoproteins[END_REF], i.e. no transfer of carotenoid was detected. Indeed, in the insect model most (>90%) carotenoids were lutein, while in the unilamellar vesicle model the carotenoid studied was -carotene.

The fact that a significant transfer of the carotenes could not be significantly measured with human lipoproteins can be explained by three hypotheses. First, it is possible that in humans the carotenes do not transfer between lipoproteins. However, the demonstrated exchange of -carotene between trout lipoproteins, which have a close lipid composition to that of human [START_REF] Chapman | Distribution and characterization of the serum lipoproteins and their apoproteins in the rainbow trout (Salmo gairdnerii)[END_REF][START_REF] Babin | Plasma lipoproteins in fish[END_REF], suggests that this is probably not the case.

Another explanation could be the difference between trout and human with regard to PLTP activity. Indeed, if PLTP is involved in the transfer of carotenoids, its lower activity in human than in trout [START_REF] Guyard-Dangremont | Phospholipid and cholesteryl ester transfer activities in plasma from 14 vertebrate species. Relation to atherogenesis susceptibility[END_REF], and the lower transfer of the carotenes as compared to the xanthophylls, might explain that it is more difficult to detect a transfer of the carotenes in humans. Finlly, the fact that we were able to detect a transfer of lutein between human lipoproteins while Romanchik et al [START_REF] Romanchik | Distributions of carotenoids and alpha-tocopherol among lipoproteins do not change when human plasma is incubated in vitro[END_REF] did not, can be explained by the fact that these authors have incubated lipoproteins which came from the same fasted volunteers. Indeed, carotenoids were probably already distributed in equilibrium between lipoproteins before incubation and therefore it is logical that they did not transfer.

The transfer of carotenoids between lipoproteins raises the question on the role of the plasma proteins involved in lipid metabolism (CETP, PLTP, LCAT) on this phenomenon. In fact, the protocol used to study the transfer could not differentiate between spontaneous transfer and protein mediated transfer. Indeed some proteins involved in lipid metabolism could have remained associated with lipoproteins. We have therefore performed an additional experiment with CETP and LCAT inhibitors in order to check whether these proteins are involved in carotenoid transfer. We used CETP inhibitors because we hypothesized that this enzyme that exchanges cholesterol esters between lipoproteins might exchange carotenoids as well. We used LCAT inhibitors because we hypothesized that modification of lipoproteins lipid metabolism might indirectly affect the transfer of the carotenoids by changing the lipid composition of lipoproteins. Addition of the inhibitors to the incubation medium led to a higher proportion of carotenoids in trout HDL after exchange. To explain this finding we suggest that a factor which was responsible for the transfer from HDL to VLDL, but not from VLDL to HDL, was partially impaired. Thus a factor sensitive to LCAT and/or to CETP inhibitors is directly or indirectly involved in the transfer from HDL to VLDL.

Note that we state « directly or indirectly », because it is possible that carotenoids simply follow the fate of certain lipid classes. Thus the fact that the exchange of lipids was probably affected (due to the presence of lipid transfer protein inhibitors), may have led to indirectly affect the distribution of carotenoids. It is also possible that the inhibitors had inhibited a protein which is specifically responsible for the transfer of carotenoids between lipoproteins.

In conclusion, our study demonstrates that carotenoids, chiefly the xanthophylls, exchange between lipoproteins. It shows that, at equilibrium, the repartition of carotenoids between lipoproteins is related to carotenoid hydrophobicity. It also suggests that the exchange depends on factor(s) sensitive to inhibitors of LCAT and/or CETP. No significant difference in the repartition of carotenoids before and after incubation was found (Student's t-test, P<0.05).

Figures

Figure 1 :

 1 Figure 1: Distribution of carotenoids among trout and human lipoproteins. Values

Figure 2 :

 2 Figure 2: Distribution of carotenoids among trout VLDL and HDL after

Figure 3 :

 3 Figure 3: Distribution of carotenoids among trout VLDL and HDL after

Figure 4 :

 4 Figure 4: Exchange of carotenoids among human carotenoid-poor VLDL and

Figure 5 :

 5 Figure 5: Exchange of carotenoids between human carotenoid-rich VLDL and

Acknowledgments

The authors wish to thank Mr. F. Sandres, F. Terrier and Y. Hontang from INRA Experimental Fish Farm of Donzacq (France) for the maintenance of the experimental fishes, and Roche Vitamines France (Neuilly-sur-Seine, France) for the gift of carotenoids.


Member, IEEE Pau Closas

Senior Member, IEEE Carles Fernández-Prades

Jordi Vilà-Valls

Multiple Quadrature Kalman Filtering

Keywords: Adaptive filters, complexity reduction, high dimensional, Kalman filtering, nonlinear filters, quadrature rules

Bayesian filtering is a statistical approach that naturally appears in many signal processing problems. Ranging from Kalman filter to particle filters, there is a plethora of alternatives depending on model assumptions. With the exception of very few tractable cases, one has to resort to suboptimal methods due to the inability to analytically compute the Bayesian recursion in general dynamical systems. This is why it has attracted the attention of many researchers in order to develop efficient algorithms to implement it. We focus our interest into a recently developed algorithm known as the Quadrature Kalman filter (QKF). Under the Gaussian assumption, the QKF can tackle arbitrary nonlinearities by resorting to the Gauss-Hermite quadrature rules. However, its complexity increases exponentially with the state-space dimension. In this paper we study a complexity reduction technique for the QKF based on the partitioning of the state-space, referred to as the Multiple QKF. We prove that partitioning schemes can effectively be used to reduce the curse of dimensionality in the QKF. Simulation results are also provided to show that a nearly-optimal performance can be attained, while drastically reducing the computational complexity with respect to state-of-the-art algorithms that are able to deal with such nonlinear filtering problems.

I. INTRODUCTION

T HIS paper addresses nonlinear filtering problems where both process and measurement noises are additive and normally distributed. The filtering problem involves the recursive estimation of time-varying unknown states of a system using the incoming flow of information (estimation of the states at time using the measurements up to time ), along some prior statistical knowledge about the variations of such states. The general discrete state-space model can be expressed as [START_REF] Ito | Gaussian filters for nonlinear filtering problems[END_REF] (2)

The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Hing Cheung So. This work was partially supported by the European Commission in the framework of the COST Action IC0803 (RFCSET), by the Spanish Ministry of Economy and Competitiveness project TEC2012-39143 (SOSRAD), the Spanish Science and Technology Commission TEC2010-19171 (MOSAIC), and by project 2009-SGR-1236 of the Catalan Administration (AGAUR).

P. Closas and C. Fernández-Prades are with the Centre Tecnològic de Telecomunicacions de Catalunya (CTTC), Parc Mediterrani de la Tecnologia, 08860 Castelldefels, Barcelona, Spain (e-mail: pclosas@cttc.cat; cfernandez@cttc.cat).

J. Vilà-Valls is with the Universitat Politècnica de Catalunya (UPC), Jordi Girona 1-3, 08034 Barcelona, Spain (e-mail: jordi.vila-valls@upc.edu).

Digital Object Identifier 10.1109/TSP. 2012.2218811 where is the hidden state of the system at time , is a known, possibly nonlinear, function of the states; and is referred to as process noise, modeled with a zero-mean Gaussian distribution of covariance ; is the measurement at time , is a known, possibly nonlinear, function, which relates measurements with states; and is referred to as measurement noise, also zero-mean normally distributed with covariance , and independent of . We are interested in the marginal distribution , which gathers all the information about the system contained in the available observations, with . This distribution can be recursively computed in two steps:

1) Prediction: we obtain the predictive distribution using prior information, , and the previous filtering distribution, ,

2) Update: we use the new measurements (measurement likelihood) and the predictive distribution to obtain the new filtering distribution ,

Under the Gaussian assumption, the state transition density and the measurement likelihood function are Gaussian densities, which in turn reverts to a Gaussian posterior density [START_REF] Ito | Gaussian filters for nonlinear filtering problems[END_REF]. Therefore, the problem is reduced to the estimation of the mean and covariance of each distribution. The predictive and filtering distributions can be expressed as (5) [START_REF] Djuric | Multiple particle filtering[END_REF] respectively, where and are the state estimates obtained at the prediction and update stages at time , and and are the corresponding covariance matrices of the estimation error.

Depending on the dimensionality of the state-space model, the computational complexity associated to such estimation can be high. Actually, most algorithms are prone to fail in high-dimensional systems, an effect that is typically referred to as the curse of dimensionality. For instance, particle filters (PFs) [START_REF] Djuric | Particle filtering[END_REF] are known to require a large sample pool to characterize the filtering distribution when increases [START_REF] Daum | Curse of dimensionality and particle filters[END_REF]. In other words, PFs suffer from the curse of dimensionality: it is generally not possible to generate samples with significant weight, as required for importance sampling, in high dimensions. To circumvent this problem, some solutions were reported in the literature in the context of particle filtering. Marginalization of linear states was proposed in [START_REF] Schön | Marginalized particle filters for mixed linear/nonlinear state-space models[END_REF], where the core idea was to use a Kalman filter (KF) to optimally deal with those states, while reducing the dimension of the state-space that the PF has to explore (that is, the nonlinear part). However, this technique can only be considered when the system has linear substructures and other solutions should be considered for more general cases. The idea of dividing the state-space into subsets and run a PF for each partition was presented in [START_REF] Bugallo | Target tracking by multiple particle filtering[END_REF], [START_REF] Djuric | Multiple particle filtering[END_REF]. The resulting method is known as the Multiple PF (MPF), which showed promising results both in terms of computational reduction and estimation performance. Recently the Iterated MPF (iMPF) was proposed in [START_REF] Closas | Improving accuracy by iterated multiple particle filtering[END_REF], which enhances the performance of the MPF by using tools of game theory to deal with the coupling of the filters and overcome the scarce data exchanged among them.

In this paper, we borrow the idea of the Multiple PF and apply it to the dimension reduction of the Quadrature Kalman filter (QKF) [START_REF] Tam | An efficient radar tracking algorithm using multidimensional Gauss-Hermite quadratures[END_REF], a kind of sigma-point Kalman filter (SPKF) [START_REF] Van Der Merwe | Sigma-point Kalman filters for probabilistic inference in dynamic state-space models[END_REF]. SPKFs are a family of derivative-free Gaussian filters, which are based on a weighted sum of function evaluations at specified (i.e., deterministic) points within the domain of integration, as opposite to the stochastic sampling performed by particle filtering methods. Different SPKF-like algorithms involve different sigma-points and weights, which are used to approximate the transformation of means and covariances when applied to a nonlinear system. For instance, the Unscented Kalman filter (UKF) draws points using the Unscented Transform [START_REF] Julier | A new extension of the Kalman filter to nonlinear systems[END_REF], [START_REF] Merwe | The square-root unscented Kalman filter for state and parameter estimation[END_REF], delivering estimates that are exact in mean for monomials up to third degree, while covariance computation is exact only for linear functions; the Cubature Kalman filter (CKF) resorts to spherical-radial cubature rules [START_REF] Arasaratnam | Cubature Kalman filters[END_REF], which are exact in mean for all polynomials in up to the third degree and in covariance for linear functions; and the QKF is based on Gauss-Hermite quadrature rules [START_REF] Ito | Gaussian filters for nonlinear filtering problems[END_REF], [START_REF] Tam | An efficient radar tracking algorithm using multidimensional Gauss-Hermite quadratures[END_REF], [START_REF] Golub | The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate[END_REF], [START_REF] Arasaratnam | Square-root quadrature Kalman filtering[END_REF]. Whereas UKF and CKF exhibit a linear growth of with respect to , it is exponential for the QKF method. A single parameter is required for the use of quadrature rules, which is the number of sigma-points per dimension . The total number of quadrature points is then fixed to . Indeed, this parameter can be used to adjust the algorithm, with the quadrature rules being optimal for nonlinearities of degree . Despite the curse of dimensionality, the remarkable performance improvement exhibited by the QKF with respect to other SPFKs [START_REF] Fernández-Prades | Bayesian nonlinear filtering using quadrature and cubature rules applied to sensor data fusion for positioning[END_REF], makes it an appealing tool for practitioners. Recently, Smolyak rules (a.k.a. sparse grids) have been applied to the QKF in order to avoid tensor products of quadrature rules, further reducing the computational load [START_REF] Jia | Sparse Gauss-Hermite quadrature filter with application to spacecraft attitude estimation[END_REF], an approach that can be complementarily applied to the proposed Multiple QKF (MQKF).

Our contribution investigates if partitioning approaches could be used to reduce the computational complexity of the problem and proposes a method based on partitioning which we have named the Multiple Square-root QKF (MSQKF). The assumptions are that the dynamic system is driven by Gaussian processes and that the possible nonlinearities are approximated by the Gauss-Hermite quadrature rules.

The paper is organized as follows. Section II introduces the partitioning of the states and describes the implementation of the MQKF and the corresponding square-root version (MSQKF).

Section III discusses some important issues related to the multiple approach. Section IV proves the complexity reduction of partitioning schemes applied to the QKF. Section V supports the approach with computer simulations where two examples are considered: an illustrative academic example and a multiple frequency estimation problem. Section VI draws some conclusions.

II. MULTIPLE QUADRATURE KALMAN FILTER

A. State-Space Partitioning

The state-space (1) can be partitioned into subspaces, possibly with different dimensions. Also, the considered system can be coupled in the observations, where states are combined via . Therefore, state equation can be equivalently expressed as 1. . . . . . . . . [START_REF] Closas | Improving accuracy by iterated multiple particle filtering[END_REF] where each function , with , can be different, and we define the dimension of each subspace such that . Notice that the state-space models which can be considered within the partitioning approach are general. A discussion is provided in Section III on the simplifications and correlations neglected by the multiple approach in general models. In the sequel, we write instead of to make the subspace partitioning more explicit.

The -th process noise is distributed as

, where is constructed from as the entries corresponding to the -th subspace. In general, the partitioned process noise vector is equivalent to in (1) taking into account that the cross-covariance matrices among subspace process noise vectors may not be null.

In the proposed approach, each subspace considers only its own process noise, , and thus neglecting the possible cross-correlations among subspace process noise vectors. In practice, the partitioned process noise considered is only equivalent to for uncorrelated partitions. This is also discussed in Section III.

A special case: the state-space partitioning is strongly simplified when dealing with independent subspaces, where the subspace process noise cross-covariances are null and there is no interconnection among subspaces. The -th subspace process equation is reduced to [START_REF] Tam | An efficient radar tracking algorithm using multidimensional Gauss-Hermite quadratures[END_REF] with in this case.

As we mentioned, the key idea consists of dividing the state-space into subspaces and applying a QKF to each partition. The Gaussian filter in charge of the -th subspace, , is mainly interested in the marginal posterior distribution , where the conditioning on shows the interconnection among subspaces. The Bayesian recursive solution to obtain this distribution is given in ( 3) and ( 4), which in this case reads as [START_REF] Van Der Merwe | Sigma-point Kalman filters for probabilistic inference in dynamic state-space models[END_REF] and [START_REF] Julier | A new extension of the Kalman filter to nonlinear systems[END_REF] respectively.

Notice that the marginal predictive distribution is conditioned to and not to , because the distribution is obtained by integrating out the latter over the corresponding marginal posterior at . In the Gaussian domain, the expressions of the marginal predictive and filtering distributions are:

(11) [START_REF] Arasaratnam | Cubature Kalman filters[END_REF] respectively. The problem is then to estimate first the predicted state vector and its covariance matrix, , and then the estimates at instant incorporating the information provided by the new measurement , . The equations involved in the -th prediction and update steps 2 are summarized as follows:

• Prediction:

(13) (14)
• Update:

(15) 2 We write , , and as the shorthand for , , and , respectively. We omitted the dependence with time and the superscript of the process function , and the dependence with time of the measurement function , for the sake of clarity. [START_REF] Jia | Sparse Gauss-Hermite quadrature filter with application to spacecraft attitude estimation[END_REF] where the Kalman gain, measurement prediction, innovation covariance and cross-covariance are obtained as

Inspecting the prediction and update steps equations, we realize that a number of integrals must be solved by the filter. These integrals can be seen as expectations of some known (nonlinear) function of the states over a distribution, which can be either the predictive or the filtering distribution. Under the Gaussian assumption, these distributions are Gaussian and given by ( 11) and [START_REF] Arasaratnam | Cubature Kalman filters[END_REF]. The assumption done allows us to resort to the Gauss-Hermite quadrature rules to solve for the integral [START_REF] Arasaratnam | Discrete-time nonlinear filtering algorithms using Gauss-Hermite quadrature[END_REF]. Those rules were seen to be a powerful tool to approximate integrals of the kind we mentioned [START_REF] Golub | The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate[END_REF],

constituting the core concept of the QKF.

The difference with a conventional filter is that each step is performed in parallel by the bank. At each step, the -th filter is aware of the estimates delivered by the rest of filters. The different filters are interconnected at each step as expressed in [START_REF] Merwe | The square-root unscented Kalman filter for state and parameter estimation[END_REF] and [START_REF] Arasaratnam | Cubature Kalman filters[END_REF] with the conditional distribution upon and , respectively. Unfortunately, these two quantities are not available due to the inability to marginalize over nonlinear functions, and hence approximations should be performed. Following the approach in [START_REF] Bugallo | Target tracking by multiple particle filtering[END_REF], [START_REF] Djuric | Multiple particle filtering[END_REF], here we propose to use [START_REF] Arasaratnam | Discrete-time nonlinear filtering algorithms using Gauss-Hermite quadrature[END_REF] in prediction and update steps of each parallel filter, respectively. Notice that these values are available at the required step.

denotes the filtering solution of all the filters but at the previous time instant, which is shared among filters to predict at . The update is performed using the predicted values of each subspace, . To sum up, the simplifications made here when applying partitioning schemes are twofold: i) the cross-terms among statepartitions in are neglected and ii) the coupling among filters is performed with the point estimates in [START_REF] Arasaratnam | Discrete-time nonlinear filtering algorithms using Gauss-Hermite quadrature[END_REF]. The impact of these simplifications is studied in Sections III-B1 and III-B2, respectively.

C. Multiple Square-Root Quadrature Kalman Filter

In the following, we describe the operation of the proposed MSQKF. Initially, we have to specify the state-space partitioning , the number of sigma-points per dimension , an estimation of the process and measurement noise covariances and (assuming stationarity for the sake of simplicity, they will be considered constants over the time of observation), and the initial conditions and the corresponding covariance . This new algorithm is constructed as a bank of parallel SQKFs, each one tracking a different subspace. Each filter computes sigma-points and weights, , resorting to the Gauss-Hermite quadrature rules [START_REF] Fernández-Prades | Bayesian nonlinear filtering using quadrature and cubature rules applied to sensor data fusion for positioning[END_REF], [START_REF] Arasaratnam | Discrete-time nonlinear filtering algorithms using Gauss-Hermite quadrature[END_REF]. The corresponding deterministic points are indeed function of the dimension of the subspace and the number of points per dimension . Hereinafter, the latter is considered equal for all filters. We define the weighting matrix as . The prediction step can be done in parallel for each subspace. At time step , the previous state and covariance estimates ( , and ) and the estimation of the subspace process noise covariance are available. First we evaluate the sigma-points [START_REF] Golub | Matrix Computations[END_REF] and then we propagate each one through the corresponding transition function [START_REF] Closas | Bayesian nonlinear filters for direct position estimation[END_REF] The subspace predicted state is computed as the weighted mean of the propagated sigma-points [START_REF] Golub | Calculation of Gauss quadrature rules[END_REF] The predicted state is then constructed as the concatenation of each subspace predicted state, . The square-root factor of the predicted error covariance is [START_REF] Hilands | Nonlinear filtering methods for harmonic retrieval and model selection in Gaussian and non-Gaussian noise[END_REF] where is a square-root factor of such that , and , and denotes a general triangulation algorithm (for instance, the QR decomposition), where , , and is a lower triangular matrix such that . For computational reasons, we prefer to keep the square root as a triangular matrix of the dimension . This can be achieved by the thin QR decomposition [18, Section 5.2, Theorem 5.2.2]], which has a computational complexity of flops.

As for the prediction step, the update step can also be parallelized. Considering the -th filter, the sigma-points are first evaluated using the subspace predicted state and its corresponding predicted error covariance matrix [START_REF] Dash | Accurate tracking of harmonic signals in VSC-HVDC systems using PSO based unscented transformation[END_REF] and then propagated through the measurement function [START_REF] Dash | A hybrid unscented filtering and particle swarm optimization technique for harmonic analysis of nonstationary signals[END_REF] The predicted measurement is computed as the weighted mean of the propagated sigma-points [START_REF] Reddy | Fast tracking of power quality disturbance signals using an optimized unscented filter[END_REF] The square-root of the innovation covariance matrix is [START_REF] Alves | An adaptive algorithm for real-time multi-tone estimation and frequency tracking of non-stationary signals[END_REF] where denotes a square-root factor of such that , and

The cross-covariance matrix can be obtained from [START_REF] Niedzwiecki | Estimation and tracking of complex-valued quasi-periodically varying systems[END_REF] where Using now the standard Kalman solution we obtain the Kalman gain [START_REF] Mitrinovic | Analytic Inequalities[END_REF] the subspace estimated state (28) and the square-root factor of the corresponding error covariance 3(29)

The final state estimate is obtained as the concatenation of each subspace state estimates, .

III. ON THE MULTIPLE APPROACH

Considering the partitioned state-space model defined by ( 2) and ( 7), the posterior distribution of interest is . In the proposed method, the -th filter of the bank tracks the -th subspace using the subspace marginal predictive and filtering distributions specified in [START_REF] Merwe | The square-root unscented Kalman filter for state and parameter estimation[END_REF] and [START_REF] Arasaratnam | Cubature Kalman filters[END_REF], considering the implementation approximation stated in [START_REF] Arasaratnam | Discrete-time nonlinear filtering algorithms using Gauss-Hermite quadrature[END_REF], and the final estimate is constructed from the concatenation of the subspace estimates.

In the following subsections we address some questions which naturally arise when using the multiple approach.

A. Equivalence Between Both Approaches

Intuitively we can see that the estimation using the partitioning and the direct estimation of the full state may not be equivalent in a general case. But, when is the estimation obtained with both approaches equivalent?

The standard estimation can be expressed as

(30)
and the proposed multiple approach is . . . . . .

Expressions (30) and (31) are equivalent only when the subspaces are independent and one can write the posterior distribution as (32)

and the subspace marginal filtering distributions as (33)

In this case, we have that , where

Notice that the independence among subspaces does not imply that we deal with independent estimation problems, because the observations still may combine the full state:

(35)
The coupling of all the subspaces can also be seen within the MQKF structure through the innovations. Because the subspaces are independent, the -th filter subspace prediction is (36) but the predicted measurement [START_REF] Reddy | Fast tracking of power quality disturbance signals using an optimized unscented filter[END_REF] still depends on the full state (37) Moreover, the different subspaces are coupled in [START_REF] Fernández-Prades | Bayesian nonlinear filtering using quadrature and cubature rules applied to sensor data fusion for positioning[END_REF] through the innovations and the cross-covariance to compute the subspace estimates.

B. QKF Vs MQKF: Theory and Practice

In the previous subsection we stated that from a theoretical point of view the multiple approach is equivalent to the standard filtering method only when the subspaces are independent. But in a general case, which is the difference between both methods?

From a theoretical standpoint, we have to analyze the difference between the standard and the multiple approach. Regarding the implementation of the MSQKF, we need to assess the impact of using the estimates and instead of and .

1) Theoretical Analysis:

The standard solution uses the posterior density (38) and the multiple approach uses the subspace filtering densities (39) From a probabilistic point of view, the inability to marginalize the subspace filtering densities makes impossible to obtain a closed form comparison of these two distributions. That is why we resort to the Gaussian expressions of the posterior and the subspace marginal densities:

(40) (41)
Using expressions (41) and (39), we can compute the multiple approach log-posterior density with . This distribution may be reformulated as where corresponds to a vector containing the subspace estimates and is a block diagonal matrix

(42) (43)
The difference between both methods and the information that we lose with the partitioning is given by the difference between both Gaussian distributions, and , which are characterized by their mean and covariance matrix:

As we are dealing with a recursive estimation method, the update is directly related to the prediction. Notice that the same derivation can be done for the standard and subspace marginal predictive distributions, and , respectively, and we also need to compare their mean and covariance matrix:

where is also constructed as the concatenation of the subspace predicted states and is block diagonal. Concerning the prediction step (see Section II-B), note that each subspace predicted error covariance matrix is computed using the corresponding subspace process noise covariance , so the block diagonal matrix considers only the noise affecting each subspace, , instead of the full process noise covariance matrix . We lose the information about the correlation of the noise among partitions. Also, if there exists any information, because of the interconnection among subspaces, which may contribute to the off-diagonal elements of , it is not taken into account by the algorithm. The errors introduced in the prediction step are propagated to the update step and the computation of and . In this step, we also note that the innovation's covariance matrix is computed only over the subspace marginal predictive distribution instead of the complete predictive density, what may also imply a loss of information. For numerical results illustrating these effects see Section V-A.

2) Practical Implications: To assess the impact of using the predicted and estimated states instead of the true values for the interconnection among the different subfilters, refer to [START_REF] Arasaratnam | Discrete-time nonlinear filtering algorithms using Gauss-Hermite quadrature[END_REF], we perform here a first-order analysis. To that aim we consider the following linear/Gaussian state-space model (44) (45) where and act as the state transition and measurement matrices. The rest of the variables are defined as in the original state-space model, (1) and [START_REF] Djuric | Particle filtering[END_REF].

Applying the multiple approach, the -th subspace state equation is (46) where the process noise is distributed as and is the corresponding subspace state transition matrix. The multiple prediction step should be (47) but instead we use the following approximation (48)

We can separate the matrix into two blocks (the first one affecting the -th subspace, , and the other the rest, )

with dimensions and , respectively.

The covariance of the prediction error is Thus, the effect of using the estimation instead of the true value is that we introduce noise into the system, as it is evidenced in (50) and (51). The prediction error cross covariance matrix between the -th subspace and the rest is not available, and this is precisely the information that the algorithm discards when using the partitioning strategy.

Regarding the measurement update step, we can see that the different subspaces are interconnected to compute the innovations, (53) and the corresponding innovation covariance is (54) with defined as in (52). In this case, we are also introducing noise into the innovation, because the terms and should be null for equality. Regarding the state estimation we can see that this also introduces an error (55)

where we used a similar partition than for the state transition matrix (56) with dimensions and , respectively.

C. On the State Partitioning

We have seen in the previous subsections that the MQKF does not take into account possible correlations among noise process subspaces, therefore, there is a possible loss of information regarding interconnections among such subspaces due to the architecture of the algorithm. As a result, the information that is lost using the multiple approach is directly related to the partitioning, which is set by the user and should be determined according to the model. The questions to be considered here are: "How do we specify the state partitioning?" and "Which is the best partitioning?".

For the first question, the most important point to consider is that the partitioning should be based on the model under study. The preferred partitioning design depends on the application, the degree of the nonlinearity and the available computational resources. It is important to keep in mind that the required computational complexity which defines the resources needed, is directly related to the number of sigma-points per dimension, , and the subspace dimensions, . For a fixed complexity, the best partitioning is the one that groups the states which are highly correlated and puts the uncorrelated ones (or with low correlation) into different subspaces.

For example, in a multiple target tracking application, we would group the parameters of each target into a subspace. Otherwise, we could use an adaptive state partitioning method which first computes the correlation among states and then sets the partitions according to the result obtained.

IV. A COMPLEXITY RESULT FOR THE MQKF

The time complexity of an algorithm can be viewed as the number of floating point operations it performs per time step. The asymptotic time complexity of square-root SPKFs is known to be , where and represents the number of sigma points. This computation only considers the cost of the matrix operations, without taking into account the evaluations of the nonlinear functions, which implementation can range from a look-up table to very complex numerical methods that could represent the actual computational bottleneck of the algorithm. More details of this analysis can be found in [START_REF] Arasaratnam | Square-root quadrature Kalman filtering[END_REF], [START_REF] Closas | Bayesian nonlinear filters for direct position estimation[END_REF]. Thus, the number of sigma points is the dominant parameter in QKF schemes, as grows exponentially with the state dimension, and can be considered an indicator of the computational complexity of the algorithms.

Whereas the number of points used by a QKF is , the total number of points generated by the MQKF is . The computational complexity of SPKFs in general is highly related to the number of generated points, and thus reducing this value has a beneficial impact on the implementation cost. In this section, we are interested in identifying whether is larger than in general, and under which conditions. The result is stated in Proposition 1.

Proposition 1: Let and with , , and guaranteeing that . Then, (57) for and . Proof: The proof is given in Appendix A. This result proves that the MQKF is always reducing the number of generated quadrature points, and thus the computational complexity of the overall filter.

As a final remark, it should be pointed out that the multiple filtering architecture might not be suitable in general SPKFs. For instance, the UKF requires sigma-points, whereas a Multiple UKF would require , that is an increase of points. Similarly, the CKF generates cubature points, and a Multiple CKF would use exactly the same amount.

V. COMPUTER SIMULATIONS

In this Section, in order to provide illustrative numerical results, the performance of the proposed method is shown in an academic example and a practical estimation problem.

A. Illustrative Academic Example

We considered the academic example proposed in [START_REF] Arasaratnam | Cubature Kalman filters[END_REF], where state dimension can be arbitrarily set. States evolved according to with a zero-mean Gaussian noise with covariance matrix , and measurements were obtained as (58) where is a parameter used to tune the nonlinearity of the function and . With this setup, we compared the Root Mean Square Error (RMSE) of 6 nonlinear filters in their square-root version (i.e., with enhanced numerical stability), namely, the standard SQKF and the MSQKF with 5 different state partitions (see Table I). We averaged over 5000 independent Monte Carlo runs, with 100 measurements per run. The standard QKF was used as a benchmark for this problem, and the results were also compared to the CKF and UKF, being the state-of-the-art reference methods for lightweight nonlinear Gaussian filtering.

As the filters not always converged, we define the of failure: for each realization, a filter is said to fail if its resulting RMSE is larger than the RMSE at initialization. In the figures we only plot the RMSE of the realizations which did not fail, while the of failure is shown in the corresponding tables. Notice that the results in this section do not include those obtained by an Extended Kalman filter (EKF), the reason is that EKF exhibited a of failure, that is it diverged in this highly nonlinear example.

In order to assess the performance of the proposed method we considered three explanatory cases:

1) Case 1: In this first case, we considered that the state transition and the process noise covariance matrices were diagonal, so the state evolved according to , where ( filter) is equivalent to the conventional SQKF, which is plotted in order to validate our implementation (we will not plot again the results of in the following figures). As simulations show, Fig. 1, a remarkable reduction of the computational cost can be achieved by employing the multiple architecture with moderated (depending on the state-space partitioning) accuracy degradation, and always obtaining better results than the UKF and the CKF. The reason is that the third-order rules used by the UKF and CKF are not able to characterize the high nonlinearity of the model. Notice that the standard SQKF and the MSQKF considering the full state use 15625 points, and the MSQKF with more than 2 subspaces use less than 100 points (Table I), with the consequent reduction in the overall computational cost.

The filters which considered partitions with dimension , namely and , provided a worse estimation performance because the errors introduced by the MSQKF implementation (see Section III-B2) are larger than in case of considering triples and pairs . Moreover, the smaller is the subspaces dimension, the larger is the estimation error.

To overcome this problem we could to increase the noise covariance matrices, to allow the filters converge to the results obtained by the SQKF, which is known to be optimal in the minimum-mean-square-error (MMSE), the maximum likelihood (ML), and the maximum a posteriori (MAP) senses for all functions and expressible as a polynomial of degree [START_REF] Golub | Calculation of Gauss quadrature rules[END_REF]. Fig. 2 shows the results obtained with a modified process covariance matrix:

. With this configuration we can see that all the MSQKFs performed as the SQKF with notable savings in the computational cost.

Table II provides the of failure for each filter. Considering the setup with , we can see that filters and never failed in 5000 realizations. When compared to the CKF and the UKF, the of failure for the MSQKF is much lower even in the worst partitioning cases ( and ). When overestimating the process noise covariance, we decrease also the number of fails.

2) Case 2: In this case, we used the same setup as in Case 1 but introducing correlation in the process noise, that is, a non-diagonal covariance matrix . We considered a weak correlation matrix , with values in the main diagonal and in the off-diagonal entries; and a strong correlation matrix with values in the main diagonal and in the off-diagonal entries.

In the weak correlation case, , we can see (Fig. 3) that all the filters deal correctly with the process noise correlation, because there is few information outside the block matrices considered . When dealing with a strong correlation, , there is much more information outside which is lost, so a greater error is introduced. Notice that smaller the subspace dimensions are, the larger the amount of information lost and the bigger the estimation errors are.

Table III shows that with a weak correlation, the of failure for the MSQKFs is slightly higher than in the reference case , but in the strong correlation scenario only and resist to fail most of the time. Thus, in such strongly correlated noise scenarios, the partitions with higher dimension capture more information, and this constitutes the recommended partition strategy. With adequate tuning of the process noise covariance matrix, even in the strong correlation case, the MSQKFs perform as the SQKF with a drastically reduced computational cost, obtaining the same results as plotted in Fig. 2.

3) Case 3: In the third case we introduced an interconnection among states in their evolution, that is, a non-diagonal state transition matrix . We considered a first scenario where states were correlated in triples: and a second scenario where the states were correlated in pairs: Simulation results are in Fig. 4 and Table IV. Notice that, as expected, the error for (which considers the partition in pairs) was larger with than with . It can be explained by the fact that partition strategy is optimal when it fits the interconnection among states. So the partitioning should be related to the model, that is, considering correlated states in the same subspace provides better results.

When overestimating the process noise covariance, as done in Case 1 and Case 2, we obtained optimal results with all the MSQKFs, because a larger process noise covariance matrix allowed the filter to converge and implicitly introduced a higher

Fig. 2 .

 2 Fig. 2. Case 1: RMSE of state estimation, with an overestimated process noise covariance .

Fig. 3 .

 3 Fig. 3. Case 2: RMSE with two different correlated process noise covariance matrices, namely, (top) and (bottom).

Fig. 4 .

 4 Fig. 4. Case 3: RMSE with two different state transition matrices (3 3 and 2 2 correlations), namely, (top) and (bottom).

TABLE I DIFFERENT

 I SUBSPACE PARTITIONING AND THE CORRESPONDING NUMBER OF SIGMA-POINTS FOR

	,	, and		. The measurement
	noise variance was set to	,	,	and	.
	The filter used	and	, and was initialized as
	. The MSQKF with

AND Fig. 1. Case 1: RMSE of state estimation, with .

TABLE II OF

 II FAILURE FOR THE 8 FILTERS FOR CASE 1 WITH TWO CONFIGURATIONS OF

TABLE III OF

 III FAILURE FOR THE 8 FILTERS IN BOTH SCENARIOS FOR CASE 2

denotes the -th element (possibly a vector) in a vector and is the vector of all elements in except for .

Notice that the SQKF computes the square-root factor of the estimation covariances, and . The distributions in[START_REF] Merwe | The square-root unscented Kalman filter for state and parameter estimation[END_REF] and[START_REF] Arasaratnam | Cubature Kalman filters[END_REF] can be readily obtained using and .

uncertainty on the system model, that is, trusting the observation much more than the model itself. This is not a general statement and an overestimated process noise covariance may give worse performances depending on the application and the overestimation ratio.

B. Multiple Superimposed Sinusoids Estimation

In the presented application, we considered the problem of estimating the parameters of superimposed sinuosoids [START_REF] Hilands | Nonlinear filtering methods for harmonic retrieval and model selection in Gaussian and non-Gaussian noise[END_REF], which is a problem appearing in many engineering fields, such as power systems [START_REF] Dash | Accurate tracking of harmonic signals in VSC-HVDC systems using PSO based unscented transformation[END_REF]- [START_REF] Reddy | Fast tracking of power quality disturbance signals using an optimized unscented filter[END_REF], nuclear science [START_REF] Alves | An adaptive algorithm for real-time multi-tone estimation and frequency tracking of non-stationary signals[END_REF] or communications [START_REF] Niedzwiecki | Estimation and tracking of complex-valued quasi-periodically varying systems[END_REF].

The complex measurements were obtained as (59)

which can be rewritten as (60)

where . The state consisted of the amplitudes and the normalized frequencies per sinusoid, (61) that is, parameters were estimated. For each parameter we considered a random walk evolution, so the state evolved according to with , and .

We considered 3 sinusoids with the following initial parameters: , , , , , , so the initial state was . The signal was sampled at 5 KHz, the variances of the Gaussian process noise driving the states were and , and the measurement noise variance was set to . The filter was set with and , and initialized with a random variable with distribution , where . With this setup, we compared the RMSE of the estimation of the frequencies, , using the filters in Table V. As in the case of the academic example, the EKF diverged for all realizations. We made 400 independent Monte Carlo runs with 350 measurements per run (70 ms), and we set the number of sigma-point per dimension to . The of failure was defined as follows: a realization was said to fail if the error on the estimation of the frequencies was larger than 300 Hz. Considering this threshold we obtained the results plotted in Fig. 5 and the of failure given in Table VI. The simulations show the good performance of the MSQKF, corroborating the results obtained in the previous example. The MSQKF improves the CKF with a similar number of sigma-points ( uses 18 points) while being more robust, and with a suitable partitioning gives almost optimal performance compared to the SQKF with a notable complexity reduction (729 vs 54 sigma-points).

VI. CONCLUSIONS

The QKF constitutes a powerful tool for dealing with nonlinear dynamic systems. However, in order to estimate accurately the posterior distribution, it requires a number of sigmapoints that increases exponentially with the dimension of the state-space model. In this paper, a new method based on the partitioning of the state-space, called Multiple QKF, was proposed in order to alleviate this issue. It was proved in Proposition 1 that the state-partitioning approach reduces the computational complexity of a QKF operating on the complete system.

The performance of the filter was assessed by computer simulations using an academic example, and compared to the standard QKF, CKF and UKF, with a remarkable reduction of the computational cost with a relatively low performance degradation compared to the QKF, while improving the performance of the other state-of-the-art methods. The new method's performance was also shown for a practical estimation problem (where the standard QKF is not an option because of its high computational cost), corroborating the good results obtained in the first example.

The assumptions made are that the dynamic system is driven by Gaussian processes and that the possible nonlinearities are approximated by the Gauss-Hermite quadrature rules. Separability of process function is not required, although it is desirable to partition the state-space in such a way that one groups the states which are highly correlated and puts the uncorrelated ones (or with low correlation) into different subspaces. The simplifications made are that the subspace cross-terms of the noise covariance are neglected and that the coupling among filters is performed by point estimates. Depending on the partitioning, these simplifications may degrade the performance of the filter. We have observed that overestimation of the model covariance might result in more robust implementations of the MQKF when subspaces are correlated.

To conclude, the MQKF can be considered to be a versatile tool for practitioners with an applicability covering a large variety of high-dimensional problems.

APPENDIX PROOF OF PROPOSITION 1

Proof: Let us operate with the difference :

we would like to see if , that is under which conditions a MQKF scheme provides computational cost reduction with respect to conventional QKF. We resort to the procedure used to proof some set of Weierstrass' inequalities [START_REF] Mitrinovic | Analytic Inequalities[END_REF], which tackle a similar problem 4 .

For the sake of clarity, let us define , then we can express as the following function of interest (64) which is multivariate and depending on the different dimensions of each subspace .

Since we seek to proof that , it suffices to show that the function is lower bounded by a positive constant. Let us thus analyze and characterize the function as follows, with Fig. 6 being a supporting illustration for the mathematical derivations. Suppose now that all but one variable are fixed, then we obtain a linear function of a single variable (65) with constants (66)

The support in which function (65) can be evaluated is in the closed set in the real line, with the limit points corresponding to the cases (i.e., each state has an associated filter) and (i.e., the conventional QKF without state partitioning), respectively. Since (65) is linear on , its lower bound is given by evaluation of one of its limit points depending on the sign of the slope . We can easily see that , if we identify that the dimension of subspaces is at least equal to 1 and that the minimum number of quadrature points 5 is 2. Then, (67) and thus (68) Therefore, the supremum and infimum of are (69) (70) 4 More precisely, we recall the Weierstrass' product inequality that states that where and . 5 Note that for , Gauss-Hermite rules are exact for polynomials of degree 1. The case of linear systems is not of interest in the context of QKF as these could be tackled optimally by other means, namely the KF. Also, first-order approximations could be obtained by the Extended KF.

for any subspace , respectively. Notice that the root for which is positive (71)

The analysis holds , and thus it can be extended to the rest of variables in (64) to see that the lower bound is (72) (73) and then

. To show that it suffices to prove that . After straightforward mathematical manipulation of the latter, we found the following condition to ensure strict positiveness of :


Sasho Nedelkoski
email: nedelkoski@tu-berlin.de

Jasmin Bogatinovski

Ajay Kumar Mandapati

Soeren Becker

Jorge Cardoso
email: jorge.cardoso@huawei.com

Odej Kao

Multi-Source Distributed System Data for AI-powered Analytics

Keywords: aiops, distributed system, dataset, tracing, metrics, logs, anomaly detection, root-cause analysis

The emerging field of Artificial Intelligence for IT Operations (AIOps) utilizes monitoring data, big data platforms and machine learning to automate operations and maintenance (O&M) tasks in complex IT systems. The available research data usually contain only a single source of information, often logs or metrics. The inability of the singlesource data to describe the precise state of the distributed systems leads to methods that fail to make effective use of the joint information, thus, producing a large number of false predictions. Therefore, current data limits the possibilities for greater advances in AIOps research. To overcome these constraints, we created a complex distributed system testbed, which generates multi-source data composed of distributed traces, application logs, and metrics. This paper provides detailed descriptions of the infrastructure, testbed, and the experiments for the generated data. Furthermore, it identifies how this data can be utilized as a stepping stone for the development of novel methods for O&M tasks such as anomaly detection, root cause analysis, and remediation. The data from the testbed and its code is available at https://zenodo. org/record/3549604.

Introduction

AIOps refers to multi-layered technology platforms that automate and enhance IT operations by using analytics and machine learning [START_REF] Dang | Aiops: real-world challenges and research innovations[END_REF]. AIOps was introduced to reduce the cost and increase the effectiveness of O&M tasks on everincreasing complex public, private, edge, mobile, and hybrid cloud environments. The transition from mainframes, to virtual machines, to containers, and serverless computing made existing approaches and tools which rely on simple statistical methods obsolete due to the increasing complexity and communication patterns between services. Notable examples include Zabbix, Cacti, and Nagios [START_REF]Nagios enterprises[END_REF]21].

Monitoring data is a key element of new AIOps tools and one of the cornerstones of research. The data generated by distributed IT systems can be classified into three main categories: metrics, application logs, and distributed traces [START_REF] Sridharan | Distributed Systems Observability: A Guide to Building Robust Systems[END_REF]. Metrics are numeric values measured over some time. They describe the utilization and status of the infrastructure, typically regarding CPU, memory, disk, network throughput, and service call latency. Application logs enable developers to record what actions were executed at runtime by software. Service, microservices, and other systems generate logs which are composed of timestamped records with a structure and free-form text. Distributed traces record the workflows of services executed in response to requests, e.g., HTTP or RPC requests. The records contain information about the execution graph and performance at a (micro)service level.

Recently, various approaches -focusing on a wide range of datasets, O&M tasks, and IT systems -have been proposed. This includes a variety of tasks, which extract knowledge from a specific type of data. For example, anomaly detection has been applied to metrics (numeric) [START_REF] Schmidt | Iftm -unsupervised anomaly detection for virtualized network function services[END_REF], logs (unstructured numeric and text data) [START_REF] Du | Deeplog: Anomaly detection and diagnosis from system logs through deep learning[END_REF][START_REF] Meng | Loganomaly: Unsupervised detection of sequential and quantitative anomalies in unstructured logs[END_REF], and also to distributed system traces (unstructured numeric and text data) [START_REF] Nedelkoski | Anomaly detection and classification using distributed tracing and deep learning[END_REF][START_REF] Nedelkoski | Anomaly detection from system tracing data using multimodal deep learning[END_REF].

The existing research has mainly explored publicly available data, which usually captures only a single data source category. This limits both the development of new methods that could extract knowledge from multi-source data and their proper evaluation. The absence of data repositories capturing the three data categories from modern distributed systems prevents the development of methods for multi-source mining, knowledge extraction, semantic information learning from the naturally linked data sources. Furthermore, enables fault detection, root-cause analysis, and remediation. These contributions can provide further advances in the field as existing approaches typically produce a large number of false positives.

We address these issues by producing the following contributions:

-A new data of metrics, logs, and traces generated by a distributed system based on microservice architecture.

-Description of the approach developed to generate the multi-source system data.

-Analysis of existing datasets utilized for the evaluation of AIOps algorithms, highlighting their benefits and their limitations.

-Applications of the multi-source data to develop new algorithms to support additional O&M tasks.

Specifically, during the development and data generation process, we adhere to the following requirements to ensure quality of the data: (R1) originality, (R2) reusability, (R3) quality, and (R4) extendability.

Related Work

Metrics, logs, and traces are important data sources that are fundamental to the operation of complex distributed systems. In following we study the related work for these data accordingly.

The metrics data are obtained from monitoring of the resources such as CPU, memory, disk, network throughput and latency. A plethora of available collections of datasets containing metric data can be found in Stonybrook [20]. As a collection, it has multiple datasets for different tasks related to anomaly detection. Numenta [START_REF] Ahmad | Unsupervised real-time anomaly detection for streaming data[END_REF] predominantly stores datasets from streaming and realtime applications, while Harvard [START_REF] Goldstein | Unsupervised Anomaly Detection Benchmark[END_REF], ELKI [START_REF] Elki | [END_REF], LMU [11] store network intrusion data.

The main challenge AIOps systems built on log data are facing, is the unstructured nature of the logs. This problem usually requires prior and proper preprocessing and/or inclusion of domain knowledge. Often, approaches extract log key identifiers for the logs and are modeling their sequences. There exist two resources of log data for cluster systems available. The CFDR resource [3] stores link to 19 log datasets grouped in 11 data collections. The datasets cover both hardware and software logs. The second resource is the loghub data resource [START_REF] Zhu | Tools and benchmarks for automated log parsing[END_REF]. It consists of 16 datasets describing systems spanning across distributed systems, supercomputers, operating systems, mobile systems, server applications and standalone software. The datasets cover a different period from a few days until a few months. From the perspective of the system description, these data have weakness in providing just a single aspect of the system.

In microservice architectures, traces are graph-like structures composed of events or spans [16]. The traces represent the system execution workflow, hence detailed information for individual services and the causal relationship to other related services can be inferred. Nedelkoski et al. [START_REF] Nedelkoski | Anomaly detection and classification using distributed tracing and deep learning[END_REF][START_REF] Nedelkoski | Anomaly detection from system tracing data using multimodal deep learning[END_REF] introduce novel anomaly detection methods for distributed tracing data. They proposed a multimodal neural network with long short-term memory (LSTM) to enable the learning from the sequential nature in the tracing data. They describe how the data is obtained, but the datasets are not publicly available. Azure Public dataset composes of two datasets representing two traces of the virtual machine of Microsoft Azure [START_REF] Cortez | Resource central: Understanding and predicting workloads for improved resource management in large cloud platforms[END_REF]. It is mostly utilized to improve resource management in large cloud platforms. Alibaba's cluster data is a collection of two datasets from real-world production [START_REF]Alibaba trace data[END_REF]. Google's collection of two tracing datasets originates from parts of Google cluster management software and systems [START_REF]Google trace data[END_REF].

Our collection of data, describing the same system from the three perspectives of logs, metrics, and traces, to the best of our knowledge, is the first of its kind. This enables building models with diverse complementary information, hence making AIOps systems to perform better [START_REF] Nedelkoski | Anomaly detection from system tracing data using multimodal deep learning[END_REF].

Dataset generator

In this section, we describe the infrastructure, experiments, workload, and the injected faults as part of the testbed for data generation. The testbed and the generated data follow the requirements stated above, as every parameter stated in the following can be easily changed, satisfying part of R2, and R4.

Infrastructure

An OpenStack [START_REF] Shrivastwa | Open-Stack: Building a Cloud Environment[END_REF] testbed based on a microservice architecture that is running in a dockerized environment called Kolla-Ansible was first deployed. OpenStack is a cloud operating system that controls large pools of computing, storage, and networking resources throughout a data-centre. They are all managed and provisioned through APIs with common authentication mechanisms.

The experimental testbed setup is shown in Figure 1 and for the purpose of the generation of the data it consists of one control node named wally-113 and four compute nodes: wally-127, wally-122, wally-123, and wally-124. It was deployed on bare-metal nodes of a cluster where each node has RAM 16GB, 3x 1TB of disks, and 2x 1Gbit Ethernet NIC. Three hard disks were combined to a software RAID 5 for data redundancy.

Workloads and faults injected

To generate workloads and inject faults into the infrastructure we used Rally.

Rally docker image was used to create the load and inject os-faults appropriately. The listed workloads and faults in the following cover user request that is served by the main OpenStack projects:

-Create and delete server. We injected a compute fault which is restarting the API container that runs on the compute nodes. -Create and delete image. We inject the fault in the glance-api running on the controller node. -Create and delete network. There are various components that we focus on while injecting faults such as disrupting the below-mentioned services running in docker containers: neutron metadata agent, neutron l3 agent, neutron dhcp agent, neutron openvswitch agent and neutron server.

We performed two different experiments. In the first experiment, the user actions as a workload were executed in a sequential way, when one finishes then the next is started. This experiment was performed for 750, 1000, and 3000 iterations (create and delete server, create and delete image, create and delete network ), where faults were injected every 250 iterations respectively. The fault was injected in only one iteration, however, we noticed that some of the faults take time and propagate the errors to other iterations as well. In the second experiment, the Rally workloads were concurrently executed. This experiment was performed for 2000, 3000, and 6000 iterations for create and delete server, create and delete image and create and delete network, respectively. The faults were injected at different rates, 250 for create and delete server and create and delete image and 500 iterations for create and delete network. The number of iterations for each action was chosen so that all workloads approximately finish at the same time. The data from the second experiment is slightly more suited for multi-source methods utilizing distributed log data, as it was generated with that as a goal. Also, HTML reports were collected which correlates all the events of creations, failures and fault injections. These reports serve as pseudo ground truth for the normal and anomalous state of the system.

Dataset Description

The workloads and faults described in the previous section were executed on the testbed. As explained, the execution generated three main categories of observability data: distributed traces, metrics, and application logs. These data were recorded in concurrently to provide the state of the system from multiple points of view, which satisfies the R1 for originality as no such dataset exists in previous work.

Metrics

The metrics data category contains data for the 5 physical nodes in the infrastructure. The 5 files are named metrics wally N, where N is either the controller node or one of the compute nodes. Each of these files has 7 features: now (the timestamp of the recording), cpu.user (percentage time spent in userspace), mem.used (the RAM usage of the physical host), load.cpucore (the number of cores of the physical host), load.min1, min5, min15 (Linux load averages are system load averages that show the running tasks demand on the system as an average number of running plus waiting threads).

Logs

The log files are distributed over the infrastructure and they are grouped in directories by the OpenStack projects (e.g., nova, neutron, glance, etc.) at the wally nodes. At each of the physical nodes, different projects are running. The control node has more services running and thus has more log files for the Open-Stack projects. We provide the raw log directories in this dataset along with the aggregated log file. Using the Elastic Search and Kibana stack we can aggregate all the logs into a central database which can serve as a starting point for the analysis.

The log entries have in total of 23 features. Not all the features are always present for all the log entries. The features appearing are: id, index, score (added metadata from Kibana), type (collector which is responsible for sending all the metrics and logs to Kibana), hostname (name of the physical host (e.g., wally113)) user id, project domain, tenant id, request id, user domain, domain id (features describing the user request to Openstack) timestamp, @timestamp (time when the record was created), log level (describes the level of the log entry (info, error, warrning etc.)), pid (Process ID), Payload (has the most important information of the log i.e., the body of the log entry), programname (the OpenStack project that generated the log entry), python module (module responsible for generation of the log entry), logger (tells which project logs the event) http related fields (only present if there is an HTTP call describing the endpoint, status core, version, and the method).

Traces

The traces in the dataset are contained in 3 directories: boot delete, create delete image, and network create delete. Each of the directories contains the scripts for running the workload and the fault injections along with the actual tracing data. These directories contain .JSON files of the traces. This structure is preserved among all types of workloads (Rally actions).

Every trace has its features in the JSON entries or events. These features depend on multiple factors such as the user request, infrastructure, load balancers, and caching. An event is a vector of key-value pairs (k i , v i ) describing the state, performance, and further characteristics of service at a given time t i . In following we describe the main features of the events in a trace:host. Name of the physical host, name, event name (e.g., compute apistop), service. service name (e.g., osapi compute), project, Openstack project (e.g., nova), timestamp, the time when the event is recorded, trace id, ID of the span (contains two events, e.g., compute api-stop and compute api-start), parent id, the parent id gives the ID of the parent event. This attribute can be used to represent the trace in a graph, base id. ID of the trace, different events and spans with same base id belong to one trace.

Two events, start and stop (e.g., compute apistart and compute apistop) with the same trace id form a span. The subtraction between the stop timestamp and the start timestamp gives the duration of the span. The above features together with the duration are the most important in describing the structure, preserving the parent-child causal relationship, and the duration which represents the response time of the service invoked.

The events also contain other attributes that can be found for specific types. For example, path, scheme, method for HTTP calls, where the path and scheme represents the HTTP endpoint and HTTP scheme and method can be GET or POST. Further, the db statement in DB (data base) calls gives information about the SQL query, while the function, name, args, kwargs in RPC calls tell which function was invoked with the its corresponding arguments.

Applications of Multi-source AIOps

While previous work has been generally done on single-source data, we believe that to develop robust, holistic approaches for anomaly detection, root-cause analysis, self-healing, resource optimization, and performance analysis a multisource data is highly desirable. In this section, we shortly describe anomaly detection and root-cause analysis can exploit the benefits of processing multisource observability data.

Multi-source Anomaly Detection. The distributed logs over projects and physical hosts enable multimodal end-to-end learning and more robust log anomaly detection. Of course, this adds complexity for data integration and fusion, as the distributed logs are produced with different timestamps. Together, the distributed logs and metrics can again be combined into more complex model or network of models. Lastly, the graph-like structures of the tracing data can be incorporated to complete the robust anomaly detection where all available observability data is considered.

Root-cause Analysis. The integration of multi-source observability data can be exploited by using some kind of Fishbone diagrams [START_REF] Ishikawa | Guide to Quality Control[END_REF] to find the root-cause of problems. A method can start with simple metric-only anomaly detection, which typically provides little information about the root-causes of problems, and drill down to more complex data structures which are richer in explaining anomalies. For example, one can start by analyzing the latency of microservices endpoints. If anomalies are detected after processing metrics, one can use the timeframe when the anomaly occurred to select and analyze structural changes in traces. Traces can provide information about which servers are possibly faulty. Afterwards, application logs can be accessed to find the root-cause of problems.

Conclusion

AIOps systems rely on suitable observability data. We released a multi-source data containing distributed metrics, logs, and tracing data obtained from a complex distributed system based on microservice architecture. We describe in details the infrastructure, experiments performed, and the fault injection. Furthermore, we provided descriptive statistical properties of the data.

Furthermore, we motivated possible applications of this data for improvements in anomaly detection, root-cause analysis, remediation, and feature extension. We hope that this dataset will foster advances in the research of AIOps, which has been limited mainly to explored data capturing only a single data source category.

Fig. 1 .

 1 Fig. 1. Illustration of the infrastructure from where the data was generated.