Florence Sagnard
email: florence.sagnard@ifsttar.fr

Elias Tebchrany
email: elias.tebchrany@ifsttar.fr

Using polarization diversity in the detection of small discontinuities by an ultra-wide band ground-penetrating radar

A ground-penetrating radar (GPR) has been developed for civil engineering applications.

Ultra-wide band (UWB) bowtie slot antennas operating at frequencies from 460 MHz to beyond 4 GHz have been designed to be integrated in a ground-penetrating radar (GPR) positioned very close to the soil surface. FDTD modeling has allowed to define the optimal geometrical parameters associated with the ground-coupled radar system that has been studied in two polarization configurations TE and TM. The ability of the GPR system in detecting small discontinuities using polarization diversity has been analyzed considering several buried canonical objects with different dielectric characteristics. Measurements in a sand box have been compared to full-wave simulations.

Introduction

Ground-penetrating radar (GPR) is a well-known non-destructive technique based on electromagnetic waves to detect and image dielectric discontinuities in the subsurface [START_REF] Daniels | Ground penetrating radar. 2 nd edition: The IEE[END_REF].

GPR applications are numerous involving archaeology, geology, civil engineering, environmental geophysics, utilities or target detection. The dielectric properties of a soil correlate with many of the mechanical, geologic and structural parameters of the constituents.

The choice of the central frequency and the bandwidth of the GPR is an important issue, and depends on the particular application, mostly of the kind of object one is looking for: size of the object, its electrical properties, depth of the object, properties of the soil, etc... An ultrawide band (UWB) radar offers an opportunity to probe a soil structure using the benefit from both low and high frequencies and to obtain a compromise in terms of depth resolution and penetration in a single measurement. The basic GPR system is made of a pair of parallel antennas that radiate a polarized electric field, and the co-polarization configuration is generally chosen. Thus, the GPR system probes the subsurface at a single polarization. An optimal matching of the GPR system with the soil in order to eradicate the significant reflection from the air-soil interface is achieved by positioning both antennas in close proximity to the soil interface. The application of interest is the detection of buried objects or discontinuities in civil engineering structures particularly pipes [START_REF] Porsani | Comparing detection and location performance of perpendicular and parallel broadside GPR antenna orientation[END_REF][START_REF] Tsoflias | Vertical fracture detection by exploiting the polarization properties of ground-penetrating radar signals[END_REF], and defaults (cracks, joints, buried repair patches, delaminations, density changes, etc…) which can be caused by mechanical, chemical and biological causes. Because the GPR reflected signal traces issued from embedded objects result from multiple scattering both inside each object and between a given object and its environment, we have considered a simplified soil structure to interpret the radar response by comparing numerical FDTD modeling and field-experiments in the presence of well-separated canonical objects. Thus, we have designed a compact UWB GPR system using full-wave FDTD simulations to model and control its radiation characteristics. The experimental GPR system is supposed to operate in the frequency domain using a step-frequency continuous wave (SFCW) to benefit from a wide dynamic range, a low figure noise and the possibility of shaping the power spectral density.

The aim of this study is to check the sensitivity of the UWB GPR for the detection of small discontinuities in the two main polarization configurations TM (Transverse Magnetic) and TE (Transverse Electric), and to extract information of dielectric characteristics from reflection hyperbolas. The comparison of theoretical and experimental B-scans has allowed to interpret the polarization phenomena involved by different discontinuities characterized by their shape and their dielectric properties.

UWB GPR system

The GPR system consists of a pair of transmitting and receiving shielded bowtie slot antennas. The antennas have been designed in our laboratory using full-wave FDTD simulations under the commercial software EMPIRE. The classical geometry of the bowtie slot antenna, as visualized in Figure 1a . The antenna port is supposed to be connected to a Vector Network Analyzer (VNA) via a SMA (subminiature version A) connector. To eliminate backward radiations in air induced by the close environment, and to reduce the direct coupling between transmitting and receiving antennas in the GPR system, each antenna has been partially enclosed in a perfectly conductive box opened towards the ground surface as shown in Figure 2; the conductive box (height h c =67.5 mm, width W c =231 mm, and length L c =362 mm) has been filled with a layered absorbing material which is supposed to progressively absorb the electromagnetic waves and to reduce multiple reflections inside the cavity. In the numerical modeling, a three-layered radar absorbing material (RAM) with a conductivity profile characterized by the power law 1 3

. 10

- - = m S n σ
(n is the layer number, and n=1 is the layer just in contact with the antenna) has been considered; such a structure is supposed to represent the five-layered RAM (150 mm-thick absorbing foam HPS 125 distributed by EUROMC) used in the experiments [START_REF] Atteia | Wideband partially-covered bowtie antenna for groundpenetrating radars[END_REF].

Thus, according to a parametric study non presented here, the characteristics of the absorbing layers are finally: ) appear the closest to the measurements. This permittivity estimation will be confirmed later by offset measurements using the GPR system. The E-field distributions in the TE and TM planes (f=800 MHz) visualized in Figure 2b in proximity to the unshielded antenna positioned on a soil interface (

5 . 3 ' = s ε , 1 . 01 . 0 - = m S s σ , mm h s 10 =
) highlights that the TM plane has null radiating energy at particular angles [START_REF] Nobes | Broadside versus end-fire radar response: some simple illustrative examples[END_REF]; this phenomenon is also observed when the antenna is shielded as shown in Figure 2c at the frequency 800 MHz.

To acquire GPR linear profiles (B-scans), two symmetric antenna configurations have allowed to consider two polarizations: the parallel configuration (or end-fire, transverse magnetic mode TE, the opposite situation of a dipole antenna) with both antennas aligned along their larger dimension (see Figure 3a), and the mirror configuration (or broadside, transverse electric mode TM) with both antennas facing each other symmetrically along their larger dimension (see Figure 3b). For each configuration, the offset value between antennas results from a compromise between a weak direct path amplitude (low transmitting coefficient

) ( 21 f S
) and a sufficient high signal amplitude issued from reflections inside the soil induced by a buried object or a dielectric contrast. Offset measurements (Wide Angle Reflection and Refraction, WARR profiles) have been made in the range [50 ; 1000] mm in the parallel and mirror configurations (see Figure 4) on a wet sand. The comparison between theoretical (soil amplitude difference around 12 dB for frequencies lower than 1.5 GHz; however, it has to be considered that the dielectric real permittivity of the wet sand has been a priori estimated less than 5.5. It appears from the simulations that a higher coupling at a given offset particularly below 1 GHz is observed in the mirror configuration, that can be explained by the lower lateral dimension of each antenna in this configuration; this coupling phenomenon does not appear so marked in the measurements. Thus, according to theoretical and experimental results, the antenna offset will be then defined to 60 mm that allows to obtain a compact system with a reduced coupling at lower frequencies.

) ( / ' " ' s s s c v ε ε ε << = , the arrival time ) ( y t
is expressed as a function of the horizontal position y of the GPR system as follows:

2 2 2 2 / ) 0 ( ) ( v y t y t + = (1)
In the measurements, the bottom of the sand box associated with an arrival time close to 6 ns corresponds to a depth around 470 mm.

Theoretical aspects in discontinuity detection

The present study is particularly focused on the detection of small canonical discontinuities (lateral dimensions less than 25 mm) to further consider defaults in civil engineering structures. Such discontinuities allow to evaluate the GPR system in both polarization configurations. The antenna offset has been defined to 60 mm (common offset mode (COM) configuration), thus the distances between transmitting and receiving ports is in the mirror configuration.

Analytical modeling

When the GPR system moves along a straight line on the soil surface a discrete discontinuity induces reflected waves when it is under the antenna footprint. Because the antenna footprint has the shape of a wide cone, the target is imaged not only when the GPR system is immediately above, but also when the GPR is approaching several centimeters from the target. This leads to a defocalised signature with a hyperbolic shape. The two-way travel time is easily modeled by analytical relations associated with the far-field zone (ray path hypothesis) in the case of a buried cylindrical pipe. Such a modeling helps to interpret the different object signatures observed in both polarizations in a radar profile that are induced by the dielectric contrast between the surrounding medium and the object. Thus, the hyperbolic signature is formulated using a geometric model based on the Pythagorean theorem, and we have considered the center-to-center antenna offset SR.

The buried cylindrical object assumed infinitely long and conductive is characterized by : a radius R , a horizontal location at abscissa 0 y and a depth d under the soil surface. The displacement of the center axe of the radar along axis Oy is noted i y , and the signal issued from the reflection on the object arrives at time i t .

According to Figure 7a, the travel-time equations write as follows [START_REF] Shihab | Radius estimation for cylindrical objects detected by ground penetrating radar[END_REF]:

   + = - = 2 / 2 / SR y y SR y y i R i T (2) ( ) [ ] ( ) [ ]      - + + - = - + + - = R R d y y T R R d y y T R Rx et t T et t Tx 5 . 0 2 2 0 2 arg 5 . 0 2 2 0 arg 2 ) ( ) ( (3)
The generalized hyperbola equation ( ) ). First analysis of measured Bscans with distinguishable hyperbola signatures can be performed using this modeling. In the case of reproducible background clutter and antenna coupling, there influence can be significantly reduced by removing the median value at each time sample. Afterwards, the hyperbola points ( )

