Alessandro Gecchele

Collision Entropy Estimation in a One-Line Formula

Keywords: Rényi entropies, collision entropy estimation, collision entropy rate estimation

come

Collision Entropy Estimation in a One-Line Formula

Introduction

The information theory indices belonging to the parametric family of Rényi entropies are able to express, each with a different weight, the information content of a discrete probability distribution (DPD) [START_REF] Rényi | On measures of entropy and information[END_REF]. Typical members of this family are, for example, Shannon entropy, collision entropy and min-entropy. These indices can also be used to classify the output of experimental processes studied in any branch of the applied sciences, provided their reduction to pseudostationary discrete-state processes and then in the form of DPDs. Since usually, during the experiments, only brief realizations can be obtained from the process under investigation, and since the realizations give rise to relative frequency distributions (RFDs) and not to DPDs, then these indices, being based on probabilities, have to be estimated through the elaboration of the few available data. In this regard, the methods for the estimation of Rényi entropies are of two kinds: 1) those that first aim to estimate the probability distribution from the relative frequencies and then plug the estimated probabilities into the formulas of the entropies and 2) those that circumvent the still-open problem of the estimation of the probabilities and aim to estimate the entropy indices through the application of other elaborations to the data. Despite the numerous studies carried out in the last decades (e.g., [START_REF] Grassberger | Finite sample corrections to entropy and dimension estimates[END_REF], [START_REF] Cachin | Smooth Entropy and Rényi Entropy[END_REF], [START_REF] Schmitt | Estimating the Entropy of DNA Sequences[END_REF], [START_REF] Holste | Bayes' estimators of generalized entropies[END_REF], [START_REF] Strong | Entropy and Information in Neural Spike Trains[END_REF], [START_REF] De Wit | When do finite sample effects significantly affect entropy estimates?[END_REF], [START_REF] Antos | Convergence properties of functional estimates for discrete distributions[END_REF], [START_REF] Nemenman | Entropy and inference, revisited[END_REF], [START_REF] Paninski | Estimation of entropy and mutual information[END_REF], [START_REF] Chao | Non parametric estimation of Shannon's index of diversity when there are unseen species[END_REF], [START_REF] Schürmann | Bias analysis in entropy estimation[END_REF], [START_REF] Paninski | Estimating entropy on m bins given fewer than m samples[END_REF], [START_REF] Bonachela | Entropy estimates of small data sets[END_REF], [START_REF] Grassberger | Entropy Estimates from Insufficient Samplings[END_REF], [START_REF] Hausser | Entropy inference and the James-Stein estimator, with application to nonlinear gene association networks[END_REF], [START_REF] Lesne | Entropy estimation of very short symbolic sequences[END_REF], [START_REF] Xu | Renyi's Entropy, Divergence and Their Nonparametric Estimators[END_REF], [START_REF] Vinck | Estimation of the entropy based on its polynomial representation[END_REF], [START_REF] Valiant | Estimating the Unseen: Improved Estimators for Entropy and Other Properties[END_REF], [START_REF] Zhang | Bias Adjustment for a Nonparametric Entropy Estimator[END_REF], [START_REF] Acharya | The complexity of estimating Rényi entropy[END_REF], [START_REF] Archer | Bayesian entropy estimation for countable discrete distributions[END_REF], [START_REF] Li | Improved estimation of entropy for evaluation of word sense induction[END_REF], [START_REF] Zhang | Entropic representation and estimation of diversity indices[END_REF], [START_REF] Acharya | Estimating Rényi entropy of discrete distributions[END_REF], [START_REF] De Oliveira | A Note on the Shannon Entropy of Short Sequences[END_REF], [START_REF] Berrett | Efficient multivariate entropy estimation via k-nearest neighbour distances[END_REF], [START_REF] Verdú | Empirical estimation of information measures: a literature guide[END_REF], [START_REF] Goldfeld | Convergence of smoothed empirical measures with applications to entropy estimation[END_REF], [START_REF] Contreras Rodríguez | Selecting an effective entropy estimator for short sequences of bits and bytes with maximum entropy[END_REF], [START_REF] Kim | On the efficient estimation of Min-entropy[END_REF], [START_REF] Grassberger | On Generalized Schürmann Entropy Estimators[END_REF]), optimal estimators have not been found yet. Moreover, this persistent lack of satisfactory solutions for the estimation of the indices belonging to the Rényi family (and for the estimation of their more rapidly converging derived quantities called Rényi entropy rates) has prompted, as a side effect, the proliferation of other similar indices conceived in many different ways (e.g. [START_REF] Pincus | Approximate entropy as a measure of system complexity[END_REF], [START_REF] Richman | Physiological time-series analysis using approximate entropy and sample entropy[END_REF], [START_REF] Manis | Bubble entropy: An entropy almost free of parameters[END_REF]), but all having the same purpose of classifying data with a nonparametric approach. An overview of this peculiar situation can be found in [START_REF] Ribeiro | The entropy universe[END_REF], where Ribeiro et al. collected and described a "galaxy" of at least thirty indices somehow functionally equivalent to those of the family initially proposed by Rényi (and to their rates). In this context, the search for the best estimators of the original indices seems most appropriate. In this regard, Skorski ([38], [START_REF] Skorski | Towards More Efficient Rényi Entropy Estimation[END_REF]) rightly pointed out that the estimation of those integer-order Rényi entropies that have a parameter value greater than one reduces to the estimation of the moments of a DPD. Our work just starts from this latter consideration and limits its investigation only to the case of the estimation of the second raw moment, which, in turn, allows the collision entropy to be estimated.

Theoretical Methods

Transforming a Discrete-State Stochastic Process into a DPD

Consider a discrete-state stochastic process (DSP q ) x -∞ , . . . , x i-1 , x i , x i+1 , . . . , x ∞ whose values belong to an alphabet A q containing q ordered symbols. Let Ω(q, d) be a d-dimensional discrete sample space resulting from the Cartesian product d times of A q .

Ω(q, d) = A q × A q × ... × A q d times , (1)
and let n = q d be the cardinality of the sample space Ω(q, d). According to the procedure indicated by Shannon in [START_REF] Shannon | A mathematical theory of communication[END_REF] at pages 5 and 6, the infinite sequence of samples constituting the DSP q can be transformed into occurrences #(e k ) of the elementary events of Ω(q, d) by progressively considering all the d-grams taken from the samples as if they were the vector coordinates of the events and counting the number of times that each vector appears in the sequence. Then, according to the frequentist definition of probability, the final resulting DPD is expressible in set theory notation as

p(Ω(q, d)) DSP q = p(e k ) DSP q = #(e k ) DSP q ∑ n k=1 #(e k ) DSP q e k ∈ Ω(q, d) . ( 2
)
In the following, in the absence of ambiguity, p(Ω(q, d)) DSP q -that is, a DPD obtained by elaborating the data of a DSP q -will be indicated with the bold symbol p and one of its elements with p k .

Integer-Order Rényi α-Entropies as Synthetic Indices for the Characterization of DPDs

