Christopher Vautrin

Daniel Lacour

Coriolan Tiusan
email: coriolan.tiusan@phys.utcluj.ro

Yuan Lu

François Montaigne

Mairbek Chshiev

Wolfgang Weber

Michel Hehn
email: michel.hehn@univ-lorraine.fr

Wall Racetrack Memory

Masamitsu Stuart S P Parkin

Jacob Torrejon

Flavio Mathieu Riou

Abreu Araujo

Sumito Tsunegi

Guru Khalsa

Damien Querlioz

Paolo Bortolotti

Vincent Cros

Kay Yakushiji

D Valenzuela

C H Makarov

E E Marrows

P Fullerton

Fischer

Low-energy spin precession in the molecular field of a magnetic thin film

Electronic spin precession and filtering are measured in the molecular field of magnetic thin films. The conducted lab-on-chip experiments allow injection of electrons with energies between 0.8 and 1.1 eV, an energy range never explored up to now in spin precession experiments. While filtering angles agree with previous reported values measured at much higher electron energies, spin precession angles of 2.5° in CoFe and 0.7° in Co per nanometer film thickness could be measured which are 30 times smaller than those previously measured at 7 eV. Band structure effects and layer roughness are responsible for these small precession angle values.

Since the discovery of Giant Magneto-Resistance (GMR) in 1988 1,2 the Spintronics research field has become the ground of intense investigations. Accompanying the growth of fundamental knowledge on spin transport in solid-state devices, numerous proposals for applications have emerged (see for instance 3 and 4 ). Among those, some have already hit the market as hard drive read heads, magnetic fields sensors and spin transfer torque based magnetic random access memories (STT-MRAMs). Despite the apparent maturity of the field, fundamental points remain to be clarified 5 . In particular, very little is known about the electronic spin behavior in its out-of-equilibrium state (i.e. beyond the Fermi sea) even if it is acknowledged to be a source of spin-transfer torque 6 .

When a beam of electrons with an initial spin polarization vector 𝑷 𝟎 is injected into a region of space where a magnetic field 𝑯 is present, the polarization vector 𝑷 will exhibit a precessional motion around the magnetic field. Two angles can then be defined: the filtering angle, 𝜃, that describes the reorientation of 𝑷 towards 𝑯 and the precession angle, 𝜀, that describes the precession of 𝑷 around 𝑯 (figure 1 in which the blue arrow is the field 𝑯). The precession frequency is given by the Larmor frequency 𝜔 = 𝛾 𝐻 with 𝛾 ≃ 1,7 ⋅ 10 rad s T the gyromagnetic ratio. If the incident polarized electrons are considered to move at a typical speed of 2 ⋅ 10 ms (close to the Fermi velocity of many metallic elements), a precession angle per µm and per Tesla, 𝜀, of about 0,17 rad T μm is expected. Large precession angles can thus be achieved either by a short travel distance in a strong magnetic field or by a long travel distance in a small magnetic field. This latter scheme was used in metals by Jedema et al 7 as well as in semiconductors by I. Appelbaum et al 8 and by D. D. Awschalom et al 9 , while the first strategy was employed by Oberli et al 10 in their free-electron beam experiments. By injecting a spin polarized electron beam into a magnetic layer, the so-called molecular field of a ferromagnetic layer is estimated to be of the order of several 100 T to 1000 T. Oberli et al achieved experimentally precession angles of several tens of degrees per nanometer. Unfortunately, measurements with a free electron beam at electron energies (with respect to the Fermi level) below the vacuum level (4-5 eV for ferromagnetic metals, such as Co and Fe) are not possible. However, this is exactly the energy range of interest for all spintronics applications (typical bias voltages applied to tunnel junctions are 1 to 2 V). Therefore, we have conducted lab-on-chip experiments allowing us to measure at these low energies the spin precession induced by the molecular field of thin ferromagnetic layers. Three elements are essential to perform such experiments: a spin polarizing layer, an active precession layer and an analyzing layer. In order to study the dependence of the precession angle as a function of electron energy, the lab-on-chip has to host an electronic device that allows varying the injection energy of the electrons. In this work the electron injection is accomplished by a magnetic tunnel junction (figure 2). After having aligned the spin polarization of the injected electrons within the polarizing layer along its magnetization direction, the electrons are transported via the tunnel effect through the MgO barrier. As the tunnel transport is spin conservative, the spin polarization of the electrons arriving in the active layer is perpendicular to the active's layer magnetization direction and will consequently precess around it during the electron's propagation. Changing the bias voltage across the tunnel barrier varies the injection energy in the active layer and thus allows a spectroscopic analysis of the precession angle. This angle is analyzed through the GMR effect occurring in the active layer / Cu / analyzer spin valve (blue/orange/green rectangles in Figure 2). Note that the analyzer magnetization is orthogonal to the magnetization of both the active and the polarizing layers. Finally, one last key ingredient to the precession angle analysis is a Schottky diode (figure 2). It allows a dual analysis. First of all, it ensures that the collected electrons in the semiconductor have always an energy higher than 0.7 eV (the height of the Schottky barrier) after having passed the spin valve. Thus, only the spin precession of hot electrons is analyzed, while all thermalized electrons are reinjected by the tunnel barrier through the spinvalve's electron recovery circuit. Second, it defines an acceptance cone with an opening angle θc of only 4.5° at E = 1 eV at the Schottky interface due to the conservation of the momentum parallel to the Cu/Si interface (see additional material). This angular wave vector filtering effect is reinforced by another angular filtering taking place during the tunnelling process. Thus, for an injection energy of around 0.7 eV, the collected electrons in silicon have been transported across the spin valve in an almost ballistic manner and practically perpendicular with respect to the multilayer interfaces. The multilayer is grown by sputtering on a HF cleaned Si substrate (see method section for supplementary details). The CoFeB layer is the polarizer and X is the active layer. The [Ni(0.6)/Co(0.2)]x5/Ni(0.6) multilayer represents the analyzer. To determine a precession angle in our lab-on-chip experiment it is required to stabilize the aforementioned threedimensional magnetic configuration. The way to obtain a crossed configuration of spin valve magnetizations has been reported in a previous study11 . The crossed configuration in the Pt/IrMn/Co/Ta/CoFeB/MgO/X(y) tunnel junction is obtained by establishing an exchange bias field at the IrMn/Co interface to set the magnetization easy axis of the polarizer along the xdirection. The multilayer deposition is followed by an annealing process under an applied field to initiate the exchange bias field and by four steps of optical lithography to define the electrical contacts on the different layers of interest (see method section for supplementary details).

The collected hot electron current 𝐼 can be expressed as 𝐼 = 𝐼 (1 + 𝑀𝐶 𝑷 • 𝑴 𝑨𝒏 ) where 𝑷 is the hot electron spin polarization vector after propagation through the active layer and 𝑴 𝑨𝒏 indicates a unit vector pointing along the magnetization direction of the analyzer 12 . 𝑀𝐶 is the magneto-current ratio defined as ∥ where is 𝐼 ∥ and 𝐼 are the collected currents when 𝑷 and 𝑴 𝑨𝒏 are parallel or perpendicular to each other, respectively. Since we plan a spectroscopic analysis, the tunnel junction bias voltage (V E ) will be changed and so will the injected current. It is then convenient to normalize the collected current by the injected one. This defines the transfer ratio as: 𝑇𝑅 = 𝑇𝑅 (1 + 𝑀𝐶 𝑷 • 𝑴 𝑨𝒏 ) , which could also be expressed as 𝑇𝑅 [1 + 𝑀𝐶 𝑃 𝑐𝑜𝑠 (𝜃) 𝑠𝑖𝑛(𝜀)]. The 𝑐𝑜𝑠 (𝜃) 𝑠𝑖𝑛(𝜀) product containing our angles of interest can thus be nicely obtained experimentally by measuring the transfer ratio in three different magnetic configurations: parallel ∥13 , clock wise ↻ and counter clock wise ↺ as illustrated in figure 1. The three transfer ratios 𝑇𝑅 ∥ , 𝑇𝑅 ↻ and 𝑇𝑅 ↺ , can be expressed as 𝑇𝑅 ∥ = 𝑇𝑅 1 + 𝑀𝐶 𝑃 and 𝑇𝑅 ↻/↺ = 𝑇𝑅 [1 ± 𝑀𝐶 𝑃 𝑐𝑜𝑠 (𝜃) 𝑠𝑖𝑛(𝜀)]. As a result, the 𝑠𝑖𝑛(𝜀) 𝑐𝑜𝑠 (𝜃) product as a function of experimentally available quantities writes as:

𝑠𝑖𝑛(𝜀) 𝑐𝑜𝑠 (𝜃) = ↻ ↺ ∥ ( ↻ ↺ )
.

