Aurélie Suzanne
email: aurelie.suzanne@ls2n.fr

Guillaume Raschia
email: guillaume.raschia@ls2n.fr

José Martinez
email: jose.martinez@ls2n.fr

Damien Tassetti
email: damien.tassetti@etu.univ-nantes.fr

Slicing Techniques for Temporal Aggregation in Spanning Event Streams

Keywords: Data Stream, Spanning Events, Temporal Aggregates, Sliding Windows

Slicing is a popular approach to perform aggregation in streaming systems. It allows sharing computation costs among overlapping windows. However those systems are limited to point events. In this paper, we address the temporal aggregate computation issue in streams where events come with a duration, denoted as spanning event streams. After a short review of the new constraints ensued by event lifespan in a temporal sliding-window context, we propose a new structure for dealing with slices in such an environment, and prove that our technique is both correct and effective to deal with such spanning events. We then further extend this technique to compensate for the new constraints induced by the duration of spanning events with a multi-level structure able to reduce insertion costs.

Introduction

Windows have become a pillar of streaming systems. By keeping only the most recent data, they transform infinite flows of data into finite data sets, allowing aggregate functions. These aggregates continuously summarize the data, providing useful insights on the data at a low memory cost. Sliding windows advance across time, and, in many cases, two successive windows share events, leading to redundancy in computation between consecutive or intersecting windows. This redundancy can be avoided with slicing techniques that allow to pre-compute aggregates on sub-parts of the windows which can then be shared.

Up to now, these optimizations were limited to instantaneous events only, i.e., points in time, thereafter denoted as Point Event Streams (PES), and Spanning Event Streams (SES), where events are not assigned to a single point in time but rather to a time interval, have been overlooked. Those events also need to be handled efficiently, as they are used in many applications, e.g., monitoring systems like telecommunications or transportation. As an example, in a telecommunication network, antennas transmit spanning events like phone calls and monitoring them is crucial. A common metric would retrieve, every five minutes, the number of devices connected during the last fifteen minutes. With PES we would need to choose between the connection and disconnection of a device to an antenna as an indicator. With SES we can fully use the phone call interval, from connection to disconnection, hence improving the accuracy of the analysis. In that case, events with device connection, disconnection, or ongoing calls, can all three be handled correctly.

Problem Statement. In this communication we focus on the problem of efficient query processing for sliding windows dealing with SES. For this purpose we extend current streaming systems and their slicing techniques to SES. This extension cannot be done straightforwardly, as lifespan of events incurs side effects and an overhead cost on slice computation. Indeed, one spanning event may cover several slices, which implies that aggregates, such as the count of events, cannot be deduced from the partial aggregates in the covering slices. Figure 1 illustrates this problem. With spanning events on the right, the first window (orange bar) contains five events (blue lines), while the count of events we can deduce from the covering slices (green rectangles) is nine. With point events (blue triangles on the left), the direct count of events and the count from the slices coincide.

Contributions. In this paper, we propose a novel slicing technique designed for SES. Our technique relies on a new slice structure, adapted to the sensibility to duplication of aggregate functions. From that slice data model, we develop an event insertion workflow that takes care of events and slice bounds. We also propose a slice combination function to ensure that no duplication occurs at window release. As long events need to be inserted in potentially many slices, we further extend our technique to a multi-level data model which allows merging adjacent slices and reduce the number of insertions. Those aggregate computation techniques are agnostic to the way slices are created, such that one may use the best fitted stream slicer for a given use case.

Road Map. In order to do so, Section 2 deals with background definitions to extend streams and windows for spanning events. It subsequently gives key concepts to introduce an extension of the PES slice model required to support spanning events in Section 3. Section 4 presents an efficient generalization of that model. In Section 5 we expose and study algorithms to perform temporal aggregate computations in SES thanks to our slice data model. We experiment slicing algorithms supporting our model and its extension in Section 6, compared to state-of-the-art aggregation techniques. Then, Section 7 reviews prior works in the data stream and temporal database processing fields. We conclude in Section 8.

Preliminaries

Timeline and Time Intervals

Time is represented as an infinite, totally ordered, discrete set (T, ≺ T ), where each time point c is called a chronon [START_REF] Böhlen | Temporal Data Management : An Overview[END_REF]. (Discrete) Intervals are expressed with a lower and an upper bound, as pairs ( , u) ∈ T × T with ≺ T u. By convention, a time interval is written as a left-closed-right-opened interval [ , u). We denote by I ⊂ T × T the set of time intervals. For any t ∈ I, (t) ∈ t and u(t) / ∈ t are respectively the lower and upper bounds of the interval t. A chronon c can be represented by the interval [c, c + 1).

Two intervals can be compared with the thirteen Allen's predicates [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF]. We introduce three predicates as a combination of Allen's base predicates, which will prove useful hereafter. They are illustrated in Figure 2. Their corresponding formal definitions are as follows:

• P ∩ (

Spanning Event Stream

Within our SES framework, we consider that each event comes with a time interval, adding the notion of lifespan to events. Instantaneous events can still be modeled with a single-chronon interval. We consider that events are received after their ending.

Definition 1 (Spanning Event Stream). A Spanning Event Stream S is as follows, where Ω corresponds to any set of values, whether structured or not, that brings the contents of each event e ∈ S, and t(e) = t is a time interval that gives the lifespan of the event e: S = (e i ) i∈N with e i = (x, t) ∈ Ω × I In the following, the generic function t(.) will be used to denote the time component of any temporal data structure.

The order of events in the stream obeys the constraint: ∀(e, e ) ∈ S 2 , e < e ⇔ u(t(e)) ≺ T u(t(e )), which means that events are ordered by their end time. In this paper, only on-time events are considered. This implies that events are received as soon as their upper bound is reached, i.e., at time u(t(e)). The set of streams is denoted by S.

Aggregate Functions

Streaming systems require continuous queries to process the data. As data load often makes it impossible to process data individually by an end-user application, a common solution is to use aggregates. Many aggregate functions exist, which can often be studied by categories rather than individually. We propose two classifications, based on their properties for slices and spanning events. Table 1, gives an overview of the most popular aggregate functions [START_REF] Tangwongsan | General incremental sliding-window aggregation[END_REF], with their associated classification.

One can distinguish several algebraic properties [START_REF] Arasu | Resource Sharing in Continuous Sliding-Window Aggregates[END_REF][START_REF] Gray | Data Cube : A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals[END_REF][START_REF] Kim | A review of window query processing for data streams[END_REF][START_REF] Krishnamurthy | Continuous analytics over discontinuous streams[END_REF][START_REF] Shein | SlickDeque: High Throughput and Low Latency Incremental Sliding-Window Aggregation[END_REF] such as: distributive: a stream can be split into sub-streams and there exist some functions to compute the final aggregate from sub-aggregates, e.g., a count can be computed from a set of sub-counts; algebraic: an aggregate can be computed from a list of distributive aggregates, e.g., a mean can be computed from sum's and corresponding count's sub-aggregates; holistic: some functions do not belong to any of the above categories, e.g., median. No constant upper bound on storage applies for the last category of functions, which yields to using specifically tailored algorithms. For this reason, holistic functions are not considered in this paper.

One can also distinguish among accumulative properties [START_REF] Piatov | Sweeping-based temporal aggregation[END_REF]: cumulative: an aggregate is an accumulation of all the events, e.g., count adds one for each event; selective: an aggregate keeps only one event, in its original form, e.g., max keeps only the maximum value. Cumulative functions are sensitive to event duplicates that can happen as a consequence of working with SES. Therefore, we shall study these categories separately.

Temporal Sliding Window in SES

Aggregate functions are blocking operators that require window definition in order to be performed on data streams. Windows split the infinite stream into finite sub-streams from which events can actually be aggregated. Sliding windows have the particularity to advance with time independently from the stream. They are associated to time intervals that are defined by two parameters: the size or range ω, and the step β which determines how fast the window advances in time. Overlaps can happen in such windows as soon as ω > β, e.g., a window of size ω = 15 minutes advancing each β = 5 minutes. Altogether, they provide an infinite list of sliding windows over the data stream S.

Definition 2 (Sliding Window Family).

A Sliding Window Family W S is as follows, where S wi is a finite sub-stream of S containing the events that occurred in the window w i , and t i is the time interval of w i , also denoted t(w i ):

W S = (w i ) i∈N with w i = (S wi , t i ) ∈ S × I
At run-time, window life-cycle goes through several steps: window creation is triggered when the window lower bound is reached, and window release is triggered as soon as the upper bound is reached. Between these two triggers, the window accumulates all the incoming events of interest. At window release, the system computes the final aggregate.

Following this general workflow, SES however, requires to investigate further in order to handle temporal sliding windows. Firstly, it is worth noting that window creation is not impacted by spanning events as the bounds of the window, (t(w)) and u(t(w)), are independent from the stream content. But an incoming event is both assigned to the current window and in several past windows depending on its lifespan. Indeed, event assignment to a window is decided according to the intersection predicate P ∩ , as defined in Section 2.1. Thus, triggering a window release immediately at closing time would yield to missing events for this window because they are still ongoing and they will be caught only in the future.

To overcome this problem, we introduce a Time-To-Postpone (TTP) parameter. Its role is to delay the window release, with a trigger now occurring at the window upper bound plus the TTP. Of course, this value needs to be chosen very carefully as long-standing events could still arrive after the TTP. Various methods exist to define this value, from a fixed user-defined value to an evolving value continuously learned by the system. Accurate definition of the TTP is out of the scope of this communication, since our main focus is the aggregate computation. Hence we consider the basic setting with a constant TTP value that is expected to be larger than the largest event. With this additional delay for window release, any event is now taken into account in active windows.

Slices

Point Event Slices

Slicing techniques divide windows into non-overlapping slices which keep events in the form of continuously updated sub-aggregates. These sub-aggregates are then combined in order to compute the final window aggregate. Advantages of slices are numerous: (i) they limit memory usage by requiring only one aggregate per slice instead of buffering all the events, and (ii) they reduce spikes in the system at window release since only partial aggregates need to be computed, and (iii) they allow for sharing computation among windows [START_REF] Carbone | Cutty: Aggregate Sharing for User-Defined Windows[END_REF][START_REF] Li | No Pane, No Gain: Efficient Evaluation of Sliding-Window Aggregates over Data Streams[END_REF][START_REF] Traub | Scotty: Efficient Window Aggregation for Out-of-Order Stream Processing[END_REF]. Definition 3 (PES Slice Data Model). We define a series of slices Γ W,S depending on a window family W and a data stream S as follows, where φ ∈ Φ is an internal slice structure that stores the partial aggregate value, and t = t(γ i ) is the time interval of the slice γ i :

Γ W,S = (γ i ) i∈N with γ i = (φ, t) ∈ Φ × I
The internal slice structure φ depends on the aggregate function, e.g., sum would store a sum for each slice, whereas mean would store a sum and a count. A list of internal structures for common aggregate functions can be found in [START_REF] Tangwongsan | General incremental sliding-window aggregation[END_REF].

Slices obey two properties:

P1 ∀(i, j) ∈ N 2 , i = j → ¬ P ∩ (t(γ i ), t(γ j )): two slices cannot overlap; P2 ∀i ∈ N, u(t(γ i )) = (t(γ i+1
)): two successive slices meet, in Allen's meaning.

Those properties ensure that Γ W,S is a time partitioning of the stream S, w.r.t. a family window W . The exact conditions on slice bounds are given by the slicing policy that we are going to discuss in Section 5.

To use the slices, we adopt the incremental aggregation method introduced by Tangwongsan et al. [START_REF] Tangwongsan | General incremental sliding-window aggregation[END_REF] and reused in [START_REF] Traub | Efficient Window Aggregation with General Stream Slicing[END_REF]. This approach is based on the three functions: lift, combine and lower. They are illustrated in Figure 3, and informally described as follows:

• lift : S → Φ, prepares events for an ongoing insertion in slices. It is triggered when an event arrives in the system, and it transforms the event to fit the internal slice structure.

• combine : Φ 2 → Φ, merges two slices into a new one. This operation is used both at event insertion and at window release, as shown on Figure 3.

• lower : Φ → Agg, computes the final aggregate from the internal structure of a slice, in order to actually release a window. As an example, we want to know, every 5 minutes, the number of device disconnections and the maximum call duration for an antenna for the past 15 minutes. For such a query, the slice structure would consist in partial counts and max. A typical scenario is as follows:

• The initial state of the internal structure contains seven 5-minute slices,

where n represents the partial counts, and max the partial maximums: • A new event with a call duration of 18 minutes arrives at time 34, then:

1. the event is transformed by lift, giving (n = 1, max = 18); 2. this lifted event is combine'd with the latest slice, as illustrated below.

Spanning Event Slices

With spanning events, one event can find itself in several slices as shown on Figure 1, which is obviously not an issue for point events since slices are nonoverlapping. Hence, we have to adapt the above slicing technique to SES. Firstly, it requires to update several slices during the insertion, at the combine level. However, this quickly leads to a duplication problem that must be leveraged. As their sensitivity to duplication varies, we shall study selective and cumulative aggregate functions separately.

Selective Aggregate Functions

The former is the simpler. By definition, selective functions, e.g., max, only retains one event by slice, thus duplication is not a problem. We can compute selective aggregate functions with the same slice model than the one for PES, following an almost identical workflow. Figure 4 illustrates the slicing workflow for selective aggregate functions. We can see that only the combine step at the insertion of a new event is modified. Indeed, all the slices that have a non-empty intersection with the event need to be updated, rather than the latest one only. Back to our phone call example, one focuses on the selective function, i.e., the maximum call duration, as follows:

• The initial state contains slices with their local maximum values: • At window release, the steps to process the [0, 15) window are:

1. incrementally combine the first three slices. This gives (max(20, 63) = 63) after the first combine, then (max(63, 19) = 63) in the second round; 2. apply lower to output a maximum of 63.

Cumulative Aggregate Functions

Cumulative functions accumulate the data; hence they are sensitive to event duplication among slices. To compensate for this problem, we extend the internal slice structure, as shown in the following definition.

Definition 4 (SES Slice Data Model). We define a series of slices Γ W,S adapted for SES cumulative aggregate functions as follows, where both φ ∈ Φ and ϕ ∈ Φ are internal slice structures that stores the partial aggregate value, and t = t(γ i ) is the time interval of the slice γ i :

Γ W,S = (γ i ) i∈N with γ i = (φ, ϕ, t) ∈ Φ 2 × I
We propose the (φ, ϕ)-structure to separate events that end in the slice (φ), defined with P (t(e), t(γ)), from events that continue after the slice (ϕ), defined by P → (t(e), t(γ)). To show that our extension performs the expected computation we use the properties of our defined interval comparison predicates, which states that an event overlapping a slice interval either finishes inside its time range or goes beyond.

AT NEW EVENT:

AT WINDOW RELEASE: The aggregation process uses modified versions of the lift, combine, and lower operators as described in Section 3.1. This is illustrated in Figure 5. A formal definition of these modified versions is given in Table 2.

The new functions operate in the following way: lift * (e : S, t :

I) → (φ, ϕ, t) : Γ W,S lower * ((φ, ϕ, ) : Γ W,S ) → y : Agg φ = lift(e) if P (t(e), t) else 0 Agg y = lower(combine(φ, ϕ)) ϕ = lift(e) if P → (t(e), t) else 0 Agg combine * ((φ a , ϕ a , a) : Γ W,S , (φ b , ϕ b , b) : Γ W,S ) → (φ, ϕ, a ∪ b) : Γ W,S assert u(a) = (b) or u(b) = (a) or a = b φ = combine(φ a , φ b ) ϕ = combine(ϕ a , ϕ b ) if a = b else ϕ max{a,b}
• lift * : S, I → Γ W,S : promotes each event as a (φ, ϕ) slice item. Choosing among the slice part to contribute to is made thanks to P and P → conditions, respectively for φ and ϕ. Each event is eligible to only one of them, and the non-eligible part is let empty. Basically, as one can see on Figure 5, the event contributes to the φ part of the most recent slice, and to the ϕ part of all other intersecting slices. This implies that the lift * operation depends on the interval of the slice, and should be computed for each slice;

• combine * : Γ 2 W,S → Γ W,S : behaves differently depending on the moment it is triggered. When combine * is triggered at events insertion, it will rely on the raw combine operator from [START_REF] Tangwongsan | General incremental sliding-window aggregation[END_REF] to update as much φ as ϕ. We can, however, note, as shown in Figure 5, that only one of them is updated as the event cannot contribute to both at the same time during the lift * step. When combine * is triggered at window release , it ignores the ϕ part of the oldest slice to prevent event duplication, since an event in ϕ necessarily contributes to the next slice, either in φ or ϕ. Hence updating only the most recent ϕ ensures neither to duplicate the event nor to forget it. This behavior can be seen on Figure 5 where, at each combine * , only the ϕ of the most recent slice is considered.

• lower * : Γ W,S → Agg: merges the distinct parts φ and ϕ to provide the exact aggregate value.

As neither event duplication nor omission are possible with the (φ, ϕ)-structure, we claim that all popular cumulative aggregate functions can be used with this new structure.

We continue our example with the cumulative function part, and use these new lift * , combine * and lower * functions to count the number of devices connected to an antenna with spanning events.

• In the initial state, φ and ϕ both represent partial counts. • When a new event arrives, the 18-minute phone call at time 34:

1. the event is transformed with lift * into (φ = 1, ϕ = 0) for the most recent slice, whereas it gives (φ = 0, ϕ = 1) for the three previous slices; 2. this lifted event is then combined with each related slice, which corresponds to the latest four slices. • At window release, we process the [0, 15) window as follows:

1. use combine * twice for the first three slices. This gives (φ = 8 + 19 = 27, ϕ = 18) after the first combine * , then (φ = 27 + 15 = 42, ϕ = 12) after the second; 2. apply lower to output a (correct) count of 42 + 12 = 54.

Multi-Level Slices

Streaming systems are dealing with extremely high ingestion rates, and hence one of the main concerns for our system is the insertion cost. Furthermore, we saw that spanning events can overlap with several slices, which implies multiple slice insertions for a single event. In this section, we propose a generalization of the slice model with a multi-level slice structure allowing managing longstanding events within a unique slice instead of several ones.

Multi-Level Model

We first assume that one can reduce insertion cost by controlling the number of slices in which we insert events. The proposed structure is meant to work with both selective and cumulative aggregate functions. Hence, in this section, we will not distinguish between those two types of aggregate functions.

Definition 5 (SES Multi-Level Slice Data Model). Given a height d ∈ N, one creates d levels by slice, each of them containing a structure similar to the one of Definition 4, i.e., it has a time interval t ∈ I and a (φ, ϕ) ∈ Φ 2 structure. We define a series of multi-level slices Γ W,S as follows:

Γ W,S = ((γ k i ) 1≤k≤d ) i∈N with γ k i = (φ, ϕ, t) ∈ Φ 2 × I
It is worth noticing that selective functions only require a φ ∈ Φ structure. This generalized slice model is schematized on Figure 6.

In Definition 5, γ k i is the slice structure at the level k for the slice γ i , which we further denote as slice level ; t(γ k i ) = t is the time interval of that level. When the height d is equal to one, it is strictly equivalent to the Definition 4. Therefore, Definition 5 provides a generalized form of the spanning event slice structure.

Time Intervals of Upper Slice Levels

The base level (k = 1) of each slice defines the actual time interval t(γ 1 ) = t. Those slice ranges are non-overlapping and they are given by the slicing technique (see Section 5), as the "flat" slice model.

Intervals for levels k > 1 are created as a composition of raw slice intervals, as follows:

∀i ∈ N, ∀k ∈ 2, d , t(γ k i ) = i j=i-k+1 t(γ 1 j ) (1)
For instance, level 2 covers the current and the previous slices, and so on, until level d which will contain the d -1 previous slices. An example is given by slice 7 on Figure 7.

In Equation 1, one considers t(γ 1 j ) = 0 I for j ≤ 0, to fix the equation at the very beginning of the slice timeline (when i < k).

[7, 8) [1, 2) [2, 3) [3, 4) [4, 5) [5, 6) [6, 7)
Slices [START_REF] Kim | A review of window query processing for data streams[END_REF][START_REF] Shein | SlickDeque: High Throughput and Low Latency Incremental Sliding-Window Aggregation[END_REF] [5, 8) [START_REF] Arasu | Resource Sharing in Continuous Sliding-Window Aggregates[END_REF][START_REF] Shein | SlickDeque: High Throughput and Low Latency Incremental Sliding-Window Aggregation[END_REF] ... ... ... ... ... This implies that for levels higher than 1 the constraint of non-overlapping does not hold. To avoid any redundancy at event insertion, we define some additional properties: P3 ∀i ∈ N, ∀p, q ∈ 1, d , p = q, S γ p i ∩ S γ q i = ∅: an event can contribute to at most one level of a given slice; P4 ∀i, j ∈ N, ∀p, q ∈ 1, d , i = j, P ∩ (t(γ p i ), t(γ q j )) → S γ p i ∩ S γ q j = ∅: an event cannot contribute to any slice level which overlaps with a slice level where it has been inserted.

In the above properties, S γ k i denotes the sub-stream of events from S that contribute to the level k of the slice γ i .

Working with the Multi-Level Slice Model

In the multi-level technique, we use the (φ, ϕ)-structure in the same way as with cumulative functions for SES (see Section 3.2.2). This allows to separate events according to their end time. Then, for an event to contribute to a slice, whatever the level, it must intersect with the raw slice interval t(γ 1 ). Then, to satisfy property P4, insertion into past slices may skip contiguous slices and jump directly to non-overlapping ones.

To release a window w, we combine all the slice levels γ k i which overlaps with the window, i.e., such that P ∩ (t(w), t(γ k i )) = ∅. As for any level k > 1, slices are overlapping with previous slices, we also need to include upper levels for slices where u(t(w))

≤ (t(γ 1 i )) ∧ u(t(w)) > (t(γ k i ))
). Note that those slices are not used for release in the case where the height is equal to one, as in Section 3.2.2. For all slice levels ending with or after the window, i.e., where u(t(w)) ≤ u(t(γ k i ))), property P4 ensures us that the event contributing to ϕ are not contributing to any other later slice. Thus we need to change the combine * function, as exposed in Table 3. This new function takes into account that when u(t(w)) ≤ u(t(γ k i )): (i) we need to combine both φ and ϕ for slice levels, (ii) the interval output from the combine function cannot have an upper bound higher than u(t(w)). This update implies that combine * is now asymmetric with parameters order impacting the final result. The left part (a) contains the future final result, while the right part (b) contains the slice level to add to the result.