In general, a DPD can be characterized by some indices, each of which can quantify the presence rate of a particular feature in the distribution. The parametric family of integerorder Rényi α-entropies is composed of synthetic indices suitable for the characterization of DPDs from the point of view of their informative content [START_REF] Rényi | On measures of entropy and information[END_REF]. They are defined as

α = 1 H 1 (p) ≜ - n ∑ k=1 p k log p k α ∈ N + α ̸ = 1 H α (p) ≜ 1 1 -α log n ∑ k=1 p α k 0 ≤ H α (p) ≤ log n α -→ ∞ H ∞ (p) ≜ -log max{p}. (3)
The corresponding specific integer-order Rényi α-entropies of the DPD p are then defined as

α = 1 η 1 (p) ≜ H 1 (p) log n = - n ∑ k=1 p k log n p k α ∈ N + α ̸ = 1 η α (p) ≜ H α (p) log n = 1 1 -α log n n ∑ k=1 p α k 0 ≤ η α (p) ≤ 1 α -→ ∞ η ∞ (p) ≜ H ∞ (p) log n = -log n max{p}. (4)
Once the value of a specific entropy is known, it is always possible to retrieve the value of the corresponding plain entropy, expressed in a particular base b and for a particular cardinality n, using the following conversion formula:

H α (p, b, n) ≜ η α (p) log b n. (5)
Specific entropies are preferable to plain entropies because:

1. they are the result of a min-max normalization, that is obtained using the minimum and the maximum possible values of plain entropies (respectively 0 and log n);

2. they are formally independent from the number of ordered symbols q chosen for the quantization of the range of the output values of the process and independent from the cardinality of the sample space n; for this reason, they allow the comparison of values obtained from different distributions, even generated using different sample spaces; 3.

they allow the doubt on the choice of the base for the logarithm present in the formula of entropies ( 2 or e or 10 ) to be removed, thanks to the use of a variable base, depending on the cardinality of the considered sample space ( n );

Rényi Entropy Rates

Unlike Rényi entropies, whose utility is mainly related to the classification of DPDs, Rényi entropy rates are important theoretical quantities useful for the characterization of DSP q s [41], [START_REF] Golshani | Some properties of Rényi entropy and Rényi entropy rate[END_REF]; they are defined as

H ′ α (DSP q ) ≜ lim d→∞ 1 d H α (p(Ω(q, d)) DSP q ) 0 ≤ H ′ α (DSP q ) ≤ log q. (6)
Moreover, it is known that, for strongly stationary DSP q , any Rényi entropy rate converges to the same limit of a sequence of Cesaro means of conditional entropies:

H ′ α (DSP q ) = lim d→∞ H α (p(A d )|p(A 1 × A 2 × • • • × A d-1 )). (7)
and, as conditional Rényi entropies preserve the chain rule [START_REF] Golshani | Rényi entropy rate for Gaussian processes[END_REF], [START_REF] Teixeira | Conditional Rényi Entropies[END_REF], [START_REF] Fehr | On the Conditional Rényi Entropy[END_REF], they can also be calculated as

H ′ α (DSP q ) = lim d→∞ H α (p(Ω(q, d)) DSP q ) -H α (p(Ω(q, d -1)) DSP q ) . (8)

Specific Rényi Entropy Rate

Similarly to Formula (4), specific Rényi entropy rate is defined by the following min-max normalization:

η ′ α (DSP q ) = H ′ α (DSP q ) log q = = lim d→∞ H α (p(Ω(q, d)) DSP q ) -H α (p(Ω(q, d -1)) DSP q ) log q = = lim d→∞ d η α (p(Ω(q, d)) DSP q ) -(d -1) η α (p(Ω(q, d -1)) DSP q ) , (9)
with 0 ≤ η ′ α (DSP q ) ≤ 1.

Relationship between Specific Rényi Entropy Rate and Specific Rényi Entropy

In summary, the following relationship subsists:

η ′ α (DSP q ) = lim d→∞ η α (p(Ω(q, d)) DSP q ) (10)
This means that, varying d, the specific Rényi entropy tends to the same value of the specific Rényi entropy rate, with the important difference being that the rate of convergence of the specific Rényi entropy rate is much faster than the rate of convergence of the specific Rényi entropy. For this reason, when possible, using the specific Rényi entropy rate is preferable to using the specific Rényi entropy.

Empirical Methods

Transforming a Realization into a Distribution of Relative Frequencies

For the practical cases, the theoretical procedure described in § 2.1 can be adapted according to the following procedure already presented with greater generality in [START_REF] Packard | Geometry from a Time Series[END_REF] and in [START_REF] Takens | Detecting strange attractors in turbulence[END_REF]: consider the N samples x 1 , x 2 , . . . , x d , x d+1 , . . . , x N of a realization r q extracted from a DSP q . Each d-gram composed of d adjacent samples of r q is interpreted as the occurrence of the elementary event of a d-dimensional sample space Ω(q, d) having just those values as vector components. For example, the first two d-grams taken from r q , (x 1 , x 2 , ..., x d ) and (x 2 , x 3 , ..., x d+1 ) identify the first occurrences of two elementary events. The count of the occurrences of the events is performed for all the d-grams progressively identified in the sequence of the samples of r q . Finally, the absolute frequency of every elementary event #(e k ) is divided by the total number of occurrences (L = ∑ n k=1 #(e k ) r q = Nd + 1), yielding its relative frequency f (e k ) r q . The final resulting RFD is expressible in set theory notation as

f (Ω(q, d)) r q = f (e k ) r q = #(e k ) r q ∑ n k=1 #(e k ) r q e k ∈ Ω(q, d) (11)
In the following, in the absence of ambiguity, an RFD f (Ω(q, d)) r q resulting from the insertion of the data of a realization in a sample space will be simply indicated with the bold symbol f and f k indicates one of its elements.

Estimating the Second Raw Moment of a DPD

Preliminarily, the α th -raw moment of a DPD p and the α th -raw moment of a RFD f are defined as

M α (p) ≜ n ∑ k=1 p α k , M α ( f ) ≜ n ∑ k=1 f α k 1 n α-1 ≤ M α (•) ≤ 1 (12)
Limited to the raw moments of Poissonian distributions, Grassberger in 1988 [START_REF] Grassberger | Finite sample corrections to entropy and dimension estimates[END_REF], Formula (8), and subsequently Schürmann in 2004 [START_REF] Schürmann | Bias analysis in entropy estimation[END_REF], Formula (6), reported the theoretically demonstrable, unique unbiased estimator, repeated in Formula (13):

M α (p) Poisson = n ∑ k=1 p α k r q = n ∑ k=1 1 L α #(e k ) r q ! (#(e k ) r q -α)! r q p α k := 0 for #(e k ) r q < α, (13)
where • r q is the mean over the infinite number of realizations that can be taken from the underlying process. For the specific case of the estimation of the second raw moment, Formula (13) becomes:

M 2 (p) Poisson = n ∑ k=1 [#(e k ) r q -1]#(e k ) r q L 2 r q = n ∑ k=1 f 2 k - 1 L r q = M 2 ( f ) - 1 L r q . ( 14
)
As far as we know, the scientific literature does not indicate whether the result of Formula ( 14) can also be valid for distributions different from Poissonians. So, from now on we proceed assuming provisionally that this hypothesis is true, and we leave the decision concerning its acceptance or rejection to the phase of the interpretation of the results of the Monte Carlo experiments described in one of the following sections. The hypothesis can be resumed as:

∀ DSP q M 2 (p) DSP q = max M 2 ( f ) - 1 L , 1 n r q , ( 15
)
where the lower limit 1 n is necessary because, when the cardinality of the sample space becomes high and the data density becomes too rarefied, the only possible estimate of the probability distribution results in the uniform distribution.

Estimating the Specific Collision Entropy of a DSP q

Collision entropy is the particularization of Formula (3) for α = 2, and it is defined as

H 2 (p) ≜ -log n ∑ k=1 p 2 k = -log M 2 (p) 0 ≤ H 2 (p) ≤ log n (16)
Inserting Formula ( 16) into Formula (4), the specific collision entropy is defined as

η 2 (p) ≜ - H 2 (p) log n = -log n M 2 (p) 0 ≤ η 2 (p) ≤ 1. ( 17
)
In the steps of Formulas ( 13) and ( 14), the displacements of the symbol that indicates the average over different realizations ⟨•⟩ r q from the outside to the inside of the symbol of summation ∑ and vice versa are mathematically indisputable. But the application of the logarithm to the second raw moment for arriving at the estimation of the collision entropy does not allow these shifts anymore. In fact, although the two possible expressions for the evaluation of the mean over the realizations give similar results in the presence of

RFDs (i.e. -log n M 2 ( f ) r q ≃ -log n ⟨M 2 ( f )⟩ r q )
, in general they differ remarkably when the logarithm is applied to the estimate of the second raw moment:

-

log n max M 2 ( f ) - 1 L , 1 n r q
Mean of Logs of Moment (MLM)

̸ = -log n max M 2 ( f ) - 1 L , 1 n r q
Log of Mean of Moments (LMM)

. ( 18
)
Consequently, the estimation of the specific collision entropy is performed averaging the previous two possible expressions:

η 2 (p) DSP q = -log n M 2 (p) = MLM + LMM 2 . ( 19
)
This is also the main result of this paper. The estimation of plain collision entropy can be obtained by inserting Formula (19) into Formula (5).

Estimating the Specific Collision Entropy Rate of a DSPq

From Formula (9) and Formula [START_REF] Vinck | Estimation of the entropy based on its polynomial representation[END_REF], it can be inferred that

η ′ 2 (p(Ω(q, d)) DSP q ) = d η 2 (p(Ω(q, d)) DSP q ) -(d -1) η 2 (p(Ω(q, d -1)) DSP q ) (20)
and

η ′ 2 (DSP q ) = min η ′ 2 (p(Ω(q, d)) DSP q ) 1 ≤ d < ∞ . ( 21
)

Method of Validation of Entropy Estimators

Monte Carlo simulations are the most correct experiments for observing the average effect of the application of an entropy estimator to every realization extracted from a process under examination. The protocol for the validation of the estimators of entropy and entropy rate consists of the following steps:

1.

choice of a convenient DSP q , 2. choice of the number of realizations R,

Materials: Choice of Convenient DSP q s Suitable for the Experiments

For the validation of the previous estimation formulas three completely different types of processes were used: two types, located at the opposite extreme borders of the entropy scale, are regular processes and independent, identically distributed (IID) processes exhibiting maximum entropy; the third type, located in between, is composed of simple processes with minimal memory, such as stationary, irreducible, and aperiodic Markov processes. All these types of processes have the fundamental characteristic of having known theoretical values of entropy; in this way the empirical values obtained by elaborating the realizations can be compared with precise reference values.

1.

Regular Processes. The first important sanity check for entropy estimators involves the use of a completely regular process, that consists of an infinitely repeating brief symbolic sequence. Once the initial sequence is known, no additional information is brought by the following samples, and the evolution of the process becomes completely determined. So, for these processes we have

∀ d ≥ 2 η ′ 2 (Regular) = 0. ( 22
)
Then, even for short realizations of this kind of processes, any good estimator of the specific Rényi entropy rate has to rapidly fall to zero during the progressive increment of the dimension of the sample space.

2.

Markov Processes. When the DSP q is a stationary, irreducible, and aperiodic Markov process, it is possible to calculate the theoretical value of its specific Rényi entropy rate.

In fact, given the transition matrix p qq and the unique stationary distribution µ * q obtained as the scaled (with rule ∑ µ * i = 1) right eigenvector associated to eigenvalue λ = 1 of the equation

p 11 p 12 • p 1q p 21 p 22 • p 2q • • • • p q1 p q2 • p qq T µ 1 • • µ q = µ 1 • • µ q then η ′ 2 (Markov) ≜ lim d→∞ 1 d H 2 (p(Ω(q, d)) Markov ) log q = - q ∑ i=1 µ * i log q q ∑ j=1 p 2 ij . (23)

3.

Maximum Entropy IID Processes. A third sanity check for entropy estimators involves the use of memoryless IID processes with maximum entropy, because:

• with these processes, the distance between the entropy of the relative frequencies and the actual theoretical entropy of the process is the maximum possible (i.e., using these processes, the estimator is tested in the most severe conditions, obliging it to generate the greatest possible correction);

• the theoretical value for the specific entropy of the processes generated is a priori known and results in being constant, regardless of the choice of the dimension of the considered sample space because the outcome of each throw is independent from the past history.

• having an L-shaped one-dimensional distribution, with one probability bigger than the others, which remain equiprobable, the calculation of their theoretical entropy is trivial;

• they are easily reproducible by, for example, simulating the rolls of a loaded die on which a particular preeminence of the occurrence of a side is initially imposed; the general formula is:

η ′ 2 (MaxEnt) ≜ η 2 (p(q, d)) MaxEnt ∀ d = -log q p 2 main + (1 -p main ) 2 q -1 d=1 . ( 24
)

Results and Discussion

As part of this research, countless Monte Carlo experiments were conducted to validate the novel specific collision entropy estimator η 2 (p) obtained in Formula ( 19) and, consequently, to verify the plausibility of the hypothesis proposed for the estimation of the second raw moment of any DSP q described by Formula ( 15). Here, only some of the most significant results are reported. Each figure presented in this section contains two diagrams that show, for an established number of realizations and for an established length of each realization, the trend of the estimated specific collision entropy and the trend of the estimated specific collision entropy rate, calculated as the dimension of the sample space varies.

Experiments with Realizations Coming from Completely Regular Processes

For the experiment whose results are reported in Figure 1 the input parameters are:

• DSP q = Regular process obtained repeating the ordered numerical sequence of the values associated with the six faces of a die (q = 6).

• N = 250 and R = 1, because every realization is identical. The upper diagram of Figure 1 shows that, in general, the theoretical specific collision entropy η 2 (p) decreases only asymptotically to zero and does not reach a minimum value in the dimensional range 1 ≤ d ≤ 20. For this reason, this quantity is not indicated for the procedure of process classification. Instead, the lower diagram shows that the specific collision entropy rate η ′ 2 (p) rapidly decreases to the minimum value of zero, overlapping the theoretical trend for d > 2. This example shows that, as a first necessary prerequisite, any entropy rate estimator has to exhibit this behavior when dealing with regular processes to be able to be considered suitable for the classification of processes.