Measurements of the three aforementioned 𝑇𝑅 vs. V E performed on the sample having an active layer composed of a 1 nm thick CoFeB film are reported in figure 3a. They provide clear evidence of a precessional effect in the CoFeB layer since 𝑇𝑅 ↻ and 𝑇𝑅 ↺ are not superimposed. Precession angles 𝜀 obtained for different filtering angles 𝜃 ranging from 0 ° to 85 ° are shown in figure 3b. One must note that the obtained values are always smaller than the ones reported by Weber et al14 and this even if strong filtering effects are considered. Increasing 𝜃 towards 90 ° naturally increases 𝜀 towards Weber's values but such a high spin filtering effect is not expected for such a thin magnetic layer. In order to determine 𝜀, the determination of 𝜃 is mandatory. Quantitative values are obtained by varying the active precession layer thickness and taking into account that electrons overcoming the Schottky barrier have 𝑘 ⃗ ∕∕ = 0 ⃗ (see additional material). In this case, the distance traveled by the electrons equals the thickness d of the active magnetic layer. Since the hot electron current is exponentially decreasing as a function of d (see additional material), the 𝑠𝑖𝑛(𝜀) 𝑐𝑜𝑠 (𝜃) product can be rewritten as:

𝑠𝑖𝑛(𝜀) 𝑐𝑜𝑠(𝜃) = sin( * d) 𝑐𝑜𝑠ℎ ( 𝜆 -) ,
where  * is the precession angle per nanometer and = ↓ -↑ (𝜆 ↓↑ being the minority/majority inelastic electron mean free paths).

Fits of the 𝑠𝑖𝑛(𝜀) 𝑐𝑜𝑠(𝜃) product vs. d (reported in additional material) allows then the extraction of  * and λ as a function of hot electron energy. Precession was studied in two ferromagnetic layers, Co and CoFeB. These two materials have been chosen for the good quality of the tunnel barriers that can be achieved when the MgO is deposited on top. The thicknesses of the active layer were varied between 1 and 10 nm. As both  * and λ are mostly constant over the energy window studied, their mean values are presented in table 1 for comparison to reported values. The surprise of our study relies on the values of the precession angle. Since no other data are available in this low energy range (E F +1eV), we can only compare with the work of Weber et al. which has been performed with the same material (Co) but at a much higher electron energy (E F +7eV): the precession angle per nanometer is 30 times smaller at E F +1eV than at E F +7eV. By changing the active layer material to CoFeB, i.e. Co is partly replaced by Fe, we find in our lab-on-chip experiments an increase of the precession angle by a factor of 3.5. This tendency seems to be followed in the free electron beam experiments at higher electron energy when going from Co to Fe. sin ().cos () When a spin-polarized electron beam is injected into a region of space where a perpendicular magnetization exists, the precession of the spin-polarization vector is theoretically given by  * (𝐸) = ∆𝑘 where ∆𝑘 = 𝑘 ↑ -𝑘 ↓ is the difference in 𝑘-vector for both spin bands at energy E (see additional material). When only the spin-up band is accessible as for instance in figure 4a at energies below 0.7 eV we have ∆𝑘 = 𝑘 ↑ (see additional material). As a result, the value of  * should be strongly dependent on the spin-dependent band structure of the active layer. Ab initio calculations have been performed to get the band structure of CoFe(100) in the  direction (figure 4a) that allows the determination of  * (figure 4b). At energies above 1.95 eV, the two spin bands are accessible and increasing the energy

Results comparison table

 * 2.4° nm -1 0.7° nm -1 19° nm -1 33° nm -1 𝜆 0.
V E (V) 0 0,2 0,4 0,6 0,8 1 1,2 1,4 1,6 1,8 2 Roughness (nm) c Ab Initio.   = 65 (E-E F ) + 720

𝑑𝑡

The experimental values of 𝑠𝑖𝑛(𝜀)𝑐𝑜𝑠(𝜃) could be reproduced with ∆𝑑 = 0.4 nm (figure 4c).

This difference in travel distance cannot be related to specular electron travelling: it would correspond to an angle of 44.4°, which is completely out of the acceptance cone. However, a layer roughness of 0.4 nm is reasonable and can be considered as being constant as a function of layer thickness. The mean values of 𝑠𝑖𝑛(𝜀)𝑐𝑜𝑠(𝜃) can then be calculated as a function of 𝑑 and injection energy with a fixed value of ∆𝑑 = 0.4 nm. Oscillations could be calculated that are in agreement with our experimental results as seen in figure 4d. Furthermore, even if a strong variation of  * is expected theoretically with energy, the theoretical mean values 𝑠𝑖𝑛(𝜀)𝑐𝑜𝑠(𝜃) are almost constant as observed experimentally.

In conclusion, we show for the first time the manipulation of the spin direction in an unexplored energies range thanks to an all solid-state device. As forecasted theoretically,  * is huge and requires, to be usable, a better control of the active layer roughness. This result is the starting point for new studies in which materials, crystallographic orientations, band structure are parameters that can affect precession and pave the way for exploration of far richer spin transport properties than the one at high energies. arriving at the Cu/Si interface at an angle to the normal at the interface of less than 4.5° can pass into the Silicon.

Experimental measurements

All the measurements reported in the paper have been performed at 60 K. Indeed, it is known that at low temperatures, less than 50K, electrons trapping effects at the Cu/Si interface have been identified in the past by our group in samples made using the same chemical process to clean the Si surface and with the same deposition conditions of the Cu layer [START_REF] Lu | Interfacial Trapping for Hot Electron Injection in Silicon[END_REF]Lu14]. On the other hand, at high temperatures, Schottky barrier could be leaky. In order to check those spurious effects, we have measured the transport properties of a structure that comes as close as possible to the one studied in this paper. The magneto transport-and the characteristics of the Schottky barrier have been measured at the same time in a Pt 𝑀𝐶 is defined as in the paper. It is the magneto-current ratio defined as ∥ where 𝐼 ∥ and 𝐼 are the collected currents when the magnetization of Co and Co/Ni are parallel or perpendicular to each other, respectively. The effective Schottky conductance is defined as measured for V E less than 100 mV. We can clearly see that for temperatures below 250 K, the effective Schottky conductance is zero and so the Schottky diode is not leaking. Above 250 K, regardless of the magnetic configuration of the spin valve, the energy barrier continues to play its role as a filter of hot electron energy but a current of thermalized electrons is added to this electron current such that the MC decreases. Thus, the measurement of the hot electrons current is no longer reliable. For temperatures less than 50K, the MC also decreases which is a sign of charge trapping as reported previously [START_REF] Lu | Interfacial Trapping for Hot Electron Injection in Silicon[END_REF]Lu14].

Conclusions

Thus, for an energy injection around 0.7 eV, the electrons that will be measured in the silicon will have passed through the spin valve in an almost ballistic manner. The hot electrons current measurements are reliable for temperatures between 50 and 250 K.

2-Emission cone: the tunnel junction emits electrons with k-vector mainly perpendicular to the interface

As it will be discussed in the next section, when electrons are injected from a magnetic tunnel junction [Man08], the probability of injection depends on the k-vector direction. In the simplest model, the highest injection probability occurs when the k-vector is perpendicular to the barrier interface. As a result, k-vector selection is done by the tunnel barrier [Man08] and an emission cone exists.

Discussion on the 𝒌 ∕∕ = 𝟎 hypothesis

It is well known in solid state physics that when an electron moves through a material, it interacts not only with other electrons in the material but also with pseudoparticles such as phonons and magnons. The higher the energy of the electrons, the more electron-electron interaction dominates scattering processes. This makes an essential difference between our lab-on-chip experiments and the free-electron beam experiments of W. Weber et al: in our measurements, for electrons with low energies of around E F +1eV, all types of interaction have to be considered. This is shown in following figure. Nechaev's calculations show that the mean free path of spin up electrons is overestimated with respect to experimental values (blue triangles) at low energies if only electron-electron interaction is taken into account ( [Nec10], dark blue curve in the figure). By including an interaction with pseudoparticles (phonons and/or magnons) with a typical energy of 50 meV, the mean free path values are close to those measured experimentally (cyan blue curve in the figure). In the case of spin down electrons (red line and triangles) the agreement between theory and experiment is already quite good without the inclusion of the interaction of the electrons with pseudoparticles. In fact, for spin down electrons the electron-electron interaction is so strong that it overwhelms completely other possible types of interaction. Thus, electron-electron, electron-phonon and electron-magnon interactions have to be considered in general. The question is now to what extent these interactions can modify the electron trajectory and in particular the distance travelled by the electrons in the active layer. In any case, the relevant interaction, i.e. the interaction that influences the electrons which pass the Schottky barrier, must be elastic or quasi-elastic (energy filtering of the Schottky barrier) and the electrons must impact the Schottky barrier with a small 𝑘 ⃗ ∕∕ to be within the acceptance cone with a cone angle of 4,2 o . . Blue curve: mean free path of spin up electrons by only considering electron-electron interaction; Red curve : mean free path of spin down electrons by only considering electron-electron interaction; Blue cyan curve: mean free path of spin up electrons by adding an interaction with a particle with 50meV energy; Blue triangles: mean free path of spin up electrons measured experimentally; Red triangles: mean free path of spin down electrons measured experimentally.

 electron-electron interaction

