Clement Moreau

Veronika Peralta

Patrick Marcel

Alexandre Chanson

Thomas Devogele

Learning Analysis Patterns using a Contextual Edit Distance

, showing that our approach is able to identify the patterns imposed by the generator. To the best of our knowledge, this is the first attempt to characterize human analysis behavior in workloads of data explorations.

INTRODUCTION

Analyzing a database workload offers many practical interests, from the monitoring of database physical access structures [START_REF] Chaudhuri | Self-Tuning Database Systems: A Decade of Progress[END_REF] to the generation of user-tailored collaborative query recommendations for interactive exploration [START_REF] Eirinaki | QueRIE: Collaborative Database Exploration[END_REF]. There has been much attention lately devoted to the analysis of user past activities to support Interactive Database Exploration (IDE) [START_REF] Idreos | Overview of Data Exploration Techniques[END_REF]. OLAP analysis is a particular case of IDE, that takes advantage of simple primitives like drill-down or slice-and-dice for the navigation of multidimensional data. These particularities enable the design of approaches for characterizing user explorations in how focused they are [START_REF] Djedaini | Detecting User Focus in OLAP Analyses[END_REF], in how contributive a query is to the exploration [START_REF] Djedaini | Automatic assessment of interactive OLAP explorations[END_REF], or even in how to ensure that a sequence of analytical queries forms a coherent exploration [START_REF] Romero | Describing Analytical Sessions Using a Multidimensional Algebra[END_REF]. Characterising user behavior while analysing data, i.e. learning the way users analyse data (the type and order of operations, the level of detail, the degree of focus) is a step forward in the understanding of analysis activities.

Identifying analysis behavior has several applications. The more natural one is a better support of IDE, for instance to understand users' information needs, to identify "struggling" during the exploration, or to provide better query recommendations. Notably, IDE systems usually do not offer such facilities. The prediction of next analysis steps is particularly interesting, enabling beforehand execution of probable queries and caching of results, as well as advanced optimization strategies. Another benefit is the design of more realistic workloads for database benchmarking. Classical benchmarks like TPC-H or TPC-DS poorly include interactive exploration activities in their synthetic workloads, and are not appropriate to evaluate modern IDE systems [START_REF] Eichmann | Towards a Benchmark for Interactive Data Exploration[END_REF]. Identifying analysis patterns would allow to better model user's explorations and mimic such activities in benchmark workloads. Finally, we mention the detection of clandestine intentions [START_REF] Aybar | Why Is this User Asking so Many Questions? Explaining Sequences of Queries[END_REF] as another potential benefit. Indeed, as reported by [START_REF] Aybar | Why Is this User Asking so Many Questions? Explaining Sequences of Queries[END_REF], query sequences may reflect such intentions, where users prefer to obtain information by means of sequences of smaller, less conspicuous queries to avoid direct queries which may disclose their true interests. The identification of typical analysis patterns may help distinguishing normal from clandestine intentions.

In this paper we deal with the identification of analysis patterns in a log of explorations devised by real users. We consider that an exploration is a coherent sequence of queries over a database schema, done by a user with the goal of fulfilling an information need. In [START_REF] Rizzi | CubeLoad: A Parametric Generator of Realistic OLAP Workloads[END_REF], Rizzi and Gallinucci described 4 recurrent types of user analyses and propose a tool for generating realistic explorations based on these usage types. Our goal is to go a step forward and learn more analysis patterns from the explorations of real users. Concretely, we aim to cluster together explorations showing similar analysis patterns. The idea behind analysis patterns is to look for sequences of common actions or operations performed together when analysing data, as some kind of movements in a data space. From this point of view, OLAP operations (e.g. drilling down, adding a filter, changing a measure) are first class citizens, while the actual analyzed data is less important. For example, we can retain that a user performed a sequence of drills down, disregarding the dimension that was drilled down or the semantics of the underlying data. Explorations can be compared in such terms, i.e. to what extent they share the same sequences of operations and evolve at the same level of aggregation and filtering.

Many distances proposed to compare sequences, for example the Damerau-Levenshtein distance [START_REF] Damerau | A Technique for Computer Detection and Correction of Spelling Errors[END_REF] or the Smith-Watermann algorithm [START_REF] Tf | Identification of Common Molecular Subsequences[END_REF], part of Edit Distance family, count the minimum number of operations (modification, addition, deletion) required to transform one sequence into the other. They are particularly adapted for sequences of independent symbols, as DNA sequences or strings. However, when symbols represent human behavior, including homogeneous, interconnected and repetitive actions, an appropriate distance should satisfy other requirements. In particular, we want the following requirements:

(R 1 ) edition cost depends on the similarity of nearby symbols. (R 2 ) edition of repeated close symbols has little cost. (R 3 ) permutation of close symbols has little cost. Indeed, while edition cost is constant in classical Edit Distance, for comparing interconnected actions, it should take context (i.e. the nearby actions) into account. For example, removing a measure should be costly within a focused sequence of drills down and filters, while it should be cheaper inside a sequence with other changes in measures. In addition, sequences of filters should be similar, no matter how many filters there are. Furthermore, permuting operations should have little impact, e.g. filtering and then drilling vs. drilling then filtering.

Previous attempts made for measuring the similarity of sequences of OLAP queries (like e.g. [START_REF] Aligon | Similarity measures for OLAP sessions[END_REF], that extends the Smith-Watermann algorithmm) were not designed to satisfy the stated requirements. We propose a Contextual Edit Distance (CED) specially designed to satisfy them.

Our contributions, sketched in Figure 1 include: (i) a representation of queries and explorations in the space of OLAP operations, including a similarity function among OLAP operations in such space (described in Section 3), (ii) a CED for comparing explorations considering context (Section 4), (iii) a proposal for clustering explorations, based on CED (Section 5), and (iv) a set of experiments showing that CED outperforms state of the art distances allowing the learning of analysis behavior in varied logs of explorations (Section 6).

RELATED WORK

The recurrent types of user analyses described by Rizzi and Gallinucci [START_REF] Rizzi | CubeLoad: A Parametric Generator of Realistic OLAP Workloads[END_REF] are the first attempt to define analysis patterns in OLAP workloads. Authors claim that obtaining real OLAP workloads by monitoring the queries actually issued in companies and organizations is hard, and propose a parametric generator of OLAP workloads, CubeLoad, based on a four templates that model recurrent types of user analyses:

• Slice And Drill. Following the default behavior of several OLAP front-ends, hierarchies are progressively navigated by choosing a member of a current group-by level, creating a selection predicate on such member and drilling down on it. Therefore, explorations of this template contain sequences of filter and drill-down operations. A e 1 = hq 1 , q 2 , ..., q m i e 2 = hq 1 , q 2 , ..., q n i . . . • Slice All. Users are sometimes interested in navigating a cube by slices, i.e., repeatedly running the same query but with different selection predicates. Then, this templates generates sequences of unfilter/filter operations. • Exploratory. The motivation for this template is the assumption that several users, while exploring the cube in search of significant correlations, will be "attracted" by one surprising query and then evolve casually. So, explorations based on this template contain varied random operations. • Goal Oriented. Explorations of this type are run by users who have a specific analysis goal, but whose OLAP skills are limited so they may follow a complex path to reach their destination. Explorations of this template contain varied operations but converging to some specific point.

e k = hq 1 , q 2 , ..., q p i {e1, e2, ..., ek} ✓ Q ⇤ d : Q ⇤ ⇥ Q ⇤ ! R +
Other works analyse real workloads and observe tendences or patterns. Aligon et al. [START_REF] Aligon | A Holistic Approach to OLAP Sessions Composition: The Falseto Experience[END_REF] analyse a workload of explorations devised by master students and observe some general tendence. They report the number of OLAP operations used between two consecutive queries, the level of detail and the number of filters of queries in the explorations, as well as the queries indicated as relevant by the students. As general behavior, they highlight that explorations are more focused at the end (i.e. the number of filters and level of detail increase along the exploration, while the number of OLAP operations between consecutive queries varies before a final drop at the end of the exploration) and contain more relevant queries at the end. The term focus is used as in [START_REF] Djedaini | Detecting User Focus in OLAP Analyses[END_REF]: "When focused, an analyst would expect more precise queries, related to what she is currently analyzing. On the contrary, when exploring the data, the analyst would prefer more diverse queries, for a better data space coverage." Djedaini et al. [START_REF] Djedaini | Automatic assessment of interactive OLAP explorations[END_REF] analyse another workload of explorations of master students and propose a model for learning the quality of an exploration (and the skill of the user) based on a set of query features.

To our knowledge, our work is the first devoted to discover exploration patterns in OLAP workloads.

Many recent works aimed at comparing queries and sessions. We mention as good recent surveys [START_REF] Aligon | Similarity measures for OLAP sessions[END_REF] for OLAP queries and explorations, and [START_REF] Arzamasova | On the Usefulness of SQL-Query-Similarity Measures to Find User Interests[END_REF] for SQL queries.

Aligon et al. [START_REF] Aligon | Similarity measures for OLAP sessions[END_REF] also proposes two similarity measures: one tailored for OLAP queries and another tailored for OLAP sessions. Their measures were designed for satisfying other requirements, in particular capturing the portions of the cube that are more explored for improving query recommendation. Consequently, similarity measures are based on common query parts (e.g. filters and measures) more than common operations, and are strongly dependent on cube schema. To our knowledge, no similarity already proposed in the literature for comparing explorations includes the requirements presented in the previous section.

EXPLORATION MODEL

This section introduces the description of queries and explorations used all along the paper as well as their representation in a space of OLAP operations.

Queries and explorations

In order to keep the formalism simple, we only take into account cubes under a ROLAP perspective, described by a star schema [START_REF] Kimball | The Data Warehouse Toolkit: Practical Techniques for Building Dimensional Data Warehouses[END_REF]. For convenience, we consider that a dimension consists of a unique hierarchy without branches, i.e., consisting of chains of levels. In this paper, we focus on multidimensional queries modeled as a collection of fragments extracted from the query expression, as in [START_REF] Aligon | Similarity measures for OLAP sessions[END_REF]. Definition 3.1 (OLAP query). An OLAP query over cube schema S is a triple q = ⟨G, P, M⟩ where:

(1) G = {д 1 , . . . , д j } is the query group-by set, each д i being a level of a hierarchy of the cube; (2) P = {p 1 , . . . , p k } is a set of Boolean predicates, of the form l = v, with l a level and v a value. Compound predicates are build as the disjunction of predicates on a same level (l), at most one for each hierarchy, whose conjunction defines the selection predicate for q;

(3) M = {m 1 , . . . , m l } is the measure set whose values are returned by q.

We intentionally remain independent of presentation and optimization aspects, specially the order in which attributes are projected (and visualized), the order of joins, etc.

Finally, an exploration is a coherent sequence of queries over a cube schema, devised by a user with the goal of fulfilling an information need that may not be well defined initially. Definition 3.2 (Exploration). Let S be a cube schema. An exploration e = ⟨q 1 , . . . , q p ⟩ is a sequence of queries over S. We note q ∈ e if q appears in the exploration e, and exploration(q) to refer to the explorations where q appears.

Query features

For each query, we extract a set of simple features computed from the query text and its relationship with previous query in an exploration. The set of features is inspired from our previous works [START_REF] Djedaini | Automatic assessment of interactive OLAP explorations[END_REF][START_REF] Djedaini | Detecting User Focus in OLAP Analyses[END_REF]. It intends to capture various aspects of OLAP navigation, in particular the set of OLAP operations that express one query w.r.t. the previous one (e.g. a query being a drill down of the previous one), the level of aggregation (i.e. how deep the query is in the aggregation lattice) and the level of filtering (i.e. how filtered is the data space). Table 1 presents an overview of the features, where added (resp., deleted) indicates the modification made compared to the previous query.

For the following definitions let q k = ⟨G k , P k , M k ⟩ be the query occurring at position k in the exploration e over cube schema S. All the queries we considered are supposed to be well formed, and so we do not deal with query errors. Features are computed comparing the query q k to the previous query in the exploration e, q k-1 = ⟨G k -1 , P k -1 , M k -1 ⟩. For the first query of e, i.e. q 1 , we consider as predecessor the "empty" query q 0 = ⟨∅, ∅, ∅⟩. All the following features are defined for k ≥ 1.

Number of Added Levels. N AL(q k , q k -1 ) counts the number of levels in the group by set of q k that were not part of the group by set of q k-1 .

N AL(q k , q k -1 ) = |G k -G k -1 | (1)
Number of Deleted Levels. N DL(q k , q k-1 ) counts the number of levels in the group by set of q k -1 that are not longer used in

q k . N DL(q k , q k -1 ) = |G k -1 -G k | (2)
Number of Added Filters. N AF (q k , q k -1 ) counts the number of filters of q k that were not filters of q k -1 .

N AF (q k , q k-1 ) = |P k -P k -1 | (3)
, q k-1 ) counts the number of filters of q k-1 that are not longer used in q k . N DF (q k , q k-1 ) = |P k -1 -P k | (4)
Number of Added Measures. N AM(q k , q k -1 ) counts the number of measures of q k that were not measures of q k -1 .

N AM(q k , q k -1 )

= |M k -M k -1 | (5)
Number of Deleted Measures. N DM(q k , q k -1 ) counts the number of measures of q k -1 that are not longer used in

q k . N DM(q k , q k -1 ) = |M k -1 -M k | (6)
Aggregation Depth. Adepth(q k ) measures the granularity of q k in terms of the depth of each level in its hierarchy. It can be seen as the number of drills down necessaries for obtaining G k from the most aggregated group-by set. Let depth(д i ) be the depth of level д i in the hierarchy h i to which it belongs (ranging from 0 if

д i is the top level of h i to |h i | -1 if д i is the bottom level of h i ): Adepth(q k ) = д i ∈G k depth(д i ) (7)
Filter Depth. Fdepth(q k ) measures the number of filters appearing in q k .

Fdepth

(q k ) = |P k | (8)
In what follows, we represent an OLAP query in the space of query features, i.e. as a 8-dimensional vector, each position corresponding to one of the features described above. This representation is at the core of our proposal for computing the similarity between queries and then between explorations. It focuses in operations between queries and is independent of the underlying data cube, i.e. a given sequence of operations, even on different data cubes, will result in the same sequence of query vectors.

Example 1. Consider an exploration e 1 composed of 4 queries: q 1 = ⟨{year }, ∅, {qty}⟩ -sales quantity per year; q 2 = ⟨{year }, {year = "2019"}, {qty}⟩ -adds a filter; q 3 = ⟨{year, country}, ∅, {qty}⟩ -unfilter, drill-down; q 4 = ⟨{year, city}, ∅, {qty, amount }⟩ -drill-down, adds measure; Vector for q 1 , ⟨1, 0, 0, 0, 1, 0, 1, 0⟩, indicates an added level (year) and an added measure (qty) w.r.t. the empty query; last positions correspond to aggregation and filter depths. Vectors for q 2 , q 3 and q 4 indicate the differences w.r.t. previous queries and the changes in aggregation and filter depths: ⟨0, 0, 1, 0, 0, 0, 1, 1⟩, ⟨1, 0, 0, 1, 0, 0, 2, 0⟩, ⟨1, 0, 0, 0, 1, 0, 3, 0⟩, resp.

Finally, we use cosine similarity for computing similarity between queries. This measure is adapted to compute similarity of two vectors and is normalized in [0, 1]. In this way, it privileges the nature of OLAP operations and not their number. This section describes our proposal of Contextual Edit Distance: definition and implementation issues.

CED is a generalization of the Edit Distance that incorporates the following requirements:

(1) Context-dependent cost: Edition cost depends on the similarity of nearby queries. The more similar and closer the queries, the lower the cost of operation. (2) Repetition: Edition of repeated close queries has low cost.

(3) Permutation: Similar and close queries can be exchanged with a low cost.

Example 2. Consider an exploration reflecting an exploratory behavior at the beginning (many changes in measures and group by set) and more focus at the end (drilling and filtering). We can sketch it as follows (where L, F and M means level, filter and measure, + means addition and -means deletion; we skip aggregation and filter depth for simplicity): ⟨ +D+M, +M, +M, +D, +M-M, -M+D, -D+D, +F+D, +F+D, +F, +F ⟩.

Consider the insertion of a query adding an additional measure (+M). The edition cost should be low if the query is inserted at the beginning (as it is similar to near queries), even lower at positions 2 to 4 (because repeating the same operations), but high at the end.

This requirements ensure that explorations reflecting a given pattern (e.g. sequences of drill-downs) are judged to be very similar no matter the exploration length (i.e. how many drilldowns) nor the underlying data (which data was drilled-down).

We remark that although this paper deals with explorations, CED definition and properties are independent on the type of explorations, the type of queries and even the nature of data. Indeed, CED can be adapted to any type of sequence on an alphabet of symbols provided that exists a similarity metric among them.

Definition of Contextual Edit Distance

The main contribution of CED is the modification of the cost function γ which generalizes the classical definition of Edit Distance and takes into account the local context of each query in the exploration. Intuitively, the cost of an edit operation will be lower if the edited query (e.g. a query to be added to an exploration) is similar to nearby queries (e.g. the queries that are near the position where the query is added). This notion of local context is modeled as a context vector, which controls the zone of influence of the context. This subsection presents these concepts and a formal definition of CED.

Let Q be the set of all possible queries over a cube schema S and Q * the set of all possible explorations on Q. For the following definitions, let e = ⟨q 1 , ..., q n ⟩ be an exploration, q k be a query in e, 1 ≤ k ≤ n, and q x be a new query to be edited in e. These notations are partially adapted from the formal language theory community and particularly from [START_REF] Wagner | The String-to-String Correction Problem[END_REF].

CED extends the set of edit operations of Edit Distance (usually modification, addition, deletion) to take context into account. • mod : (e, q x , k) → q 1 , ..., q k -1 , q x , q k +1 , ..., q n

Replace the query at index k by the query q x .

• add : (e, q x , k) → q 1 , ..., q k-1 , q x , q k , ..., q n Insert query q x at index k. The queries at and after index k are shifted forward. • del : (e, ε, k) → q 1 , ..., q k -1 , q k +1 , ..., q n Delete the query at position k. The queries after position k are shifted backward.

Given an operation o(e, q x , k), a context vector is a numeric vector that indicates the level of influence of nearby queries for this operation, being stronger near index k and softening farther. We use the context vector for weighting the similarity between queries. Intuitively, the context vector quantifies the relationship between a query q x and another query q i . Thus, the greater v i , the greater the impact of query q i on q x . A seed function is used to generate context vectors. Definition 4.2 (Context function and context vector). Consider a contextual edit operation o(e, q x , k) and a seed function f k : N → [0, 1] which holds the following properties:

(1) f k (k) = 1. (2) f k is a monotonically increasing function on ] -∞, k]. (3) f k is symmetrically centered on k.
The third property guarantees to take with the same importance previous and future queries located at equal distance from q k . A context function φ o : N * → [0, 1] is a transformation of f k stretching the function according to the type of operation o. We distinguish three cases for o in {mod, add, del}:

• φ mod (x) = f k (x) • φ add (x) = f k (x + 1) if x ≤ k -1 f k (x) if x ≥ k • φ del (x) =          f k (x + 1) if x ≤ k -1 0 if x = k f k (x -1) if x ≥ k + 1 Finally, a context vector v : O → [0, 1] n is defined as v(o) = ⟨v 1 , . . . , v n ⟩ where v i = φ o (i).
About add and del contextual vector functions:

• For an insertion add : (e, q x , k), query q k -1 and q k are fully taken into account for the addition of q x in e because we insert q x between index k -1 and k i.e. φ add (k -1) = 1 and φ add (k) = 1. • For a deletion del : (e, ε, k), the absence of the query q k in e is quantified in relation to the remaining of e i.e. φ del (k) = 0.

q 1 q 2 q 3 q 4 f 4 = exp ( - 1 2 ( x -4 2 ) 2 ) φ o = : (e, q x ,4) | {z } e Figure 2:
Add a new query q x in position 4 in e.

Example 3. Consider the operation o = add(e, q x , 4), adding a query at index 4 of an exploration. Figure 2 illustrates the computation of φ add (plotted in blue) from a given seed function (in red). The corresponding context vector is v(o) = ⟨0.61, 0.88, 1, 1⟩. It indicates that the similarity score of queries at indexes 3 and 4 is fully considered (weight of 1) while a lower score is considered for query at index 1.