Experiments with Realizations Coming from Processes Presenting Some Sort of Regularity

Consider a Markov process with six possible states (alphabet A q = {1, 2, 3, 4, 5, 6} and q = 6); let the associated transition matrix p 66 and stationary distribution µ * 6 be

p
µ * 6 = 1 6 1 6 1 6 1 6 1 6 1 6
.

For this process, the theoretical value of specific collision entropy rate η ′ 2 (p) results:

∀d ≥ 2 η ′ 2 (p) = H ′ 2 (p) log q = - 1 6 6 log(0.8 2 + 5 • 0.04 2 ) log 6 ≃ 0.242 .
The upper diagram of Figure 2 shows that, in general, for processes whose samples have a dependence from the past, the trend of the estimated specific collision entropy, calculated using Formula [START_REF] Vinck | Estimation of the entropy based on its polynomial representation[END_REF], presents, at the beginning, a decrease, which depends on the progressive reduction of the topological ambiguity encountered during the detection of recurrences hidden in the data when the dimension of the sample space is increased. The curve subsequently rises due to the reduction of the density of the occurrences in the sample space. This corresponds to a reduction in the reliability of the information supplied by the relative frequencies; as a consequence, the uncertainty contained in the probability estimates grows, and the entropy increases accordingly. This ability to ramp up the curve when the estimate is no longer reliable is the second necessary prerequisite for an estimator. The observation of the diagrams of Figure 2 allows also to infer that RFDs cannot be used in place of DPDs because they intrinsically lack this capability. In fact, the use of the RFDs in the estimator gives poor results because their mean specific collision entropy seamlessly decreases even when the density of the data is actually no longer sufficient for producing any kind of estimation. In the middle of the curve, the minimum value of the specific collision entropy represents the best possible compromise between the request to observe in ever greater detail the regularities contained in the data and the limitations imposed by the shortness of the data. From Figure 2 it is also possible to establish a third necessary prerequisite that an entropy estimator must fulfill: in fact its output has always to be greater or equal than the corresponding theoretical value, because otherwise the estimator would erroneously signal the presence of an excessive amount of regularities in the process, thus violating the fundamental precaution principle required by all those situations in which statistical fluctuations are present. In a sentence: an estimator that expresses values of entropy higher than the correct theoretical ones is preferable to an estimator that expresses lower values.

Moreover, when the trend of the estimated specific collision entropy is compared with the trend of the estimated specific collision entropy rate, it becomes clear once again that this second index produces an impressively more rapid convergence towards the theoretical value (blue line) than the first one. In the lower diagram of Figure 2 it is possible to see that the adherence of η ′ 2 (p) to η ′ 2 (p) persists up to dimension d = 11, and in this case the data density results:

δ min (Markov, R = 300, N = 500) = L n = N -d + 1 q d = 490 6 11 = 1.35 • 10 -6

Experiments with Realizations Coming from Maximum Entropy Memoryless IID Processes

For the experiment whose results are reported in Figure 3, the input parameters are:

• DSP q = process generated by tossing a loaded die with 50% of the outcomes equal to "1" (q = 6); From Formula (24) it results that η ′ 2 (MaxEnt50%) = η 2 (MaxEnt50%) = -log 6 (0.5 2 + 0.5 2 5 ) = -log 6 0.3 ≃ 0.672. Both diagrams of Figure 3 show that:

• the proposed estimator satisfies the aforementioned third prerequisite of never falling below the theoretical line, even in the heaviest test conditions, represented by the elaboration of data coming from a maximum entropy IID process;

• when using RFDs to estimate specific collision entropy, there is only a slight difference between the two possible ways of averaging the logarithm of the second raw moment (dotted and dashed lines in orange); on the contrary, there is a remarkable difference between the two possible ways of averaging the estimates of the logarithm of the second raw moment (dotted and dashed lines in grey) as indicated in Formula (18);

• when the data density in the sample space becomes insufficient for a reliable estimate of the entropy, its value rises toward the value corresponding to the uniform distribution.

In the upper diagram of Figure 3 it is possible to see that considering 250 samples per realization the adherence of η 2 (p) to η 2 (p) persists up to dimension 6; for this dimension the data density in the sample space results:

δ min (MaxEnt 50%, R = 2000, N = 250) = L n = N -d + 1 q d = 245 6 6 = 5.25 • 10 -3
and the statistical fluctuations are considerable because of the shortness of the realizations.

In the lower diagram of Figure 3 it is possible to see that considering 1000 samples per realization the adherence of η 2 (p) to η 2 (p) persists up to dimension 9 (three dimensions more than the other situation); for this dimension the data density in the sample space results:

δ min (MaxEnt 50%, R = 500, N = 1000) = L n = N -d + 1 q d = 992 6 9 = 9.84 • 10 -5
and the statistical fluctuations are reduced because of the greater number of samples of each realization. From the comparison of the two diagrams, it can be seen that the increment in the availability of the data improves all the performance indicators of the estimator, and this fact proves its consistency even in the most severe test conditions represented by this kind of processes. In general, to obtain an adequate horizontal trend of η ′ 2 for at least two consecutive dimensions, it is necessary to rely on a sufficiently large number of samples per realization N or, alternatively, on a sufficiently high number of realizations R. The total number of aggregated samples (i.e., R x N) necessary for a good result of the estimation depends on the effective degree of irregularity of the signal. In fact, for completely regular processes with an alphabet composed of q symbols, even only 5 q samples are sufficient for a correct estimate. Vice versa, for almost random processes, at least 1, 000, 000 aggregated samples seem to be necessary.

Finally, concerning the hypothesis made at the beginning about the possibility of estimating the second raw moment of the DPDs coming from any kind of DSP q using Formula (15), the evidences that emerged from the results of the experiments made for the validation of the estimator have not provided any counterexample that may exclude its validity. For this reason, the following statistics postulate is proposed:

Postulate. Given a sample space Ω(q, d) with cardinality n = q d , and given a set of relative frequency distributions { f (Ω(q, d)) r q }, each composed of L occurrences, resulting from the transformation of R short realizations r q taken from the underlying discrete stochastic process DSP q , to which an unknown discrete probability distribution p(Ω(q, d)) is associated, then the unbiased and consistent estimator of the second raw moment of p(Ω(q, d)) is inferred as ∀ DSP q M 2 (p(Ω(q, d))) DSP q = lim R→∞ max M 2 ( f (Ω(q, d)) r q ) -1 L , 1 n r q .

Conclusions

Figures 2 and3 show that the proposed specific collision entropy rate estimator η ′ 2 allows a very prolonged and consistent stay of its output, exactly at the values expected by the theory. This highly desirable and very rare feature, the simplicity of its formula and its complete usability with any discrete stationary process make this estimator a valid tool, suitable for measuring the degree of irregularity in experimental data from the perspective given by the collision entropy. Possible future research directions include:

• the evaluation of the admissibility of this estimator by comparing it to other similar collision entropy estimators and by using the same kind of processes for the tests;