i
meas i meas i t y , ,
, have been extracted by detecting the maximum or the minimum along each column in a selected area. Then, the minimum of the sum of squares of the distances between theoretical and measured data can be solved using the Gauss-Newton method as follows:

( ) ∑ = - = n i meas i theo i y y F 1 2 , , (5)
Some constraints relative to the parameter ranges have been added in the algorithm to better drive the solution. The influence of the dielectric characteristics of the cylinder (index d) illuminated by a electromagnetic (EM) polarized plane wave is described by the scattering theory [START_REF] Radzevicius | Ground penetrating radar polarization and scattering from cylinders[END_REF][START_REF] Balanis | Advanced engineering electromagnetic[END_REF]. The backscattered fields (

s s H E ,
) depend strongly on the orientation of the cylinder relative to the antennas, its dielectric properties, and the radius of the cylinder compared to the wavelength 0 λ of the surrounding medium (index 0). The scattering properties of a long cylinder has been described by the Bessel and Hankel functions. The scattering width (SW) is the equivalent area proportional to the apparent size of the target (in the far-field zone) that scatters the field relative to the incident power in a given direction φ . Four expressions associated with SW consider both TE and TM polarizations and the case of a dielectric or a conductive cylinder as follows:

• TE polarization : Conductive cylinder 2 0 0 )' 2 ( 0 ' 0 ) cos( ) ( ) ( 2 φ β β ε π λ n R H R J SW n n n n ∑ ∞ + = = Dielectric cylinder: 2 0 0 ) 2 ( ' 0 )' 2 ( 0 0 ' 0 0 ' 0 ) cos( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( 2 φ β β η β β η β β η β β η ε π λ n R H R J R H R J R J R J R J R J SW n n d n d n d n d n n n d n d n ∑ +∞ = - - = • TM polarization : Conductive cylinder 2 0 0 ) 2 ( 0 0 ) cos( ) ( ) ( 2 φ β β ε π λ n R H R J SW n n n n ∑ ∞ + = = Dielectric cylinder 2 0 0 ) 2 ( ' 0 0 )' 2 ( 0 ' 0 ' 0 0 ) cos( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( 2 φ β β η β β η β β η β β η ε π λ n R H R J R H R J R J R J R J R J SW n n d n n d n d d n n d n d n n ∑ +∞ = - - =
Where 0 β and d β are the wavenumbers, associated with the surrounding medium and the dielectric cylinder; they can be complex.

) ( 0 R J n β
is the Bessel function of the first kind of order n,

) ( 0 ' R J n β is its derivative, ) ( 0 ) 2 ( R H n β
is the Hankel function of the second kind of order n, and

) ( 0 )' 2 ( R H n β is its derivative.
The simplified modeling of the GPR system considers that the antennas, linearly polarized, are closely spaced. This results to a backscattering angle corresponding to °= 180 φ . In this context, before analyzing theoretical and experimental B-scans, we have studied the scattered responses SW in a very large frequency band [0.2 ; 2] GHz considering several pipe radii and two dielectric contrasts between the pipe and the surrounding medium. The results collected in Figures 8a and8b, in the case of a conductive cylinder with a radius in the range [5 ; 40] mm, highlight that the TM polarization (electric field parallel to pipe axis) generally leads to a higher backscattering response whatever the value of the real permittivity value ( . Consequently, the TM polarization is preferred to detect a conductive pipe independently of its radius and the wavelength of the surrounding medium. Figures 8c and8d associated with a dielectric cylinder show that the TE polarization gives a higher SW when the radius value is inferior to the wavelength and when the permittivity of the pipe (here filled with air) is less than the medium permittivity ( ) than the medium, we remark that the TM polarization is in general higher than the TE polarization. We also observe that for a radius greater than 10 mm, TE and TM components oscillate and they can meet each other.

Numerical modeling

Full-wave simulations based on the FDTD approach considering buried canonical discontinuities have been performed to preliminary analyze radar profiles (B-scans). The moving step of the GPR system along the horizontal axis has been defined to 40 mm, and the elevation on the ground surface is h s =10 mm. The soil is homogeneous and includes losses expressed by its conductivity Figures 9c and9d. Thus, we remark that the TE polarization gives a more blurred image than the TM polarization that gives a sharp response. The arrival times of the direct wave has been estimated to 2.8 ns and 2.2 ns in the parallel and mirror configurations respectively, that correspond to the analytical model with the average celerity in air and in the soil. The first arrival times of the hyperbola apexes are 3.7 and 3.3 ns in both polarizations respectively; they correspond to the reflection at the bottom of the crack at the depth 75 mm. There values agree with those issued from the simplified model illustrated in Figure 7a with an object positioned at the depth 75 mm. Afterwards, hyperbola extraction has been performed on grayscale images. Selecting the area where the hyperbola is located, the minimum of the maximum (parallel case) or the minimum (mirror configuration) at each horizontal position has been stored. Then, the hyperbola fitting has been performed in two steps: firstly, a polynomial fitting (degree 2) using the least-square criterion has been performed on the raw data, and secondly, then a hyperbola fitting based on relation (4) has been applied on the polynomial data. This results in the fitting curves shown in Figures 9c and9d. In general, we remark that the mirror configuration gives a higher scattering amplitude than the parallel one as shown in Figures 9c, 9d and10a (position i y of the apex); this result agrees satisfactorily with the plots of Figure 8c. In this case, the probing in both polarizations can give dielectric information concerning the detected discontinuity, however it remains difficult to estimate its width. These fitting curves have been compared in Figure 10b with those associated with an open V-crack of 5 mm width at the soil interface with height 75 mm. This comparison highlights that it appears difficult to distinguish in a B-scan from a rectangular and a V-crack when they are thin. has also been probed by the radar system. B-scans associated with the parallel and mirror configurations as visualized in Figures 11a and11b have been obtained from FDTD simulations. The arrival times from the B-scans associated with the clutter are estimated to 3 and 3.3 ns in the parallel and mirror configurations respectively, and the first arrival times associated with the hyperbola apexes are 4.6 and 4 ns; the first positive peak of the incident signal arrives at 0.5 ns. Thus, we remark a positive time difference of around 0.5 ns for the clutter, and 0.8 ns for the reflection hyperbola when comparing to the analytical model. Figures 11c and11d highlight that the TM polarization induces a higher and sharper reflection amplitude as compared to the TE polarization. The signal at the apex in the TM polarization is characterized by a sharp and significant positive component and higher than the clutter, as shown in Figure 12. In the TE polarization, the positive and negative components show similar amplitudes and the signature appears more blurred. The hyperbola traces associated with the first reflection on the pipe in both polarization and calculated using the analytical relation ( 4) have been superimposed to the B-scans in Figures 11c and11d; these traces follow satisfactorily the signatures observed in the calculated B-scans.

Analysis of experimental results

Buried canonical objects in the large sandy box of the public square Perichaux, Paris 15 th district, have been probed using the radar system developed. The sand was wet and not compacted; its dielectric permittivy has been estimated to 3.5 from the slope of the WARR profiles (see Figures 6b and6d). The time zero has been corrected according to the comparisons of WARR profiles issued from measurements and simulations (Figures 6b and6d). In general, a couple of canonical objects (pipe or strip) has been probed in a single Bscan to compare the signatures. Both objects have different dielectric properties, and have been buried at a depth close to 150 mm. They have been separated by a distance around 700 mm, and the displacement range is [0;1760] mm with a 40 mm step; the position i y corresponds to the center of the radar system in both polarizations. The complex transmission coefficients 21 S have been measured in both polarizations, parallel and mirror, at an offset of 60 mm in the frequency domain [0.05;4] GHz (1601 samples) using the VNA.

At first, a 25 mm diameter dielectric pipe and a thin conductive 2 mm width strip have been probed. As shown in the soil cross-section of Figure 13a, the pipe has been filled with water and the strip has been vertically positioned, thus its lateral dimension is 2 mm, and its height is 10 mm. The B-scans in both parallel and mirror polarizations are presented in Figures 13b and13c respectively. The time zero has not been corrected as the soil permittivity is not a priori precisely known, thus the arrival time of the clutter will serve as a reference to the arrival times of the hyperbola apexes. Comparing to the experimental WARR measurements in Figures 6b and6d, we remark that a few ground waves superimposed the reflected waves mostly in the parallel configuration. The arrival times of the clutter has been estimated to 4 and 4.2 ns in the parallel and mirror configurations respectively. Consequently, the time difference observed in the mirror configuration between the arrival of the clutter and the hyperbola apex is close to 1 ns, that corresponds to a real permittivity value of 3. This value has been confirmed when fitting both hyperbolas associated with the two buried objects. The probing of this soil structure highlights that the TM polarizations is preferred to detect a pipe filled with water and a very thin strip. The width of the objects cannot be estimated because of the significant lateral dimension of the radar as compared to their sizes, however we can observe that the strip gives a narrower hyperbola signature.

This soil structure has been reconsidered to include an air-filled pipe with air and the strip positioned horizontally a visualized in Figure 14a. From the B-scans presented in Figures 14b and14c, we notice that the arrival times associated with the apexes in both polarizations appear similar to the previous results. Furthermore, we remark that the TM polarization is not able to detect the air-filled pipe; this result agrees with the analysis of the SWs made from Figure 8d. The detection of the strip having a 1 mm lateral dimension is now possible using both polarizations.

Figure 14 A 20 mm diameter nylon pipe and a 12 mm conductive pipe have been now buried in the sand box as illustrated in Figure 15a. From B-scans in Figures 15b and15c, we notice that when the dielectric contrast between the soil and the buried object is weak, the TM polarization is not able to make a detection. However, the TE polarization reveals a non contrasted hyperbola. According to previous results, the conductive pipe is better detected in the TM polarization. Because of the lack of contrast in this experiment, we have only plotted hyperbolas using the analytical modeling. The arrival times agree with those obtained in previous experimental radargrams.

Finally, two canonical cracks filled with carboard have been made into the sand as shown in ) ; in this case the arrival time difference has been estimated to 0.5 ns that corresponds to the analytical modeling.

Conclusion

A parametric study associated with a novel compact UWB ground-coupled GPR radar operating in the frequency band [0.46 ; 4] GHz is presented in this work. This study has allowed to first characterize the radiating characteristics of each antenna, and then the radar system itself considering the two polarizations TM and TE. The performance of the GPR system in detecting very long buried dielectric or conductive objects has been particularly considered by comparing FDTD full-wave simulations and experimental results. The results highlight that the polarization diversity allows to discriminate the dielectric contrast between the buried object and the surrounding medium. Thus, the TM polarization is preferred to detect water-filled (higher real permittivity than the soil) or conductive pipes, and the TE polarization appears suitable for detecting air-filled (lower real permittivity than the soil)

  , has been modified to operate in an UWB from frequency 460 MHz to beyond 4 GHz (reflection coefficient ) ( 11 f S dB less than -10 dB) and at lower frequencies as usual with a reduced size close to the A4 sheet size [4-9]. The antenna has been designed on a single-sided FR4 substrate ( in Figure 1b, the antenna is fed at its port by a tapered coplanar waveguide CPW line with length

.

  The printed face of the antenna, positioned very close to the soil at an elevation s h around 10 mm to consider potential irregularities on the soil surface, has been protected by a thin PVC sheet.

Figure 1 Measurements

 1 Figure 1

  Figure 6a, 6c highlights a higher coupling between both antennas in the measurements with a ) ( 21 f S

Figure 4 From 4 ]

 44 Figure 4

Figure 5 Figure 6

 56 Figure 5

Figure 7 Considering

 7 Figure 7

  surrounding medium. We remark that the TE component oscillates under the TM component for a radius higher than 5 mm. In general, the scattering width increases with the pipe radius and when the radius becomes large as compared to the wavelength of the medium; at 2 GHz,

..

  The excitation current has the shape of the derivative of the Gaussian function with a time zero estimated to 0.3 ns and a duration (99% of the total energy) of 0.5 ns.A 5 mm-width rectangular air-filled crack of height 75 mm opened towards the soil interface has been first probed in the parallel and mirror configurations, as shown in Figures9a and 9b.The crack is centered at the position displacement step used in the simulations is 40 mm. The real permittivity of the soil considered is To reduce the antenna coupling expressed in the B-scans by horizontal lines having different polarities, the horizontal median value associated with each time sample has been removed as presented in

Figure 10 A

 10 Figure 10

Figure 12

 12 Figure 12

Figure 16a .

 16a Figure 16a. Their average width from the left and the right has been estimated to 18 mm and their height is 75 and 150 mm respectively. Raw B-scans associated with both TM and TE polarizations presented in Figures16b and 16crespectively show that the hyperbolas have a slope corresponding to the propagation in the sand; the time zero has been corrected using the WARR B-scan in Figure6b and 6d. We remark that the hyperbolas appear with a weak contrast in the B-scans, and they are more detectable in the mirror configuration. This observation has been confirmed by the theoretical raw B-scan associated with two air-filled cracks at position y=-442.5 and 162.5 mm visualized in Figure 17 in the case of the mirror configuration (common soil 1 ' . 01 . 0 , 5 . 5 -= = m S s σ ε

Figure 1 :Figure 2 :

 12 Figure 1: Geometry of the bowtie slot antenna (a) top view, (b) tappered CPW feed line, and (c) antenna shielded by a back-cavity filled with a layered radar absorbing material Figure 2: Radiation properties of the bowtie slot antenna: (a) Comparison between theoretical and experimental S11 versus frequency; (b) E-field distribution in the TM and TE planes, and (c) radiation patterns of the shielded antenna at 800 MHz

Figure 3 :Figure 4 :Figure 5 :)

 345 Figure 3: The parallel (TM polarization) and mirror (TE polarization) configurations modeled under FDTD simulations Figure 4: The experimental outdoor setup filled with wet sand in both (a) parallel, and (b) mirror configurations Figure 5: FDTD simulation results associated with WARR probing on a common soil ( 1 ' . 01 . 0 , 5 . 5 -= = m S s σ ε

Figure 6 :

 6 Figure 6: Experimental results associated with WARR probing on the sandy box (square Perichaux, Paris 15 th ) in the frequency and time domains in both parallel (a, b) and mirror (c, d) configurations

Figure 7 :Figure 8 :Figure 9 :Figure 10 :

 78910 Figure 7: The simplified analytical modeling based on the ray-tracing theory: (a) cross-view of the soil including a cylindrical pipe, and (b) plots of hyperbolas considering the dimensions of the experimental GPR systems in both configurations of polarization (d=150 mm, R=10 mm, offset=60 mm) Figure 8: Influence of the pipe radius and the real permittivity on the scattering width (SW) as a function of the frequency in the case of a conductive (a,b) and a dielectric air-filled cylinder (c,d) Figure 9: Probing issued from FDTD simulations (soil ε'=5.5; σ=0.01 S/m) of an opened rectangular crack filled with air in the (a) parallel, and (b) mirror configurations; B-scans associated with (c) the parallel and (d) the mirror configurations Figure 10: (a) Comparison of waveforms at the apex (median value removed, soil ε'=5.5; σ=0.01 S/m) issued from the probing of the rectangular air-filled crack in the parallel and mirror configurations; (b) Comparison of hyperbolas extracted from numerical B-scans (soil ε'=5.5; ; σ=0.01 S/m) and associated with a rectangular and a V-crack with 5 mm width

Figure 11 :

 11 Figure 11: Probing issued from FDTD simulations of a buried (soil ε'=3.5; σ=0.01 S/m) conductive cylindrical pipe in (a) the parallel, and (b) mirror configurations; B-scans associated with (c) the parallel and (d) the mirror configurations

Figure 12 :

 12 Figure 12: Comparison of the theoretical waveforms straight above the cylindrical pipe at the hyperbola apex associated with the parallel and mirror configurations

Figure 13 :Figure 14 :Figure 15 :Figure 16 :

 13141516 Figure 13: (a) Experimental setup associated with the probing of a water-filled cylindrical pipe and a vertical conductive strip; B-scans (with median value removed) associated with (b) the parallel and (c) mirror configurations Figure 14: (a) Experimental setup associated with the probing of an air-filled cylindrical pipe and a horizontal conductive strip; B-scans (with median value removed) associated with (b) the parallel and (c) mirror configurations Figure 15: (a) Experimental setup associated with the probing of a solid nylon pipe and a conductive pipe; associated with (b) the parallel (raw image) and (c) mirror (with medium value removed) configurations Figure 16: (a) Experimental setup associated with the probing of two opened 18 mm width cracks with heights 75 and 150 mm; B-scans (raw images) associated with (b) the parallel and (c) mirror configurations

Figure 17 :

 17 Figure 17: Theoretical B-scan (raw image) obtained from FDTD simulations of two opened 18 mm width cracks with heights 75 and 150 mm in a common soil 1 ' . 01 . 0 , 5 . 5 -= = m S s σ ε

Acknowledgments

The authors are grateful to the Sense-city project leaders who have accepted to bury utilities for research studies with GPR systems.

pipes. The polarizations of the transmitting and receiving antennas (co-polarization or cross polarization) that play a significant role in the detection of long object can play a significant role in improving the signal to clutter ratio [START_REF] Khuut | Application of Polarimetric GPR to detection of subsurface objects[END_REF][START_REF] Chen | Fully-polarimetric ground penetrating radar application[END_REF][START_REF] Tebchrany | Assessement of statistical-based clutter reduction techniques on ground-coupled GPR data for the detection of buried objects and cracks in soil[END_REF]. First studies [START_REF] Chen | Fully-polarimetric ground penetrating radar application[END_REF][START_REF] Tebchrany | Assessement of statistical-based clutter reduction techniques on ground-coupled GPR data for the detection of buried objects and cracks in soil[END_REF] need to be deepened to characterize the clutter for different target orientations with respect to the incident electric field and dielectric characteristics. This characterization will facilitate the reduction of the clutter in a given polarization. In subsequent studies soon proposed for publication, the authors have developed a semi-automatic algorithm for hyperbola detection based on template matching in the presence of overlapping signatures to detect a specific hyperbola pattern that has been used as a reference in the similarity measure. Afterwards, the parametric analysis of each hyperbola associated with the first arrival times has allowed to obtain estimates of the depth, size and soil real permittivity. Further studies will be focused on the sounding of the subsurface of our novel test site that will be built in the project Sense-City [18]. This subsurface will contain several buried utilities with different shapes (pipes and strips filled) and dielectric characteristics (conductor, air, and water) buried in parallel trenches. In particular, the influence of the polarization and the dielectric contrast of the objects with the surrounding medium will be studied.

Highlights

• Design of a shielded UWB bowtie slot antenna at frequencies 460 MHz to beyond 4 GHz • 3D FDTD simulations of a GPR system as a function of various parameters • Imaging of dielectric and conductive pipes using polarization diversity • Comparison of theoretical and experimental B-scans with buried pipes in a sand


Marcos Roberto Ribeiro
email: marcos.ribeiro@ifmg.edu.br

Maria Camila
email: camila.barioni@ufu.br

N Barioni

Sandra De Amo
email: deamo@ufu.br

Claudia Roncancio
email: claudia.roncancio@imag.fr

Cyril Labbé
email: cyril.labbe@imag.fr

Temporal Conditional Preference Queries on Streams

Keywords: Data streams, Preference queries, Temporal preferences

come

Introduction

There is a variety of application domains which data naturally occur in the form of a sequence of values, such as financial applications, sport players monitoring, telecommunications, web applications, sensor networks, among others. An especially useful model explored by many research works to deal with this type of data is the data stream model [START_REF] Arasu | STREAM: The Stanford Data Stream Management System[END_REF][START_REF] Hirzel | A catalog of stream processing optimizations[END_REF][START_REF] Margara | Streaming the web: Reasoning over dynamic data[END_REF][START_REF] Golab | Issues in data stream management[END_REF]. Great part of these research works has focused on the development of new techniques to answer continuous queries efficiently [START_REF] Arasu | The CQL continuous query language: semantic foundations and query execution[END_REF][START_REF] Liu | An efficient approach of processing multiple continuous queries[END_REF]. Other research works have been concerned with the evaluation of preferences in continuous queries to monitor for information that best fit the users wishes when processing data streams [START_REF] Kontaki | Continuous top-k dominating queries[END_REF].

The research literature regarding this later issue is rich in works dealing with processing of continuous skyline queries where the preferences are simple independent preferences for minimum or maximum values over attributes [START_REF] Chomicki | Skyline queries, front and back[END_REF][START_REF] Lee | Efficient processing of multiple continuous skyline queries over a data stream[END_REF]. However, these works do not meet the needs of many domain applications that require the users to express conditional preferences. That is, those applications where the preferences over a data attribute can be affected by values of another data attribute. Moreover, they do not take advantage of the implicit temporal information of data streams to deal with temporal preferences.

Temporal preferences may allow users to express how an instant of time may influence his preferences at another time moment. Therefore, it allows an application to employ continuous queries to find sequences of patterns in data according to user preferences. For example, considering a soccer game where players are monitored, it is possible for a coach to check if some player behavior matches certain preferences before making an intervention in the game. Thus, it is possible to evaluate queries such as "Which are the best players considering that if a player was at defensive intermediary, then I prefer that this player go to the middle-field instead of staying in the same place?".

The evaluation of continuous queries with conditional preference has already been explored in previous works [START_REF] De Amo | Continuous processing of conditional preference queries[END_REF][START_REF] Petit | Top-k context-aware queries on streams[END_REF]. Nevertheless, to the best of our knowledge, the support for temporal conditional preference queries on data streams began to be exploited recently in our previous paper [START_REF] Ribeiro | Reasoning with temporal preferences over data streams[END_REF]. The main goal herein is to present an extension for the Continuous Query Language (CQL) that is specially tailored to efficiently process temporal conditional preference queries on data streams. Although CQL is an expressive SQL-based declarative language [START_REF] Arasu | The CQL continuous query language: semantic foundations and query execution[END_REF][START_REF] Arasu | STREAM: The Stanford Data Stream Management System[END_REF], it was not designed to deal with temporal preferences. In order to cope with this issue, we define appropriate data structures for keeping the temporal order of tuples and new specific operators for selecting the best sequences according to users preferences. These new features allow our approach to achieve a considerable better performance.

Main Contributions. The main contributions of this paper can be summarized as follows: (1) The definition of new operators for the evaluation of continuous queries containing temporal conditional preferences; (2) A new and efficient incremental method for the evaluation of the proposed preference operator; (3) A detailed demonstration of the CQL equivalences for the proposed operators; (4) An extensive set of experiments showing that our proposed operators have better performance than their equivalent operations in CQL.

In the following sections, we introduce a motivating example. In addition, we present the fundamental concepts regarding the temporal conditional preferences and describe the operators and algorithms proposed for the evaluation of temporal conditional preference queries on data streams. We also discuss the equivalent operations in CQL and the experimental results. Finally, at the end we give the conclusions of this paper.

A Motivating Example

Philip is a soccer coach who uses technology to make decisions. He has access to an information system that provides real-time data about players during a match. The information available is the stream Event(PID, PC, PE) containing the match events along with an identification of the involved players. The attributes of the stream Event are: player identification (PID), current place (PC) and the match event (PE). The values for PC are the regions showed in Fig. 1. The match events (PE) are: carrying the ball (ca), completed pass (cp), dribble (dr), losing the ball (lb), non-completed pass (ncp) and pass reception (re). Based on his experience, Philip has the following preferences: [P1] If the previous in-game event was a pass reception then I prefer a dribble than a completed pass, independent of the place; [P2] Completed passes are better than non-completed passes; [P3] If all previous in-game events were in the middle-field then I prefer events in the middle-field than events in the defensive intermediary.

These preferences can be used by Philip to submit the following continuous query to the information system: [Q1] Every instant, give me the in-game event sequences that best fit my preferences in the last six seconds. When the coach says "best fit my preferences" it means that if a data item X is in the query result then it is not possible to find another response better than X according to his preferences. The query answers could help the coach to give special attention to a particular player having behavior fitting the coach preferences.

Background: Temporal Conditional Preferences

Our proposed language, called StreamPref, uses the formalism introduced in our previous work [START_REF] Ribeiro | Reasoning with temporal preferences over data streams[END_REF] to compare sequences of tuples. Let Dom(A) be the domain of the attribute A. Let R(A 1 , ..., A l ) be a relational schema. The set of all tuples over R is denoted by Tup(R) = Dom(A 1 )×...×Dom(A l ). A sequence s = t 1 , ..., t n over R is an ordered set of tuples, such that t i ∈ Tup(R) for all i ∈ {1, ..., n}. The length of a sequence s is denoted by |s|. A tuple in the position i of a sequence s is denoted by s[i] and s[i].A represents the attribute A in the position i of s. We use s[i, j] to denote the subsequence s = t i , ..., t j of s = t 1 , ..., t n such that 1 ≤ i ≤ n and i ≤ j ≤ n. The concatenation s of two sequences s = t 1 , ..., t n and s = t 1 , ..., t n , denoted by s + s , is s = t 1 , ..., t n , t 1 , ..., t n . We denote by Seq(R) the set of all possible sequences over R.

Our preference model uses StreamPref Temporal Logic (STL) formulas composed by propositions in the form Aθa, where a ∈ Dom(A) and θ ∈ {<, ≤, =, =, ≥, >} (see Definition 1). Let Q(A) be a proposition,

S Q(A) = {a ∈ Dom(A) | a |= Q(A)} denotes the set of values satisfying Q(A).
Definition 1 (STL Formulas). The STL formulas are defined as follows:

(1) true and false are STL formulas; (2) If F is a proposition then F is a STL formula; (3) If F and G are STL formulas then (F ∧ G), (F ∨ G), (F Since G), ¬F and ¬G are STL formulas.

A STL formula F is satisfied by a sequence s = t 1 , ..., t n at a position i ∈ {1, ..., n}, denoted by (s, i) |= F , according to the following conditions:

(1) (s, i) |= Q(A) if and only if s[i].A |= Q(A); (2) (s, i) |= F ∧ G if and only if (s, i) |= F and (s, i) |= G; (3) (s, i) |= F ∨ G if and only if (s, i) |= F or (s, i) |= G; (4) (s, i) |= ¬F if and only if (s, i) |= F ; (5) (s, i) |= (F since G) if
and only if there exists j where 1 ≤ j < i and (s, j) |= G and (s, k) |= F for all k ∈ {j + 1, ..., i}. The true formula is always satisfied and the false formula is never satisfied. We also define the following derived formulas:

Prev Q(A): Equivalent to (false since Q(A)), (s, i) |= Prev Q(A) if and only if i > 1 and (s, i -1) |= F ; SomePrev Q(A): Equivalent to (true since Q(A)), (s, i) |= SomePrev Q(A)
if and only if there exists j such that 1 ≤ j < i and (s, i)

|= Q(A); AllPrev Q(A): Equivalent to ¬(SomePrev¬Q(A)), (s, i) |= AllPrev Q(A) if
and only if (s, j) |= F for all j ∈ {1, ..., i -1}; First: Equivalent to ¬(Prev(true)), (s, i) |= First if and only if i = 1.

The Definition 2 formalizes the temporal conditions used by Definition 3 (tcp-rules and tcp-theories).

Definition 2 (Temporal Conditions).

A temporal condition is a formula F = F 1 ∧ ... ∧ F n , where F 1 , ..., F n are propositions or derived formulas. The temporal components of F , denoted by F ← , is the conjunction of all derived formulas in F . The non-temporal components of F , denoted by F • , is the conjunction of all propositions in F and not present in F ← . We use Att(F ) to denote the attributes appearing in F . Definition 3 (TCP-Rules and TCP-Theories). Let R be a relational schema. A temporal conditional preference rule, or tcp-rule, is an expression in the format ϕ :

C ϕ → Q + ϕ Q - ϕ [W ϕ ],
where: (1) The propositions Q + ϕ and Q - ϕ represent the preferred values and non-preferred values for the preference attribute A ϕ , respectively, such that

S Q + ϕ ∩ S Q - ϕ = ∅; (2) W ϕ ⊂ R is the set of indifferent attributes such that A ϕ / ∈ W ϕ ; (3) C ϕ is a temporal condition such that Att(C • ϕ ) ∩ ({A ϕ } ∪ W ϕ ) = ∅.
A temporal conditional preference theory, or tcp-theory, is a finite set of tcp-rules.

Example 1. Consider the coach preferences of Section 2. We can express them by the tcp-theory Φ = {ϕ 1 , ϕ 2 , ϕ 3 }, where ϕ 1 :

Prev(PE = re) → (PE = dr) (PE = cp)[PC]; ϕ 2 : → (PE = cp) (PE = ncp); ϕ 3 : AllPrev(PC = mf ) → (PC = mf ) (PC = di).
Given a tcp-rule ϕ and two sequences s, s . We say that s is preferred to s (or s dominates s ) according to ϕ, denoted by s ϕ s if and only if there exists a position i such that:

(1) s[j] = s [j] for all j ∈ {1, ..., i -1}; (2) (s, i) |= C ϕ and (s , i) |= C ϕ ; (3) s[i].A ϕ |= Q + ϕ and s [i].A ϕ |= Q - ϕ ; (4) s[i].A = s [i].A for all A / ∈ ({A ϕ } ∪ W ϕ ) (ceteris paribus semantic).
The notation Φ represents the transitive closure of ϕ∈Φ ϕ . The notation s Φ s means that s is preferred to s according to Φ. When two sequences cannot be compared, we say that they are incomparable. We also must consider consistency issues when dealing with order induced by rules to avoid inferences like "a sequence is preferred to itself". So, we check the consistency of tcp-theories using the test proposed in [START_REF] Ribeiro | Reasoning with temporal preferences over data streams[END_REF] before the query execution.

Our StreamPref language introduces the operators SEQ and BESTSEQ. The SEQ operator extracts sequences from data streams preserving the temporal order of tuples and the BESTSEQ operator selects the best extracted sequences according to the defined temporal preferences. If it is necessary, our operators can be combined with the existing CQL operators to create more sophisticated queries. As we will see in the next section, our operators can be processed by equivalent CQL operations. However, the definition of these equivalences is not trivial and our operators have better performance than their CQL equivalent operations.

The SEQ Operator. The SEQ operator retrieves identified sequences (Definition 4) over a data stream according to: a set of identifier attributes (X), a temporal range (n) and a slide interval (d). The parameters n and d are used to select a portion of tuples from a data stream analogous to the selection performed by the sliding window approach [START_REF] Arasu | The CQL continuous query language: semantic foundations and query execution[END_REF][START_REF] Petit | An algebric window model for data stream management[END_REF]. The parameter X is used to group the tuples with the same identifier in a sequence. It is important to note that the values for the identifier attributes must be unique at every instant to keep a relation one-to-one between tuples and sequences. Definition 4 (Identified Sequences). Let S(A 1 , ..., A l ) be a stream. Let Y and X be two disjoint sets such that X ∪Y = {A 1 , ..., A l }. An identified sequence s x = t 1 , ..., t n from S is a sequence where t i ∈ Tup(Y ) for all i ∈ {1, ..., n} and x ∈ Tup(X). 2 where TS is the timestamp (instant). The sequence extraction needed by query Q1 presented in the motivating example is performed by operation SEQ {PID},6,1 (Event) as follows: TS 1: s 1 = (mf, re) ; TS 2: s 1 = (mf, re), (oi, dr) , TS 3: s 1 = (mf, re), (oi, dr), (oi, cp) , s 2 = (mf, re) ; TS 4: s 1 = (mf, re), (oi, dr), (oi, cp) , s 2 = (mf, re), (oi, cp) ; TS 5: s 1 = (mf, re), (oi, dr), (oi, cp) , s 2 = (mf, re), (oi, cp), (oi, lb) ; TS 6: s 1 = (mf, re), (oi, dr), (oi, cp) , s 2 = (mf, re), (oi, cp), (oi, lb) , s 3 = (mf, ca) ; TS 7: s 1 = (oi, dr), (oi, cp) , s 3 = (mf, ca), (mf, dr) ; TS 8: s 1 = (oi, cp) , s 2 = (mf, re), (oi, cp), (oi, lb) , s 3 = (mf, ca), (mf, dr), (di, ncp) , s 4 = (mf, ca) ; TS 9: s 2 = (oi, cp), (oi, lb) , s 3 = (mf, ca), (mf, dr), (di, ncp) , s 4 = (mf, ca), (mf, dr) ; TS 10: s 2 = (oi, lb) , s 3 = (mf, ca), (mf, dr), (di, ncp) , s 4 = (mf, ca), (mf, dr), (mf, cp) . Note that from TS 7 the SEQ operator appends the new tuples and drops the expired positions in the beginning of the sequences.

The BESTSEQ Operator. Let Z be a set of sequences and Φ be a tcp-theory. The operation BESTSEQ Φ (Z) returns the dominant sequences in Z according to Φ. A sequence s ∈ Z is dominant according to Φ, if s ∈ Z such that s Φ s.

Example 3. Let Z be the extracted sequences of Example 2 and Φ be the tcp-theory of Example 1. The query Q1 is computed by the operation BESTSEQ Φ (SEQ {PID},6,1 (Event)) as follows: TS 1: {s 1 } (the unique input sequence); TS 2: {s 1 } (same result of TS 1); TS 3: {s 1 , s 2 } (incomparable sequences); TS 4: {s 1 } (s 1 ϕ1 s 2 ); TS 5: {s 1 } (same result of TS 4); TS 6: {s 1 , s 3 } (s 1 ϕ1 s 2 and s 3 is incomparable); TS 7: {s 1 , s 2 , s 3 } (incomparable sequences); TS 8: {s 1 , s 2 , s 3 , s 4 } (incomparable sequences); TS 9: {s 2 , s 3 , s 4 } (incomparable sequences); TS 10: {s 2 , s 4 } (s 4 ϕ2 ... ϕ3 s 3 and s 2 is incomparable).

CQL Equivalences

This section demonstrates how our StreamPref operators can be translated to CQL equivalent operations. It is worth noting that although this means the StreamPref does not increase the expression power of CQL, the equivalences are not trivial. Moreover, the evaluation of the StreamPref operators are more efficient than their CQL equivalent operations (see Section 7). The equivalences consider a stream S(A 1 , ..., A l ) and the identifier X = {A 1 }. Although, we can use any subset of {A 1 , ..., A l } as identifier without lost of generality. In addition, the CQL equivalences represent the sequences using relations containing the attribute POS to identify the position of the tuples.

We use the symbols π, -, , γ, σ and ∪ for the CQL operators that are equivalent to the traditional operations: projection, set difference, join, aggregation function, selection and union, respectively. The RSTREAM is a CQL operator to convert a relation to a stream and the symbol is the CQL sliding window operator. The notation TS() returns the original timestamp of the tuple. We rename an attribute A to A by using the notation A → A in the projection operator.

Equivalence for the SEQ Operator. Equation (1) establishes the CQL equivalence for the SEQ operator such that P 0 = {} and i ∈ {1, ..., n}.

W 0 = π POS,A1 ( n,d (RSTREAM(π TS() →POS,A1,...,A l ( 1,1 (S))))) (1a) W i = W i-1 -P i-1 (1b) P i = γ A1,min(POS) →POS (W i ) A1,POS W (1c) SEQ {A1},n,d (S) = π 1 →POS,A1,...A l (P 1 ) ∪ ... ∪ π n →POS,A1,...A l (P n ) (1d)
Equivalence for the BESTSEQ Operator. The CQL equivalence for the BEST-SEQ operator is computed over a relation Z(POS, A 1 , ..., A l ) containing the input sequences where {A 1 } is the identifier and POS is the position attribute. First, Equation (2) calculates the position to compare every pair of sequences.

Z = π POS,A1 →B ,A2 →A 2 ,...,A l →A l (Z) (2a) P nc = σ A2 =A 2 ∨...∨A l =A l (π POS,A1 →B,A2,...,A l (Z) POS Z ) (2b) P = γ B,B ,min(POS) →POS (P nc ) (2c)
The next step is to identify the sequence positions satisfying the temporal components of the rule conditions. Equation (3) calculates the positions satisfied by every derived formula.

P First = π POS,B (σ POS=1 (P )) (3a) P Prev Q(A) = π POS,B (P POS,B (π (POS+1) →POS,A1 →B (σ Q(A) (Z)))) (3b) P SomePrev Q(A) = π POS,B (σ POS>POS' (P B (γ A1 →B,min(POS) →POS' (σ Q(A) (Z))))) (3c) P max = γ A1 →B,max(POS) →POS (P ) (3d) P ¬Q(A) = γ B,min(POS) →POS' (π POS,A1 →B (σ ¬Q(A) (Z)) ∪ P max ) (3e) P AllPrev Q(A) = π POS,B (σ POS≤POS'∧POS>1 (P B (P ¬Q(A) ))) (3f)
Next, Equation (4) computes the relation R i containing the positions satisfied by condition C ← ϕi = F 1 ∧ ... ∧ F p for every tcp-rule ϕ i ∈ Φ.

P j =        P First , if F j = First P Prev Q(A) , if F j = Prev(Q(A)) P SomePrev Q(A) , if F j = SomePrev(Q(A)) P AllPrev Q(A) , if F j = AllPrev(Q(A)) (4a) R i = (P 1 ) POS,B ... POS,B (P p ) (4b)
Equation ( 5) performs the direct comparisons for every ϕ i ∈ Φ. This equation also consider the tuples of Tup(S) for posterior computation of the transitive closure. The relations D + i and D - i represent the tuples satisfying respectively the preferred values and the non-preferred values of ϕ i . These tuples include original tuples (from existing positions) and fake tuples from Tup(S). We use the attribute A t to separate these tuples (A t = 1 for original tuples and A t = 0 for fake tuples). Note that the Equation (5e) applies the filter

E ϕi : (A i1 = A i1 )∧ ... ∧ (A ij = A ij ) such that {A i1 , ..., A ij } = ({A 1 , ..., A l } -{A ϕi , B, B } -W ϕi ).
This filter is required to follow the ceteris paribus semantic.

Z + i = π POS,B (R i ) POS,B (σ C • ϕ i ∧Q + ϕ i (π POS,A1 →B,...,A l ,1 →At (Z))) (5a)
D + i = Z + i ∪ (π POS,B (R i ) B (π A1 →B,...,A l ,0 →At (σ C • ϕ i ∧Q + ϕ i (Tup(S))))) (5b)
Z - i = π POS,B (R i ) POS,B (σ C • ϕ i ∧Q - ϕ i (π POS,A1 →B ,...,A l ,1 →At (Z))) (5c)
D - i = Z - i ∪ (π POS,B (R i ) B (π A1 →B ,...,A l ,0 →At (σ C • ϕ i ∧Q - ϕ i (Tup(S))))) (5d) D i = σ Eϕ i (P POS,B,B (D + i POS (π POS,B ,A2 →A 2 ,...,A l →A l ,At →A t (D - i )))) (5e)
Equation ( 6) calculates the transitive closure. The relations T i , T i and T i are computed for i ∈ {2, ..., m}. In the end, T m has all comparisons imposed by Φ where m = |Φ| is the number of tcp-rules.

T 1 = D 1 ∪ ... ∪ D m (6a) T i = π (POS,B,B ,A2,...,A l ,At,A 2 →A 2 ,...,A l →A l ,A t →A t ) (T i-1 ) (6b) T i = π (POS,B,B ,A2 →A 2 ,...,A l →A l ,At →A t ,A 2 ,...,A l ,A t ) (T i-1 ) (6c) T i = π POS,B,B ,A2,...,A l ,At,A 2 ,...,A l ,A t (T i POS,B,B ,A 2 ,...,A l T i ) ∪ T i-1 (6d)
Equation ( 7) calculates the dominant sequences. Observe that just comparisons between original tuples are considered (A t = 1 ∧ A t = 1).

BESTSEQ Φ (Z) = Z A1 (π A1 (Z) -π B →A1 (σ At=1∧A t =1 (T m ))) (7)
6 Data Structures and Algorithms

Our previous work [START_REF] Ribeiro | Reasoning with temporal preferences over data streams[END_REF] proposed the algorithm ExtractSeq for extracting sequences and the algorithm BestSeq for computing the dominant sequences. The StreamPref operators SEQ and BESTSEQ can be evaluated by the algorithms ExtractSeq and BestSeq, respectively. However, only the algorithm ExtractSeq uses an incremental method suitable for data streams scenarios. In this paper we propose a new incremental method to evaluate the BESTSEQ operator.

Index Structure. The main idea of our incremental method is to keep an index tree built using the sequence tuples. Given a sequence s = t 1 , ..., t n , every tuple t i is represented by a node in the tree. The tuple t 1 is a child of the root node.

For the remaining tuples, every t i is a father of t i+1 . The sequence s is stored in the node t n .

Example 4. Consider the sequences of the Example 2 at TS 6. Fig. 3(a) shows how these sequences are stored in the index tree. The root node, represented by black circle, is an empty node without an associated tuple.

• (mf, ca)

[s3] (mf, re)

(oi, cp) (oi, lb) [s2]
(oi, dr) Starting from the root node, it is possible to find the position where two sequences must be compared. For instance, consider the sequences s 1 and s 2 in the tree of Fig. 3(a). The paths from the root to these sequences are different in the second node. Thus, the comparison of s 1 and s 2 happens in the position 2.

(oi, cp) [s1] (a
The index is updated only for changed sequences and new sequences. The new sequences are just inserted in the tree. When positions are deleted from a sequence s (and s is still no empty), we reinsert s in the tree. The empty sequences are dropped from the tree. If a sequence s has new tuples (and no expired tuples), we move s to a child branch of its current node.

Given a node nd, nd.t is the tuple associated to nd and nd.Z represents the set of sequences stored in nd. The children of nd are stored in a hash-table nd.Ch mapping the associated tuples to the respective child nodes. In addition, each node nd stores a preference hierarchy nd.H over the tuples of the child nodes. The preference hierarchy allows to determine if a child node is dominant or is dominated. Thus, it is possible to know if a sequence dominates another one.

Preference Hierarchy. Our preference hierarchy structure is based on the preference partition technique originally proposed in our previous work [START_REF] Ribeiro | Efficient algorithms for processing preference queries[END_REF]. The main idea is to build a knowledge base for the preferences valid in a node and keep a structure containing the preferred and non-preferred tuples according to such preferences. Given a set of non-temporal preference rules Γ . The knowledge base K Γ over Γ is a set of comparisons in the format b :

F + b F - b [W b ]. The terms F +
b and F - b are formulas representing the preferred values and non-preferred values, respectively. The term W b is the set of indifferent attributes of b. For more details about the construction of the knowledge base, please see [START_REF] Ribeiro | Efficient algorithms for processing preference queries[END_REF].

After the construction of K Γ , the preference hierarchy is built by grouping the child node tuples into subsets called partitions. For every comparison b ∈ K Γ , we group the tuples into partitions according to the attribute values not in W b . If a partition does not contain preferred tuples (those satisfying F + b ), then all tuples of this partition are dominant. On the other hand, if a partition has at least one preferred tuple, then all non-preferred tuples (those satisfying F - b ) are dominated. Therefore, a tuple t is dominant if t is not dominated in any partition.

Example 5. Consider again the tcp-theory Φ of the Example 2 and the tree of the Fig. 3(a). The preference hierarchy of the node (mf, re) is built using the non-temporal components of the rules temporally valid in the last position of the sequence s = (mf, re), t , where t is any tuple (t is not used to temporally validate the rules). For this node, all rules are used. So, we have the knowledge base

K Γ over Γ = {ϕ • 1 , ϕ • 2 , ϕ • 3 } containing the comparisons b 1 : (PE = dr) (PE = ncp) [PC, PE]; b 2 : (PE = dr) (PE = cp) [PC, PE]; b 3 : (PC = mf ) ∧ (PE = dr) (PC = di) ∧ (PE = ncp) [PC, PE]; b 4 : (PC = mf ) (PC = di) [PC]; b 5 : (PE = cp) (PE = ncp) [PE]. Fig. 3(b)
shows the partitions imposed by K Γ . The symbols + andindicate if the tuple is preferred or non-preferred, respectively. We can see that (oi, cp) is dominated because it is a non-preferred tuple in the partition of the comparison b 2 containing a preferred tuple.

Our technique uses just the essential information to update the index efficiently. For every partition p, we keep the mappings Pref(p) and NonPref(p) representing the number of preferred tuples in p and the set on non-preferred tuples in p, respectively. Thus, a node nd is dominated if there exists p such that Pref(p) > 0 and nd.t ∈ NonPref(p).

The construction of the knowledge base is not a trivial task since we must compute comparisons representing the transitive closure imposed by the preferences [START_REF] Ribeiro | Efficient algorithms for processing preference queries[END_REF]. Thus, we also use a pruning strategy to avoid the construction of unnecessary preference hierarchies. Nodes having a unique child, do not need preference hierarchy since this child is always dominant. In addition, dominated nodes and their descendants do not require preference hierarchy. For example, in the tree of Fig. 3(a), we know that (oi, dr) dominates (oi, cp) according to the evaluate how the number of tuples per instant (equal to NSQ × 0.5) affects the algorithms. Table 1(b) displays the parameters used for sequence extraction. These parameters are temporal range (RAN) and slide interval (SLI) and they allow to evaluate how the selection of the stream elements influences the algorithms. Table 1(c) shows the parameters number of rules (RUL) and maximum preference level (LEV) employed for the generation of the preferences. These parameters allow us to evaluate how different preferences affect the cost of the sequence comparison done by the algorithms. We use rules in the form

ϕ i : First ∧ Q(A 3 ) → Q + (A 2 ) Q -(A 2 )[A 4 , A 5 ] and ϕ i+1 : PrevQ(A 3 ) ∧ SomePrevQ(A 4 ) ∧ AllPrevQ(A 5 ) ∧ Q(A 3 ) → Q + (A 2 ) Q -(A 2 )[A 4 , A 5 ] hav- ing variations on propositions Q + (A 2 ), Q -(A 2 ), Q(A 3 ), Q(A 4 ), Q(A 5 ).
The number of iterations is RAN plus maximum slide interval and the sequence identifier is the attribute A 1 . The definition of the parameter values was based on the experiments of related works [START_REF] Ribeiro | Reasoning with temporal preferences over data streams[END_REF][START_REF] Ribeiro | Efficient algorithms for processing preference queries[END_REF][START_REF] Lee | Efficient processing of multiple continuous skyline queries over a data stream[END_REF][START_REF] Pereira | Evaluation of conditional preference queries[END_REF][START_REF] Petit | An algebric window model for data stream management[END_REF]. For each experiment, we varied one parameter and fixed the default value for the others.

Real Datasets. We also used a real dataset containing play-by-play data of the 2014 soccer world cup 5 . This dataset contains 10,282 tuples from the last 4 matches. For this dataset we varied the parameters RAN and SLI. The values for RAN were 6, 12, 18, 24 and 30 seconds, where the default was 12 seconds. The values for SLI were 1, 3, 6, 9 and 12 seconds, where the default was 1 second. The experiments consider the average runtime per match which is the total runtime of all matches divided by the number of matches.

Experiments with the SEQ Operator. Fig. 4(a) and Fig. 4(b) show the experiment results with synthetic data confronting the SEQ operator (evaluated by the algorithm ExtractSeq) and its CQL equivalence. The first experiment considers the variation on the parameter ATT. Even for few attributes, the SEQ operator outperforms the CQL equivalence. Regarding the NSQ parameter, the SEQ operator has the best performance again. When there are more sequences, there are more tuples to be processed and the CQL operations are more expensive.

When examining the results obtained with different temporal ranges, it is possible to see that higher temporal ranges had greater impact on the CQL equivalence due to the generation of bigger sequences. Considering the results obtained for the SLI parameter, bigger slides caused more tuples expiration. So, once the sequences are smaller, the SEQ operator had the best performance. Finally, considering all experiments shown in Fig. 4(a), it is possible to see that the SEQ operator is more efficient than its CQL equivalence. Moreover, when comparing the memory usage displayed on Fig. 4(b), it is possible to verify that 5 Extracted from data available in http://data.huffingtonpost.com/2014/world-cup Experiments with the BESTSEQ Operator. Fig. 5(a) shows the runtime and Fig. 5(b) shows the memory usage for the experiments with the BESTSEQ operator with synthetic data. Notice that the runtime graphs are in logarithm scale. We can see that the CQL equivalence is slower than the remaining algorithms due to the processing of the intermediary operations. In addition, the incremental algorithm outperforms the naive algorithm due to the index tree and the pruning strategy. The same behavior is observed for the memory usage.

The results obtained for the parameters NSQ, RAN and RUL deserve to be highlighted. Considering the NSQ parameter, the behavior of the BESTSEQ algorithms is explained by the fact that when the number of sequences increases, we have more repetition of sequence identifiers and more chances for pruning. So, the updates in the index tree affect fewer branches and the incremental algorithm outperforms the naive algorithm.

Considering the RAN parameter, the incremental algorithm presents an advantage over the naive algorithm since longer sequences have more chances for overlapping. This behavior results in a more compact index tree and in a better performance for the incremental algorithm. Regarding the results obtained by the naive algorithm considering the RUL parameter, it is worth noting that the number of rules has a great impact in its complexity [START_REF] Ribeiro | Reasoning with temporal preferences over data streams[END_REF]. Moreover, more rules means more intermediary relations in the CQL equivalence as addressed by Equations ( 4) and [START_REF] Golab | Issues in data stream management[END_REF].

Fig. 5(c) and Fig. 5(d) show the results obtained for the BESTSEQ operator with the real data. Analyzing this figure, it is possible to see that the naive and the incremental algorithms outperform the CQL equivalence again. In addition, the CQL runtime cannot be applied in a real situation since a regular soccer match has duration of 5400 seconds. Regarding the memory usage, as expected, the CQL equivalence presented the greatest memory usage due to the storage of the intermediary relations. Both versions of BESTSEQ have a stable memory usage in all executions (around 20 MB).

Conclusion

In this paper we described the StreamPref query language presenting new operators to support temporal conditional preference queries on data streams. Stream-Pref extends the CQL language including the SEQ operator for the sequence extraction and the BESTSEQ preference operator for the selection of dominant sequences. Regarding the evaluation of this later operator, a new incremental algorithm was proposed. In addition, we also demonstrated the CQL equivalences for the proposed operators. It is worth noting that these equivalences are not trivial since they involve many complex operations. In our experiments, we compared the previous algorithms proposed in [START_REF] Ribeiro | Reasoning with temporal preferences over data streams[END_REF], the new incremental algorithm and their CQL equivalences. The experimental results showed that our proposed operators outperform the equivalent operations in CQL. Furthermore, our incremental algorithm achieved the best performance for evaluating the BESTSEQ operator.

Fig. 1 .

 1 Fig. 1. Values for attribute PC: (a) Field division; (b) Values description.

Fig. 2 .

 2 Fig. 2. Event streamExample 2. Consider the Event stream of Fig.2where TS is the timestamp (instant). The sequence extraction needed by query Q1 presented in the motivating example is performed by operation SEQ {PID},6,1 (Event) as follows: TS 1: s 1 = (mf, re) ; TS 2: s 1 = (mf, re), (oi, dr) , TS 3: s 1 = (mf, re), (oi, dr), (oi, cp) , s 2 = (mf, re) ; TS 4: s 1 = (mf, re), (oi, dr), (oi, cp) , s 2 = (mf, re), (oi, cp) ; TS 5: s 1 = (mf, re), (oi, dr), (oi, cp) , s 2 = (mf, re), (oi, cp), (oi, lb) ; TS 6: s 1 = (mf, re), (oi, dr), (oi, cp) , s 2 = (mf, re), (oi, cp), (oi, lb) , s 3 = (mf, ca) ; TS 7: s 1 = (oi, dr), (oi, cp) , s 3 = (mf, ca), (mf, dr) ; TS 8: s 1 = (oi, cp) , s 2 = (mf, re), (oi, cp), (oi, lb) , s 3 = (mf, ca), (mf, dr), (di, ncp) , s 4 = (mf, ca) ; TS 9: s 2 = (oi, cp), (oi, lb) , s 3 = (mf, ca), (mf, dr), (di, ncp) , s 4 = (mf, ca), (mf, dr) ; TS 10: s 2 = (oi, lb) , s 3 = (mf, ca), (mf, dr), (di, ncp) , s 4 = (mf, ca), (mf, dr), (mf, cp) . Note that from TS 7 the SEQ operator appends the new tuples and drops the expired positions in the beginning of the sequences.

Fig. 3 .

 3 Fig. 3. Preference hierarchy: (a) Index tree; (b) Partitions imposed by KΓ of (oi, 1, la).

Fig. 4 .

 4 Fig. 4. Experiment results for the SEQ operator: (a) Synthetic data runtime; (b) Synthetic data memory usage; (c) Real data runtime; (d) Real data memory usage. the CQL equivalence for the SEQ operator had a high memory usage in all experiments due to the extra tuples stored by the intermediary operations. Fig. 4(d) and Fig. 4(c) present the results obtained with the real data. These results are analogous to the ones obtained with the synthetic data. Analyzing these figures, it is possible to see that the SEQ operator outperforms the CQL equivalence for all the experiments.

Fig. 5 .

 5 Fig. 5. Experiment results of BESTSEQ operator: (a) Synthetic data runtime; (b) Synthetic data memory usage; (c) Real data runtime. (d) Real data memory usage.

Table 1 .

 1 Parameters for the experiments over synthetic data: (a) Dataset generation; (b) Sequence extraction; (c) Preferences.

		(a)		(b)		(c)
	Param.	Variation	Param.	Variation	Param.	Variation
	ATT 8, 10, 12, 14, 16	RAN 10, 20, 40, 60, 80, 100	RUL 4, 8, 16, 24, 32
	NSQ	4, 8, 16, 24, 32	SLI	1, 10, 20, 30, 40	LEV	1, 2, 3, 4, 5, 6

http://streampref.github.io

Acknowledgments. The authors thanks the Research Agencies CNPq, CAPES and FAPEMIG for supporting this work.

hierarchy of (mf, re). Thus, we do not need preference hierarchies for nodes in the branch starting at (oi, cp).

Algorithms. Our full index structure is composed by the tree nodes represented by its root and the mapping SeqNod. For every identified sequence s x , SeqNod(x) stores (s x , nd) where nd is the node where s x is stored. In addition, we use the sequence attributes deleted and inserted to keep the number of deletions and insertions in the last instant.

The algorithm IndexUpdate (see Algorithm 1) incrementally updates the index according to sequence changes. The first loop (lines 2-11) processes the changes for every sequence s x already stored. If s x has expired positions (s x .deleted > 0), we remove s x from the index. When s x is not empty (|s x | > 0), we add s x into I to be reinserted later since s x must be repositioned in the index tree. If s x has no expired positions and has inserted positions, the routine AddSeq reallocates s x from its current node. The second loop (lines 12-13) looks for sequences in Z not stored in the index and adds them into I. At the end, the algorithm stores the sequences of I and calls the routine Clean to remove empty nodes.

Algorithm 1: IndexUpdate(idx, Z)

The routine AddSeq (see Algorithm 2) performs the insertion of a sequence s x in the index tree. First, the routine checks if the depth (d) of node nd is equal to the length of s x (d = |s x |). If true, s x is stored into nd since the full path containing the tuples of s x is already created. Otherwise, the routine selects an existing child or creates a new one. At the end, the routine makes a recursion over this child node.

The algorithm IncBestSeq (see Algorithm 3) employs the index tree to evaluate the BESTSEQ operator incrementally. The execution starts at idx.root.

The algorithm acquires the sequences of input node nd and uses the preference hierarchy to select the dominant children of nd. Thus, for every dominant child, the algorithm makes a recursive call to retrieve all dominant sequences. Example 6. Consider again the index tree of Fig. 3(a) (the dominant nodes are in gray). The execution of IncBestSeq over this index tree works as follows:

(1) The execution starts at the root node. This node has no sequences and the algorithm makes a recursion over the dominant children (mf, ca) and (mf, re);

(2) At (mf, ca) the algorithm reaches the sequence s 3 . So, Z = {s 3 };

(3) At (mf, re), the algorithm performs a recursion over (oi, dr);

(4) At (oi, dr), the algorithm starts a recursion over (oi, cp);

(5) The algorithm reaches the sequence s 1 and returns Z = {s 1 , s 3 }.

Complexity. The complexity analysis of the algorithms takes into account the number of input sequences (k), the length of the largest sequence (n) and the number of tcp-rules in Φ (m). We also assume a constant factor for the number of attributes. In the worst case, the insertion or the deletion of a node tuple in the preference hierarchy has the cost O(m 4 ) (the size of K Γ [START_REF] Ribeiro | Efficient algorithms for processing preference queries[END_REF]). Moreover, in the worst case scenario, the degree of nodes is O(k), the tree depth is O(n) and the number of partitions associated to a child node is O(|K Γ |). Our mapping structures SeqNod, Ch, Pref and NonPrefSet are implemented using hash-tables. So, the retrieval and the storage of elements is performed with a cost of O(1).

In the worst case, the routine AddSeq reaches a leaf node and the routine Clean scans all tree nodes. So, the costs of AddSeq and Clean are O(nm 4 ) and O(k n m 4 ), respectively. The complexity of the algorithm IndexUpdate is O(k n m 4 ). Regarding the algorithm IncBestSeq, the selection of the dominant children has a cost of O(km 4 ). Thus, the complexity of IncBestSeq is O(k n m 4 ).

Experimental Results

Our experiments confront our proposed operators against their CQL counterparts to analyze the performance (runtime) and memory usage of both approaches. All experiments were carried out on a machine with a 3.2 GHz twelvecore processor and 32 GB of main memory, running Linux. The algorithms and all CQL operators were implemented in Python language. Synthetic Datasets. Due to the nonexistence of data generators suitable for the experiment parameters employed herein, we designed our own generator of synthetic datasets 4 . The synthetic datasets are in the format of streams composed by integer attributes. Table 1 shows the parameters (with default values in bold).

Table 1(a) presents the parameters related to the dataset generation. The number of attributes (ATT) allows to evaluate the behavior of the algorithms according to data dimensionality. The number of sequences (NSQ) allows to