The cost function γ of CED generalizes the classical definition of Edit Distance and takes into account the local context of each query in the exploration.

γ (o) = α × δ (o)+ (1 -α) 1 -max i ∈[[1,n]] {sim(q i , q x ) × v i (o)} (9)
where:

• α ∈ [0, 1] is a contextual parameter.
If α → 0 the contextual part is maximal and therefore the distance between two queries will be strongly evaluated according to the content of the exploration being edited ; if α → 1 then cost of edition is fixed.

• δ (o) = 1 -sim(q k , q x ) i f o = mod 1 else
is the local cost of the Edit Distance.

• sim : Q × Q → [0, 1]
is a similarity measure between two queries, computed as the cosine of query vectors.

Example 4. Consider the exploration e 1 of Example 1 and consider the insertion of query q x , with vector ⟨0, 0, 1, 0, 0, 0, 2, 1⟩ (addition of a filter), at position 4, as shown in Figure 2, with α = 0.1. Then, the cost γ (o) is such that:

γ (o) = 0.1 + 0.9 1 -max            cos(q 1 , q x ) × φ add (1) cos(q 2 , q x ) × φ add (2) cos(q 3 , q x ) × φ add (3) cos(q 4 , q x ) × φ add (4)            = 0.1 + 0.9 1 -max            0.47 × 0.61 0.94 × 0.88 0.66 × 1 0.74 × 1            = 0.1 + 0.9 × (1 -0.83) = 0.25
The insertion of q x at position 2 (i.e. to other filter operation) has cost 0.15. Definition 4.4 (Edit path). Given two explorations e, e ′ ∈ Q * , an edit path P = ⟨o 1 , o 2 , ..., o m ⟩ from e to e ′ is a sequence of operations that transform e in e ′ . We note P(e, e ′ ) the set of all edit paths to transform e in e ′ .

An important point to be mentioned here is that, for efficiency reasons, the context is static, i.e. it only considers the original queries in exploration e. This means that the contextual edit operation o i has no impact on the cost of operation o i+1 . If it was otherwise, i.e., dealing with dynamic context, the edition problem would have been NP-hard by reduction to Job shop scheduling problem [START_REF] Karp | Reducibility among Combinatorial Problems[END_REF]. Also note that as the add operator is not the reverse of del operator, the edition is asymmetric. Thus, by re-using the definition of the Edit Distance in [START_REF] Wagner | The String-to-String Correction Problem[END_REF], we can define the one-side distance from an exploration e 1 to an exploration e 2 . dCED (e 1 , e 2 ) = min

P ∈ P(e 1 ,e 2 )        |P | i=1 γ (o i )        (10)
In this form, CED would be very similar to Hausdorff distance [START_REF] Huttenlocher | Comparing images using the Hausdorff distance under translation[END_REF], but would remain asymmetric. This is why we use the same trick as Hausdorff distance and we apply the max operator on each one-sided contextual edit distance to recover the symmetry.

Implementation of CED

We can compute d C ED using a Dynamic Programming approach like the classical Edit Distance [START_REF] Wagner | The String-to-String Correction Problem[END_REF]. This solution has a polynomial complexity in O(n × p) and can be adapted easily for the computation of CED. Algorithm 1 computes the context vector and the cost function (as in Equation 9). Note that φ o : N * → [0, 1] and α ∈ [0, 1] are fixed parameters and operator • represents vector concatenation. Algorithm 2 computes the one-sided Contextual Edit Distance (Equation 10), and Algorithm 3 recovers the symmetry.

Algorithm 1: Cost function γ

Data: Contextual edit operator o : (e, q x , k).

Result: Cost γ (o) of the operation o. v(o) ← ⟨⟩ for i ∈ ⟦1, |e |⟧ do v(o) ← v(o) • ⟨φ o (i)⟩ v sim ← ⟨⟩ for i ∈ ⟦1, |e |⟧ do v sim ← v sim • ⟨sim(q i , q x ) × v i (o)⟩ if e = mod then δ (o) ← 1 -sim(q k , q x ) else δ (o) ← 1 return α × δ (o) + (1 -α) × (1 -max(v sim ))
Next, we prove that the computation of CED is polynomial in time: Proof : Let's note T (A i ) the big O time complexity of the algorithm A i , with i ∈ {1, 2, 3}. So we have :

• T (A 1 (o)) = |e |
where e is the edited exploration.

• T (A 2 (e 1 , e 2 )) = n × p × T (A 1 (o : e 1 , q x , k)) = n 2 × p • T (A 2 (e 2 , e 1 )) = n × p × T (A 1 (o : e 2 , q x , k)) = n × p 2 • T (A 3 (e 1 , e 2 )) = T (A 2 (e 1 , e 2 )) + T (A 2 (e 2 , e 1 )) = n 2 p + p 2 n ∈ O(n × p × max(n, p))
As a result, the Algorithm