• the characterization of the variability of the values returned by the estimator η ′ 2 as the number of aggregated samples and the irregularity of the processes vary;

• further studies on the methods of estimation in presence of the logarithm operator.

3 .

 3 choice of the length N of each realization, 4. transformation of the samples of any realization in a RFD according to § 3.1, 5. extraction of the estimated indices according to Formulas (19) and (20), 6. production of the diagrams, 7. and evaluation of the performances of the estimator.

Figure 1 .

 1 Figure 1. Trend of η 2 (upper diagram) and trend of η ′ 2 (lower diagram) for a realization composed of 250 samples taken from a regular process.

Figure 2 .

 2 Figure 2. Trends of η 2 (upper diagram) and η ′ 2 (lower diagram) for 300 realizations, each composed of 500 samples taken from the Markovian process previously described by the transition matrix p 66 and the stationary distribution µ * 6 .

•

  Upper diagram: R = 2000 and N = 250; • Lower diagram: R = 500 and N = 1000.

Figure 3 .

 3 Figure 3. Trends of η 2 for the realizations of a process generated by tossing a loaded die with 50% of the outcomes equal to "1". Upper diagram: 2000 realizations, each 250 samples long; lower diagram: 500 realizations, each 1000 samples long.

  Each elementary event e k , with k ∈ {1, 2, ..., n}, is uniquely identified by a vector with d coordinates (x1 k , x2 k , ..., xd k ), with x1 k , x2 k , ..., xd k ∈ A q .

Funding: This research received no external funding.

Conflicts of Interest:

The author declares no conflict of interest.

Abbreviations

The following abbreviations are used in this manuscript:

A q alphabet composed of q ordered symbols Ω(q, d)

Sample space resulting from the Cartesian product d times of the alphabet A q n = q d cardinality of the sample space Ω(q, d) DSP q Discrete-state stochastic process whose samples belong to an alphabet A q r q Realization of a DSP q N Number of samples of r q L = Nd + 1 Number of occurrences inserted in the events of Ω(q, d) RFD

Relative frequency distribution DPD Discrete probability distribution f (Ω(q, d)) r q RFD obtained from a realization r q of a DSP q whose d-grams are inserted in Ω(q, d) p(Ω(q, d)) DSP q DPD obtained from a DSP q whose d-grams are inserted in Ω(q, d) p(Ω(q, d)) DSP q Estimate of the DPD obtainable from a DSP q whose d-grams are inserted in Ω(q, d) M 2 ( f )

Second raw moment of an RFD M 2 (p)


Claire Laudy
email: claire.laudy@thalesgroup.com

Johann Dreo
email: johann.dreo@thalesgroup.com

Christophe Gouguenheim
email: christophe.gouguenheim@thalesgroup.com

Applying MapReduce principle to High level information fusion

The InSyTo Synthesis framework is based on graph structures, graph algorithms and similarity measures for soft data fusion managing inconsistencies. The framework can be used to enable non-redundant additions to an information network, as well as graph based information query on several applications. The graph fusion algorithm relies on the search of a maximum common subgraph isomorphism, which makes it a difficult problem, especially on large graphs. In this work, the subgraph matching algorithm is partially parallelized, based on the MapReduce approach and on the Hadoop framework. Using Hadoop enables the management of big graphs, first by avoiding the load of the graphs in memory and secondly by distributing the computations over several processing nodes. Our experiments on the Global Terrorism Database (which contains the descriptions of more than 113,000 terrorist attacks in a graph of more than 20,000,000 nodes) shows that InSyTo Synthesis now scales to socalled "big data" applications.

I. INTRODUCTION

Soft data fusion is an ever growing trend in the information fusion community. More and more tracks dedicated to soft information are organized within the International Conference on Information Fusion over the years and numerous authors stress the need for soft data management and fusion. For instance in the detection of people and complex activities, the use of soft information sources is critical. The authors of [START_REF] Llinas | A multi-disciplinary university research initiative in hard and soft information fusion: Overview, research strategies and initial results[END_REF] describe a 5 year program involving several academic actors that aim at addressing major stakes of soft data fusion. It includes the development of a framework as well as evaluation methods. In addition, many authors relate about new issues raised by soft data fusion. Among them [START_REF] Gross | Towards hard+soft data fusion: Processing architecture and implementation for the joint fusion and analysis of hard and soft intelligence data[END_REF] and [START_REF] Date | Data association and graph analytical processing of hard and soft intelligence data[END_REF] quote natural language processing, transformation of data into comprehensive and semantic data structures, soft data association and graph matching. Studies such as [START_REF] Belov | Mixed initiative soft data fusion associate[END_REF] and [START_REF] Kohler | Implementing soft fusion[END_REF] emphasize on the importance of integrating soft data in situation awareness support systems. As the automation of soft data fusion is a very challenging issue, due to, e.g., error estimation, normalization and context extraction for information interpretation, the authors propose a mixed approach that embeds the participation of a human analyst to the fusion process.

Within their day to day work, intelligence analysts pile up a large amount of information. The different information items are linked through a big information network, as the analysts express part of their reasoning and domain knowledge through links between different pieces of information, piled up within one or more working sessions. One of the issue for using such an amount of information is to be able to access relevant parts of it efficiently. For example, this enables highlighting schemes of actions of terrorist groups, recognize modus operandi and deviation from usual behavior for instance.

We previously developed a framework based on graph structures, graph algorithm and similarity measures for soft data fusion managing inconsistencies (InSyTo Synthesis v1 [START_REF] Laudy | Semantic Knowledge Representations for Soft Data Fusion -Efficient Decision Support Systems -Practice and Challenges From Current to Future[END_REF], [START_REF] Fossier | Managing uncertainty in conceptual graph-based soft information fusion[END_REF]). The use case presented in [START_REF] Laudy | Multi-granular fusion for social data analysis for a decision and intelligence application[END_REF] dealt with the management of an information network containing descriptions of entities (companies, universities...) that collaborate through several media such as research project, scientific papers and so on. The InSyTo Synthesis framework was used to enable nonredundant information addition to the information network, as well as graph based information query. This network contains more than 10000 nodes and the operations took a few seconds. The processing time was operationally accepted and the memory load was not an issue. However, the new step envisioned for our work on soft data fusion, was to enable the management of bigger graphs.

The graph fusion algorithm relies on the search for matches between sub-graphs and more precisely for a maximal matching subgraph. Maximal subgraph matching is used in order to determine where to add information in an information graph, and which parts of two information graphs are redundant and should thus be fused rather than be repeated twice in the graph resulting from the fusion.