For electron-electron interaction processes, Fermi's liquid theory predicts that a hot electron will lose half of its energy, the other half allowing a Fermi-level electron to become a hot one. Thus, this interaction is extremely inelastic and electrons that have undergone such an interaction will not be collected in the Si and will thus not participate in the detected current. As a result, electron-electron interaction exists in the range of energy but the electrons that experience an interaction with another electron will not contribute to the hot electron current.

 electron-phonon interaction

The process of electron-phonon interaction is indeed quasi-elastic but leads to electronic backscattering because of the strong wavevector change. Thus, the electron returns to its emission zone, i.e. the tunnel junction. It will be reflected there and will return towards the Schottky barrier. Thus, electrons subjected to an interaction with phonons will pass at least 3 times through the active precession layer. This will greatly increase their chance of losing energy (due to electron-electron interaction) and not being collected in the Si. We will thus consider that electron-phonon interaction is not relevant for the detected current.

 electron-magnon interaction

The electron-magnon interaction process is also quasi-elastic but leads to a spin flip of the electron spin. When a spin-flip occurs in a layer where the magnetization is perpendicular to the spin, the spin-flip process leads to a reorientation of the spin along the magnetization direction and thus to an additional spin-filtering process. However, when we compared our

 (nm) E-E F (eV)
values for the spin filtering angle with those measured at higher energies, we did not notice a big difference. Thus, electron-magnon scattering is not believed to be relevant in our experiments.

In conclusion, none of the hot electron interaction processes alone seems to explain the small precession angle values estimated using our measurements. We can then evoke classical decoherence effects of our electron beam.

Classical decoherence

The depth dependence of absorption of a spin current has been predicted for transverse spin currents in ferromagnetic layers. It arises from the transverse spin coherence length, which depends upon the Fermi surface integration. In spinvalve structures, for which integration has to be done over all k-vectors, the length scale is set to first order by [Zha04,Zwi05,Sti02,Car07,Wan08,Pet12] 𝜆 ~𝜋 |𝑘 ↑ -𝑘 ↓ | Theoretical estimations of this length scale in spinvalve structures yield 1 to 2nm, values that have also been confirmed experimentally [START_REF] Ghosh | Penetration Depth of Transverse Spin Current in Ultrathin Ferromagnets[END_REF]. As a result, the precession angle should average to zero if the thickness of the magnetic layer is larger than 2 nm (case a in next figure ). Things appear to be different when the electrons are injected from a magnetic tunnel junction ([Man08], [Chs15], case b in the figure). In this case, the transverse component of the spin density is damped by 50% within the first few nanometers. This decay length, evaluated to be 4 nm, is very large compared to previous theoretical predictions and experimental investigations on spinvalves. In the case of tunnel junctions, the averaging of torques will be less destructive than in metallic spin valves where all the Fermi surface is involved in the quantum interferences. This arises from the fact that 𝜆 has not to be integrated over all the k-vector direction since k-vector selection is done by the tunnel barrier [Man08].

In our case (case c in the figure), the injection of hot electrons is the one described in figure b but, though the use of the collecting Schottky barrier, the integration has to be done for kvectors in the acceptance cone θ C = 4.5°. The decay length over which average precession angle is zero is much longer than 4nm. Our experimental results suggest that it should be longer than 10nm.

Experimental measurements

From the experimental point of view, it is very difficult to test the existence of hot electron diffusion. For a given device, we can play with the temperature to activate diffusion and see if the collected current is strongly dependent on temperature. We have to keep in mind that temperatures only between 60 and 250 K are allowed to avoid spurious effects from the Schottky barrier (see section Emission and acceptance cones, energy filtering). Therefore, the transfer ratio has been measured as a function of temperature and injection energy in the configuration for which all the magnetizations are parallel. As can be seen in the following figure, the TR shows a variation of only 4% when the temperature varies from 60 to 100 K. Diffusion of the collected electrons is thus very limited.

Variation of filtering with thickness

As expected and reported in previous studies, the hot electron current decreases exponentially with the active layer thickness

𝐼 ↑(↓) ∝ 𝑒 ↑(↓)
where 𝜆 ↑(↓) are the thermalization length for spin up and spin down hot electrons. We have measured the transfer ratios (TR) as a function of precession layer thickness (in the following From this experimental result, we can rewrite the expression of the spin asymmetry as:

𝐴 = ↑ ↓ ↑ ↓ = 𝑡𝑎𝑛ℎ( ) with = ↓ -↑ .
The spin polarization after precession can then be expressed as: As a result, the experimental results are fitted by the relation:

↻ ↺ ∥ ( ↻ ↺ )
= sin(𝜀) 𝑐𝑜𝑠ℎ ( 𝜆 -) .

Variation of filtering with thickness

Cobalt-Iron alloy Since the values of 𝜆 ↑(↓) for CoFeB could not be found in the literature, in a first step we made the assumption that ε =  * 𝑑. As shown in the following figure a and b, values of  * and 𝜆 could be extracted. The results of the fits show that the quantities are constant over the range of energy studied. In a second step, no assumption has been made on the thickness variation of ε. We find again a linear variation of ε with active layer thickness.

Cobalt

No assumption has been made on the thickness variation of ε with d. We find a linear variation of ε with active layer thickness. The values of 𝜆 ↑(↓) are in agreement with literature. The results of the fits show that the quantities are constant over the range of energy studied.

Precession in a one band structure

The quantum state of an electron in the precession layer is given by:  The following expression when two bands of opposite spin can be accessed with wave vectors k + et k -( is the filtering angle).

| = cos

 e |+> +𝑠𝑖𝑛  e |-> .

The average of the spin components along x and y are then expressed as:

< S > =  sin cos(∆k. x) , < S > =  sin sin(k. x) .

The precession angle per nanometer is given by k = k + -k -.

 The following expression when only one band of spin (here spin up) can be accessed with wave vector k + . Electron waves of the other spin direction (here spin down), however, can only exist as evanescent waves with a typical decay length 1/K.

| = cos  2 e |+> +𝑠𝑖𝑛  2 e |->
The average of the spin components along x and y are thus expressed as:

< S > =  sin cos(k . x)e , < S > =  sin sin(k . x)e .

Consequently, the precession angle per nanometer is given by k + .

Co50Fe50 band structure

Ab initio calculations have been performed to get the band structure of CoFe(100) in the  direction and symmetry analysis led to identify the  1 ,  2 and  5 bands for spin up and spin down electrons. At energies above 1.95 eV,  1 spin up and down bands are accessible. However, for energies below 1.95 eV, only  1 spin up band can be accessed.

Figure 1 :

 1 Figure 1 : Angles of precession and filtering of the spin polarization vector of an electron beam injected into a magnetic layer with magnetization MAL or a field H oriented along MAL. See text for further details.

Figure 2 :

 2 Figure 2 : All solid state device based on a magnetic tunnel transistor that allows measuring the spin precession at low energies in the molecular field of a thin magnetic layer. See text for further details.

  5)/Co(2)/Ta(0.5)/CoFeB(2)/MgO(2.5)/X(y)/Cu(3.5)/[Ni(0.6)/Co(0.2)]x5/Ni(0.6)/Cu(5)/Ta(1)/ Cu(5)//Si(100), where numbers in brackets indicate the layer thicknesses in nm.

Figure 3 :

 3 Figure 3 : CoFeB (1 nm) precession layer. a) 𝑇𝑅 ∥ (black), 𝑇𝑅 ↻ (red) and 𝑇𝑅 ↺ (blue) versus applied voltage on the tunnel barrier measured at 60 K. b) Precession angle calculated from TRs as a function of applied voltage on the tunnel barrier considering different filtering angles 𝜃 (measure at 60K).

  Figure 4: a) Ab initio computation of the band structure along  direction in the CoFe(100) case. b) * vs. E-EF from ab initio computation in the CoFe case. c) Mean sin()cos (θ) vs. VE. Line for an active layer composed of a 1 nm thick CoFeB active layer and for various variation of travel distance. Points are experimental data. d) Mean sin()cos (θ) vs. d for different values of VE. Points : experimental values of sin()cos (θ) for d= 1 nm, 3 nm, and 4 nm.

  leads to a decrease of  * as observed experimentally by Weber et al. Furthermore, the values are in rough agreement with the experimental report at higher energies. However, for energies below 1.95 eV, only one band can be accessed. In this case,  * = 𝑘 ↑ such that huge values of  * should be measured experimentally. In real samples, however, fluctuations in the hot electron travel distance should be considered. Using the values and the linear variation of  * from the ab initio calculations and the experimental values of 𝜆 , we calculated a mean value of 𝑠𝑖𝑛(𝜀)𝑐𝑜𝑠(𝜃) considering a travel distance varying from 𝑑 to 𝑑 + ∆𝑑 for a sample with 𝑑 = 1 nm and by varying ∆𝑑: 𝑠𝑖𝑛(𝜀)𝑐𝑜𝑠(𝜃) = 1 ∆𝑑 𝑠𝑖𝑛(𝜀 * . 𝑡)

  Contributions M.H. and D.L. conceived the project. C.V., M.H. and D.L. were in charge of the thin-film growth and optimization of magnetic properties. C.V. patterned the samples. Y. L. designed the lithography masks and optimized the Cu/Si Schottky barrier. C.V. and D.L. conducted the electronic transport under applied field experiment. C. T., M. C., C.V., W.W., D.L. and M.H. analyzed the data and D.L. and M.H. wrote the manuscript. All authors contributed to the discussion.

  (5)Cu(20)/MgO(2.5)/Co(3)/Cu(3.5)/[Ni(0.6)/Co(0.2)]x5/Ni(0.6)/Cu(5)/Ta(1)/ Cu(5)//Si[100.HF] structure as a function of temperature.