if i = 0 ∨ j = 0 then D[i, j] ← i + j else o mod ← mod : (e 1 , q (2)
j-1 , i -1) o del ← del : (e 1 , q (1) i-1 , i -1) o add ← add : (e 1 , q (2) j-1 , i -1) D[i, j] ← min{ D[i -1, j -1] + γ (o mod ), D[i -1, j] + γ (o del ), D[i, j -1] + γ (o

CLUSTERING OF EXPLORATIONS

Our objective is to cluster together explorations showing the same user behavior. To this end, we pair CED to an off-the-shell clustering algorithm, and we test it against several workloads concerning users with varied analytical skills and different UI, aiming to discover different types of patterns. In addition, as some datasets come with a ground truth, they allow for the quantification of clustering quality and the comparison to state of the art distances. The following subsections describe the workload used in experiments, the experimental protocol and implementation details.

Workloads

In our experiments, we reuse several workloads described in the literature [START_REF] Aligon | A Holistic Approach to OLAP Sessions Composition: The Falseto Experience[END_REF][START_REF] Djedaini | Automatic assessment of interactive OLAP explorations[END_REF][START_REF] Milo | Next-Step Suggestions for Modern Interactive Data Analysis Platforms[END_REF] consisting of navigation traces of real users on real data. We chose to test our proposal in several workloads to avoid learning specific behavior of a set of users. The 3 workloads concern users with different analysis skills (students, experts), using different analysis tools (an OLAP tool, a research prototype and an advanced IDE interface) and accessing data cubes of different sizes and complexities. We are not aware of other public analytical workloads, specially from senior analysts, whose analysis activity is jealously guarded by companies [START_REF] Rizzi | CubeLoad: A Parametric Generator of Realistic OLAP Workloads[END_REF].

We also generated artificial explorations on artificial data using a state-of-the-art workload generator [START_REF] Rizzi | CubeLoad: A Parametric Generator of Realistic OLAP Workloads[END_REF].

Real explorations on ipums data. The first workload, henceforth dubed Ipums, consists of navigation traces of OLAP users collected during the testing phase of the development of Falseto [START_REF] Aligon | A Holistic Approach to OLAP Sessions Composition: The Falseto Experience[END_REF], a tool meant to assist query and exploration composition, by letting the user summarize, browse, query, and reuse former analytical explorations. The 17 OLAP users engaged in the test were students of two Master's programs specialized in Business Intelligence. The test was not part of the programs, was not graded and all the participants were volunteers. They developed explorations for answering four analytical questions on the IPUMS cube. The IPUMS cube integrates data from the IPUMS (Integrated Public Use Microdata Series) website 1 . It is organized as a star schema with 5 dimensions, 12 (non-top) levels, 25 measures, and contains 500,000 facts recorded in the fact table. From this experiment, we reuse 27 explorations and 306 queries, with an average of 11 queries per exploration.

During a preliminary analysis of the workload, Aligon et al. labelled explorations distinguishing five analysis styles:

• FOCUS. The exploration is more focused as time passes,

• OSCILLATE-FOCUS. The exploration is more exploratory (the levels of detail and filtering oscillate) at the beginning but is more focused at the end, • OSCILLATE. The exploration is always exploratory, • FIX. The exploration keeps constant levels of detail and filtering, • ATYPICAL. The exploration has atypical or erratic behavior.

Real explorations on open data. The second workload, henceforth dubed Open, consists of navigation traces collected in the context of a French project on energy vulnerability. These traces were produced by 8 volunteer students of a Master's degree in Business Intelligence, answering fuzzy information needs defined by their lecturer, to develop explorative OLAP navigations using Saiku 2 over three cubes instances [START_REF] Djedaini | Automatic assessment of interactive OLAP explorations[END_REF]. The main cube is organized as a star schema with 19 dimensions, 68 (non-top) levels, 24 measures, and contains 37,149 facts recorded in the fact table. The other cubes are organized in a similar way. From this experiment, we reuse 28 explorations and 941 queries, with an average of 34 queries per exploration. A particularity of some third party OLAP tools, like Saiku, is that their user interface submits a new query for each user action (including intermediate drag-and-drops), resulting in very long explorations in the log. Nevertheless, there were some extremely short explorations (6 explorations counting less than 10 queries), which mainly correspond to incomplete studies.

Real explorations on cyber security data. The third workload, henceforth dubed Security, consists of analysis sessions made by real analysts in the context of the "Honeynet Project" [START_REF] Milo | Next-Step Suggestions for Modern Interactive Data Analysis Platforms[END_REF]. 56 analysts specialized in the domain of cyber-security were recruited (via dedicated forums, network security firms, and volunteer senior students from the Israeli National Cyber-Security Program) and asked them to analyze 4 different datasets using a prototype web-based analysis platform. Each dataset contains between 350 to 13K rows of raw network logs that may reveal a distinct security event, e.g. malware communication hidden in network traffic, hacking activity inside a local network, an IP range/port scan, etc. (there is no connection between the tuples of different datasets). The analysts were asked to perform as many analysis actions as required to reveal the details of the underlying security event of each dataset. They used a web-based analysis platform developed for the project [START_REF] Milo | Next-Step Suggestions for Modern Interactive Data Analysis Platforms[END_REF].

Even if there is no ground truth for this workload, it is interesting because queries were devised by expert analysts.

Artificial explorations. The last workload, with artificial data, comes from the Star Schema Benchmark [START_REF] O'neil | The Star Schema Benchmark and Augmented Fact Table Indexing[END_REF], and was used with artificial explorations. The Star Schema Benchmark (SSB) is a variation of TPC-H, a popular benchmark from the Transaction Processing Performance Council (TPC). SSB cube consists of a relational database under the form of a star schema, with one fact table and 4 dimension tables.

Instead of using the rather limited SSB workload, we generated artificial explorations using CubeLoad [START_REF] Rizzi | CubeLoad: A Parametric Generator of Realistic OLAP Workloads[END_REF].

Protocol

In order to cluster explorations, we execute an off-the-shelf clustering algorithm using CED as distance function. For comparison, we execute the same clustering algorithm with two alternative distances: (i) the classical Edit Distance (henceforth dubed ED) as a baseline, and (ii) Aligon et al. 's distance [START_REF] Aligon | Similarity measures for OLAP sessions[END_REF] (henceforth dubed AD), a state of the art metric for session similarity. We analyze the obtained clusters under several angles:

Firstly, when we have some knowledge qualifying explorations, even if it is not exactly a ground truth, we compare our results to such knowledge. For the artificial explorations we compare the obtained clusters with the Cubeload templates used for the generation of the workload. This experiment aims to show that our approach is able to cluster together all the explorations corresponding to a given template. For the ipums workload we compare to the preliminary labels assigned by Aligon et al. Actually, such labels are not ground truth, as there were not produced with the goal of clustering explorations, but they may provide a nice idea of the quality of the exploration. We report Adjusted Rand Index (ARI) and V-measure (harmonic mean of clusters homogeneity and completeness) scores 3 , and we compare our clustering scores to those obtained with ED and AD distances.

Second, for the four workloads, we report further scores concerning intrinsic cluster quality. Indeed, too few clusters will mix different behaviors, too many clusters will overfit user behavior. We aim to balance: number of clusters, cluster diameter (the distance between the farthest objects in the cluster) and mean Silhouette Coefficient (a measure of how similar an object is to its own cluster (cohesion) compared to other clusters (separation)). Silhouette scores 3 are merely informative in out tests, as the metric is more adapted to hyper-spherical clusters.

Finally, we study the medoids of each cluster (the exploration that is the most similar to all other explorations in the cluster) and we manually observe the OLAP operations of the medoid for providing an explanation of the concerned behavior pattern.

Implementation and setting

Our methods are implemented in Python, using Scipy, Sklearn [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF] and Matplotlib libraries. Code and data are available from Github 4 . CED parameters were tuned and set as follows:

• Cosine similarity is used to compare two queries in an exploration. • α parameter is set to 0 to give fully priority to context. • We use the following seed function.

f k (x) = exp - 1 2 2 √ k + 1(x -k) |e | 2
It is a Gaussian function centered at k, therefore satisfying the properties announced in Definition 4.2. Furthermore, it is 3 Metrics for clustering performance evaluation are well described in https://scikit-learn.org/stable/modules/clustering.html sect. 2.3.10. [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF] 4 https://github.com/ClementMoreau-UnivTours/CED_Dolap |e | . This coefficient is interesting because, as it depends on k, it allows to vary context size along the exploration. In particular, when k is small (at the beginning of the exploration, when user intents are less defined and behavior is more exploratory), the standard deviation is high (i.e. the curve of f k is flattened) which allows to include in local context, some queries that are far from the index k. On the other hand, when k → |e | (at the end of the exploration, when behavior is more focused), the curve of f k narrows around k reducing context size. Figure 3 illustrates the context function for several values of k.

f 1 f 3 f 5 q 1 q 1 q 2 q 3 q 4 q 5
As we do not know, a priori, the form of clusters, nor their density, we use a hierarchical clustering algorithm, which provides more flexibility than hyper-spherical and density-based algorithms. In addition, it outputs a dendrogram that allows to parameter the setting of number of clusters and eases the visual analysis of clusters. In order to find a good balance, we experimentally combine some criteria to cut the dendrogram: relative loss of inertia, cluster diameter and minimum number of clusters. We use the Ward method as agglomeration criteria.

Finally, a correlation study among query features revealed that Fdepth was highly correlated with Adepth in all workloads. In consequence, we excluded Fdepth from query vector.

EXPERIMENTS

In this section we report the results of the experiments conducted to validate our proposal.

Comparison against ground truth

In this experiment on Artificial and Ipums workloads, we compared the clusters obtained with our method to the available ground truth (i.e. the template used to generate each exploration and the preliminary classification of Ipums).

Figure 4 (a andd) shows the obtained dendrograms. Explorations (identified by numbers) are arranged in the horizontal axis, plotting similar explorations close (according to CED). Links indicate which explorations are clustered together, shorter links meaning more similar explorations (vertical axis reports distances). Links of the same color represent a cluster, while dotted links just indicate inter-cluster distances. For easing the interpretation we also color explorations ids, according to ground truth labels. We deliberately chose the same set of colors as clusters to visually highlight the good matches.

Artificial workload. The dendrogram exhibits a perfect match among CubeLoad templates (Slice and Drill, Slide All, Exploratory and Goal Oriented, described in Section 2) constituting well separated clusters. We expected a good result with this workload, as CubeLoad templates are well differentiated. E E E E E E E E E A A A A A A A A A A A A

Colored Dendrogram ( 4 groups)

0 2 4 6 8 GO_5 GO_44 GO_30 GO_39 GO_33 GO_49 GO_46 GO_1 GO_9 GO_40 GO_38 GO_10 GO_19 GO_18 GO_27 GO_25 GO_35 E_14 E_24 E_22 E_11 E_17 E_6 E_47 E_41 E_43 SA_42 SA_31 SA_16 SA_8 SA_13 SA_15 SA_32 SA_26 SA_23 SA_20 SA_7 SA_12 SD_45 SD_4 SD_34 SD_29 SD_48 SD_50 SD_2 SD_37 SD_36 SD_28 SD_3 SD_21 Labels G G G G G G G G G G G G G G G G G
GO_40 E_17 E_41 E_14 GO_46 GO_18 E_43 GO_9 GO_30 GO_39 SA_8 SA_31 SA_42 SA_13 SA_32 GO_5 GO_44 GO_27 GO_33 E_11 SA_7 SA_20 SA_23 E_22 GO_1 GO_25 E_6 SA_16 GO_35 GO_38 E_47 GO_49 SD_34 SD_4 SD_45 GO_19 SD_36 SD_28 SD_3 SD_21 SD_50 SD_2 SD_37 SD_29 SD_48 GO_10 SA_12 E_24 SA_15 SA_26 Labels

G E E E G G E G G G A A A A A G G G G E A A A E G G E A G G E G D D D G D D D D D D D D D G A E A A

Colored Dendrogram ( 6 groups) 0.0 0.5 In addition, many explorations of the Slice All template (and some of the Slice and Drill template) are highly similar (distance near 0) as they contain sequences of the very same operations, even if exploration size is variable. This is one of the characteristics that makes CED a well-adapted distance for this problem.

E E E E E G E E E A A A D A A A G A G G G D D D A D A G G G G G G G G G D D D G D D G D D D G D G G

Ipums workload. CED correctly classes most FOCUS and ATYP-ICAL explorations. However, it fails to distinguish between OSCI-LLATE-FOCUS and OSCILLATE explorations, the frontier being quite fuzzy, and FIX explorations are not distinguished from FO-CUS ones. We remind that these labels are not a real ground truth, but a preliminary classification for other purpose. Table 2 indicates ARI and V-measure scores.

Comparison with other distances

In this experiment we compare the clusters obtained using 3 distances: CED, ED and AD. Results are reported in Table 2 and Figure 4. In Table 2 we can see that CED outperforms AD and ED in both Artificial and Ipums workloads on both quality metrics.

With ED, clusters reflect exploration sizes instead of query operations. For example, in Figure 4(e) the first cluster includes short explorations, the second cluster contains the longest ones, and the last cluster contains medium ones. 4 (b)). On the other hand CED is solely based on the structural properties of the explorations.

Other quality considerations

In addition to ARI and V-measure scores (calculated w.r. 3: Nb of clusters, diameter, Silhouette, ARI and Vmeasure scores for each workload using CED scores to complete our quality analysis. Results are reported in Table 3 for the 4 datasets.

Globally, we observe that most diameters are low, indicating that clusters are compact. Therefore, medoids are good representatives of each cluster. Most Silhouette scores are also positive, which is a good result given that our clusters are not hyperspherical. In particular, we note that even if CED was able to generate a pure partition for the Artificial workload, we observe a low Silhouette score.

Interpretation of students' behavior

The next experiment clusters students explorations of the Ipums and Open workloads. We manually examine some explorations of each cluster, including the centroid, with the goal of abstracting students explorations patterns.

Ipums workload. The 27 explorations are arranged in 4 clusters of different sizes.

Clusters of explorations represent the following behavior:

• The 2 explorations in the first cluster start by many changes in the measure set (as trying to choose the good measures), followed by a long period of filter/unfilter operations, combined with some drill-downs and roll-ups, but with little changes in the level of detail. • Globally, explorations in the second cluster alternates drilldowns and roll-ups. Some of them include a few filters, but most of them (this is the case of the medoid) do not filter any data. • The 3 explorations of the third cluster start alternating drills down and rolls up (as in cluster 2), then alternate filters/unfilters, some of them focusing at the end (as in cluster 4). This cluster has common points with clusters 2 and 4, some kind of intermediate behavior. • The last cluster includes focused explorations, which regularly increase the level of detail and filtering by adding drill-down and filter operations. Some of them mix other operations, mostly at the beginning, but drill-downs and filters are the predominant operations.

From a more general perspective, our study shows that half of the explorations follow a focused pattern (cluster 4) translating that those students have developed a particular type of analysis skills, while other students are more exploratory (cluster 2), perhaps translating a lack of maturity in their analysis skills, perhaps just showing their style. Clusters 1 and 3 depicts outlier behaviors.

Open workload. Our method organizes the 28 explorations in 6 clusters, 3 of them containing an outlier the first one being very different from all the others (inter-cluster distance around 50).

The interpretation of clusters is harder for this workload, as Saiku tool produce very longs explorations (the longest in this workload counts 127 queries). So manual inspection of explorations is tedious and may lead to judgement errors. With this disclaimer, we summarize the behavior represented by clusters as follows:

• The outlier in first cluster is the shortest exploration (4 queries), whose queries are fully aggregated (only ALL levels), and operations only change measures. • The second cluster contains 10 explorations, many ones being very short, including the medoid. A general behavior is a constant or lightly increasing level of detail, sometimes being high, sometimes medium. Most explorations (except one) have little filters, but exhibit some changes in the measure set. • The third cluster contains 7 explorations, all of them continuously increasing the level of detail and filtering. There are multiple drill-downs and multiple filters all along the explorations. • Cluster 4 contains another outlier clustered alone. It exhibits several abrupt changes in the level of detail with several peaks, continuous changes of measures and some filters in the middle. • Another exploration also clustered alone. It also shows many abrupt changes in the level of detail, with some changes in filters and measures at the beginning and an increase in the filter level at the end. • The last cluster contains 8 explorations. Its medoid has no filters nor changes in the measure set. OLAP operations include only drill-downs and roll-ups, with an increase of the level of detail in the middle, decreasing at the end of the exploration. Other explorations in the cluster include other OLAP operations. The common behavior resides in the increasing-decreasing pattern in the level of detail.

In conclusion, this clustering confirmed some of the already identified patterns and enabled to discover a new one. Specifically, cluster 3 corresponds quite well to the Focus cluster of Ipums workload and the Slice and Drill template of CubeLoad; while cluster 6 corresponds to the Oscillate cluster of Ipums (having no equivalent template in CubeLoad). The new pattern, reflected by cluster 2, corresponds to less skilled students, making timid usage of OLAP operations (some drill-downs and roll-ups, few filters, some changes of measure). The recognition of outlier behavior is another strong point of our method.

Interpretation of experts' behavior

This experiment shows the application of our approach to a larger workload, whose explorations were devised by expert analysts using an advanced IDE interface. Surprisingly, many explorations of the Security workload contain only one query (260 out of 723); we excluded them from the study. Another interesting point is that there are long sequences of repeated queries (i.e. the exploration contains many times the same query). This may reflect movements in the way query results are arranged and visualized, while referring to the same underlying query.

There is no ground truth and a manual observation of the 723 explorations is not doable, however, we provide some general comments and a detailed analysis of the medoids of the 5 retrieved clusters (and some randomly picked explorations):

• Explorations in cluster 1 do many movements in the group by set, oscillating the level of detail, with some peaks in the middle. There are other operations; the medoid does many changes in measure set.

• Cluster 2 contains many long explorations, which characteristic is the alternation of adding and deleting one fragment (a level in the group by set, a filter or a measure). • Explorations in the third cluster are highly similar (many distances are around 0). It includes many short explorations (as the medoid), with few operations, mainly drilldowns. • Explorations in cluster 4 have very few operations, and globally exhibit long subsequences of identical queries. • In the last cluster, queries have constant level of detail (generally low), with some movements in the group by set and few filters.

As expected, analysts' behavior is different from students'. Globally, their explorations exhibit less operations, with more emphasis in the grouping of data, probably also in their arrangement and visualization (which is not captured in our method) of the data; while students are more click-oriented and produce longer explorations with much more operations.

Clusters 3 and 4 evidence this behavior and Cluster 2 is some kind of generalization of the Slice All pattern of CubeLoad. Clusters 1 and 5 coincide with those of the other workloads. Table 4 summarizes the discovered patterns.

CONCLUSION

This paper addressed the problem of learning analysis patterns in OLAP explorations, which is a hot topic for the understanding of human behavior and providing IDE support. Concretely, we propose to cluster similar explorations using a Contextual Edit Distance, and then extract analysis behavior from clusters. CED is a new distance that is well-suited for comparing explorations taking into account their local context, and then lowering the edition cost of similar queries, repetitions and permutations. Our experiments with four workloads allowed to detect CubeLoad templates and to learn some new analysis patterns from students and expert analysts explorations. Even if these results are promising, our method needs to be tested in larger workloads, with varied skilled and non-skilled users and different types of user interfaces, before abstracting more general patterns.

As future work, we plan to tune our method and study its sensibility and robustness with respect to CED parameters, query features and query similarity. We would also like to compare our results to other clustering methods and distances. Our long term goal is to automatically classify explorations and qualify users skills, allowing the recommendation of pertinent next queries, among other applications.

Finally, we remark that CED is not endemic to analysis behavior and it can be adapted to study other types of human behavior (provided that such behavior could be represented as a sequence of symbols). In particular, we have used CED for comparing human daily moves [START_REF] Moreau | A Contextual Edit Distance for Semantic Trajectories[END_REF] and we are currently discovering and analysing peculiar patterns of children mobility.

Figure 1 :

 1 Figure 1: Overview of the approach: (a) explorations and queries are represented in a space of OLAP operations, (b) computation of CED, (c) clustering of explorations based on CED, (d) extraction of patterns of user behavior (here, represented as the patterns of Cubeload).

Definition 4 . 1 (

 41 Contextual edit operation). A contextual edit operation o is a function o : (Q * × Q ∪ {ε} × N) → Q * whosearguments are an exploration, a new query to be included in the exploration (or none) and the index (position) in the exploration where the edition takes place. We consider the following set O = {mod, add, del} of edit operations:

Definition 4 . 3 (

 43 Cost function γ ). Given an operation o(e, q x , k), a cost function γ : O → [0, 1] for the contextual edit operations is defined as:

Definition 4 . 5 (

 45 One-sided Contextual Edit Distance). Let dCED : Q * × Q * → R + be the Contextual Edit Distance from e 1 to e 2 such that:

Definition 4 . 6 (

 46 Contextual Edit Distance). Let d C ED : Q * × Q * → R + be the Contextual Edit Distance such that: d C ED (e 1 , e 2 ) = max dCED (e 1 , e 2 ), dCED (e 2 , e 1 )(11)

Theorem 4 . 7 .

 47 CED is in O(n × p × max(n, p)) where |e 1 | = n and |e 2 | = p.

Figure 3 :

 3 Figure 3: Example of context function with k = 1, 3, 5 and |e | = 5

Figure 4 :

 4 Figure 4: Dendrogram results on Artificial (on left) and Ipums (on right) workloads.

Table 1 :

 1 Query featuresNumber of Deleted Filters. N DF (q k

	Feature Description
	NAL	Number of added levels
	NDL	Number of deleted levels
	NAF	Number of added filters
	NDF	Number of deleted filters
	NAM	Number of added measures
	NDM	Number of deleted measures
	Adepth	Aggregation depth
	Fdepth	Filter depth

  One-sided Contextual Edit Distance dCED Data: Exploration couple (e 1 , e 2 ). Result: One-sided Context Edit Distance dCED (e 1 , e 2 ) D ← [0...|e 1 |][0...|e 2 |] for i ∈ ⟦0, |e 1 |⟧ do for j ∈ ⟦0, |e 2 |⟧ do

3 has a time complexity in O(n × p × max(n, p)). □ Algorithm 2:

Table 4 :

 4 Summary of discovered patterns and ids of the concerned clusters.

	Pattern	Artificial Ipums Open Security
	Slice and Drill	4	4	3
	Slice All	3
	Exploratory	2
	Goal Oriented	1
	Oscilating		2	6	1
	Oscilate+Focus		3
	Constant Agg. level			2	5
	Add-Delete Fragment				2
	Few operations				3
	Repeted queries				4
	Outliers		1	1,4,5

Minnesota Population Center. Integrated Public Use Microdata Series. http://www.ipums.org,

2 http://meteorite.bi/products/saiku

ACKNOWLEDGMENTS

The authors would like to thank Nicolas Labroche for their useful insights on clustering quality. This work is partially supported by French ANR Agency, in the context of Mobi'kids project.


Study Design. Continuous measurements and computation of absolute metrics of cervical subarachnoid space (CSS) and spinal cord (SC) geometries proposed are based on in vivo magnetic resonance imaging and 3D reconstruction.

Objective. The aim of the study is to offer a new methodology to continuously characterize and to quantify the detailed morphology of the CSS and the cervical SC in 3D for healthy subjects in both neutral supine and flexion.

Summary of Background Data. To the best of our knowledge, no study provide a morphological quantification by absolute indices based on the 3D reconstruction of SC and CSS thanks to in vivo magnetic resonance imaging. Moreover, no study provide a continuous description of the geometries.

Methods. Absolute indices of SC (cross-sectional area, compression ratio, position in the canal, length) and of CSS (cross-sectional area, occupational ratio, lengths) were computed by measures from 3D semi-automatic reconstructions of high resolution in vivo magnetic resonance images (3D T2-SPACE sequence) on healthy subjects (N=11) for two postures : supine neutral and flexion neck positions. The variability induced by the semi-automatic reconstruction and by the landmarks positioning were investigated by preliminary sensitivity analyses. Inter and intra-variability were also quantified on a randomly chosen part of our population (N=5).

Results. The length and cross-sectional area of SC are significantly different (p<0.05) in flexion compared to neutral neck position. Spinal cord stays centered in the canal for both postures. However, the cross-sectional area of CSS is submitted to low variation after C3 vertebra for both postures. OR and CR after C3 are significantly lower in flexion.

Conclusions. This study presented interpretations of morphological measures :

1) left-right stability (described by the Left-Right eccentricity index) ensured by the denticulate ligaments and the nerve roots attached to the dural sheaths, 2) a Poisson effect of the SC was partially notified through its axial (AP diameter, OR, CR) and its longitudinal geometrical descriptions (LSC). Such Structured Abstract (300 words) morphological data can be useful for geometrical finite element modeling and could now be used to compare with injured or symptomatic subjects.

Key points. (3-5 full sentences of the main pts of the article)

The mechanical roles of the structures inside the vertebral canal in flexion : left-right stability (described by the LR eccentricity index) ensured by the denticulate ligaments and the nerve roots attached to the dural sheaths.

A Poisson effect of the SC was partially highlighted through its axial (AP diameter, OR, CR) and its longitudinal geometrical descriptions (LSC).

Such morphological data can be useful for geometrical finite element modeling of the canal in terms of boundaries, initial conditions as well as for an optimization of the mechanical properties by geometrical calibration of the model. Key Points (3-5 main points of the article) Précis. (Submit a short description of the manuscript to appear in the Table of Contents, 3 sentences Max 50 words.

Introduction

Considering the limited spatial resolution that could be reached on conventional MR system (1.5 or 3T), 9 the subarachnoid space is often simplified as a dural tube or as a space in the sagittal plane between the spinal 10 cord and the anterior and posterior parts of the canal. Using this assumption, Kato et al. provided a large data 11 base of MRI morphological measurements and showed the influence of the age and the gender on the occupation 12 rate of the spinal cord in the dural tube on a large population [START_REF] Wolf | In cervical spondylotic myelopathy spinal cord motion is focally increased at the level of stenosis: a controlled cross-sectional study[END_REF] . Dahlan et al. [START_REF] Kong | Predictive factors of symptomatic lumbar canal stenosis in patients after surgery for cervical spondylotic myelopathy[END_REF] established normal values of 13 cervical canal diameters for young military subjects. Others studies focused on the SC location in the cervical 14 canal based on two-dimensional (2D) visualization analysis for heathy subjects [START_REF] Tykocki | Correlation between the severity of myelopathy and cervical morphometric parameters on dynamic magnetic resonance imaging[END_REF] and for symptomatic subjects [START_REF] Tykocki | Analysis of Morphometric Parameters in Cervical Canal Stenosis on Neutral and Dynamic Magnetic Resonance Imaging[END_REF] .

15

CSS and SC characterization at specific spine levels (mid-vertebrae, discs) can also be found, with different 16 parameters such as compression ratio, cross-sectional area and spinal cord displacement that have been used in 17 clinical research context [START_REF] Kato | Normal morphology, age-related changes and abnormal findings of the cervical spine. Part II: Magnetic resonance imaging of over 1,200 asymptomatic subjects[END_REF][START_REF] Dahlan | Morphometric Analysis of the Corpus, Spinal Canal and Torg Ratio Using Midsagittal Cervical Vertebrae Computed Tomography Scan: Indonesian Population[END_REF][START_REF] Fradet | Morphometrics of the entire human spinal cord and spinal canal measured from in vivo high-resolution anatomical magnetic resonance imaging[END_REF][START_REF] Kar | MRI Study on Spinal Canal Morphometry: An Indian Study[END_REF] . In patients with Cervical Spondylotic Myelopathy (CSM), area of the SC, as well as 18 antero-posterior and left-right diameters were described [START_REF] Bilston | The biomechanics of the spinal cord during traumatic spinal cord injury[END_REF][START_REF] Bilston | Biomechanics of cervical spinal cord injury in flexion and extension: A physical model to estimate spinal cord deformations[END_REF] so as to evaluate the cord compression in the canal. 19 When characterizing changes in posture, some articles considered a quantification of the strain of cord 20 while others considered displacement measurements. Indeed, longitudinal strain of human cervical cord can 21 reach a magnitude of 5% and 20% for, respectively, flexion and extension [START_REF] Hu | Pathological changes of cervical spinal canal in cervical spondylotic myelopathy: A retrospective study on 39 cases[END_REF][START_REF] Smith | Association of Myelopathy Scores With Cervical Sagittal Balance and Normalized Spinal Cord Volume: Analysis of 56 Preoperative Cases From the AOSpine North America Myelopathy Study[END_REF][START_REF] Stoner | Measurement of in vivo spinal cord displacement and strain fields of healthy and myelopathic cervical spinal cord[END_REF][START_REF] Yuan | In vivo human cervical spinal cord deformation and displacement in flexion[END_REF] , respectively.

22

In this study, based on 3D MR acquisitions in healthy subjects in both neutral supine and flexion, we propose 23 a new methodology to characterize and to quantify the morphology of the CSS and the cervical SC in 3D for 24 healthy subjects in both neutral supine and flexion. This approach aims at providing accurate and detailed 25 morphological data (cross-sectional area, eccentricity indices, and displacements of the cord and canal) in order 26 to have a deeper understanding of the impact of the flexion in the cervical canal.

Method

MRI acquisition 30

Eleven european healthy subjects (5 females and 6 males, mean age : 30 +/-6y, BMI : 23.86 +/-1.78 31 kg/m²) were scanned using a 3T MR system (Siemens Healthineers, Erlangen, France) equipped with head, 32 neck and spine coils. Subjects were first examined with the neck in neutral and flexion positions, using a

39

Segmentation and anatomical markers

Morphological parameters were computed from anatomical markers and centerline coordinates in less than 56 10 s per subject (Dell Latitude 7480, Intel® Core™ i7-7600U CPU -2.80GHz/2.90GHz, RAM : 8Go).

57

The boundaries of the SC and the canal were interpolated as the intersection [START_REF] Tropp | A fast triangle to triangle intersection test for collision detection[END_REF] of the surface meshes and 58 meshed planes orthogonal to the centerline [Fig. 2-c] using 3D splines. Then, the CSA of the SC, canal and 59 CSS (𝐶𝑆𝐴 𝑆𝐶 , 𝐶𝑆𝐴 𝑐𝑎𝑛𝑎𝑙 , 𝐶𝑆𝐴 𝐶𝑆𝑆 , respectively) were computed (see [1]).

60

The cord transverse and antero-posterior diameters (ØT 𝑆𝐶 , ØAP 𝑆𝐶 respectively), as well as distance 61 between the SC and the canal in anterior (A), posterior (P), right (R) and left (L) directions were computed 62 from the most eccentrical points in AP (4) and LR (5) directions. Compression (CR -2) and occupation (OR -63 3) ratios, as well as eccentricity indices were then derived from these metrics [START_REF] Tykocki | Correlation between the severity of myelopathy and cervical morphometric parameters on dynamic magnetic resonance imaging[END_REF] (see [2] to [5]).

64

𝐶𝑆𝐴 𝐶𝑆𝑆 = 𝐶𝑆𝐴 𝑐𝑎𝑛𝑎𝑙 -𝐶𝑆𝐴 𝑆𝐶 (1) 65

𝐶𝑅 = ØAP 𝑆𝐶 ØT 𝑆𝐶 (2)
66

𝑂𝑅 = 𝐶𝑆𝐴 𝑆𝐶 𝐶𝑆𝐴 𝑐𝑎𝑛𝑎𝑙 (3)

71

Three specific lengths were also computed in both positions [START_REF] Jha | Kinetic change of spinal cord compression on flexion-extension magnetic resonance imaging in cervical spine[END_REF][START_REF] Endo | Kinematic Analysis of the Cervical Cord and Cervical Canal by Dynamic Neck Motion[END_REF]

Results

96

Segmentation and inter-operator reliability 97

The maximum error value between manual and automatic canal CSA measurements was found for the 98 C2 dens reaching 25.06% while for the others cervical levels, the canal CSA relative errors reminded lower 99 than 18%. The standard deviation was steady around 15% [Tab. 5 -Supplemental Digital Content].

100

The maximal distance, when considering inter-operator differences, was found of 2.

Cervical subarachnoid space (CSS) and spinal cord (SC) in the canal

108

Cross-sectional areas and occupational ratio 109

The mean 𝐶𝑆𝐴 𝐶𝑆𝑆 evolution along the canal after normalization in abscissa is depicted [Fig. 2]. The abscissa represents the averaged distances of each "cervical vertebral landmarks" from the top "reference 111 landmarks" for all the subjects normalized using :

123

The mean of 𝐶𝑆𝐴 𝑆𝐶 for both postures is given on [Fig. 5]. In flexion, it was systematically lower than in 124 neutral position and differences were found significant (p<0.05) for all local locations (see [Tab. 4]).

125

The mean OR increased from C2 dens to C2 inferior endplate for the both neutral and flexion postures 126 (from 0.18 to 0.32 and 0.19 to 0.32, respectively). After the superior C3 endplate (0.33 -neutral ; 0.35 -127 flexion), the flexion OR decreases faster than in neutral position with an oscillating behavior until the C7 128 inferior vertebrate endplate (0.31 -neutral ; 0.22 -flexion). Large standard deviations could be noticed (± 8-129 30% -neutral ; ± 13-45% -flexion) [Fig. 2]. OR differences between both postures were found significant 130 (p<0.05) for C1-C2, C5, C6, C7 described in (cf. [Tab. 4 -Supplemental Digital Content]).

Eccentricity indices and compression ratio 132

The mean AP and LR eccentricity indices, as well as the CR index along the normalized length of the canal 133 are depicted [Fig. 3]. The first tenth of the presented curves (0 to 0.1 in abscissa) will not be considered in further analysis because of the difficulty of the post-processing algorithm (section 2.3) to be efficient with 135 the small complex geometry of the subarachnoid space (cisterna magna/pontis/interpeduncularis, medulla 136 oblongata) between the foramen magnum and the C2 dens.

137

Between the C2 dens and the inferior C2 endplate, the 𝐴𝑃 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 index decreased steadily with the 138 same behavior for both neutral and flexion postures (from 52% to -22% and 58% to -24%, respectively). After Thirdly, the high reduction of 𝐶𝑆𝐴 𝐶𝑆𝑆 from C2 dens to C3 vertebra in flexion position compared to the 178 neutral one appears to be induced by the high mobility of the upper cervical segment [START_REF] Nightingale | Comparative strengths and structural properties of the upper and lower cervical spine in flexion and extension[END_REF] . After the C3 179 vertebra, the 𝐶𝑆𝐴 𝑆𝐶 was globally steady while the 𝐶𝑆𝐴 𝐶𝑆𝑆 decreased. In addition, the action of the yellow 180 and posterior longitudinal ligaments inside the vertebral should be noticed [START_REF] Johnson | Some new observations on the functional anatomy of the lower cervical spine[END_REF] while explaining the CSS 181 modification [START_REF] Holmes | Changes in Cervical Canal Spinal Volume During In Vitro Flexion-Extension[END_REF] .

182

Toward cord and spine biomechanical description 183

The geometrical evolution described by the CR index was intrinsically linked to the mechanical 184 properties of the spinal cord. Indeed, the decrease of the CR from C4 to C6 observed in flexion depicts a 185 significant strain of the SC from 3% to 7%. Such results underline the "stretching" phenomenon previously 186 mentioned. This is further confirmed by the 13% increase of the LSC in flexion, in line with literature [START_REF] Smith | Association of Myelopathy Scores With Cervical Sagittal Balance and Normalized Spinal Cord Volume: Analysis of 56 Preoperative Cases From the AOSpine North America Myelopathy Study[END_REF][START_REF] Kuwazawa | The Length of the Cervical Cord: Effects of Postural Changes in Healthy Volunteers Using Positional Magnetic Resonance Imaging[END_REF][START_REF] Endo | Kinematic Analysis of the Cervical Cord and Cervical Canal by Dynamic Neck Motion[END_REF][START_REF] Hu | Pathological changes of cervical spinal canal in cervical spondylotic myelopathy: A retrospective study on 39 cases[END_REF] .

187

The "stretching" phenomenon results from the the Poisson effect described as the amount of lateral 188 contraction against the amount of axial elongation experienced by a material under the action of a force.

203

Clinical aspects 204

In this study, we presented ten morphological parameters were used to describe the postural 205 modifications occurring in the canal. These parameters were chosen in relation to their use in a clinical 206 research context. Indeed, transverse area criteria corresponding to our 𝐶𝑆𝐴 𝑆𝐶 , 𝐶𝑆𝐴 𝐶𝑆𝑆 , 𝐶𝑆𝐴 𝐶𝑎𝑛𝑎𝑙 ,

207

ØT 𝑆𝐶 , ØAP 𝑆𝐶 and CR, are used for CSM description [START_REF] Bilston | The biomechanics of the spinal cord during traumatic spinal cord injury[END_REF][START_REF] Bilston | Biomechanics of cervical spinal cord injury in flexion and extension: A physical model to estimate spinal cord deformations[END_REF] . CSM, disc herniation, osteophytes (bony outgrowth) 208 can also cause reduction of the canal and an occupation ratio (sagittal diameters ratio of spinal cord over 209 canal, or ratio of spinal cord over canal area corresponding to our OR index) could be useful to quantify the 210 degree of compression [START_REF] Sun | Analysis of the Correlation Between Cerebrospinal Fluid Space and Outcomes of Anterior Controllable Antedisplacement and Fusion for Cervical Myelopathy Due to Ossification of the Posterior Longitudinal Ligament[END_REF][START_REF] Pratali | A Technique for Dynamic Cervical Magnetic Resonance Imaging Applied to Cervical Spondylotic Myelopathy: A Reliability Study[END_REF] . Moreover, additional parameters related to the location of the spinal cord in the

221

The second limitation is the ambiguous difference between displacements and elongation of the SC in 222 the CSS, which will be confirmed in the future by refine MR acquisition of head neck at 7T in order to enable 223 a more precise localization of the nerve roots along the CSS, in complement to description already provided 224 at 3T [START_REF] Cadotte | Characterizing the location of spinal and vertebral levels in the human cervical spinal cord[END_REF] .

225

The last limitation of our methodological work is the small amount of subjects currently included and the 226 lack of symptomatic subjects. Future investigations and multicentric studies could complete this work to 227 turn it into normative database adapted to a clinical routine. 228

Conclusion

CSA SC [mm2]

CSA

Supplemental Digital Content Table 5 : table of CSA relative error [%] between manual and automatic CSA measurements for

5 subjects randomly selected. Mean and standard deviation were computed by averaging all subjects for seven levels along the cervical spine.

1 Magnetic

 1 Resonance Imaging (MRI) has become a gold standard method to understand different 2 physiological mechanisms of the spine. In the context of degenerative process, Kinematic MRI (kMRI), or postural 3 MRI, which refers to imaging of the spine at different neck positions, is largely used to diagnosis position-4 dependent alterations that could not be detected in normal posture. It is mostly applied qualitatively to visualize 5 cervical canal narrowing or spinal impingement by degenerated disk in flexion for instance, however little is 6 known concerning the dynamical changes occurring at the level of the healthy cervical subarachnoid space(CSS)7 and spinal cord (SC) tissues.

8

 8

33 dedicated

 33 homemade device (device flexion up to 40°). Images were acquired using a sagittal 3D T2-SPACE 34 sequence (Sampling Perfection with Application optimized Contrasts using different flip angle Evolution) 35 with the following parameters: voxel size (1x1x1 mm 3 ), field-of-view (256x256 mm 2 ), echo time (TE : 124 36 ms), repetition time (TR : 1500 ms,) , total acquisition time (6 min). The MR protocol was approved by the 37 institutional ethics committee and all subjects signed the informed consents. The cohort was chosen 38 excluding history, presence of cervical pathologies or deformations.

An

  𝐴𝑃 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 > 0 (<0) indicates that the SC is anteriorly (posteriorly) positioned.70Similarly, a 𝐿𝑅 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 > 0 (<0) indicates that the SC is located on the right (left) side of the canal.

29 mm 101 (

 101 corresponding to an error of two 1 mm-isotropic voxels) in neutral position and 4.29 mm (ie. 4 voxels) in 102 neutral position and 3.62 mm (ie. 4 voxels) in flexion. 103 Consequences of inter/intra-operator differences in landmarks positioning were additionally assessed 104 on four metrics (𝐶𝑆𝐴 𝑆𝐶 , 𝐶𝑆𝐴 𝐶𝑆𝑆 , 𝐴𝑃 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 and 𝐿𝑅 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 ). The first tenth of the cervical segment (C1-105 C2 functional unit) presented high variability (gray zone [Tab. 1]), whereas mean differences were less than 106 5% of the measured values otherwise, except for the 𝐶𝑆𝐴 𝐶𝑆𝑆 (inter-operator mean relative error of 7.5%).

  Y : the normalized vector of the abscissa.

116X

  : the vector of mean values of the distances on the centerline from the top projected "reference 117 landmark" to the projected "cervical vertebral landmark".

  from C2 dens to C2 inferior endplate (from 481.6 mm 2 to 177.5 mm 2 in neutral 120 position ; 379.8 mm 2 to 157.9 mm 2 in flexion), with minimal values around C3, followed by a low increasing 121 and oscillating phase to reach 157 mm 2 in neutral and 164 mm 2 in flexion. CSA differences between both 122 postures were found significant (p<0.05) for C1-C2, C5, C6, C7 described in (cf.[Tab. 4]).

  139the C3 superior endplate, mean 𝐴𝑃 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 index in neutral was systematically lower than in flexion 140 position. [Fig.3-Top]. Differences between both postures were found significant (p<0.05) for C1-C2, C5, C6, 141 C7 described in (cf.[Tab. 4]). 142 The 𝐿𝑅 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 index constantly oscillated around 0% and 8% respectively in neutral and flexion neck 143 postures respectively [Fig.3-Middle]. No significant difference in 𝐿𝑅 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 index between the postures 144 was found (0.08 < p <0.97 ) except for the vertebral level C1-C2 (cf. [Tab. 04]). 145 The CR index decreased steadily between C2 dens and to C7 inferior endplate for both posture. The CR 146 for the flexion case was systematically lower than in neutral position, except along the C3 vertebra [Fig. 3-147 Bottom]. CR differences between neutral and flexion neck postures were significant (p<0.05) locally for the 148 vertebral levels C4, C5, C6 and for the mid-levels of intervertebral discs values of C4/C5 to C6/C7 [Tab. 04]. 149 Anterior/Posterior columns and of the spinal cord 150 The mean length values were measured equal to 118 ± 5 mm and 120.3±7.6 mm for LAC, 107±6 and 151 120.4±6.4 mm for LPC, 142±7 mm and 159.4 ± 11.5 mm for LSC in neutral and flexion neck postures, 152 respectively, with significant differences between both the postures in each case (p<0.05) [Fig. 4, Tab. 4]. 153 4. Discussion 154 This study proposes a new approach to collect detailed anatomical measurements of the cervical canal. 155 Using MRI segmented 3D geometrical reconstructions, it was possible to investigate the morphological 156 changes between neutral supine and neck-flexion positions. Different geometrical metrics (CSA, eccentricity 157 indices, ratios) related to the SC and the CSS could be derived. The most noticeable results are summarized 158 in [Tab. 3]. 159 Cord and CSS kinematical description 160 Firstly, the low oscillating behavior of 𝐶𝑆𝐴 𝐶𝑆𝑆 and OR indices along the spinal segment in [Fig. 2,3] 161 describes the geometry of dura mater at each spine level : nerve root funnel-shaped lateral extensions of sheaths leave the dura mater as spinal ganglions toward the peripheral nervous system 22 , hence including 163 pseudo-periodic fluctuations in the CSS outer border. 164 Secondly, the kinematic of the cord is not only induced by the flexion itself but also by the surrounding 165 structures. The spinal cord being fixed to the superior anatomical structures (pons, medulla) on one hand 166 and to the filum terminale on the other hand, it is subject to tensile forces applied in both cranio-caudal and 167 antero-posterior directions when flexed. Previous studies reported up to 2-mm displacements of the 168 medulla oblongata and the pons in flexion 23 . Here a "stretching" phenomenon (+13% for LSC in flexion with 169 respect to neutral position, after C2 endplate) occurs while the SC is pull through the anterior side of the 170 spine column, as reflected by the 𝐴𝑃 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 and 𝐿𝑅 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 [Fig 3-a,b]. The nerve roots attached in the 171 dural sheaths could be limiting the longitudinal motion and allow an elongation that follows the spinal 172 motion. The SC lateral position stays globally centered (slight shift on the left : 2-3% from the center of the the SC dorsal and ventral side by pairs and exiting the CSS by the dural sheath, insure coronal stabilization 176 of the SC.

  177

189

  The three OR, CP, and LSC metrics could overcome the current lack of mechanical characterization and could 190 be used for biomechanical modeling validation. Such Poisson effect can induce some local stresses or damages in the structure near the zone where the cord is attached, namely nerve roots and denticulate 192 ligaments[START_REF] Hu | Pathological changes of cervical spinal canal in cervical spondylotic myelopathy: A retrospective study on 39 cases[END_REF] .193The LAC and LPC values (respectively +2% and +12% in flexion) are also in line with literature[START_REF] Jha | Kinetic change of spinal cord compression on flexion-extension magnetic resonance imaging in cervical spine[END_REF] 194(respectively 5% and 8%). The LSC metric in comparison to LAC and LPC ones shows that the SC follows the 195 motion of the canal in freeing more space posteriorly in flexion (-22% < 𝐴𝑃 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 < 47%) than in neutral 196 position (-22% < 𝐴𝑃 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 < 7%) after C2 vertebra. Validation and further use of spine models, especially 197 with finite element modeling, require advanced knowledge of spinal cord interaction with surrounding 198 structures. Hence the data related to the location of the cord and its space distribution obtained in this study 199 could provide a strong added value for model design. In addition, spinal cord positioning and length 200 variations are also providing additional indirect information (based on Poisson ratio effects) to support 201 further modeling choices. Altogether, our study provide the necessary measurements [Tab. 4] in a healthy 202 adult population in physiologically conditions for such validation.

  211 canal (𝐴𝑃 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 and 𝐿𝑅 𝑒𝑐𝑐𝑒𝑛𝑡𝑖𝑐𝑖𝑡𝑦 indices) and the characteristic lengths (LSC, LAC, LPC) complete this 212 physiological database of healthy subjects that could now be used to compare with injured or symptomatic 213 subjects. This methodology and database open the perspective of more accurate clinical indices. 214 Limitations 215 (incompressibility), the fluid limits the effect of gravity in supine position.

229A

  new methodology allowing a detailed description of the vertebral canal morphology thanks to high 230 resolution 3T-kMRI was developed. It allowed characterizing the CSS dynamic behavior through 10 231 geometrical metrics. Reference values in healthy population are provided in [Tab. 4]. 232 The mechanical roles of the different structures inside the vertebral canal in flexion were also confirmed 233 through geometric measurements changes : 1) left-right stability (described by the LR eccentricity index) 234 ensured by the denticulate ligaments and the nerve roots attached to the dural sheaths, 2) a Poisson effect 235 of the SC was partially notified through its axial (AP diameter, OR, CR) and its longitudinal geometrical 236 description (LSC). Such morphological data can be useful for geometrical finite element modeling of the 237 canal in terms of boundaries or initial conditions or for an optimization of the mechanical properties by 238 geometrical sensitivity analysis. Confronting this methodology and these results in a further study with a 239 pathological cohort (CSM, post-traumatic population) is crucial to refine these clinical criteria in the medico-240 surgical management.

  passing through the ring of C1 vertebra), value picked up at the middle of the vertebra in the middle sagittal plan (MID VERT) and value picked up at the middle of the intervertebral disc in the middle sagittal plan (MID IVD) , considering the disc below the mentioned vertebral level). The LAC, LPC and LSC parameters correspond to the lengths of the anterior canal, posteriorcanal and the spinal cord, along the whole cervical segment, respectively. *indicates p<0.05 (Paired samples Wilcoxon test).