* ((φ a , ϕ a , a) : Γ W,S , (φ b , ϕ b , b) : Γ W,S ) → (φ, ϕ, t) : Γ W,S φ = combine(φ a , φ b ) ϕ = combine(ϕ a , ϕ b ) if u(a) ≤ u(b) else ϕ b t = a ∪ b if u(a) = (b) else a 4.3.1. Example
Let's use an example to help understanding the multi-level slice model and the way it works. To this end, we follow on our running example and count the number of devices connected to an antenna. It is then a scenario with a cumulative function. For a selective function, as with "flat" slices, only one internal structure would be required, the rest would work similarly. In order to skip the initialization phase, where higher levels cannot be created as there is no previous slices, we consider slices starting at time 50. Slices are defined every 5 minutes and they have 3 levels.

• The initial state is made of six 5-minute slices with 3 levels each.

A slice level has a time interval (in gray) and a partial count, which is divided between its φ part on the top and its ϕ part on the bottom: • When a new event arrives, a phone call with the duration of 18 minutes at time 79, giving a valid time of [61, 79), one observes that it covers 4 slices:

1. the event is inserted into the slice where it ends, here [75, 80), at the highest level, which is k = 3 corresponding to range [65, 80). The event is transformed with lift * into (φ = 1, ϕ = 0). Then, it is inserted with combine * , updating the slice level from (φ = 5, ϕ = 6) to (φ = 6, ϕ = 6). 2. As the beginning of the event is older than 65, we look at the first previous slice which does not overlap the current slice level, i.e., [60, 65). Since the event starts in that slice level, one has to lift * it into (φ = 0, ϕ = 1) and combine * with the raw slice level to get (φ = 6, ϕ = 10). 1. successively combine * all slice levels which overlap with the window.

To this end, when the slice level ends within or after the window interval, one incorporates both the φ and ϕ parts; otherwise one uses only the φ part. Activated values are shown below (in red). The resulting structure is (φ = 55, ϕ = 36). 2. then, apply lower * to output a (correct) count of 91.

Stream Slicer

Candidate Frameworks to Meet the SES Requirements

Along with the multi-level slice model, a method to both insert events in slices and release window aggregates from those slices was proposed. Then, one needs a system that is able to create such slices from the window parameters and the data stream. For sliding windows, several such systems already exist to address PES aggregation. One of the SES requirements is that past windows can be updated, and hence window start and end bounds must coincide with slices bounds to be able to recreate past windows. For this purpose, the algorithms Panes [START_REF] Li | No Pane, No Gain: Efficient Evaluation of Sliding-Window Aggregates over Data Streams[END_REF] and Pairs [START_REF] Krishnamurthy | On-the-fly sharing for streamed aggregation[END_REF] are good candidates, while Cutty [START_REF] Carbone | Cutty: Aggregate Sharing for User-Defined Windows[END_REF] is unsuitable as it marks only start bounds of windows and not end bounds. Panes [START_REF] Li | No Pane, No Gain: Efficient Evaluation of Sliding-Window Aggregates over Data Streams[END_REF] partitions the stream into constant size slices, equal to gcd(β, ω). At the contrary, Pairs [START_REF] Krishnamurthy | On-the-fly sharing for streamed aggregation[END_REF] creates at most two slices per step. When ω mod β = 0 both methods are equivalent, while Panes generates twice as many slices as Pairs when it is not the case. To reduce insertion and release costs [START_REF] Traub | Scotty: Efficient Window Aggregation for Out-of-Order Stream Processing[END_REF], the goal of a stream slicer is to produce as few slices as possible, thus Pairs is more appropriate. Scotty [START_REF] Traub | Scotty: Efficient Window Aggregation for Out-of-Order Stream Processing[END_REF] produces slices for each new window start or end, which makes the method equivalent to Pairs. Hence, we shall use the Pairs technique in this paper.

Slicing Algorithms 5.2.1. Single-Level Slicing

We consider cumulative aggregate functions, and each entering event is straightforwardly lifted to the (φ, ϕ)-structure, as defined in Section 3.2.

We Algorithm 2: add slices

input : Γ ∈ Slices, τ ∈ T, ω ∈ N, β ∈ N 1 ε : N ← ω mod β 2 if ε > 0 then 3 add (0, 0, [τ, τ + ε)) to Γ 4 add (0, 0, [τ + ε, τ + β)) to Γ Algorithm 3: insert event input : Γ ∈ Slices, e ∈ S 1 i : N ← | Γ | -1 2 while P∩(t(e), t(Γ[i])) ∧ i ≥ 0 do 3 Γ[i] ← combine * (Γ[i], lift * (e, t(Γ[i]))) 4 i ← i -1 Algorithm 4: release window input : Γ ∈ Slices, nω ∈ N, n β ∈ N 1 γ : (Φ, Φ, I) ← (0, 0, t(Γ[0])) 2 for i ∈ [0, nω) do 3 γ ← combine * (γ, Γ[i])
4 delete slice 0 to n β -1 from Γ 5 print lower * (γ)

Multi-Level Slicing

Multi-level slicing has a very similar algorithmic schema to SE-Slicing. Hence, it may reuse the main loop defined in the Algorithm 1, with two slight updates: (i) the height d ∈ N is a new parameter, and (ii) the Slices type becomes List (Φ, Φ, I) d to match the multi-level slice structure of Definition 5. One denote by SE-ML-Slicing the resulting algorithm. Despite its similarity with SE-Slicing, the inner functions add slices, insert event and release window need to be re-implemented.

As for the SE-Slicing technique, Pairs is the preferred framework to add new slices (see Algorithm 6). During the process, multi-level slice structures are allocated and initialized as stated in Algorithm 5. Multi-level slice structures are fed with past raw slice levels (line 5). At the very beginning, we cannot fill all the levels and stop as soon as there is no previous slice (line 4). Hence, the first slice contains only one level, the second only two, and so on, until we reach i ≥ d.

Algorithm 5: create slice input : Γ ∈ Slices, d ∈ N, t ∈ I 1 γ : (Φ, Φ, I) d 2 γ[0] ← (0, 0, t) 3 for k ∈ [1, d) do 4 if | Γ | > k then 5 γ[k] ← (0, 0, [ (t(Γ[| Γ | - k][0])), u(t)))
6 add γ to Γ Algorithm 6: add slices

input : Γ ∈ Slices, τ ∈ T, ω ∈ N, β ∈ N, d ∈ N 1 ε : N ← ω mod β 2 if ε > 0 then 3 create slice(Γ, d, [τ, τ + ε)) 4 create slice(Γ, d, [τ + ε, τ + β))
To insert an event, Algorithm 7 computes the number of slices n γ an event intersects with (lines 2-7). Then, a specific pathway is run to insert the event in as few slice levels as possible (lines 8-14).