Figure :

 : Figure: Variation of the crossed magneto-current of hot electrons at different energies and of the Schottky barrier conductance as a function of temperature.

Figure :

 : Figure: Variation of the mean free path of hot electrons with energy calculated by Nechaev et al. (Eur. Phys. J. B 77, 31-40 (2010)). Blue curve: mean free path of spin up electrons by only considering electron-electron interaction; Red curve : mean free path of spin down electrons by only considering electron-electron interaction; Blue cyan curve: mean free path of spin up electrons by adding an interaction with a particle with 50meV energy; Blue triangles: mean free path of spin up electrons measured experimentally; Red triangles: mean free path of spin down electrons measured experimentally.

  B Nechaev (2010) Calc. EPJ B Nechaev (2010) + 50 meV EPJ B Nechaev (2010) Exp. APL Dijken(2002) Exp. APL Dijken(2002)

Figure :

 : Figure: Classical decoherence evoked for different spintonics devices in the literature.

Figure :

 : Figure : Variation of the transfer ratio in the parallel configuration as a function of injection energy and temperature

  figure X=CoFeB) in the parallel configuration. As shown in figure X, ln(TR) varies linearly with CoFeB thickness.

Figure :

 : Figure: Variation of the logarithm of the transmission ratio in the parallel configuration as a function of the active layer thickness in the case of CoFeB.

Figure

  Figure: * vs. VE a) and λ -vs. VE b ) for an active layer composed of CoFeB considering that  varies linearly with active layer thickness c) Considering  independent on energy, <> vs. d for d= 1 nm, 3 nm, and 4 nm.

Figure :

 : Figure: * vs. VE a) and λ -vs. VE b ) for an active layer composed of Co

Figure :

 : Figure: Band structure of CoFe(100) in the  direction.

Magnetic tunnel transistor with a perpendicular Co/Ni multilayer sputtered on Si/Cu(100) Schottky diode. C. Vautrin, Y. Lu, S. Robert, G. Sala, O. Lenoble, S. Petit-Watelot, X. Devaux, F. Montaigne, D. Lacour, M. Hehn, J. of Phys. D : Appl. Phys. 49, 355003 (2016).

Thickness and angular dependence of magnetocurrent of hot electrons in magnetic tunnel transistor with crossed anisotropies C. Vautrin, D. Lacour, G. Sala, Y. Lu, F. Montaigne, M. Hehn, Phys. Rev. B 96, 174426 (2017).

In the ∥ configuration, magnetizations of the polarizer, the active layer and analyzer are parallel. Consequently 𝑷 • 𝑴 𝑨𝒏 = 𝑃 .

Magnetization Precession by Hot Spin Injection, W. Weber, S. Riesen, H. C. Siegmann, Science 291, 1015 (2001).

S. van Dijken et al., Phys. Rev. B 66, 094417 (2002)

I.A. Nechaev et al., Eur. Phys. J. B 77, 31-40 (2010)

Acknowledgments

This work has partially been supported by ANR SpinPress (ANR-09-BLAN-0076). Experiments were carried out on IJL Project TUBE-Davm equipment funded by FEDER (EU), French PIA project "Lorraine Université d'Excellence (ANR-15-IDEX-04-LUE), Region Grand Est, Metropole Grand Nancy and ICEEL. The authors thank Sylvie Robert and Guillaume Sala for help with the X-ray diffraction and growth experiments, Stéphane Suire and Sébastien Petit-Watelot for help to set up the high field rotating field electronic transport set up and Gwladys Lengaigne for help with lithography. The authors also thank Béatrice Négulescu and Julien Bernos for their pioneering work in the laboratory on the MgO tunnel barrier optimization and Danny Petty Gweha Nyoma for help with the experiment. The authors also thank Claire Baraduc and Peter Oppeneer for fruitful discussions.

Rough measurements done on the MTT

19

Supplementary informations

Emission and acceptance cones, energy filtering 1-Acceptance cone and energy filtering: the Schottky diode allows a dual analysis.

Energy filtering

On one hand, the electrons collected in the semiconductor, in our case silicon, will always have an energy larger than 0.7 eV (the height of the Schottky barrier). Thus, we will analyze the precession only of hot electrons that have an energy above 0.7 eV. All thermalized electrons will be reinjected by the tunnel barrier through the base's electron recovery circuit.

Acceptance cone

On the other hand, the conservation of the electron's wavevector parallel to the Cu/Si interface will induce the existence of an acceptance cone at the Cu/Si interface. The corresponding cone angle 𝜃 can be evaluated by the following equation [Vlu01]:

The value of the angle 𝜃 can be estimated in the case of the Cu/Si(100) interface. With

Methods

Samples were grown by Ultra High Vacuum sputtering on a fluorhydric acid desoxidized low resistance Si substrate. The base pressure was lower than 5x10 -9 mbar and pure Ar at pressure of 5x10 -3 mbar was used to sputter the targets.

After multilayer deposition and thermal annealing under applied field to set the exchange bias, 4 steps of lithography are performed to make electrical contacts on the polarizer layer, on the active layer/analyzer layers and on the Si. In the following figure, the details of the contacts are given and their spatial location on the device.


Dédalo Sanz-Hernández

Maryam Massouras

Nicolas Reyren

Nicolas Rougemaille

Vojtěch Schánilec

Karim Bouzehouane

Michel Hehn

Benjamin Canals

Damien Querlioz

Julie Grollier

François Montaigne

Daniel Lacour

A nano-magnetic Galton board

Keywords: Galton board, stochastic, domain-wall, nanomagnetic, neuromorphic, computing

 . Still, domain-wall stochasticity could be turned into an asset by using stochastic computing frameworks, such as Bayesian sensing 9 or random neural networks 10 . These approaches however require controlling and tuning stochasticity. An iconic device used to illustrate the emergence of order from controlled randomness is the Galton board 11 . In this device, multiple balls fall into an array of pegs to generate a bell-shaped curve that can be modified

A foreseen stalling of Moore's Law [START_REF] Leiserson | There's plenty of room at the Top: What will drive computer performance after Moore's law?[END_REF] and the success of brain-inspired artificial-intelligence hardware [START_REF] Merolla | A million spiking-neuron integrated circuit with a scalable communication network and interface[END_REF][START_REF] Prezioso | Training and operation of an integrated neuromorphic network based on metal-oxide memristors[END_REF][START_REF] Torrejon | Neuromorphic computing with nanoscale spintronic oscillators[END_REF][START_REF] Ambrogio | Equivalent-accuracy accelerated neural-network training using analogue memory[END_REF] have triggered an intense search for spintronic devices that can perform complex computational tasks efficiently [START_REF] Grollier | Neuromorphic spintronics[END_REF] . Magnetic vortex nano-oscillators [START_REF] Torrejon | Neuromorphic computing with nanoscale spintronic oscillators[END_REF] , magnetic domain-wall synapses [START_REF] Siddiqui | Magnetic Domain Wall Based Synaptic and Activation Function Generator for Neuromorphic Accelerators[END_REF] , and spin-ice networks [START_REF] Skjaervø | Advances in artificial spin ice[END_REF] are part of this emerging family of alternative physics-based computing platforms [START_REF] Grollier | Neuromorphic spintronics[END_REF] . In magnetic domain-wall devices, nonvolatile information storage, transfer, and processing can occur simultaneously through the controlled movement of oppositely magnetized regions in a magnetic track [START_REF] Hrkac | Nanowire spintronics for storage class memories and logic[END_REF] , placing such devices under intense investigation [START_REF] Allwood | Magnetic domain-wall logic[END_REF][START_REF] Parkin | Memory on the racetrack[END_REF][START_REF] Franken | Shift registers based on magnetic domain wall ratchets with perpendicular anisotropy[END_REF][START_REF] Luo | Current-driven magnetic domain-wall logic[END_REF] .