Figure 1 -

 1 Figure 1 -a) Sagittal view with superimposed 3D reconstruction of the SC (gold color) and the CSS (blue color) in flexion (left), and neutral (right) neck positions. The red dotted lines indicates the delimitation of the cervical segment (C1-C7) considered in this study. b) Main postprocessing steps, 3D reconstruction and 3D landmarks (left), orthogonal planes to the centerline all along the cervical segment (middle), boundaries points (zoom x5) extracted from the intersection between 3D reconstruction and the plane, with distance representations of eccentricity indices (A, P, L, R, ØAP, ØT) (right). c) As inJha et al. 20 , main steps to compute the length of the cervical spinal cord (LSC) attached to the caudal side of the pons in red, length of the cervical spinal anterior column (LAC) in yellow and length of the cervical spinal posterior column (LPC) in green (top : manual inputs, bottom : 3D-spline interpolation.

Figure 2 -

 2 Figure 2 -(Top) Mean Cross-Sectional Area (CSA, mm 2 ) along the normalized cervical spinal normalized (see section 3.2 -

Figure 3 -

 3 Figure 3 -AP (top) and LR (middle) eccentricity indices along the normalized cervical cord, together with the Compression Ratio index (bottom). For each subplot figure, the mean value of the neutral (blue continuous curve) and flexion (red continuous curve) cases are indicated with their standard deviations (dotted curves). Mean normalized positions of the vertebral endplates are indicated as well, standard deviations are not indicated on the figure for a sake of clarity.

Figure 4 -Supplemental Digital Content Figure 5 -

 45 Figure 4 -Boxplots of characteristics lengths in the cervical segment, a) Length of the Anterior Column (LAC), b) Length of the Posterior Column (LPC) c) Length of the Spinal Cord (LSC). On each box, the central mark indicates the median (red line), and the bottom and top edges of the box indicate the 25th and 75th percentiles (horizontal blue lines), respectively. The whiskers extend to the most extreme data points not considered outliers, and the outliers are plotted individually using the red '+' symbol (*p<0.05).