The decision problem of whether two graphs match is well studied and is in NP [START_REF] Mckay | Practical graph isomorphism, II[END_REF]. But the problem of finding matching subgraphs, known as the subgraph isomorphism problem, is known to be NP-complete and difficult to solve in parallel [START_REF] Plantenga | Inexact subgraph isomorphism in MapReduce[END_REF]. This problem is well studied and have leds to a lot of algorithms, among which several have been parallelized [START_REF] Plantenga | Inexact subgraph isomorphism in MapReduce[END_REF], [START_REF] Zhao | SAHAD: subgraph analysis in massive networks using hadoop[END_REF], [START_REF] Liu | MapReduce-Based pattern finding algorithm applied in motif detection for prescription compatibility network[END_REF]. The most difficult graph matching problem in our case is to find the set of subgraphs that maximize the matching. This maximum common subgraph isomorphism problem (MCS) is known to be NP-hard [START_REF] Ullmann | An algorithm for subgraph isomorphism[END_REF], which makes it intractable on large graphs [START_REF] Conte | Challenging complexity of maximum common subgraph detection algorithms: A performance analysis of three algorithms on a wide database of graphs[END_REF]. It is thus often solved with tools from the combinatorial optimization domain [START_REF] Bunke | A comparison of algorithms for maximum common subgraph on randomly connected graphs[END_REF], [START_REF] Raymond | Maximum common subgraph isomorphism algorithms for the matching of chemical structures[END_REF] like constraint programming [START_REF] Ndiaye | CP Models for Maximum Common Subgraph Problems[END_REF], [START_REF] Solnon | Alldifferent-based filtering for subgraph isomorphism[END_REF], but the parallelization of MCS algorithms remains to be studied.

The InSyTo Synthesis fusion algorithm relies on subgraph isomorphism and maximum subgraph isomorphism algorithms. Both those algorithms must solve highly combinatoric problems, on which the execution time may become too long to satisfy user requirements. To manage this problem, we present a new version of the InSyTo Synthesis framework in which the subgraph isomorphism algorithm is partially parallelized. Our approach is based on the MapReduce principle and the implementation use the Hadoop framework [START_REF] White | Hadoop: The Definitive Guide[END_REF]. Using Hadoop enables the management of big graphs by avoiding the load of the graphs in memory and distributing the computations over several processing nodes.

The paper is organized as follows. The second section is dedicated to the presentation of the soft data fusion algorithms. We present the approach that relies on the use of conceptual graphs formalism to express the information graphs. We also present the limitations of the first version of the soft data fusion framework. The third section presents the parallelization of those algorithms, which permits the management of bigger data graphs. After a short presentation of the Hadoop framework parts on which our work relies, we describe the MapReduce version of a subgraph matching algorithm. Section four is dedicated to our experimentations. We used the MapReduce version of the framework on a huge database containing the descriptions of more than 113,000 terrorist attacks over the world. We show how InSyTo Synthesis now scales to so-called "big data" applications. In the last section, we conclude and present future work.

II. GRAPH BASED INFORMATION REPRESENTATION

A. Information fusion, information synthesis and information Query

The InSyTo Synthesis soft data fusion framework relies on the use of semantic graph structures to store soft data and uses a graph algorithm to carry out the fusion process. It enables three different operations on networks of information that are depicted on figure 1 and described hereafter. When a model of a situation of interest (e.g. a terrorist attack in a specific city at a specific date) is available, one may want to monitor the situation and raise alarms if an instance of such a situation is happening. Therefore, different observations, coming potentially from different sources, are filtered out in order to keep observations of interest only. They are then assembled through information fusion in order to provide a representation of the ongoing situation of interest, as precise as possible.

Information synthesis enables one to collect and organize information about a specific subject. Through information synthesis, all the gathered information items are organized into a network. The redundant part of the informations items are detected and eliminated.

All the instances of information corresponding to a specified graph pattern may be found within a network of information, through the information query function. In the following paper, we focus on the information query function. As we will see in section IV, given an already built information graph, our aim is to support intelligence analysts by providing means to efficiently query this information graph.

B. A graph based information representation

Graph based representations appear to be naturally well adapted to soft data. Our approach relies on the use of bipartite graphs, more specifically a subset of the conceptual graphs ( [START_REF] Sowa | Conceptual Structures: Information Processing in Mind and Machine[END_REF], [START_REF] Chein | Graph-based Knowledge Representation: Computational Foundations of Conceptual Graphs[END_REF]) to represent soft data and knowledge. The conceptual graphs formalism is a model that encompasses a basic ontology (called vocabulary), graph structures and operations on the graphs. The vocabulary defines the different types of concepts and relations that exist in the modeled application domain, while the graphs provide a representation of the observations which are provided by the information sources.

Basic conceptual graphs are bipartite graphs containing concept and relation nodes. Figure 2 gives an example of a conceptual graph. The rectangular boxes represent concept nodes and the ovals represent relation nodes.

Graphical form

Linear form

Month: 01

1 3 2 2 1

Fig. 2. Example of a conceptual graph

The term concept is used to refer to a concept node. The concepts represent the "things" or entities that exist. A concept is labeled with two components: the conceptual type and the individual marker.

The conceptual type defines the category to which the entity belongs. For instance, in Figure 2 the concept [Country:Philippines] is an instance of the category Country, i.e., its conceptual type is Country.

The individual marker relates a concept to a specific object of the world. The object represented by [Country:Philippines] has the name (or value) Philippines. The individual markers may also be undefined. An undefined or generic individual marker is either blank or noted with a star * , if the individual object referred to is unknown.

The term relation is used to refer to a relation node. The relation nodes of a conceptual graph indicate the relations that hold between the different entities of the situation that is represented. Each relation node is labeled with a relation type that points out the kind of relation that is represented. The notion of vocabulary was defined in [START_REF] Chein | Graph-based Knowledge Representation: Computational Foundations of Conceptual Graphs[END_REF]. The concept types and the conceptual relation types, which are used to label the concept and relation nodes, are organized in hierarchies.

We restrict our approach to relation types that are unordered in order to manage only one hierarchy, the concept types hierarchy.

Formally, we denote the set of concept types as T C , the set of relation types as T R and the set of individual markers that are used to labeled the concept nodes as markers, which defines a vocabulary

V = (T C , T R , markers). A basic conceptual graph G is then defined by a 4-uple G = (C G , R G , E G , l G ), where
• (C G , R G , E G ) is a finite undirected and bipartite multigraph. C G is the set of concept nodes. R G is
the set of relation nodes, and E G is the set of edges.

• l G is a naming function of the nodes and edges of the graph G which satisfies:

1) A concept node c is labeled with a pair l G (c) = (type(c), marker(c)), where type(c) ∈ T C and marker(c) ∈ markers ∪ { * }. 2) A relation node r is labeled by l G (r) ∈ T R .
l G (r) is also called the type of r.

C. Specialization and generalization of graphs

A specialization/generalization relationship is defined on the graphs. These relationships are used for the query function. The aim of the query is indeed to find all the sub graphs of the information graph that are specializations of the query graph. Therefore, the query is expressed as a generic graph.

We define these relationships hereafter.

1) Relationships between conceptual types: Given the hierarchical nature of the vocabulary, a partial order holds among the set of conceptual types T C , interpreted as a relation of specialization: t 1 ≤ t 2 means that t 1 is a specialization of t 2 , that is to say that any instance of the class denoted by t 1 is also an instance of the class denoted by t 2 .

2) Relationships between concepts: Given the order on T C , we can also partially order the concepts that are defined on T C ×{markers ∪ { * }}, by a specialization relation as follows. Let c 1 = [T 1 : m 1 ] and c 2 = [T 2 : m 2 ] be two concept nodes, we define:

c 1 ≤ c 2 iff T 1 ≤ T 2 m 2 = * or sim(m 1 , m 2 ) ≥ thres (1)
where sim is a similarity function and thres a user-defined threshold.

For instance, if we consider that the conceptual type Event is greater (i.e. more general) than the conceptual type TerroristEvent, we have:

[Event: * ] ≥ [Event:e1] ≥ [TerroristEvent:e1] but [Event:e1] and [TerroristEvent: * ] are not compa- rable.
3) Relationships between graphs: We also define a specialization relation between graphs. This relation is denoted by (in order to avoid confusion with the specialization relation ≤ between concepts). Let A and B be two basic conceptual graphs. C A and R A denote the set of concepts and relations of the graph A, defined over the vocabulary V. Denoting as P AB the set of graph isomorphisms between A and B, we have:

A B ⇔ ∃ p ∈ P AB ,      p : C A , R A → C B , R B c A , r A → c B , r B ∀ c A ∈ C A , c B ≤ c A ∀ r A ∈ R A , r B = r A By extension of the notation, G A | r A G B | r B
denotes that the subgraph of G A restricted to the relation node r A and its linked concept nodes is a generalization of the subgraph of G B restricted to the relation node r B and its linked concept nodes.

D. Graph based Fusion: Information Query

The InSyTo Synthesis platform encompasses a generic graph based fusion algorithm that is used for the three functions (information fusion, information synthesis and information query). The usage of the algorithm (parameters and launch mode) determines the function that is realized.

The fusion algorithm is made of two interrelated components (see Figure 3). The first component is a generic subgraph matching algorithm, which itself relies on the use of fusion strategies.

The graph matching component takes care of the overall structures of the initial and fused observations. It is in charge of the structural consistency of the fused information, regarding the structures of the initial observations, within the fusion process.

The fusion strategy part is made of similarity, compatibility and functions over elements of the graphs to be fused (see equation 1 for instance). They enable the customization of the generic fusion algorithm according to the context in which it is used. The context encompasses the application domain, the semantics of the information items and user preferences. The fusion strategies enable to manage the discrepancies that may be observed in observations of the same situation by different sources (see [START_REF] Laudy | Semantic Knowledge Representations for Soft Data Fusion -Efficient Decision Support Systems -Practice and Challenges From Current to Future[END_REF]).

Within the query function, the strategies that are used in the algorithm follow the specialization/generalization relationships defined before (II-C). We use a subsomption strategy and a whole-structure conservation mode.

The subsomption strategy is used within the nodes to nodes comparison between the query and the data graphs. That is to say that the concepts of the query graph must be more general than the ones of the data graph in order to be fused. The specialization relationship between the query and the data graphs also imply that the structure of the query graph must be entirely found in the data graph. In other words, all the relations of the query graph must have an image in the data graph, that respects the structure of the query graph. The query function relies on the search for injective homomorphism between the query graph and the data graph.

III. TOWARDS BIGGER GRAPHS

A. Hadoop : a framework for processing "big data"

Hadoop is a implementation of a distributed file system along with a model for performing distributed data processing on this file system.

Hadoop's file system is called HDFS (Hadoop Distributed File System). It allows the partitioning of data across many nodes. A Hadoop cluster scales computation capacity, storage capacity and I/O bandwidth by simply adding commodity servers.

The data processing model is called MapReduce, and allows processing of large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key. The advantage of MapReduce is that the processing can be performed in parallel on multiple processing nodes (multiple servers) so it is a system that can scale very well. Since it's based on a functional programming model, the map and reduce steps each do not have any side-effects (the state and results from each subsection of a map process does not depend on another), so the data set being mapped and reduced can each be separated over multiple processing nodes.

The use of Hadoop for the parallelization of our algorithms has two advantages. The first one is that the graphs are not loaded in memory, but sub-parts of them are passed along the processing nodes thanks to the distributed file system. The second one is that parts of the isomorphism search process itself can be distributed on the different processing nodes, enabling a speed-up of the overall process.

B. Problem decomposition

In this work, we focus on the query functionality of InSyTo Synthesis. The input data are two graphs. The data graph is a big network (more than 20,000,000 nodes). The query graph is a relatively small graph. Indeed, the query is "written" by the analyst and contains most of the time 20 to 50 nodes.

The main issue of the subgraph isomorphism algorithm is the combinatoric explosion and the big graph structures. The management of the structural part of the graphs (i.e. which node is linked to which one) is a difficult problem while looking for candidate images for the nodes of one graph in the other. Therefore, within the search for candidate images for the nodes of the query graph in the information graph, our approach is to split up the process into a first phase that will manage the values of the query and information nodes and a second phase in charge of the management of the structural aspects of the graphs.

In order to follow the MapReduce model, we cut off the two graphs (data and query) into small pieces that will then be pairwise compared. The comparison take into account the value of the nodes themselves, without taking care of the overall structures of the graphs. Therefore, the comparisons are independent from one another, and the MapReduce model can be applied.

Figure 4 shows the decomposition of a query graph into two small graphs. Each small graph corresponds to one of the relation nodes of the query graph, linked to a copy of its neighbor concept nodes. Once the two graphs are cut around the relations nodes, each relation node and the ordered list of concepts nodes it is linked to, constitutes an entry for the MapReduce algorithm. To be readable by the Hadoop framework, the set of pieces of the query are written into their linear form (see figure 2) into a file. Each line of the file is one of the subgraph and will be processed by the MapReduce algorithm.

The MapReduce algorithm looks for all the candidate images for each piece of the query (from the query graph) in the set of pieces of data (from the data graph) (see Figure 5).

R ← ∅ for all G r,ri ∈ G r do if G r,ri G d,di then {append output record} R ← R (G r,ri , G d,di ) end if end for return R
Once the map step is achieved, the reduce step takes place. The master node of the processing cluster collects the records

R = {(G r,ri , G d,di )∀G r,ri ∈ G r |G r,ri
G d,di } produced during the map phase and combine them so as to associate each subgraph G r,ri of the query with the list of all compatible subgraphs G d,di of the data graph.

The reduce function aggregates the set of candidate subgraphs G d,dj as a list of images of G r,ri . The produced associative array r img(G r,ri ) = {G d,dj ∀G d,dj ∈ G d |G r,ri G d,dj } has the same set properties than R but permits to improve further query times.

C. Result graphs build-up

Once the candidate answers to each piece of query are processed, we need to build up answer graphs from these Algorithm 2 Reduce function on the set of candidate subgraphs function reduce(R) : r img ← ∅ for all (G r,ri , G d,di ) ∈ R do {append subgraph to the list mapped to the query graph} r img(G r,ri ) ← r img(G r,ri ) G d,di end for return r img candidates. The different combinations of pieces of answers are provided, taking care of the original structure of the data graph (see Figure 5). The candidate pieces for answers are assemble one with another, if and only if their association respects the structural constraints of the initial data graph. In other words, the connectivity between the relations through the concept nodes is checked while building the answer graphs.

Within the result graph reconstruction algorithm, the following notations are used:

• query graph G r = (C r , R r , E r , l r ); • data graph G d = (C d , R d , E d , l d );
• f strategy is the fusion strategy that is used for compatibility conditions and fusion functions. The fusion strategy used within the query function is the subsomption of concept nodes.