Stochasticity in domain-wall motion is highly detrimental for traditional Boolean logic applications, and great efforts have been made to inhibit it in devices [START_REF] Muñoz | Suppression of the intrinsic stochastic pinning of domain walls in magnetic nanostripes[END_REF][START_REF] Broomhall | Suppression of Dynamically Induced Stochastic Magnetic Behavior Through Materials Engineering[END_REF] . However, a powerful set of stochastic computing frameworks exists and is under intense investigation. These frameworks function by generating and transforming probability distributions, and can efficiently deal with data in which uncertainty is intrinsically present, or with difficult optimization tasks [START_REF] Mizrahi | Neural-like computing with populations of superparamagnetic basis functions[END_REF][START_REF] Alaghi | The Promise and Challenge of Stochastic Computing[END_REF][START_REF] Camsari | From Charge to Spin and Spin to Charge: Stochastic Magnets for Probabilistic Switching[END_REF] . In this context, the once detrimental DW stochasticity becomes an exploitable asset, in the form of a natural source of randomness directly deployable within more complex architectures. Here, we demonstrate that domain-wall stochasticity is controllable and tuneable by recreating one of the iconic experiments in statistics: the Galton board [START_REF] Chernov | The Galton board: Limit theorems and recurrence[END_REF] .

Our nanoscale magnetic equivalent of a Galton board is composed of an elliptical domainwall nucleation pad and a bifurcating network of Ni80Fe20 magnetic nanowires (Figure 1a), 25 nm thick and 200 nm wide (see Methods). Upon application of an external magnetic field in the x-y plane (H1), the elliptical pad reverses and injects a domain-wall into the network. The domain-wall then travels downwards, taking a random decision at each node it encounters.

Magneto-Optical Kerr Effect (MOKE) microscopy (Figure 1b, see Methods) reveals the path taken by the domain-wall. Figure 1c illustrates, for the domain-wall path in Figure 1b, the magnetic orientation of each segment in the board. The '?' symbol indicates the nodes where the domain-wall took a random decision. In this experiment, the detection of a large number of domain-wall propagation events is required. To achieve this, we optimize a full-field MOKE microscope (see Methods) to obtain 201,852 high-resolution magnetic images, a number hardly reachable by other means such as X-ray imaging or magnetic force microscopy. An automatic extraction of domain-wall paths from this large dataset allows us to precisely probe the properties of each node in the Galton board, the tuneability of the random process, and the degree of randomness in domain-wall path selection.

We first study domain-wall motion under symmetric conditions (Field H1 along y), counting the number of times that a domain-wall reaches each of the eight outputs (Figure 1d). Stochastic domain-wall propagation is observed, with the distribution obtained approaching a binomial one. True stochasticity also requires independence between events in the time domain, i.e., the order of output activations (Figure 1e). For a quantitative evaluation of this degree of randomness, we binarized the sequence (mapping even outputs to 1, and odd outputs to 0, see Figure 1f) and passed it through the NIST Statistical Test Suite for Random and Pseudorandom Number Generators [START_REF] Rukhin | A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications[END_REF] , which searches binary sequences for deviations from complete unpredictability. The sequence passes the 13 tests applicable to its length (see Methods), indicating that it comprises a highly uncorrelated set of random events. Another possibility in domain-wall systems is to have short-term memory, leading to correlations between subsequent domain-wall decisions [START_REF] Pushp | Domain wall trajectory determined by its fractional topological edge defects[END_REF] . Detailed trajectory analysis in the Galton board reveals that no significant memory is present, which we associate to a chaotic interaction between magnetic vortices and anti-vortices in the domain-wall [START_REF] Walton | Limitations in artificial spin ice path selectivity: The challenges beyond topological control[END_REF][START_REF] Tretiakov | Dynamics of domain walls in magnetic nanostrips[END_REF] (see Methods).

We continue by investigating the tuneability of the decision process at each node, a critical degree of freedom for the generation of arbitrary distributions. We define 'node probability' as the probability of a right turn at a given bifurcation, and we evaluate how the node probability depends on the angle θ between the driving field H1 and the y-axis (Figure 2a).

Introducing this angle is the magnetic equivalent to misaligning a macroscopic Galton board with respect to the gravitational field. The structure studied contains 28 nodes, the first six marked '?' in Figure 2a, and as a MOKE image is available for each domain-wall propagation event, node probability can be studied for each node independently, at every field angle. We monitor first the overall evolution of node probability with θ. Figure 2b plots node probability for the 28 nodes as histograms, at θ = 0.0° (green), 3.0° (blue) and -3.0° (orange) respectively. We directly observe that a field tilt of 3.0° leads to a uniform bias in node probability of approximately 25 percentage units.

Figure 2c displays the centre and standard deviation of the histograms for a larger number of field alignments, revealing that this bias is continuous and smooth in θ. Examining the output probability distributions (Figure 2d), a lateral shift of the distribution is observed as direct consequence of such uniform shift in node probability, analogously to the macroscopic case of a tilted board.

To confirm the behaviour, we further characterize the complete board (Figures 2e-f), looking at the number of trajectories that went through each node (Figure 2e) and evaluating locally all node probabilities (Figure 2f) by measuring the fraction of domain-walls that took a right turn. The expected tilting in the distribution of domain-wall trajectories is observed in Figure 2e, and a narrow distribution in node probability is observed at all fields (See also Figures 1bc) with no obvious spatial correlations, indicating that variability between nodes is likely caused by small random differences during nanofabrication.

The red circles in Figure 2d show the expected output distribution of an ideal Galton board with uniform probabilities of 50% (θ = 0.0°) and 68% (θ = 3.0°) respectively. These red circles do not coincide with the observed distributions. However, if we calculate numerically the distribution resulting from cascading the individual node probabilities measured experimentally in Figure 2f, an accurate match is observed, represented by green dots in Figure 2d. This shows that the generated output distribution can be precisely computed by knowing the individual node probabilities, and can be controlled through these probabilities.

Results in Figure 2 set the foundations for creating devices in which node probability is tuned locally by means of electrical currents or geometrical modifications, to generate arbitrary output distributions. Given the wide and continuous tuneability range of node probabilities demonstrated (Figure 2e), generating an arbitrary probability distribution in such a device would only require a simple numerical optimization protocol.

Finally, we illustrate how the lattice structure can be engineered to further tune the output distribution and its normalization. In a complete board, all possible paths through the structure lead to an output, and therefore a consistent number of activations (N) is obtained at all operation angles. The structure in Figures 3a andb, however, breaks this condition by removing the central vertical element of the board and leaving the oblique elements marked *. These elements act as domain-wall sinks, preventing them from reaching an output and changing the resulting distribution. These sinks are the nanoscale equivalent to drilling a hole at the back of a macroscopic Galton board.

The measured consequences in the output distributions are presented in Figures 3c andd. At θ = 0.0°, a significant flattening of the distribution occurs compared to the complete board (see solid bars vs. grey lines), as well as a reduction of the number of detected events N. For tilted fields, the lateral shift of the output distribution is larger than in the complete board, while the reduction in N is less pronounced. These effects can be directly correlated to the number of domain-walls that travel through the central segment in Figure 2e, i.e., a reduction of 50% in N is observed at θ = 0.0°, whereas a reduction of 30% in N is observed at θ = ±3.0°.

In future devices, strategic positioning of domain-wall sinks or stochastic pinning traps may be exploited in addition to node probability tuning to control the output distributions.

  via the array spacing or the tilt of the board. Here, we demonstrate the controllability of domain-wall stochastic processes by recreating this experiment at the nanoscale. Balls are substituted by magnetic domain-walls, and bifurcating nanowires recreate the array of pegs. By probing domain-wall propagation through such a structure a large number of times, we demonstrate that stochastic domain-wall trajectories can be controlled and finetuned. This result sets the foundations for an integration of stochastic computing frameworks into domain-wall devices, opening new paths towards post-Von Neumann spintronics.

Figure 1 :

 1 Figure 1: Nanoscale magnetic Galton board. (a) Scanning electron micrograph of a nanoscale magnetic Galton board composed by an elliptical nucleation pad at the top and a branching network of magnetic nanowires.

Figure 2 :

 2 Figure 2: Tuneability of node probability. (a) The probability of a magnetic domain-wall (DW) for turning right at each node marked '?' (node probability) is controlled by tuning the angle between the applied field H1 and the symmetry axis of the Galton board (y). A dark-yellow arrow indicates the direction (left turn) favoured by the angle θ in the diagram. (b) Histogram of node probability vs. field angle for the 28 nodes in the Galton board studied in Figure 1. (c) Mean and standard deviation of the distribution in node probability as a function of field angle θ. Dashed line: guide to the eye hyperbolic tangent fit. (d) Effect of field alignment on the magnetic Galton board output distribution. In colour: output distribution, light-grey shade: distribution at θ=0.0°. Colour follows the scale in (e). N indicates the number of events in each distribution after 2,403 field cycles. Red circles and green dots in panels θ=0.0° and θ=3.0° indicate the theoretically expected distribution for an ideal Galton board with the same probability in all nodes (red) and for a board in which each probability corresponds to the measured probability in panel (f) (green). (e) Spatial distribution of node activation as a function of θ. (f) Spatial distribution of node probability values. Confidence intervals given in Supplementary Figure 3. Grey nodes indicate impossibility to perform the measurement (insufficient counts/not-applicable). (b-f) ±0.3° experimental uncertainty in the alignment between the θ=0.0° direction and the y axis.