operator variability, intra-operator variability and statistical analyses process 78

	80	was provided in 5 subjects randomly selected [Tab. 1] to assess the accuracy of the semi-automatic
	81	segmentation. Additional information on the reliability of the SC segmentation and 𝐶𝑆𝐴 𝑆𝐶 can be found in
	82	literature 15 . Inter-(by 2 raters) and intra-operator (at 2 different time points -operator 1) variabilities of 3D
	83	reconstruction and landmarks positioning were also assessed reporting the Euclidian distance, mean relative
	84	error of the CSA (CSS, SC) and of the eccentricity indices (AP, LR) [Tab. 2].
	85	Three metric values were calculated at each vertebral level : spatial averaged value (over the whole
	86	vertebra) (AVD VERT), spatial value for a cross-sectional plane mid-vertebra (MID-VERT) and spatial value
	87	for cross-sectional plane located at the middle of the intervertebral disc (MID-IVD) (vertebral levels defined
	72	: the length of the cervical spinal cord
	73	(LSC), length of the cervical spinal anterior column (LAC) and length of the cervical spinal posterior column
	74	(LPC). They were respectively delimited by the caudal side of the pons to C7 inferior endplate, the C2 dens
	75	process to C7 inferior endplate, and the top of C1 posterior arch to C7 inferior endplate. Three 3D splines
	76	passing through the points positioned manually by an operator to define each curvature were computed to
		get more accurate lengths.
		The comparison between 𝐶𝑆𝐴 𝑐𝑎𝑛𝑎𝑙 measurements derived from ITK SNAP and manual segmentation

77

Inter-as the "cervical vertebral landmarks" projected onto the centerline). For both postures (neutral and flexion), 88 all values are reported as averaged value with standard deviation by vertebra and disc on all subjects. Mean 89 vertebral level positions across all subjects were computed from : the position of each vertebra according to 90 the "Reference landmarks" and "Cervical vertebral points" positions projected to the centerline. Statistical 91 comparisons between neutral and flexion measurements were performed using RStudio (© 2009-2018 92 RStudio, Inc. -Version 1.1.463). Due to the small number of samples, paired samples Wilcoxon tests (non-93 parametric test) were used. Significant differences were defined for p-values < 0.05 (noted * in the summary 94 results table [Tab. 4]).