• r img = {(G r,ri , G d,rj )|G r,ri G d,rj
} is the associative array containning the records generated by the MapReduce algorithm.

• G r,ri is the subgraph of G r restricted to the relation r i and its linked concept nodes c j ∈ C r ;

• r mods = {G r,ri |r i ∈ R r } is the set of subgraphs of G r restricted to each relation r i of G r .

• ans = {G ansi |G ansi = subgraph(G d ) ∧ G r G ansi } the set of subgraphs of G d that are answers to the query (i.e. more specific than) G r .

• asso i = {(G r,ri , img i )} is an associative array that associates each subgraph restricted to a relation of the query graph G r to a subgraph restricted to a compatible relation of the data graph G d that is its image in the current association. An image of a relation node can be added in an association if and only if it is compatible (regarding node values and graph structures) with the already associated relations.

• assos = {asso i } is the set of all association tables asso i containing relations nodes of the data graph G d associated to the relation nodes of query graph G r and that respect the conditions given by G r and the fusion strategy f strategy

• graph(asso i ) → G answeri is a function that transforms an association table asso i into a graph by reconstructing the graph structure.

The input of the algorithm are r img, the table of potential relation images of the data graph for each relation node of the query and the fusion strategy f strategy that relies on the subsomption between concept nodes and graphs (see II-C).

A. The Global Terrorism Database

The global terrorism database 1 (GTD) is an open-source database that contains the descriptions of all the terrorist events that occurs worldwide between 1970 and 2012.

The GTD has the following characteristics :

• It contains information on over 113,000 terrorist attacks;

• It includes information on more than 47,000 bombings, 14,400 assassinations, and 5,600 kidnappings since 1970;

• It includes information on 45 to more than 120 variables for each case;

The GTD is supervised by an advisory panel of 12 terrorism research experts and over 4,000,000 news articles and 25,000 news sources were reviewed to collect incident data For each GTD incident, information is available on the date and location (region, country, state, city) of the incident, 1 The National Consortium for the Study of Terrorism and Responses to Terrorism (START) makes the GTD available via an online interface on the website of the project : http://www.start.umd.edu/gtd/ perpetrator group name, tactic used in attack, the weapons used and nature of the target, the number of casualties, etc.

Other variables provide information unique to specific types of cases, including kidnappings, hostage incidents, and hijackings.

This database represents a huge work and is particularly valuable for intelligence analysts. Therefore smart functionalities that would enable the recognition of modus operandi, for instance, are eagerly awaited.

Within our experimentations, we imported the data contained in the GTD into an information network. The importation of the data is agnostic to the contents of the database.

The GTD database is a classical "table". Each line of the table contains the description of an event, each column of the table corresponds to a characteristic of the events (date, location, attack type, etc.). To import the GTD data into the conceptual graphs format, we first automatically built the type hierarchy described in II-B. Therefore, Two concept types were defined, GTDEvent and GTDEntity that are directly attached to the root type of the hierarchy. The types of relations are extracted from the column labels of the table.

The data itself is then imported into a graph structure by creating a GTDEvent which value is the identifier of the event contained in the first column of the table. This concept is then linked to concepts of type GTDEntity and value to values of the other columns through relation nodes of the types corresponding to the labels of the columns.

The resulting network of information contains more than 10,000,000 concept nodes linked through 13,560,000 relation nodes.

B. Results

We launched several queries on the network made of the GTD data. These queries are patterns of terrorists events containing some known and unknown values. The figure 6 depicts an example of such a query.

It queries the network for information on years, types of weapons used and number of persons killed in all the terrorist events perpetrated by Tamils and that occurred in Sri Lanka. This query gave us 2935 answers under the form of graphs describing these terrorists events (see figure 6 for one of the answers).

In order to test the scalability of our implementation, we artificially increased the size of the information network by generating 7 terrorist events for each event described in the GTD. This generated a text input file of 6.64 Mo that describes the 1,560,000 events. The requests were sent on a single core CentOS 5.7 machine with 3Gb RAM and 20Gb disk memory. The answers to requests were obtained in less than 1 minute.

The results obtained during this first experimentation phase are promising. The whole data network can be processed through this new parallelized version of the fusion algorithm. This was not worth considering, using a classical algorithm for the maximum subgraph isomorphism problem.

The structure of the hierarchy that was built from the GTD database is flat. Only two types of concepts are considered, Fig. 6. Example of query and answer on the information network with no hierarchical dependency between them. The advantage of the agnostic importation of the data is that the experimentation platform can be used on any other database. However, it also prevents from taking advantages of all the aspects of the conceptual graphs based information fusion approach. The queries made on the network could be done efficiently on the table version of the database, as the structure was adapted to the contents of the data. The advantages of using the hierarchy of concept types and fusion strategies in order to query complex inexact patterns on the network where shown in previous work ( [START_REF] Laudy | Introducing semantic knowledge in high level information fusion[END_REF] and [START_REF] Laudy | Multi-granular fusion for social data analysis for a decision and intelligence application[END_REF]) however.

V. CONCLUSION AND FUTURE WORK

In this paper we present the implementation of a distributed algorithm for the graph based information fusion. The conceptual graphs based information fusion platform that was previously developed enables the management of inconsistencies withing information fusion. To do that, the platform uses a hierarchy of the types of nodes of the data network, as well as fusion strategies. The fusion strategies encompass similarity measures and fusion functions that enable managing the discrepancies between values of the information nodes of a network of information.

The new algorithm relies on the Map/Reduce principle, which enables the distribution of part of the process on several processing nodes. The implementation uses the Hadoop framework.

Tests were conducted on an information network made of the data contained in the Global Terrorist Database. The tests consisted in querying specific patterns of terrorist events. The information network contains more than 20,000,000 nodes linked together. Using Hadoop first enables to distribute the process among several processing nodes. It secondly avoid loading the whole information network in memory, by splitting and distributing on the Hadoop file system.

The second phase of the algorithm is still time consuming, which underlines the necessity of feeding it with as few inputs as possible and consider to distribute it on several processing nodes. Therefore, these results lead us two the two following trail for future work:

• How to optimize the research for potential images for each subgraph of the query restricted to the relation nodes ?

• How to parallelize the result graphs build-up ?

The present paper describes the implementation of the query functionality of the information synthesis platform. Future work will encompass the implementation of the other functions of InSyTo, namely information fusion and information synthesis. This should follow the same fusion process.

Fig. 1 .

 1 Fig. 1. InSyTo three functions

  Event: e1@e1], [Year: 1972 @y1972], [Month: 01 @january]), location([Event: e1 @e1], [Country: Philippines @Philippines]).

Fig. 3 .

 3 Fig. 3. InSyTo algorithm

Fig. 4 .

 4 Fig. 4. Decomposition of a 'query' graph

…+Fig. 5 .Algorithm 1

 51 Fig. 5. Finding candidate images and reconstructing answer graphs

ACKNOWLEDGMENT

The research leading to these results has received funding from the European Union Seventh Framework Program (FP7/2007-2013) iSAR+ FP7-SEC-2012-1-312850