Figure 3 :

 3 Figure 3: Galton board lattice edition. (a) Scanning electron micrograph of a nanomagnetic Galton board with a missing central element. The segments marked '*' act as domain-wall sinks. (b) The probability of a magnetic domain-wall (DW) for turning right at each node marked '?' (node probability) is controlled by tuning the angle

Acknowledgements. We acknowledge financial support from the ANR (ANR-17-CE24-0007), the Region Grand Est through its FRCR call (NanoTeraHertz and RaNGE projects), by the impact project LUE-N4S part of the French PIA project "Lorraine Université d'Excellence", reference ANR-15IDEX-04-LUE and by the "FEDER-FSE Lorraine et Massif Vosges 2014-2020", a European Union Program. D.S.H. and J.G. acknowledge support by DOE BES Award # DE-SC0019273 (Kerr microscopy, numerical data analysis and manuscript writing) for Q-MEEN-C, an Energy Frontier Research Center funded by the U.S. Department of Energy (DOE), Office of Science, Basic Energy Sciences (BES). We thank I. Soldatov and R. Schäffer (Evico Magnetics GmbH) for their support with Kerr microscope maintenance and software customization.

between the applied field H1 and the symmetry axis of the Galton board (y). (c) Effect of field alignment θ on the distribution of output activations. Grey lines display the distribution of a complete board. N indicates the number of events in the distribution after 2,403 field cycles. (d) Spatial distribution of node activation as a function of θ. The node removed is indicated with a white cross. Scale bar: 5µm.

In conclusion, the suitability of magnetic domain-walls to generate and sample tuneable probability distributions is demonstrated by evaluating key randomness metrics in a nanoscale magnetic Galton board. Continuous tuneability of the domain-wall path-selection process is achieved and highly-uncorrelated randomness is demonstrated in the time and space domains. Further tuneability is achieved by using domain-wall sinks, which selectively destroy domain-walls passing through some nodes. These results extend the range of applicability of magnetic domain-walls beyond deterministic computing, opening their use as information carriers in high-speed non-volatile stochastic devices. Financial Interests. The authors declare no competing financial interests.


Alexandre Chanson

Ben Crulis

Nicolas Labroche

Patrick Marcel

Verónika Peralta

Stefano Rizzi
email: stefano.rizzi@unibo.it

Panos Vassiliadis

The Traveling Analyst Problem: Definition and preliminary study

This paper introduces the Traveling Analyst Problem (TAP), an original strongly NP-hard problem where an automated algorithm assists an analyst to explore a dataset, by suggesting the most interesting and coherent set of queries that are estimated to be completed under a time constraint. We motivate the problem, study its complexity, propose a simple heuristic under simplifying assumptions for approximating it, and run preliminary tests to observe the behavior of this heuristic.

INTRODUCTION

Interactive data analysis (IDE) [START_REF] Idreos | Overview of data exploration techniques[END_REF][START_REF] Milo | Next-step suggestions for modern interactive data analysis platforms[END_REF] is an iterative process consisting in executing an action (e.g., a query or a pattern extraction algorithm) over the data, receiving the result and deciding what query comes next. It is a challenging task that a number of previous works aimed at facilitating (see e.g., [START_REF] Eirinaki | QueRIE: Collaborative database exploration[END_REF][START_REF] Milo | Next-step suggestions for modern interactive data analysis platforms[END_REF]). Automating such a process raises a number of challenges [START_REF] Marcel | Towards a benefitbased optimizer for interactive data analysis[END_REF][START_REF] Wasay | Queriosity: Automated data exploration[END_REF]: how to determine the direction to follow in often very large and disorienting datasets, how to decide what is the best query to apply, how to determine if a result is interesting, how to tell a story with the data resulting from the analysis [START_REF] Gkesoulis | Cinecubes: Aiding data workers gain insights from OLAP queries[END_REF][START_REF] Hullman | A deeper understanding of sequence in narrative visualization[END_REF], etc.

If we define a data story as a coherent sequence of queries that answer a user goal, we can express this problem as the computation of the most interesting and coherent data story that can be obtained within a reasonable time. Even with simplifying assumptions, like restricting to exploratory OLAP queries over a multidimensional schema (e.g., a star-schema, which allows navigating hierarchically-structured data with a low formulation effort) and giving a particular starting point, this problem remains inherently highly combinatorial.

This paper presents a preliminary study of this problem, that we name the Traveling Analyst Problem (TAP). Similarly to automated machine learning, which aims at finding the best model on a dataset given a time budget (see e.g., [START_REF] Feurer | Efficient and robust automated machine learning[END_REF]), TAP aims at (i) finding, from a very large set of candidate queries, a subset of queries that maximizes their interest within a limited time budget, and (ii) ordering them so that they narrate a coherent data story. More formally, each query is associated to an interest score as well as to an execution cost. A distance between queries is used to order the queries so that the transition cost between two consecutive queries is minimized. Interestingly, a study of the state-of-the-art reveals that TAP has not been studied in the Operations Research community, while being close to two classical optimization problems (the Traveling Salesman Problem and the Knapsack Problem) [START_REF] Johnson | Computers and Intractability[END_REF].

Practically, we envision TAP as being at the core of an IDE system being used by data analysts, like the one described in [START_REF] Marcel | Towards a benefitbased optimizer for interactive data analysis[END_REF]. Analysts would not directly enter TAP parameters, but would use storytelling mechanism instead (e.g., [START_REF] Gkesoulis | Cinecubes: Aiding data workers gain insights from OLAP queries[END_REF]) or patterns like "I want a quick short report around this query result" or "I want an in-depth analysis in this particular zone of the cube".

The contributions of this preliminary effort include the formalization of TAP as well as the proof of its strong NP-hardness (Section 2), an approximation algorithm (Section 3), and some preliminary tests assessing the parameter sensitivity, execution time, and closeness to the optimal of our heuristics (Section 4). Section 5 concludes the paper by discussing future research.

PROBLEM FORMULATION AND COMPLEXITY

In this section, we formalize TAP and show its NP-hardness.

Problem formulation

TAP is formulated as:

Input: Given a set of n queries, a function interest estimating an interestingness score for each query, a function cost estimating the execution cost of each query, and a function dist estimating a cognitive distance between queries, Do: find a sequence of m ≤ n queries (without repetition) S.T.: the sequence has the following properties:

(1) it maximizes the overall interestingness score, (2) the sum of the costs does not exceed a user-specified time budget t, (3) it minimizes the overall cognitive distance between the queries.

We assume that a storytelling mechanism (e.g., [START_REF] Gkesoulis | Cinecubes: Aiding data workers gain insights from OLAP queries[END_REF]) generates a set of candidate queries towards producing a story. Thus, our deliberations start with a set of n candidate queries whose execution has to be optimized. Formally, let Q be a set of n queries, each associated with a positive time cost cost(q i ) and a positive interestingness score interest(q i ). Each pair of queries is associated with a metric dist(q i , q j ) for their cognitive distance. Given a time budget t, the optimization problem consists in finding a sequence ⟨q 1 , . . . , q m ⟩ of queries, q i ∈ Q, without repetition, with m ≤ n, such that:

(1) max m i=1 interest(q i ), (2) m i=1 cost(q i ) ≤ t (3) min m-1 i=1 dist(q i , q i+1 ),

The decision problem associated with this optimization problem is to decide if such a sequence exists.

Complexity

TAP can be related to two families of classical NP-hard optimization problems: (i) the Knapsack problem, which consists in picking weighted items from a set S such that the sum of their values is maximum, without exceeding a given size [START_REF] Kellerer | Knapsack problems[END_REF], corresponding to constraints (1) and (2); and (ii) the traveling salesman problem (TSP), which aims at finding the shortest route that visits all cities and returns to the initial one [START_REF] David | The Traveling Salesman Problem, A Computational Study[END_REF] and is close to constraint [START_REF] Chanson | Profiling user belief in BI exploration for measuring subjective interestingness[END_REF].

In our context, the former problem would find the most interesting queries given a time budget but, in its classical formulation, it would miss the ordering of queries. A variant [START_REF] Díaz-Núñez | The knapsack problem with scheduled items[END_REF] includes the position of each object in the Knapsack via the definition of a function (which is constant in the case of classical Knapsack). While this problem is closer to TAP, it involves a function that only relies on the position (or order) of an object in the Knapsack, and not on the positions of objects previously picked.