95

Table 3 LegendsTable 1 :

 31 inter-and intra-mean relative errors for spinal cord ( SC) and Cervical Subarachnoid Space (CSS) CSA and Anteroposterior (AP) and Left -Right (LR) eccentricity indices. The averaged value, standard deviation, minimum and maximum averaged value on the 5 subjects randomly selected are described as : [Mean ± STD ; Min/Max]. The grey zones represent the first tenth of the measures along the cervical cord and the white zones represent the rest.

Table 2 :

 2 Distance errors (L2-norm in mm) per vertebra landmarks between operator 1 and the operator 2 (inter-operator

	variability), as well as between 2-measurements sessions by operator 1(intra-operator variability). For each cell, the results
	are presented as follow : [Mean ; Min/Max].

Table 3 :

 3 summary table of the main results for each index.

Supplemental Digital Content

Table 4 : statistical summary [Mean ± std (min/max)] of each measured parameter (SC and CSS CSA, OR, AP/LR eccentricity and CR) for both position (neutral in white, flexion in gray). For each one, three sub-values are given, corresponding to a spatial vertebral average of measures (AVD VERT, with C1 and C2 vertebrae merged : the C2 dens

Manuscript Text (must include page numbers)

The SC was first segmented in 3D by a semi-automatic approach using the Spinal Cord Toolbox (SCT,

3.1.1)[START_REF] De Leener | SCT: Spinal Cord Toolbox, an open-source software for processing spinal cord MRI data[END_REF] and providing SC centerline. The outer canal border, assumed as the dura mater, was then

segmented by a semi-automatic approach from ITK-SNAP software[START_REF] Yushkevich | User-guided 3D active contour segmentation of anatomical structures: Significantly improved efficiency and reliability[END_REF] . The 3D CSS was defined as the space 43 between the 3D canal segmentation and the 3D SC segmentation [Fig.1-a,b].

Eleven landmarks [Fig.1-b] were selected, by one operator on the middle slice of the sagittal view, using 3D

Slicer 4.8.1[START_REF] Kikinis | 3D Slicer: A Platform for Subject-Specific Image Analysis, Visualization, and Clinical Support[END_REF] for the delimitation of the segment of interest:

1) "Reference landmarks": at the top of the dens of C2 (axis) and at the posterior extremity of C7 inferior

endplate;

canal), in line with the literature[START_REF] Tykocki | Correlation between the severity of myelopathy and cervical morphometric parameters on dynamic magnetic resonance imaging[END_REF] , and similar in neutral and in flexion. Indeed, both denticulate ligaments24,

between the arachnoid (assumed to be stick to the dura mater) and the pia mater, and nerve roots leaving

The first limitation of our methodology is that the MR acquisitions were performed in supine position, 216 which is not a daily physiological posture. A previous study showed no significant difference of the spinal 217 cord length between erect and supine position[START_REF] Kuwazawa | The Length of the Cervical Cord: Effects of Postural Changes in Healthy Volunteers Using Positional Magnetic Resonance Imaging[END_REF] . However, with cervical lordosis changes, a slight difference 218 between erect and supine position is expected for SC position in the CSS and eccentricity indices.

Acknowledgments

This work was supported by CARNOT STAR Institute, CNRS (Centre National de la Recherche Scientifique) and by Aix-Marseille University. This work was performed within a laboratory member of France Life Imaging network (grant ANR-11-INBS-0006). The authors would like to thank Lauriane Pini, Véronique Derderian, and Claire Costes for MR study logistics, as well as Amira Trabelsi and Yvan Petit for helpfull discussions.

Abbreviations