Algorithm 7: insert event input : Γ ∈ Slices, d ∈ N, e ∈ S, n β ∈ N 1 i : N ← | Γ | -1 2 r : N ← | t(e)| + u(t(Γ[i][0])) -u(t(e)) 3 nγ : N ← r/β × n β 4 if r mod β > | t(Γ[i][0])| then 5 nγ ← nγ + 2 6 else if r mod β > 0 then 7 nγ ← nγ + 1 8 while i ≥ 0 ∧ nγ > 0 do 9 if nγ ≥ d then 10 combine * (Γ[i][d - 1], lift * (e, t(Γ[i][0]))) 11 else 12 combine * (Γ[i][nγ - 1], lift * (e, t(Γ[i][0))) 13 i ← i -d 14 nγ ← nγ -d Algorithm 8: release window input : Γ ∈ Slices, nω ∈ N, n β ∈ N, d ∈ N 1 γ : (Φ, Φ, I) ← (0, 0, t(Γ[0][0])) 2 for i ∈ [0, nω) do 3 for k ∈ [0, d) do 4 γ ← combine * (γ, Γ[i][k]) 5 for k ∈ [1, d) do 6 for i ∈ [0, min(k, | Γ | -nω)) do 7 γ ← combine * (γ, Γ[nω +i][k]) 8 delete slice 0 to n β -1 from Γ 9 print lower * (γ)
Writing into slices starts from the most recent slice, and inserts in the highest possible level. If it needs to insert into more slices than the height (n γ > d), then it inserts into level d (lines 9-10). As other slices still need to be written, it goes backward in the Γ slice list, skipping the ones which are already covered. The next eligible slice γ j ends at the beginning of the slice level γ d i in which the event was inserted, such as (t(γ d i )) = u(t(γ 1 j )). This slice hop from i to j is determined by the height d of the structure, and actually, the destination slice number is j = i-d (line 13). The algorithm continues inserting the event in past slices (with possible hops) until it covers the slice level γ 1 i-nγ . The successive steps to insert an event are illustrated on Figure 8. The insertion starts on the right with the most recent slice and then, it goes back in time. The event spans over 7 slices and the height is 4; hence the first insertion is performed at the highest level (level 4) of the most recent slice (slice 8) which covers 4 slices (from 5 to 8). Then, a second insertion arises at level 3 of slice 8 -4 = 4 in order to cover the 3 remaining slices (from 2 to 4). The event is therefore always inserted in a minimum number of slices thanks to the highest level insertion policy. It is important to note that this multi-level slice structure requires a specific path to insert events into slice levels (in particular for the hoping phase). Release of a window traverses all intersecting slice levels with the current window w, as shown in Algorithm 8. To this end, it first scans all levels of slices γ i such that their raw level γ 1 i overlaps with the window (P ∩ (t(w), t(γ 1 i )) (lines 2-4). Then it looks for more recent slices, from γ imax+1 to γ imax+d-1 , since at least one of their levels, for each of those recent slices, overlaps with the window (lines 5-7). Figure 9 shows all the internal structures activated at window release when d = 4. Since the window covers the first three slices, then it first combines all those 12 slice levels. Then it combines with 3 levels of slices 4, 2 levels of slices 5 and 1 level of slice 6. Note that when there TTP is small we might read fewer slices because all slices would not yet be created (line 6). For example, if we release a window of size 3 when we are currently writing slice 5, we would only read internal slice structure of slices 1 to 5 and not 1 to 6 as expected (see Figure 9).

Time Complexity Analysis 5.3.1. Single-Level Slices

The slicing technique creates one slice per step β when ω mod β = 0. Initially the cost per window for adding slices is the number of slices per window, ω/β. Nonetheless, because the slices are shared among windows, the cost of adding slices is shared too, one slice being used in ω/β windows. It yields to an amortized cost of 1 per window for slice addition. Event insertion in SES has initially a worst-case complexity in ω/β • N because all slices could receive all events. However, we assume that most of the time, event size is smaller than the window size. Hence the event does not need to be inserted into all slices of a window. Therefore we introduce the average event size µ e to analyze the number of impacted slices. The complexity becomes then µ e /β • N Again, slice sharing allows to reduce the cost, which becomes µ e /ω • N with an upper bound in N . The best-case complexity is in β/ω • N when each event is inserted into only one slice. Hence the behavior of events insertion varies depending on the size of the events.

The final aggregate computation has a complexity depending only on window parameters. The cost of window release is the number ω/β of slices per window, i.e., a constant value.

Finally, we can note that, when ω mod β > 0, two slices are created per step and all the above cost values are multiplied by two. Indeed we create twice more slices, for the same event size we would hence insert in twice more slices and we would also double the number of slices that are required for a window release.

Multi-Level Slices

The time cost for adding one slice is dependent on the parameter d of the SE-ML-Slicing algorithm. If ω mod β = 0, we create one slice per step, and the cost per step is d. As slices are shared among windows, the amortized cost per window still remains d.

Let focus on the insertion operation. When ω mod β = 0, and given a height d, the size of the highest-level time interval is d × β. Hence, an event is inserted in at most µ e /dβ slice levels. The cost to insert N events, amortized for a window considering the sharing, is then µ e /dω • N . In the best case, the cost is β/ω • N as we insert each event in only one slice. In the worst case, the cost is 1/d • N when the event is inserted in every slice. It is worth noticing that the larger the height, the smaller the cost of insertion.

Finally, the cost for releasing a window is the cost for reading all covering slices and more precisely, all the slice levels. This cost can be decomposed into several parts. We read all levels for all slices up to n ω , and the cost is d × (ω/β). We then read upper levels for slices from n ω to n ω +d -1, that yields to a cost of d×(d-1)/2. To sum up, the cost to release a window is d×(ω/β +(d-1)/2).

When ω mod β > 0 we create twice more slices per step. Hence, we double all previous costs, as expected.

Summary

Table 4 gives a summary of all time costs for slicing techniques, with the window cost on top and event cost below. For SE-Slicing and SE-ML-Slicing, window addition and deletion cost correspond to addition and deletion of slices. As it is the most common case, we consider the case where ω mod β = 0.

Table 4 also presents the cost of a baseline streaming approach Buckets [START_REF] Traub | Efficient Window Aggregation with General Stream Slicing[END_REF], and a state-of-the-art temporal database approach Plane Sweeping [START_REF] Piatov | Sweeping-based temporal aggregation[END_REF]. Buckets allocates one bucket per window, which can be split into two different methods. Tuple Buckets stores all the events intersecting a window to its associated bucket, in their original form. On the contrary, the Aggregate Buckets method stores the events in a pre-aggregated form for each window. For both tuple-based and aggregate-based methods, the events are therefore processed independently for each bucket of every non-closed window they are in. Plane Sweeping uses two endpoint indexes, one for events and one for windows. Those indexes store one entry for each starting and ending bounds. As this technique is fitted for temporal databases, when computing the results it normally contains all events and windows, and indexes are read concurrently, up to their end. In our streaming system, indexes are read partially at window release, and this up to the upper bound of the window. Plane Sweeping is shown in its cumulative (Cumul-Sweeping) and selective version (Select-Sweeping).

Table 4: Complexity overview (time cost per window), w.r.t. N , the number of events in a window, µe the average size of an event, ω and β the window parameters, and the height d of the slices. The precise cost is used as much as possible and we consider a uniform distribution of events.

Window cost

add release delete Tuples-Buckets

1 N 1 Agg-Buckets 1 1 1 Cumul-Sweeping 2 log((2δ + ω)/β) 2β/ω • N + 2 2 Select-Sweeping 2 log((2δ + ω)/β) log(δN/2ω) • (β/ω • N + 1) 2 SE-Slicing 1 ω/β 1 SE-ML-Slicing d d(ω/β + d -1) 1 Event cost insert delete Tuples-Buckets N 0 Agg-Buckets N 0 Cumul-Sweeping log((2δ + β)/ω • N ) • 2β/ω • N 2β/ω • N Select-Sweeping log((2δ + β)/ω • N ) • 2β/ω • N 2β/ω • N SE-Slicing µ e /ω • N 0 SE-ML-Slicing µ e /dω • N 0
Overall SE-Slicing greatly improves insertion cost for events smaller than the range compared to the Buckets methods. At release, SE-Slicing has a better cost than Tuple Buckets, while having slightly higher cost than Aggregate Buckets. As a result SE-Slicing promises much better insertion cost for windows with large ranges (and in particular when event size is small). Compared to Sweeping, SE-Slicing has a better window addition and release, as long as the number of events is high enough. Event insertion depends on the characteristics of the window and events, for long event size and small window size and step Sweeping has better insertion cost than SE-Slicing. However, as soon as the step is at least greater than half the event size SE-Slicing has a better complexity. We should also note that Sweeping is the only technique not presenting linear deletion cost for events, as the event index should be emptied. SE-ML-Slicing reduces insertion cost compared to SE-Slicing. But cost for slice creation and window release are slightly increased. Those new costs depend on the height of the multi-level slice structure. Height value should hence be chosen accordingly with the planned size for events. The larger the height the higher the computation cost at release, but the higher the gain at the insertion for long-standing events. A small height on the contrary gives complexities close to those of SE-Slicing. And a height of 1 would strictly match the SE-Slicing numbers.

Space Complexity

The space complexity per window is greatly improved by SE-Slicing technique compared to Tuple Buckets which buffers all the events and hence has a space complexity in O(N ), and to the Sweeping technique that keeps every event and window twice in indexes with a space requirement of (2δ +ω)/β +(2δ +β)/ω •N . In contrast, slicing technique buffers one pre-aggregate only for each slice, then it has a constant space requirement of ω/β , even reduced to 1 in amortized complexity thanks to slice sharing among many windows. Aggregate Buckets achieve the same complexity, with the same advantage of bounded memory.

SE-ML-Slicing on the other side comes at a higher cost as it stores all slice levels. The cost is ω/βd and it falls down to d for a single window.

Experiments

Experimental Setup

This series of experiments intends to show the performance improvements with SE-Slicing and SE-ML-Slicing techniques compared to baseline Buckets and state-of-the art Sweeping approaches.

Data Set. We used two data sets. Firstly, a synthetic data set where each event size is determined by a random number generated with a normal distribution (µ is given as average events size, σ = 10). The system creates a non-delayed stream with one event per chronon, totaling 2M events. Next, the SS7 data set replays a real-world telephony network with one minute of anonymized data containing 3.2M events. Each event contains 119 fields from which we extract the start and stop times to generate event intervals. In all experiments, we use δ to represent the TTP, given as an input parameter of the streaming system.

Aggregates. For each window we compute three aggregates: two cumulative functions, namely count and sum, and one selective function, max.

Setup. All experiments were executed on an 8-core Intel R Xeon R Silver 4110 CPU @ 2.10 GHz with 126 GB of RAM under Linux Debian 10.

Implementation. Implementation has been done in modern C++. Algorithms for the slicing method SE-Slicing are shown in Section 5.2.1 for count and sum. Max uses a similar algorithm, with a non-duplicated slice structure. Algorithms for the multi-level slicing method SE-ML-Slicing are shown in Section 5.2.2. For SE-ML-Slicing we use a circular array to store slices, which allows to define the array size once and then reuse previous slices instead of creating new ones. For the Tuple Buckets techniques, we only store event pointers in the buckets, so that memory overhead is reduced. The Aggregate Buckets technique uses the same partial implementation as SE-Slicing and SE-ML-Slicing. Sweeping technique uses a std::map for indexes and stores event pointers as id of events.

Metrics. To monitor the algorithms, we consider three dimensions. The throughput gives the amount of time needed to process a certain number of events. Throughput in these experiments is achieved by letting the program absorb as many events as it can. Then, we monitor CPU time and the maximum memory footprint via psutil, a Python cross-platform tool for retrieving information on running processes and system resources. It delivers CPU time spent by a given process, as well as the memory footprint in real time. The memory footprint indicator kept is the maximum memory used per experiment.

Protocol. There are three facets to the experiments. First we analyze in Section 6.2 how the different techniques react to a change in event size, and thus stress the insertion part. Then, we study the impact of varying window parameters and in particular increasing the window ranges and the number of slices, in Section 6.3. Finally, we observe the behavior of the algorithms in a more realistic setting thanks to the SS7 data set in Section 6.4.

Impact of Event Size

Event size is at the heart of spanning events. Thus, maintaining an acceptable throughput with increasing events size is a key challenge for SES streaming systems.

Single-Level Slices. As expected from the complexity review in Section 5.3, and as illustrated in Figure 10, large event size results in a decrease of the throughput for all methods, except Sweeping which has a constant throughput no matter the window or event size. For all window sizes, SE-Slicing performs better than Buckets and Sweeping. Furthermore, the smaller the event, the better the gain with SE-Slicing. Increasing window size also results in better performance for SE-Slicing compared to the other techniques, which can be explained by the need to release windows less often. However, for small windows we can see that SE-Slicing starts to be a clear concurrent to SE-Slicing. CPU and maximum memory experiments follow similar tendencies than throughput. Regarding CPU, all techniques stay roughly in the same order of magnitude, although SE-Slicing is slightly lower than the others, and with the exception of Tuple Buckets which skyrockets when windows are small and the data stream has long-standing events. Maximum memory used by both SE-Slicing and Aggregate Buckets are quite equivalent, while Tuple Buckets and Sweeping tend to use more memory. Tuple Buckets memory consumption grows with event size, while Sweeping shows a constant consumption in all use cases. Multi-Level Slices. On the complexity analysis we saw that SE-ML-Slicing reduces insertion cost and thus is fitted for use cases where the ratio between event size and window size is large. Thus we study its behavior on smaller windows than previously. As shown on Figure 11, for every height greater than 1, throughput of SE-ML-Slicing outperforms SE-Slicing for all event sizes. When SE-Slicing under-performs compared to Sweeping, SE-ML-Slicing is able to take over and provide better throughput, in particular with large height values. This gain increases with event size, as expected from the complexity review, and validates the motivation for creating this multi-level technique. Furthermore, for this series of experiments the larger the height and the faster the system. For larger window sizes (ω = 5000 and ω = 10000), the system reaches its limit at 550k events/sec. There, heights 15 and 20 have similar results and do not suffer any slow down with increasing event size. Hence we consider that, for those window sizes, increasing the height would not improve further the performance of the system. Regarding the CPU usage, the higher the height, and the less required CPU. Memory usage in both techniques is roughly the same, except for small windows where SE-Slicing saves more memory. This is due to the high slice management cost of SE-ML-Slicing.

Impact of Window Parameters

With sliding windows, the smaller the step compared to the range and the more the windows overlap with each other. As a consequence, lots of windows are opened at the same time, that yields to many aggregate computations, one per step. Hence, it is interesting to check how the system behaves for increasing window sizes, but also for large overlaps.

Single-Level Slices. SE-Slicing shows an increase in performance for all step sizes when ω mod β = 0 (see Figure 12a). In particular, a significant improvement compared to Buckets occurs when the step gets smaller compared to the window size (as long as they are not too close to one), which gives SE-Slicing a definitive advantage with overlapping windows. This also explains the poor performance of both Buckets techniques, which cannot share aggregates, when ω = 500 × β. Sweeping presents the particularity to have a constant throughput.This technique has a clear advantage on SE-Slicing for small window sizes, in particular with long events (see Figure 12b). This setting however would require events longer than the window size, which is very unlikely to happen in real-life use cases. When ω mod β > 0, performance improvement is smaller due to the overhead cost of the two slices per step. But slice techniques still perform better than Buckets, and perform similarly with the Sweeping technique. From this series of experiments, we can conclude that SE-Slicing must be the preferred approach to mitigate overlapping windows in real-life settings, i.e., as long as the ratio between window size and event length stays larger than one. Multi-Level Slices. To address the performance issue of SE-Slicing for small windows and long events, SE-ML-Slicing seems particularly well-suited. We then focus here on the behavior of SE-ML-Slicing in the window range [1, 10 000] chronons. With an event size of µ = 500, for varying window range and multiple steps, SE-ML-Slicing performs initially worse than SE-Slicing (see Figure 13a). As soon as ω ≥ 50 × β, it performs better than SE-Slicing for all heights greater than 1. This threshold phenomenon is due to the overhead cost of the multi-level structure. For all overlap factors both SE-Slicing and SE-ML-Slicing perform better than Sweeping, with however a slow down for high overlap factors. When µ = 5 000, SE-ML-Slicing clearly out-performs SE-Slicing for all heights greater than 1 (see Figure 13b). We can note that the larger the window range and the better the improvement with SE-ML-Slicing. Furthermore, increasing the event size results in a huge slowdown for windows with a high overlap factor. It makes the SE-ML-Slicing technique highly beneficial. In this case the competition with Sweeping is tighter, and for overlapping of β ≥ 50 × ω SE-ML-Slicing with large height it is even able to over-perform Sweeping, while SE-Slicing cannot. For high overlap factor, SE-ML-Slicing outperforms Sweeping as soon as the step is at least a hundredth the size of the event, where most of the time it is much larger than that. We can also note that in all conditions, increasing the height d increases the performance of the system, until we reach an optimal height for any given event size. With ω = 50 × β for instance, this optimal height is 7 when event size µ = 500, and it is 15 when event size is µ = 5 000. Changing the overlap factor also changes those optimal heights. This motivates the need to appropriately choose the height of the SE-ML-Slicing structure accordingly with the event size and the window parameters.

SS7 Data Set

Finally, we want to validate the performance of slicing techniques with a data set coming from real-life use cases.

Single-Level Slices. With real-life data, and for all window sizes, SE-Slicing performs at least 40% better than Tuple Buckets, 10% better than Aggregate Buckets, and 30% better than Sweeping (see Figure 14a). Once again, CPU and memory consumption of SE-Slicing and Aggregate Buckets are similar, while Tuple Buckets is more resources demanding. In particular Tuple Buckets almost double memory consumption for small windows where events need to be duplicated many times. On the other side SE-Slicing, Aggregate Buckets and Sweeping have a constant memory consumption for almost all window sizes. However, Sweeping is slightly more CPU demanding than SE-Slicing.Those behaviors admit an exception where we observe a peak in CPU and memory consumption for small window size in all techniques except Sweeping, which also results in a decrease of the throughput (see the 0-20 area of window range on both Figures 14a and14b).

Multi-Level Slices. With the SS7 data set, SE-ML-Slicing struggles to outperform SE-Slicing. When the window range is small, SE-ML-Slicing shows better performance, in particular for large heights (see Figure 14b). When increasing window range, the performance of SE-ML-Slicing stays a bit behind the one of SE-Slicing. This behavior can be explained with the data set which contains mainly small events (average event size is 16 seconds), and hence the multi-slice overhead at release time is not compensated by a faster insertion. CPU consumption of SE-ML-Slicing is a bit higher than SE-Slicing, while memory consumption varies between runs, at a level again slightly higher than SE-Slicing. All heights have similar CPU and memory consumption.

Summary

In summary, there is a significant improvement in using the slicing technique compared to Buckets and Sweeping. Even though SE-Slicing and SE-ML-Slicing outperformed both Buckets techniques in all situations, this is particularly significant for large windows and high-overlapping ratio. Advantage compared to Sweeping follows the inverse rule. As the Sweeping technique presents a constant throughput with all windows and events size, it starts to be competitive when the window range and event size are comparable, particularly for high overlap ratios. The SE-Slicing technique is well-suited for small events, while SE-ML-Slicing, with its specialized structure, performs better for long-standing events. The latter technique, which was meant to decrease insertion complexity, also does the job pretty well for increasing window size. However increasing height comes at a cost that is critical when the ratio between the window range and step increases. Hence, this multi-level technique should be used only when events are large enough, that is to say at least as large as the slices, in order to take advantage of the multi-level structure. Figure 15 highlights the best techniques w.r.t. a 2D parameter space. Each point gives the technique that outperformed all the others in the experiments for a given setting. The three hand-drawn areas highlight the preferred technique to use in each area. The choice between the two slicing techniques for SES and Sweepingcan thus be motivated by the expected event size and window parameters. It is definitely worth noticing that most of the real-life use cases have a small overlap factor and a high event ratio, hence privileging the SE-Slicing technique.

Related Work

Many techniques have been proposed to improve the performance of sliding windows on PES systems: buffers, buckets, aggregate trees, stacks, slices, and their compositions [START_REF] Traub | Efficient Window Aggregation with General Stream Slicing[END_REF]. Baseline techniques keep all the events and compute the aggregate at release time: buffers just do that, whereas buckets [START_REF] Li | AdaptWID: An Adaptive, Memory-Efficient Window Aggregation Implementation[END_REF] distribute events into subsets (e.g., one per window). Buffer technique can deal with out-of-order events by reordering them before processing [START_REF] Tangwongsan | Optimal and general out-of-order sliding-window aggregation[END_REF]. However, to be adapted to SES, it would require a continuous reordering as well as costly deletions of past events, which incurs a low throughput. Buckets are especially used for out-of-order processing [START_REF] Li | Out-of-order processing: a new architecture for high-performance stream systems[END_REF]. As they keep events separately for each currently opened windows, buckets techniques can be easily adapted to deal with spanning events, and provide a baseline for streaming technique as used in this paper. With overlapping windows, both buffer and buckets methods lead to redundancy in computation as well as to spikes in the system when aggregates are released. The buckets technique, however, comes in two flavors: Tuple Buckets keeps all the events in their original form, while Aggregate Buckets [START_REF] Traub | Efficient Window Aggregation with General Stream Slicing[END_REF] keeps only one partial aggregate per window, thus reducing release spikes and providing a better throughput as shown in the experiments. Aggregate trees such as FlatFAT [START_REF] Tangwongsan | General incremental sliding-window aggregation[END_REF] and FiBA [START_REF] Tangwongsan | Optimal and general out-of-order sliding-window aggregation[END_REF] store partial aggregates on top of events in a hierarchical data structure. Stack such as TwoStacks [START_REF] Tangwongsan | Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time[END_REF] and DABA [START_REF] Tangwongsan | Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time[END_REF] store events in a stack requiring in-order events. Both aggregate trees and stack structures use the timestamp of events to order the structure and assign events to windows. This can be easily achieved with time point storage, but is not fitted to spanning events as intervals start and end bound follow different ordering. Finally, slices technique can be further improved with final aggregation techniques, which define how to merge slice sub-aggregates. Instead of iterating over all the slices, those techniques use aggregate trees or indexes, e.g., B-Int [START_REF] Arasu | Resource Sharing in Continuous Sliding-Window Aggregates[END_REF], FlatFIT [START_REF] Shein | FlatFIT: Accelerated incremental sliding-window aggregation for real-time analytics[END_REF], and SlickDeque [START_REF] Shein | SlickDeque: High Throughput and Low Latency Incremental Sliding-Window Aggregation[END_REF]. This allows to mitigate the bottlenecks when computing final results at window release. As they continuously update all aggregates, insertion of spanning events would yield to large re-updates of the structure, and the duplication in slices still needs to be handled.

Other techniques from the temporal databases area can also be cited. In temporal databases, few work has been done regarding sliding windows, which is denoted as fixed intervals queries [START_REF] Piatov | Sweeping-based temporal aggregation[END_REF]. Currently the state-of-the-art technique is proposed by Piatov and Helmer with a plane sweeping algorithm [START_REF] Piatov | Sweeping-based temporal aggregation[END_REF]. This technique keeps both starting and ending bounds of events and windows in separate indexes which are then read concurrently while filling global counters on events started and ended. This technique can be extended to streaming systems as shown in this paper, providing good results only when events are longer than windows. SB-trees [START_REF] Yang | Incremental computation and maintenance of temporal aggregates[END_REF] store hierarchy of intervals along with partial aggregates. However, the B-tree structure is hard to maintain in a streaming system dealing with high ingestion rate. Indeed, after each insertion, rebalancing is run to keep the structure as packed as possible. Furthermore, this technique requires a separate tree for each aggregation function, increasing drastically its cost in real-life use cases with multiple aggregates at a time. Finally, deletion is handled on an event basis, which requires to buffer events and then, cannot be used with selective functions. TMDA-FI [START_REF] Böhlen | Multi-dimensional Aggregation for Temporal Data[END_REF] proposes a different approach where a table is built from window ranges and their partial aggregate values. Those values are computed incrementally as the input relation is scanned. When applied to streaming systems, this technique is similar to the Aggregate Buckets one.

Conclusion

This article addresses the issue of partial aggregate sharing among overlapping windows to spanning event streams (SES for short). Dealing with spanning events brings new constraints, since events overlap the ongoing window as much as past windows. Concerning slicing techniques, SES aggregation implies that adjacent slices may be assigned the very same events. Hence, operations sensitive to duplication would provide inaccurate results, and common slicing techniques cannot be used straightforwardly.

Therefore, we extended the slice model and algorithms according to properties of the aggregate functions. When functions are insensitive to event duplicates, we can reuse the model and workflow of PES, with a slight difference, however: at event insertion, we update all the intersecting slices instead of only the last one. When functions do have this sensitivity, we duplicate the structure to separate events that ends in the slice from the ones that continue afterwards.

We then optimized further this technique with the goal to reduce event insertion cost. Indeed, the duration of spanning events implies multiple insertion in slices, which could be reduced with the use of larger slices. To this end, we created a multi-level slice model which allows the insertion of events in larger intervals than the ones from the raw slices. This multi-level model has a similar behavior than the raw slice model, with the addition of a specific path to insert events.

As expected from complexity analysis, slicing techniques with spanning events are computationally more costly than with point events, but they stay, on average, lower than the buckets techniques, and in particular the tuple buckets one. More precisely, experiments show that the use of slices with spanning event results in significant improvements in throughput, in all use cases with varying events and window size as much as varying overlapping ratio. For long-standing events, slicing techniques can be further improved by the use of multi-level slices. Multi-level slices have higher or equivalent results compared to raw slices, depending on the ratio between slices and event size. Furthermore, the height of the multi-level slices should be chosen accordingly with the event size, range and step to be sure not to underperform. However, when the size of the window is too small compared to event length or too large compared to its step the slicing techniques become less efficient than plane sweeping from the temporal database area. Those settings are, however, very unlikely to happen in real life conditions.

To conclude, our raw slice model is suitable for all techniques which purpose is to partially aggregate spanning events. It can easily be implemented in more complex structures, such like multi-level slices, and could be used in final aggregation optimization techniques. Eventually, a study of the impact of out-of-order events would be of great interest as a follow-on this line of research.

Figure 1 :

 1 Figure 1: Slices and windows with point vs. spanning events

  a, b) := (a) < u(b) ∧ (b) < u(a), i.e., time intervals a and b have at least one chronon in common; • P (a, b) := (b) < u(a) ≤ u(b), i.e., time interval a ends in b, an asymmetric relation; • P → (a, b) := (a) < u(b) < u(a), i.e., a overlaps and goes beyond b, asymmetric too. It is worth noting that P ∩ = P ∨ P → and P ∧ P → = ⊥. In other words, ∀a, b ∈ I, if a overlaps b, a either finishes inside b time range or goes beyond.

Figure 2 :

 2 Figure 2: The three interval comparison predicates used in this paper

Figure 3 :

 3 Figure 3: Usage of functions lift, lower and combine to insert events and release aggregates in PES.

•

  At window release, we compute a window of size 15 minutes considering a large TTP value of 20 minutes. There are two steps to process the [0, 15) window: 1. incrementally combine the first three slices. A first combine is applied on the first two slices and gives (n = 8 + 19 = 27, max = max(20, 63) = 63). Then, a second combine on the previous result and third slice results in (n = 27+15 = 42, max = max(63, 19) = 63); 2. apply lower to output a count of 42 and a maximum of 63.

Figure 4 :

 4 Figure 4: Usage of functions lift, lower, and combine to insert events and release aggregates in SES with selective aggregate functions.

Figure 5 :

 5 Figure5: Usage of functions lift * , lower * and combine * to insert events and release aggregates in SES with cumulative aggregate functions. The internal structure is split to separate the events which end in the slice φ on the left, and the events which end after the slice ϕ on the right.

Figure 6 :

 6 Figure 6: Outline of our multi-level slices data model with a height of 4

Figure 7 :

 7 Figure 7: Time intervals of levels 1 to 4 of slice 7 in the multi-level slice structure with slices of size 1 and a height of 4.

  combine

•

  At window release, we process the [50, 65) window as follows:

  use the Pairs technique to separate the input stream into slices. It creates up to two slices per step where the first slice is of size | t(γ 1 )| = ω mod β (denoted ε in Algorithm 2)and the second one of size | t(γ 2 )| = β -| t(γ 1 )|. This leads to n β = 2 slices per step if ω mod β > 0, 1 otherwise, and n ω = 2 ω/β +1 slices per window if ω mod β > 0, ω/β otherwise. The slice-based SES aggregation process, coined SE-Slicing and exposed in Algorithm 1, uses an "event-at-a-time" execution model. In this algorithm, one considers τ ∈ T as the clock, i.e., an infinite time counter starting from 0 T . The n ω and n β values are initialized (line 3 -nb slice) with the above formulas. The conditions for the window start and end times (resp. lines 5 and 7) are performed with a T-mark incremented by β each time it is reached. δ corresponds to the TTP and delays window release. read stream(S, τ ) (line 9) retrieves the event e at current time τ if it exists, nothing otherwise. add slices (line 6) is detailed in Algorithm 2. It creates the missing slices for a new window, covering the most recent β time range. insert event on line 10 is explained in Algorithm 3. It starts from the most recent slice, scans backward, and stops as soon as it reaches a non-intersecting slice. The last operation, release window on line 8 is given in Algorithm 4. It combines n ω slices, corresponding to all the slices in a window, and then it lowers the result to release a final aggregate. It also deletes the n β oldest slices (Algorithm 4, line 4), since they are no more supporting any open window. Algorithm 1: SE-Slicing input : S ∈ S, ω ∈ N, β ∈ N, δ ∈ N 1 τ : T ← 0 T 2 Γ : List (Φ, Φ, I) as Slices ← () 3 nω, n β : N 2 ← nb slice(ω, β) 4 while True do 5 if window begins at(τ ) then 6 add slices(Γ, τ, ω, β) 7 if window ends at(τ -δ) then 8 release window(Γ, nω, n β ) 9 if e ← read stream(S, τ ) then 10 insert event(Γ, e) 11 τ ← τ + 1

Figure 8 :

 8 Figure 8: Insertion of an event in the multi-level slice structure. Only the required slice levels are enabled. The red diamonds represent parts of the internal structures that are updated.

Figure 9 :

 9 Figure 9: Internal structures to consider when releasing a window of size 3 with a multi-level slice model of height 4. Release starts with the oldest slices shown on the left.

Figure 10 :Figure 11 :

 1011 Figure 10: Comparing slices and bucket techniques for varying event size and for different ranges (β = ω/5, δ = 15000)

Figure 12 :

 12 Figure 12: Throughput depending on the range ω with varying steps β and event size

Figure 13 :

 13 Figure 13: Throughput depending on the range ω with varying steps β and event size

Figure 14 :

 14 Figure 14: Impact of the range on real data (ω/β = 5, µ = 16 seconds, δ = 2.5 hours)

Figure 15 :

 15 Figure 15: Best-fitted technique depending on event size and window parameters

Table 1 :

 1 Classification of the most popular aggregate functions

		Aggregate function	Algebraic prop. Accumulative prop.
	sum-like	count, sum	distributive	cumulative
		mean, standard-deviation	algebraic	cumulative
	max-like	max, min	distributive	selective
		argmax, argmin	algebraic	selective
		maxCount, minCount	algebraic	cumulative
	collect-like	collect, concatenate (string)	holistic	cumulative
		ith-youngest	holistic	selective
	median-like median, percentile	holistic	cumulative
		ith-smallest	holistic	selective

Slices Event Aggregate Slices

	AT NEW EVENT:		AT WINDOW RELEASE:
				Window size
	lift
	combine	combine combine	lower
	update
	: Point Event		: Slice	: Final Aggregate
	: Internal Slice Structure	(	: from event, : from slice, : after combine	)

Table 2 :

 2 Extension ( * -form) of slice operators to the (φ, ϕ)-structure for SES.

Table 3 :

 3 Rewrite of the combine * operator for the SES multi-level slice model.

Declaration of interests

☑ The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

☐The authors declare the following financial interests/personal relationships which may be considered as potential competing interests:


Arnaud Coffin

Clément Bonnefoy-Claudet

Morgane Chassaigne

Arthur Jansen

Christelle Gée
email: christelle.gee@agrosupdijon.fr

PARADe: a low-cost open-source device for photosynthetically active radiation (PAR) measurements

Keywords: PAR sensor, calibration, open source, ESP32 card, data logging, Wi-Fi

In agriculture, proximal in-field information is crucial for a precise management of crop growth. A lowcost, miniaturized and innovative device, named PARADe (PAR Acquisition Device), is designed for in-field photosynthetically active radiation (PAR) acquisition. It combines an affordable PAR line quantum sensor (PAR/LE, SOLEM) and an open source development platform (microcontroller) based on Arduino Integrated Development Environment. The quality of the measurement of the PARADe acquisition chain has been validated. The calibration is done by comparison (R 2 =0.99) with a robust acquisition chain composed of a certified PAR sensor (PQS1, Kipp & Zonen) and a data-logger (CR1000 Campbell Scientific). The accuracy of PARADe measurements is evaluated through three indicators, relative error, RMSE and normalized RMSE. They demonstrate that the PARADe system has certain operating limitations especially for low solar angles (sunset and sunrise) due to the choice of a line quantum sensor. This does not affect the accuracy and reliability of the results, but indicates that the PARADe device is specifically adapted to collect daily cumulative PAR values.

Introduction

In agriculture, to manage and control the crop growth, a fine monitoring of plant biophysical variables such as biomass and chlorophyll is required. These variables are highly dependent on the local environment of the plant and therefore on the available nutrients but also on sunlight which is a key parameter required for photosynthesis process for green plants [START_REF] Pashiardis | Characteristics of Photosynthetic Active Radiation (PAR) Through Statistical Analysis at Larnaca, Cyprus[END_REF][START_REF] Sellers | Modeling the Exchanges of Energy, Water and Cabon Betwwen continents and the Atmosphere[END_REF]. Photosynthesis is the bioenergetic process that allows plants to synthesize their organic compounds from incident solar energy interception. The part of this incident solar energy that drives photosynthesis in plants is defined as photosynthetically active radiation (PAR). It concerns the visible light waves range from 400nm to 700nm. The amount of PAR is usually expressed as Photosynthetic Photon Flux Density (PPFD, μmol.m -2 .s -1 ). Although this parameter is crucial as input data for many ecophysiological models [START_REF] Brisson | An overview of the crop model STICS[END_REF][START_REF] Keating | An overview of APSIM, a model designed for farming systems simulation[END_REF][START_REF] Jeuffroy | Azodyn: a simple model simulating the date of nitrogen deficiency for decision support in wheat fertilization[END_REF], it is often not measured in weather stations. Indeed, for green foliage under nonstressed conditions, it is approximated as a constant value (conversion energy) of the measured global solar radiation (Rg per unit area and expressed in MJ.m -2 .day -1 ). Based on summer data in a comprehensive study at 36.6°N latitude (Texas, USA), 48% is taken as a representative fraction of total solar energy that is in the 400-700nm waveband [START_REF] Britton | Relationships of photosynthetically active radiation and shortwave irradiance[END_REF][START_REF] Amthor | From sunlight to phytomass: on the potential efficiency of converting solar radiation to phyto-energy[END_REF]. The temporal variability of this radiation is very important and depends largely on meteorological conditions, which therefore requires a high adaptability of plants [START_REF] Tomson | Short-term variability of solar radiation[END_REF][START_REF] Sager | Growth Chamber Handbook[END_REF]. Thus, very precise measurements of this radiation require the sensors to be as close as possible to the cultivated plot. Commercial solutions are proposed but they are very expensive due to the possibility of accommodating several certified PAR sensors at the same time. The main drawback of these systems is that information is encapsulated preventing any modifications of the algorithms. An alternative to these solutions is the use of low-cost and open source connected systems. In [START_REF] Barnard | A Simple and Inexpensive Device for Logging Photosynthetically Active Radiation[END_REF], Barnard et The objective of the present study was to design and evaluate the performance of a low-cost open-source device, named PARADe, to automatically measure the in-field photosynthetically active radiation. It combines a non-certified PAR radiation sensor (SOLEM PAR/LE, SOLEMS, Orsay, France [START_REF] Solems | PAR_LE mode d'emploi/ Manual[END_REF]) with an acquisition chain containing an electric signal amplifier. First, the design and implement of PARADe are described. Then a calibration of the entire device (PAR sensor and acquisition chain) was provided. The results are presented and discussed in terms of the limits of functioning and of influence of the solar altitude angle. The results of both low-cost devices, PARADe and PARduino were compared and their performances are discussed.

Materials and Methods

PARADe design and presentation

PARADe was designed for logging PAR measurements, in an autonomous way, using open source technology and low-cost elements (Table 1). This device had to meet several criteria: it had to be light (under 15kg) and compact; it also had to be resistant to water and dust while being selfsufficient in energy. All components of the device had to be easily assembled. Finally, the data had to be controlled remotely by a Wi-Fi connection. All components and their price are presented in table 1.

Table 1

List and cost of components (indicative unit price in 2019).

Component Price (€)

Sensor SOLEMS PAR/LE 256.32 To get an autonomous device that operates many weeks without interruptions, a solar panel, charge controller and a 12V battery were fixed to the frame device. A 10W solar panel allowed having a comfortable safety margin without alimentation cuts especially in winter when the nights are longs and the days are fully clouded.

The design of the experimental device was an important part of the project (Fig. 1A). It included a non-certified PAR line quantum sensor (PAR/LE). The electronic circuit is composed of a ESP32 card and its shields; the electronic amplification circuit and the electric components (charge controller, battery) were placed in a waterproof junction box . This box was fixed on a mast and, at the opposite, was fixed the solar panel to balance the weights. The PAR sensor was put at the top of the mast. It was fixed on an adjustable plate with a bull's eye level to adjust horizontality. The base of the mast consisted of a removing metal cross with holes to stake the experimental device with pins in soil.

Photosynthetically active radiation sensor

The PAR/LE sensor from the SOLEMS brand has been selected. It measures Photosynthetically Active Radiation (PAR) integrated by an amorphous silicon photovoltaic cell installed in a plexiglass case and embedded in the polyurethane over its 0.3m line (Fig. 1A and Fig. 1B). This is a line quantum sensor commonly used for research purposes to measure PAR light above and below the plant canopy where light field is non-uniform [START_REF] Campillo | Study of a non-destructive method for estimating the leaf area index in vegetable crops using digital images[END_REF]. This sensor was delivered without calibration certificate.

SOLEMS makes a pre-calibration by sensor batchs, which is not sufficient to record exactly the PAR values. PAR is expressed in unit of Photosynthetic Flux Density (μmol.m -2 .s -1 ) since photosynthesis is a quantum process [START_REF] Pashiardis | Characteristics of Photosynthetic Active Radiation (PAR) Through Statistical Analysis at Larnaca, Cyprus[END_REF]. As the PAR is related to the global solar radiation, measurements are very dependent on the solar elevation angle defined as the angle between the sun's rays and the horizontal plane. This angle varies throughout the day and its calculation depends on the latitude of a position and the time of a day in a year. The purchase of unqualified equipment for reliable data requires a calibration phase based on the use of a certified PAR quantum sensor (See section 2.5).

Signal chain with amplifier

It should be noted that the output voltage (OV) of the PAR sensor is too low (under 100 mV) to be directly readable by an ESP32 card. Thus, an amplification circuit using a rail-to-rail amplifier was set up. The low power consumption ESP32 card, while providing Wi-Fi and Bluetooth connectivity, was also used as a data-logger. The choice of this low power card was partly linked to the low computing power of the card, which was sufficient for our study: few data and few calculations. This card is an easy-to-use solution without operating system to install. No peripherals, such as a monitor or a mouse, are required, as is the case with more powerful cards. As with Raspberry, the ESP32 programming language is based on that of Arduino. The open-source Arduino software (IDE) was used. It is relatively easy for someone with basic programming background and there are many tutorials and a large community of users. This card was used to record (Memory 4MB) an analogic signal as the output voltage of PAR sensor to convert it into digital signal. The card can read the analogic voltage values between 0 and 2.56V or 0 and 3.3V or 0 and 5.5V. This reading is done with a 10 bits resolution whether 1024 values ranging from 0 to 1023. To have the finest resolution in term of digital signal, an output voltage between 0 and 2.56V was chosen. The higher the output voltage from the sensor, the higher the analog reading. Additional components had been integrated to the ESP32 card, such as a Real Time Clock (RTC DS 1307) to record the time of the acquired data. To achieve voltage amplification without additional cost, a low cost voltage amplification chain was developed (Fig. 2).

Method of calibration

The calibration phase allowed determining the calibration curve of the entire PARADe device. It represents the evolution of the output voltage of the PARADe acquisition chain as a function of the PAR signal. The calibration phase requires the use of a certified PAR quantum sensor. The PSQ1 (Kipp and Zonen, Netherlands) sensor was chosen and positioned close to the PAR line quantum sensor (Fig. 1B). The calibration of the PQS1 sensor is given by the linear equation between the sensor output voltage (OV, mV) and the irradiance (PAR, μmol.m -2 .s -1 ). This equation is specific to each sensor and in our case, the equation provided by Kipp and Zonen for this sensor is:

OV = 4.7*10 -3 x PAR (3)
The PSQ1 sensor is connected to a Campbell Scientific Instrument data-logger (model CR1000) that monitored and stored the data. This constitutes the reference device. The data-logger operation was the same as for the ESP32 card: every five minutes, the average of 60 measurements was recorded in a data file. Moreover, the PQS1 sensor voltage was transformed according to Eq. 3). The voltage values from the non-certified PAR/LE sensor (SOLEMS) were recorded by the PARADe acquisition chain (ESP32 board ans amplifier) and were plotted according to the PAR radiation values measured by the certified sensor, PSQ1. For this calibration, as well as for the other tests that were done, data with a PAR value less than 100 μmol.m -2 .s -1 were deleted. Indeed, it has been demonstrated that these values, generally have a high variability [START_REF] Barnard | A Simple and Inexpensive Device for Logging Photosynthetically Active Radiation[END_REF], are not significant and represent only a small proportion of the daily PAR measurement.

RMSE (μmol.m -2 .s -1 ) = B C ∑ " C !E F GHIJ ! -F LMNLINMGJO ! $ P Q .R (5) nRMSE (%) = STU / < F LMNLINMGJO > (6)

Technical characteristics of PARduino device

In this section, another low-cost device, PARduino [START_REF] Barnard | A Simple and Inexpensive Device for Logging Photosynthetically Active Radiation[END_REF], is presented. The aim is to compare the PARADe results to a similar tool. The PARduino has been developed for recording PAR radiation values on an Arduino card using a LI-COR Quantum (PAR) circular sensor (Model LI-190SA, LI-COR, Inc., Lincoln, NE, USA) with a commercial amplifier (EME Systems 2007) [START_REF]Universal transconductance amplifier, user manual. Version 2A. EME Systems[END_REF]. The table 2 summarizes the characteristics of both devices, PARduino and PARADe. The main difference between both devices concerns the signal amplification that is an open-source circuit for PARADe.

Results and Discussion

PARADe Calibration

Data Validation

First, the performance of the PARADe acquisition chain has be studied and compared to the Campbell Scientific Instrument data-logger (model CR1000). After the PAR/LE sensor output, a bypass has been installed to measure at the same time, the output voltage with both acquisition chains. A strong agreement between both acquisition chains is observed in Fig. 5. However, the signal seems to be slightly noisy suggesting structured fluctuations rather related to electronics but without being able to define the cause. Table 3 summarizes the performance results of PARADe over the entire dataset. Looking at the Standard ISO 9847 [START_REF]Solar energy. Calibration of Field pyranometers by comparison to a reference pyranometer[END_REF], it indicates that, in practice, radiation measurements with the sun altitude angle less than 20° (at sunrise sun and sunset) need to be excluded. The explanation given in the standard is that the response of this type of linear sensors to these radiations is of poor quality and are ultimately inherent to the shape of the sensor [START_REF]Solar energy. Calibration of Field pyranometers by comparison to a reference pyranometer[END_REF]. Thus, ours results confirm these comments highlighting the limits of the sensor PAR/LE to detect low solar angle. Finally, PARADe is appropriate for daily PAR measurements because the high variability of the values at sunrise and sunset ultimately have no impact on the daily values (integration of all one-day PAR data). To overcome this problem due to the sensor, one solution proposed is to fix it on an orientable platform to follow the orientation of the sun [START_REF] Bordenave | Mise en oeuvre d'un traqueur solaire et de son instrumentation sur un site forestier. (Implementation of a solar tracker and its instrumentation on a forestry site)[END_REF][START_REF] Nadia | Advances in solar photovoltaic tracking systems: A review[END_REF].

Comparison to PARduino

The Table 4 compares the accuracy of the PARADe device to that of the PARduino. The performances of these two devices were studied over the same range of PAR measurements. Both devices present the same difficulty in measuring low PAR values when the sun is low in the sky. In addition, they present similar results concerning the mean and standard deviation of RE. However, PARduino underestimates PAR with a mean percent error of (-3.49 ± 3.88) % whereas PARADe overestimates them with a mean percent error of (4.1± 11) %. Over the entire range of measured PAR values, PARduino device seems more reliable than PARADe device where the standard deviation is higher for PARADe device. However, for PARADe device, considering only the high values of PAR, for a measurement range higher 800 μmol.m -2 .s -1 no percent error value (RE) higher than 10% is observed, unlike the PARduino which has 5 % of its values higher than 10% [START_REF] Barnard | A Simple and Inexpensive Device for Logging Photosynthetically Active Radiation[END_REF].

Conclusion

Compared to other available devices, PARADe is effective for PAR measurements especially for values higher than 250 μmol.m -2 .s -1 . In addition, the measurement quality of the PARADe acquisition chain has been validated. For this series of measurements, the calibration, carried out by comparison with a robust acquisition chain, was performed only once, but thereafter it is recommended to check it regularly (once a year). However, we must remain cautious about its limits of use because these results indicate a high accuracy with a low precision of data. Therefore, the PARADe system will be rather well geared to collect daily cumulative PAR values. These daily cumulative PAR values can then be used as input parameters for ecophysiological models to develop decision support tools to assist agronomists in monitoring crop production. Subsequently this device could be improved by connecting it to other similar devices or to proximal sensors (temperature, humidity) and by collecting all of this information remotely via a private Low Power Wide Area Networks (Sigfox or LoRaWAN communication protocol for example) dedicated to the deployments of internet of things (IoT). These low-cost devices offer new opportunities in agriculture for smart farming allowing end users (i.e.

farmers, technical or engineer staff of institute) less dependent from a brand.

  al. presented a device, called PARduino, combining open source technologies with a proprietary solution concerning the acquisition chain. This hybrid device, 2 presented as a first foray into the technology world, was a first cost-effective alternative to commercial data-loggers.

Fig. 1A )

 1A Fig. 1A) PARADe device (PAR/LE sensor + acquisition chain) placed in the agronomic field of AgroSup Dijon (47° 18' 34.443" N ; 5° 3' 57.410" E). Fig. 1B) PARADe in presence of the certified PQS1 sensor and the CR1000 data-logger during the calibration phase.

4

 4

Fig. 2 . 2 . 4 .

 224 Fig.2. The circuit design of PARADe including an ESP32 card and a Real Time Clockn an amplifier (AD623) and others electronic components and voltage converters. The amplifier used is the Analog Devices Inc. AD623 Instrumentation Amplifier, which can be alimented by a supply voltage from 2.7 to 12V. It is a rail-to-rail instrumentation amplifier with an input voltage ranging from 0 to 150 mV and it can deliver a linear output voltage whose gain is between 1 and 1000. The value of the gain can be selected according to the value of an external resistor deduced from the following equation. 623 1 (1) With the external resistor ( Ω). Several empirical tests with different resistance values were made in order to obtain output voltage (Vo) values readable by the ESP32 card. This also made it possible to know precisely the gain of the PARADe amplification chain. To amplify the input voltage (Vi) of the PAR/LE sensor, the resistor value has been chosen to 6900 Ω. The response curve AD623, whose equation is described below, indicates a strong amplification with a positive offset. 23.75

Fig. 3 .

 3 Fig. 3. Flowchart of the PARADe.

Fig. 4 Fig. 4

 44 Fig. 4 presents the calibration curve (black dots) of PARADe. Hundreds of measurements were obtained by performing a continuous acquisition over few days in July 2020, from 2020/07/24 at 4:00 p.m. to 2020/07/27 at 9:11 a.m.. The correlation coefficient is very close to one indicating a very strong correlation between the voltage issued from PARADe and the PAR radiation (PARtrue). The

Fig. 5 .

 5 Fig. 5. Voltage measured by PARADe acquisition chain versus the Campbell data-logger.

Fig. 6 .

 6 Fig.6. Profile of the percent error (RE, %) as a function of the true PAR values. The black horizontal line indicates the overall average RE for the dataset (mean ER =4.1%). The color legend for the RE values corresponds to the solar elevation angle.

  To verify the accuracy of the measurement acquired by this PARADe, a relative error (RE) profile was carried out. This profile is a graph representing the evolution of the RE values as a function of PAR values deduced from the reference device. For each measurement, RE was calculated as the

	2.6. Accuracy of measurements
	difference between values measured by PARADe (PARcalculated) and values issued from the calibrated
	sensor (PARtrue) over the PARtrue. The formula for the percent error (RE, %) is given below:
	Percent Error "RE, %$ 3	45 6786987:;< =45 :>9; 45 :>9;	? * 100	(4)
	From this graph, it is possible to determine the reliability of PARADe measurements and its limits of
	functioning according to the range of PAR values. Moreover, to evaluate the performance of PARADe,
	the PAR values (PARcalculated) were analyzed to PARtrue values using two other statistical estimators, the
	Root Means Square Error (RMSE, μmol.m -2 .s -1 ) and the normalized Root Means Square Error (nRMSE,
	%). Considering n as the total number of measurements, they are defined as:
			7

Table 2

 2 Comparison of characteristics between PARduino and PARADe.

		PARduino	PARADe
		LI-190SA	PAR/LE
	PAR sensor
		(LI-COR, Inc., NE, USA)	(SOLEMS, Orsay, France )
	Calibrated sensor	PQS1 (Kipp and Zonen)	PQS1 (Kipp and Zonen)
	Amplifier	EME Systems UTA /BNC/190	AD623
	Total cost (without frame device)	685 USD (~578€)	427.6 €

  1% with 11% heterogeneity. However, it can be notice that on Figure6most of the points are below the average value of RE, indicating an underestimation of the PAR (Eq. 3). Moreover, all these points seem to be subdivided into different populations whose origin is not clear. Perhaps, is it related to the orientation of the line quantum sensor to the sun or other artifacts (i.e. clouds, brightness)? Despite the high average RE value observed on the low PAR values (250 μmol.m -2 .s -1 ), it ultimately has little impact on the overall result. Indeed, if PARADe is used to obtain the daily PAR value, deduced from the integration of all the PAR data of a day. Thus, these low PAR values, where the ER is high (Area 1), can be neglected as they represent only a very small proportion of the daily PAR. This reinforces the idea of pursuing the development of such a device, inexpensive for access to accurate and representative daily PAR values.In addition to the mean and standard deviation of the percent error, the table 3 presents the RMSE and nRMSE for each area and for the entire dataset. Regarding the RMSE values obtained for each zone, they are quite similar and close to the value obtained on the global range of measurements. Looking at the normalized RMSE values, we can see that area 1 has the highest nRMSE. This again confirms that PARADe does not give reliable measurements for this area. However, for the two other areas, the nRMSE values are similar and lower than that of area 1.

	). For this
	area, the average RE is 33.6 % which indicates a significant overestimation of the PARcalculated with low
	measurement precision (standard deviation 17.9%). Area 2 was defined for an average RE value close
	to zero when the PAR values are between 250 and 1250 μmol.m -2 .s -1 . The average RE value is 0.8 (± 8.7)
	% indicating high accuracy of the PAR measurements but with low measurement precision. Finally,
	for area 3, when the PAR is higher than 1250 μmol.m -2 .s -1 , the average RE is 2.1 (± 2.6) % indicating a
	slight overestimation of the PARcalculated. Over the entire range of measured PAR values, the average RE
	is 4.

Table 3

 3 Values of different estimators (mean of RE, Standard deviation of RE, RMSE and nRMSE) of the PARADe according to the three studied areas and over the entire range of measured PAR values.

	PAR (μmol.m -2 .s -1 )	Area 1	Area 2	Area 3	Total
		[0 -250]	[250 -1250]	[1250 et 2500]	[0 -2500]
	Number of	11	45	91	147
	measurements
	mean RE (%)	33.6	0.8	2.1	4.1
	sd RE (%)	17.9	8.7	2.6	11
	RMSE (μmol.m -2 .s -1 )	56.2	47.8	56.7	54.1
	nRMSE (%)	25.0	6.2	3.3	4.1
	In an attempt to interpret this overestimation of PAR values in Area 1, we note that the RE values (red
	dots) are associated with low solar elevation angles (<20°) that correspond to sunrise or sunset.

Table 4

 4 Performance comparison of the two devices, PARduino and PARADe.

	PARduino	PARADe

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.