TAP could also be modeled as a TSP problem with particular constraints: (i) the TSP cities are the queries; (ii) inter-city distances correspond to the cognitive distance between queries, whose total must be minimized. However, differently from classical TSP, TAP operates under strong constraints: (iii) it is possible to visit only a subset of cities, each city has a weight corresponding to the action's interest, whose total is to be maximized; and (iv) each city has a duration of visit corresponding to the cost of the query, whose sum must not go beyond a given time budget.

Interestingly, this optimization problem has not been studied in the literature yet. The variant of the TSP called TSP with profit (TSPwP), described by Feillet & al. in [6], is closer to our problem, but still differs in two aspects: (i) it looks for circuits and does not reject any vertex in the solution, and (ii) it gives a limit in terms of the travel distance (inter-queries distance in our case) while our limit is on the cost of queries (the duration of visit).

An in-depth study of the TAP complexity is beyond the scope of this paper. However, we can easily show that our problem is strongly NP-hard since the TSP is a particular case of it. Indeed, if the time budget t is high enough, i.e., all queries can be selected, then TAP is a TSP. This result means that, unless P=NP, the TAP problem can only be solved to optimality by algorithms with a worst-case time complexity in O * (c n ), with c a positive root and n the size of Q.

Size of the problem and our naive approach

We now discuss the size n of TAP (the number of queries in Q) since the size of an optimization problem usually impacts the choice of resolution approaches. Theoretically, given a cube schema, all non empty queries over this schema could be considered. Practically, it is reasonable to consider that this set is generated from a given initial query q 0 . In what follows, we restrict to star join queries over a star schema of the form q = (д, s, m) where д is the query group-by set, s is a set of selections, and m is a set of measures, all 3 sets being pairwise disjoint. Transforming a query into another with a simple OLAP operation means either changing the group-by set д, changing a selection in s, or changing a measure in m.

Even restricting Q to the set of queries that can be generated by transforming an initial query q 0 = (д 0 , s 0 , m 0 ) with a sequence of simple OLAP operations, the size of Q is potentially very large, not allowing to look for an exact solution. A rough estimate of the number of queries that can be generated from q 0 by applying k OLAP operations, i.e., the size of Q, can be done by assuming for simplicity that dimensions only have linear hierarchies (no branches):

|Q | = ((Π i h i -1) + (|2 D | -1) + (|2 M | -1)) • k
where h i is the number of levels in dimension i, D is the union of the active domains of all levels, and M is the set of all measures in the cube. Changing the query group-by set means picking one group-by set among all the possible ones, excluding the current one д 0 . Changing the selected values means picking a set of values in the active domain, excluding the current one s 0 . Changing the measure set means picking a set of measures among all possible sets of measures excluding the current one m 0 .

In order to approach solutions of TAP for arbitrary large sets of queries, we adopt the following strategy. We first use a heuristic to solve the Knapsack problem and obtain a subset of queries, using estimated costs and interests, so that the estimated costs satisfy the time budget. Then, we order the queries by increasing estimated cost and evaluate them. We periodically check the difference between the time budget constraint and the elapsed time: if it is negative (too much time is taken) we redo a Knapsack to reduce the set of chosen queries; otherwise (we can benefit from additional time), we redo a Knapsack adding previously not taken queries. Finally, we determine an order on the chosen set of queries so that cognitive distance is minimized, using a heuristic to solve the TSP.

APPROXIMATION ALGORITHM

Before presenting our approach we discuss its parameters, i.e., the three functions for cost, interest, and distance, and the set Q of queries. Choosing the best three functions or defining the best set of queries Q is outside the scope of this paper. Note that a framework for learning cell interestingness in a cube is the topic of a recent paper [START_REF] Marcel | A framework for learning cell interestingness from cube explorations[END_REF]. We give examples in this section, and we indicate precisely in the tests of Section 4 the parameters used.

Cost

The cost of a query is related to its execution time. Classically, this cost can be estimated by a query optimizer before the execution of the query. We therefore consider that we can measure a query cost in two ways, to obtain an a priori cost (e.g., using the RDBMS optimizer) and an a posteriori cost (the actual query execution time). The a priori cost is used to decide if a query can be included or not in the solution, while the a posteriori cost is used to compute the elapsed time.

Interestingness measure

A crucial part of TAP lies in the definition of an interestingness measure to determine the optimal subset of queries. To quickly decide if a query is interesting, it is preferable that this measure can be computed before the actual evaluation of the query by the DBMS, therefore that it relies on the text of the query. In this sense, we propose to follow the idea of subjective interestingness measure of a pattern as developed by De Bie in the context of Exploratory Data Mining (EDM) [START_REF] De | Subjective interestingness in exploratory data mining[END_REF] and to extend it to measure the subjective interestingness of a query as expressed by a coherent set of query parts.

In the information-theoretic formalism proposed by De Bie, interestingness is conditioned by the prior knowledge belie f (p) on a pattern p of the data space, which is expressed as a probability distribution over the set of patterns P. The interestingness measure I M is derived by normalizing the belief by the complexity of the pattern as follows:

I M(p) = -log(belie f (p)) complexity(p) (1)
In the context of BI, [START_REF] Chanson | Profiling user belief in BI exploration for measuring subjective interestingness[END_REF] introduces an innovative approach to learn the belief distribution associated to query parts. The approach considers a connected graph of query parts based on the schema of the cube and the past usage of query parts, and uses a random walk on this graph to produce the expected long-term distribution over query parts. Interestingly, by construction, the probabilities obtained for each query part are independent, which allows to propose a simple formulation for the interestingness measure of a query q = (д, s, m) based on its query parts p ∈ (д ∪ s ∪ m):

I M(q) = -p ∈(д∪s∪m) log(belie f (p)) |д| + |s | + |m| (2)

Cognitive distance

To order a set of queries we draw inspiration from Hullman et al. [START_REF] Hullman | A deeper understanding of sequence in narrative visualization[END_REF] who estimate the cognitive cost of transiting from the result of one query to the result of another. We use this cost as a proxy for cognitive distance. Interestingly, this cost can be estimated without having evaluated the query. Using controlled studies of peoples' preferences for different types of single visualizationto-visualization transitions, Hullman et al. [START_REF] Hullman | A deeper understanding of sequence in narrative visualization[END_REF] proposed a transition cost model that approximates the cognitive cost of moving from one visualization to the next in a sequence of static views. The transition cost is defined as the number of transformations required to convert the data shown in the first view to the second. A single transformation is defined as a change to one of the data fields shown from the first view to the second. We use this cost model to define a simple distance between queries as the Jaccard distance between sets of query parts. Formally, let q 1 = (д 1 , s 1 , m 1 ) and q 2 = (д 2 , s 2 , m 2 ) be two queries; we define:

dist(q 1 , q 2 ) = 1 - |(д 1 ∪ s 1 ∪ m 1 ) ∩ (д 2 ∪ s 2 ∪ m 2 )| |д 1 ∪ s 1 ∪ m 1 ∪ д 2 ∪ s 2 ∪ m 2 | (3)

Set of queries

TAP is defined for a given set Q of queries. Practically, we consider that this set is generated from a given initial query, q 0 . This initial query can be interpreted as a particular moment in an interactive analysis where the user considers what is retrieved is important and worth exploring "around" it, but has too many directions to explore. In what follows, we consider this initial query as a parameter of our approach. Defining the set of queries worth exploring after q 0 should be rooted in the earlier OLAP literature, especially automatic reporting [START_REF] Gkesoulis | Cinecubes: Aiding data workers gain insights from OLAP queries[END_REF], automatic cube exploration [START_REF] Kamat | Distributed and interactive cube exploration[END_REF], discovery driven analysis [START_REF] Sarawagi | Explaining differences in multidimensional aggregates[END_REF][START_REF] Sathe | Intelligent rollups in multidimensional OLAP data[END_REF], and more generally realistic OLAP workloads [START_REF] Rizzi | CubeLoad: A parametric generator of realistic OLAP workloads[END_REF]. In the Cinecubes approach [START_REF] Gkesoulis | Cinecubes: Aiding data workers gain insights from OLAP queries[END_REF], the authors consider two types of queries: (i) queries for values similar to those defining the selection filters of the initial query (i.e., siblings of ancestors), and (ii) direct drill-downs into the dimensions of the initial result, one dimension at a time. In the DICE approach [START_REF] Kamat | Distributed and interactive cube exploration[END_REF], the authors consider direct roll-up queries, direct drill-down queries, sibling queries (a change of a dimension value, i.e., coordinate, in a dimension), and pivot queries (a change in the inspected dimension). In the DIFF and RELAX operators [START_REF] Sarawagi | Explaining differences in multidimensional aggregates[END_REF][START_REF] Sathe | Intelligent rollups in multidimensional OLAP data[END_REF], the authors consider direct or distant drill-down (resp. roll-up) queries that detail (resp. aggregate) two particular cells of a query result. Finally, the CubeLoad OLAP workload generator [START_REF] Rizzi | CubeLoad: A parametric generator of realistic OLAP workloads[END_REF] is based on patterns modeling realistic OLAP sessions, that could be used to generate the queries of Q.

Ideally, the set Q should include all these potentially relevant follow-up queries to q 0 . For the present work we will consider different sets varying the generation of roll-up, drill-down, and sibling queries (see Section 4).

A simple heuristic for approximating TAP

Algorithm 1 presents our heuristic, named Reopt, since it is based on a naive re-optimization principle. Note that the generation of the set Q from an initial query q 0 is considered as a pre-processing step. Algorithm 1 takes advantage of the fact that functions interest, cost, and distance can be computed solely on the basis of the query expression (and not on the result of the queries).

First, Algorithm 1 splits the time budget t in t k (time for the global query execution) and t o (time for other tasks, like solving the Knapsack, solving the TSP, etc.). Then the Knapsack is solved (line 2), and the queries selected are ordered by their estimated evaluation cost (line 3). Queries are then executed (line 6) and, after each execution, the elapsed time is checked. If it is estimated that the time budget t k will not be respected (line 9), then another Knapsack is triggered with the remaining time. If it is estimated that the time budget will not be completely spent (line 13), then another Knapsack is triggered with all the remaining queries. Finally, once all the queries of the chosen set of queries are executed, the TSP is solved. It is easy to verify that Algorithm 1 converges: the set K is at worst Q and, at each iteration of the for loop (line 5-16), the set E is augmented with one more query of K while such query is removed from K.

Note that, when actually executing the queries, Reopt attaches a particular importance to the estimated cost (see for instance Line 3) compared to interest or distance. The main cause behind this decision is due to the time budget that has to be respected: had we given priority to distance from q 0 or interest, we might have executed first costly queries or we might have many ties (since many queries would be at the same distance from q 0 ). Although alternative formulations are also possible, due to the sensitivity of time efficiency in user interactions (keep in mind that we operate in the context of exploratory data analysis), it is imperative that the other factors do not guide query execution to take up too much time.

Implementation-wise, the Knapsack problem is solved using a Fully Polynomial Time Approximation that gives a bound on the divergence from the optimum [START_REF] Lai | The knapsack problem and fully polynomial time approximation schemes (fptas)[END_REF], and for the TSP using the heuristic of [START_REF] Lin | An effective heuristic algorithm for the travelingsalesman problem[END_REF].

PRELIMINARY EXPERIMENTS

Our preliminary experiments aim at understanding the behavior of our naive algorithm Reopt. To this end, we have compared it to two other algorithms: a brute force one that looks for the optimal solutions (named optimal), which obviously works only on small instances of TAP, and a simplistic one that consists of solving the Knapsack, then solving the TSP, and then executing the queries (named K +T SP). All the algorithms are implemented in Java 12 and run on a Core i7 with 16GB RAM under Linux Fedora. The code is available via Github (https://github.com/ OLAP3/CubeExplorer). Note that, in all tests, costs are estimated Algorithm 1: Reopt: simple re-optimization heuristic for TAP approximation Data: An instance (Q, interest(), dist(), cost(), t) of TAP Result: A sequence of queries using not the estimation coming from the query optimizer of the DBMS but a linear regressive model based on the query length in ASCII, the number of tables, the number of projections, the number of selections, and the number of aggregations of the SQL star join query. This is because our empirical tests have shown that this model was more accurate than the raw estimates given by the query optimizer.

1 Split t = t k + t o 2 K = knapsack(Q, t k ) 3 sort K by increasing cost 4 E = ∅ 5 for each query q ∈ K do 6 execute q 7 K = K \ {q} 8 E = E ∪ {q} 9 if elapsedT ime + q ∈K cost(q) > t k then

Optimization time

In this first test, we use a simple synthetic cube under the schema of the SSB benchmark [START_REF] O'neil | The star schema benchmark and augmented fact table indexing[END_REF], with an instance of 1GB under Mari-aDB, produced with the TPC-H data generator. The cube has only one fact table and 5 dimension tables, which enables to keep the number of queries in Q under control for comparing Reopt and K + T SP with optimal. Over this schema, we have used the CubeLoad generator [START_REF] Rizzi | CubeLoad: A parametric generator of realistic OLAP workloads[END_REF] to generate 40 q 0 queries. These queries are used to generate Q with direct roll-up or drill down queries, i.e., Q can vary between 5 and 10. To assess the benefit of our re-optimization step (line 9-16 of Algorithm 1), we counted the number of times each branch of the if statement in line 9 of Reopt is taken, i.e., the number of times for negative (lines 10-12) and for positive (lines 14-16) re-optimizations. We have observed that both branches are used, with positive re-optimizations being rarely done compared to negative ones; precisely, over 399 total runs, positive re-optimizations are done 116 times while negative re-optimizations are done 851 times. This demonstrates that Reopt can adaptively respond to inaccurate estimates.

Distance and interestingness vs time budget

For the next series of tests, we use a cube issued by a French project on energy vulnerability. It is organized as a star schema with 19 dimensions, 68 (non-top) levels, and 24 measures, and it contains 37,149 facts recorded in the fact table. The cube is stored in SQL Server. We use 19 real user explorations over this cube (navigation traces generated by master students when analysing data during a course) and pick as q 0 the first query of the explorations. For each of these queries, we generate Q by rolling-up q 0 in a dimension, drilling down q 0 in a dimension, or computing a sibling query in a dimension. We use this cube and set Q to obtain more realistic instances of TAP. Precisely, |Q | ranges from 29 to 149 queries for these tests. Over these sets Q we run Reopt and K + T SP and observe how total interestingness and average distance between queries change when increasing time budget t from 500 milliseconds to 5 seconds. Figures 2 and3 show the results. It can be seen that Reopt outperforms the simplistic K + T SP in terms of interestingness, which illustrates the benefit of our re-optimization heuristic, while both algorithms achieve comparable average distance.

Unused time

In this last test, using the same cube and protocol as in the previous subsection, we want to understand if the budget time is used properly. As we can see, regardless of the budget, our algorithm manages to take advantage of all the time available unless all queries of the Q have been explored, in which case the ratio of unused time increases. On the contrary, the K + T SP approach, which is unaware of the possible gain in executing the other queries, has a larger ratio of unused time and does not manage to explore completely Q. The absence of idle time clearly proves the advantages of our adaptive re-optimization heuristic over the static K + T SP method, which cannot compensate for the errors in the prediction of the cost, nor ensure that the execution time is near to the time budget.

CONCLUSION

This paper introduced the Traveling Analyst Problem (TAP), the problem of computing the most interesting and coherent data story that can be obtained within a reasonable time. We formalize the problem, show its strong NP-hardness and propose a heuristic for finding approximate solutions to it. Our preliminary experiments show that a heuristic based on simple re-optimization is a promising direction to obtain acceptable solutions.

We believe that TAP opens many interesting research directions. Obviously, the first step is an in-depth theoretical study of TAP, to understand which types of optimization algorithms are more appropriate. Importantly, TAP should be investigated in the context of data exploration, which means that optimization algorithms should take advantage of classical data management optimizations, like re-optimization (e.g., [START_REF] Volker Markl | Robust query processing through progressive optimization[END_REF]), and that TAP should be declaratively formulated, for instance by having starting points expressed in an intentional fashion (e.g., [START_REF] Vassiliadis | Beyond roll-up's and drill-down's: An intentional analytics model to reinvent OLAP[END_REF]). User tests should be conducted for further evaluating the approach. Finally, we also note that the definition of TAP is general, leaving room for variants, e.g., changing the definition of queries (e.g., from non-OLAP SQL queries to more complex actions involving queries and pattern mining or statistical tests), as well as changing cost (e.g., using self-adjusting cost model), interest (e.g., using statistics or data sampling), and distance functions.

10 / 11 KFigure 1 :

 10111 Figure 1: Optimization time

Figure 2 :

 2 Figure 2: Total interestingness

Figure 3 :Figure 4 :

 34 Figure 3: Average distance

Figure 4

 4 Figure 4 plots against different time budgets the proportion of unused time versus the number of candidate queries left in Q to execute. As we can see, regardless of the budget, our algorithm manages to take advantage of all the time available unless all queries of the Q have been explored, in which case the ratio of unused time increases. On the contrary, the K + T SP approach, which is unaware of the possible gain in executing the other queries, has a larger ratio of unused time and does not manage to explore completely Q. The absence of idle time clearly proves the advantages of our adaptive re-optimization heuristic over the static K + T SP method, which cannot compensate for the errors in the prediction of the cost, nor ensure that the execution time is near to the time budget.

Acknowledgment. The authors would like to thank Vincent T'Kindt for his insights on TAP complexity.