Claudio Greco
email: greco@telecom-paristech.fr

Irina Delia Nemoianu
email: nemoianu@telecom-paristech.fr

Marco Cagnazzo
email: cagnazzo@telecom-paristech.fr

Béatrice Pesquet-Popescu

A NETWORK CODING SCHEDULING FOR MULTIPLE DESCRIPTION VIDEO STREAMING OVER WIRELESS NETWORKS

Keywords: Network coding, multiple descriptions, video coding, wireless networks

Network coding (NC) can achieve the maximum information flow in a network by allowing nodes to combine received packets before retransmission. Several works have shown NC to be beneficial in wireless networks, but the delay introduced by buffering before decoding raises a problem in real-time streaming applications. Here, we propose a framework for video delivery in wireless networks that combines Expanding Window Network Coding (EWNC), Multiple Description Coding (MDC), and a novel Rate-Distortion Optimised (RDO) scheduling algorithm that optimises the order in which the video packets are included in the coding window at the current sending opportunity. Results show that our approach consistently outperforms both EWNC applied on single description coding (SDC) and EWNC applied to MDC when a trivial scheduling is used.

INTRODUCTION

Network Coding (NC) [START_REF] Ahlswede | Network information flow[END_REF] has recently been investigated by the research community as an alternative to classical routing for multicast streaming. Using NC, a multi-hop communication is relayed at intermediate nodes by sending combinations of the received messages, rather than mere copies. An interesting application of NC is to grant partial loss immunity to data streams in unreliable wireless networks [START_REF] Katti | XORs in the air: practical wireless network coding[END_REF]. Using Random Linear Network Coding (RLNC) [START_REF] Ho | A random linear network coding approach to multicast[END_REF], a technique in which nodes send combination vectors, i.e., random linear combinations of their received packets, with coefficients taken from a finite field of proper size, the communication can be routed in unreliable networks with dynamically varying connections with no need for node coordination.

A practical implementation of RLNC [START_REF] Chou | Practical network coding[END_REF] (PNC) can be achieved segmenting the data into groups of packets called generations and combining only packets belonging to the same generation. All packets in a generation are jointly decoded as soon as enough linearly independent combinations have been received, by means of simple linear system solving. Since the coefficients are taken from a finite field, perfect reconstruction is assured regardless of the precision of the implementation.

Recently [START_REF] Thomos | Prioritized distributed video delivery with randomized network coding[END_REF], it has also been proposed to apply NC to video content delivery, dividing the video stream into layers of priority and providing unequal error protection for the different layers via PNC. Layered coding requires that all users receive at least the base layer, hence all received packets must be stored in a buffer until a sufficient number of independent combinations are received, which introduces a decoding delay that is often unacceptable in real-time streaming applications. There exist several techniques aimed to reduce the decoding delay, proposed by both the NC and the video coding communities.

From a network coding perspective, a viable solution is to use Expanding Window Network Coding (EWNC) [START_REF] Vukobratović | Unequal error protection random linear coding for multimedia communications[END_REF]. The key idea of EWNC is to increase the size of the coding window (i.e., the set of packets in the generation that may appear in combination vectors) for each new packet. Using Gaussian elimination at the receiver side, this method provides instant decodability of packets. Thanks to this property EWNC is preferable over PNC in streaming applications. Even though PNC could achieve almost instant decodability using a small generation size, this would be ineffective in a wireless network, where a receiver could be surrounded by a large number of senders, and if the size of the generation is smaller than the number of senders, some combinations will necessarily be linearly dependent. On the other hand, EWNC automatically adapts the coding window size allowing early decodability, and innovativity (i.e., linear independence) can be achieved if the senders include the packets in the coding window in a different order. However, these orders should take into account the RD properties of the video stream, as we shall discuss in detail in Sec. 2.

Another possibility is to employ NC jointly with multiple description coding (MDC). MDC [START_REF] Vivek | Multiple description coding: compression meets the network[END_REF] is a well established joint source-channel coding paradigm based on splitting a media content into N sub-streams, referred to as descriptions. Any description can be independently decoded for representing the content, but the quality improves with the number of descriptions. Video MDC has been proven to be a valuable tool to cope with packet losses in wireless networks [START_REF] Wang | Multiple description coding for video delivery[END_REF].

In this work, we propose to jointly use EWNC and video MDC, in order to provide a robust video delivery over an unreliable wireless network, without any need for centralised control or feedback channel. In order to do so, we design a Rate-Distortion Optimised (RDO) scheduling algorithm that, at each sending opportunity, selects which video packet has to be added to the coding window in such a way as to maximise the expected video quality perceived by the receiver. Since the wireless medium is inherently broadcast, we want to exploit the possibility of the receiver being exposed to multiple senders. In other words, we assure that the senders transmit innovative coding vectors even though they do not coordinate their actions.

PROPOSED APPROACH

In this section, we detail our proposed framework, whose objective is to provide a novel transmission strategy for lossy wireless networks able to guarantee a good trade-off between resiliency to losses and timely delivery.

In our scenario, a set of M uncoordinated sources transmit the same encoded video sequence to a single receiver. This scenario could model, for instance, a single hop of a multihop transmission.

We propose to jointly use EWNC and video MDC, which we expect to provide loss resiliency to the video stream without affecting the delay. However, as mentioned in Sec. 1, the efficiency of EWNC highly depends on the order in which the packets are included in the coding window. The original EWNC method was proposed for layered video coding, therefore the priority of the packets was naturally imposed by the dependencies among layers. Such a strategy is unfeasible in our scenario, as we deal with multiple uncoordinated senders sharing a broadcast medium, and if they all were to choose the same order of packets (i.e., the one imposed by the layered structure), at any given sending opportunity they would send non-innovative combinations. In general, if a prioritisation is optimal, it is also unique, and thus all the senders would always transmit dependent combinations, defeating the purpose of using NC. However, there exist frames with very similar RD-properties, hence we can generate a variety of scheduling slightly suboptimal, but with performances very close to the optimum.

For instance, the GOP structure of a video coding technique (such as H.264/AVC) leaves a certain degree of freedom in the scheduling, as frames on the same prediction level can be sent in any order (two examples of GOP structures are shown in Fig. 1), but this may not be enough to provide a sufficient number of different schedules for the different senders.

Using an MDC technique, it is possible to have multiple senders transmitting packets that refer to the same instant, but different nonetheless. Furthermore, corresponding packets of different descriptions are mutually refinable, therefore a node being served by multiple senders will perceive an enhanced video quality. Using MDC, the pool of frames candidate for inclusion in the coding window is a bi-dimensional multiple description GOP (MD-GOP), i.e., a rectangular buffer of size N × W , where N is the number of descriptions and W is the GOP size of each description. An example of MD-GOP is depicted in Fig. 2, for 4 descriptions and a GOP structure of each description as the one in Fig. 1(a), i.e., Hierarchical-B. Notice that in the buffer the frames are not ordered by their play-out date, but in the encoding order, so that frame dependencies are respected. The task of the scheduler is to provide an order in which the frames in the MD-GOP are included in the coding window. Since wireless networks are affected by churn and mobility and the video stream can be interrupted at any moment, it is desirable that any new combination maximise the marginal benefit in terms of RD properties. In other words, at each step, we want the scheduling algorithm to select the frame that optimises an RD criterion for insertion in the coding window. However, the corresponding frames of different descriptions might have differences in their RD properties, which would still lead to a unique optimal policy of inclusion in the coding window.

In order to obviate this problem, we propose a clustering of the video frames. The clustering is a classification of the frames that takes place at video source, after the video encoding and before scheduling for transmission. Its purpose is to improve diversity by letting nodes transmitting, at each sending opportunity, a random frame within an optimal cluster. Clusters are decided once at the encoder, where rate and distortion are known with negligible computational overhead, with frames in the same prediction level. The average rate and distortion of the cluster R(c) and D(c) are then computed, possibly quantised, and added as a header to each frame in the cluster.

At each sending opportunity, among the clusters whose prediction level is compatible with the scheduling so far (C), each sender chooses the cluster c that minimises the cost function J * = min c∈C {J(c) = R(c) + λD(c)}. Within this cluster, each sender randomly chooses one frame and schedules it for transmission. This frame is added to the encoding window, increasing its size by one. The size of the coding window is reset to one with the new GOP.

An example of frame clustering is presented in Fig. 3. There, the I-frames of the 4 descriptions have roughly the same RD properties and are therefore assigned to a single cluster. On the P-frames, on the other hand, descriptions 1 and 2 have similar RD properties between them, but different from descriptions 3 and 4, which are in turn close to each other. In this case, two clusters are created containing the frames with similar properties. The same holds true for the B 0 -frames, where descriptions 1, 2 and 3 have been clustered together, while description 4 was assigned to another cluster. Finally, all B 1 frames of all descriptions give similar contributions to distortion and have been assigned to a single cluster.

Large clusters increase the diversity of the scheduling among senders, thus reducing non-innovative packets. However, if clusters are chosen too large, the scheduler will randomly choose among frames with very different values of the objective function, resulting in a sub-optimal performance. Ideally, the size of the clusters should be chosen according with the expected number of senders that are going to transmit at the same time, which can be roughly estimated with the node density of the network. In practice, clustering can be performed in several ways. For instance, a coarse but simple scheme is to assign all the frames on the same prediction level to a single cluster. This scheme is independent from the actual RD properties of the sequence and can be easily implemented; nevertheless, it can be quite efficient if the descriptions are actually frame-by-frame balanced. If the corresponding frames of different descriptions have slightly unbalanced properties, then a more sophisticated scheme can be employed, e.g., based on thresholding.

An example of two different scheduling orders compatible with the clustering of Fig. 3 is presented in Fig. 4. For the sake of clarity, only the scheduling for the first 16 packets is presented. We can observe that, if only a subset of a cluster is chosen, the two schedulers choose different frames within it. If the whole cluster is chosen, then the frames still differ in the order they are included in the coding window.

EXPERIMENTAL RESULTS

In the following, we present the results of the proposed technique and compare them with the results achievable via EWNC applied to an SD-coded stream and EWNC applied on an MD-coded stream, but ordered using a trivial schedule.

The transmission scenario we simulate is depicted in Fig. 5. In this scenario, M sources S m , m = 1, . . . , M , intend to transmit the same video sequence, I(k), k = 1, . . . , K, to a single receiver R.

For SDC, the trivial strategy consists in including the frames in coding order, i.e., by prediction level and, within frames on the same level, play-out order. For MDC, we assume again that frames are included in coding order and, within frames with the same encoding time (i.e., corresponding frames of independently encoded descriptions), the descriptions are selected in a fixed order. To encode the video sequences, we chose to use 4-descriptions Polyphase Downsampling Multiple Descriptions (PDMD) [START_REF] Franchi | Multiple description video coding for scalable and robust transmission over IP[END_REF][START_REF] Caramma | Polyphase downsampling multiple-description coding for IP transmission[END_REF], a technique where N sub-streams are generated by splitting the original sequence via polyphase down-sampling along rows and columns by a factor of 2. To generate the descriptions, each sub-stream is independently encoded using an H.264/AVC reference encoder JM [START_REF] Sühring | JM reference software release 17[END_REF], version 17.0. The encoding algorithm uses the closed-GOP structure presented in Fig. 1(a). A closed-GOP was preferred in order to reduce error propagation in case of losses. The RD properties of each frame are exactly measured. Clustering is performed based on predic-tion level. The average rate and distortion for the frames in each cluster are computed, quantised on eight bits each, and sent along with the video data.

At the decoder side, all the descriptions are independently decoded in order to obtain the N sub-streams, which the receiver interleaves to reconstruct the central sequence. When some descriptions are lost, the receiver oversamples the available sub-streams, interpolating the missing pixels to obtain a good low-resolution frame (side decoding). When none of the descriptions is available, the loss is concealed using the closest decoded frames.

In order to compare the performance of the method under a variety of inputs, we selected a set of 10 QPs (in Tab. In order to allow a clear evaluation of our technique, a discrete-time transmission model is assumed: the time is segmented in transmission rounds wherein each source S m sends exactly one packet from a predetermined transmission buffer TX m . Each channel C m between transmission buffer TX m and the receiver buffer RX is in general lossy, with independent uniform packet loss probability p m ; the transmissions on different channels do not interfere with each other. At the end of each round, the receiver decodes all the frames available in its buffer RX, generating a reconstructed sequence I(k). This simple scenario is well suited to model a wireless adhoc network where a channel reservation mechanism is enforced [START_REF] Greco | A cross-layer protocol for cooperative content delivery over mobile ad-hoc networks[END_REF], which provides both discrete-time transmission and channel isolation.

In our simulations, the proposed approach has proven to be able to deliver an acceptable video quality to the receiver in a shorter number of rounds than the reference techniques. As an example, in Fig. 6, we report a comparison with the reference techniques under a few different simulation conditions. We observe that, thanks to the variety in the scheduling, our technique is able to reduce the number of linearly dependent coding vectors, and is therefore able to provide a better video quality (in terms of Y-PSNR) in fewer rounds. It should be noted that the final value of the Y-PSNR for the SD-based technique is slightly higher (about 0.5 dB) than that of both MD-based ones, which is a direct consequence of the inherent redundancy among the descriptions of the MD encoding. However, this happens after a long enough time (i.e., about 30 rounds), during which MDC/NC has already achieved its final Y-PSNR. We can also observe that the performance of the method benefits from a higher number of sources, whereas it is of course negatively affected by the loss rate.

CONCLUSIONS

In this work, we presented a novel technique for video streaming over unreliable channels using a combination of multiple description coding and network coding.

The key idea in this technique is to use Expanding Window Network Coding in order to guarantee instant decodability to the flow. The frames are included in the coding window in an order determined by an RD-optimised scheduler. In order to reduce the probability of generating noninnovative packets, the sources operate a classification of the frames (clustering) that provides them with a degree of freedom in the choice of the schedule.

We compared the performance of our technique with Expanding Window Network Coding applied on both on Single Description and Multiple Description coding, assuming a trivial scheduling order, and (in the case of MDC) limiting the combinations within the same description. We observe that the introduction of the scheduling, jointly with the possibility of mixing packets across descriptions, significantly improves the performance w.r.t. the reference techniques, in terms of video quality perceived by the user.

The result we obtained suggests that further research in this direction could be promising, in particular in the direction of a joint design of an overlay management protocol that could select which nodes of the network should relay the stream.

Fig. 1 .

 1 Fig. 1. Two possible GOP structures in H.264/AVC. Arrows indicate prediction. Frames on the same prediction level can be sent in any order.

Fig. 2 .

 2 Fig. 2. MD-GOP for N = 4 descriptions and W = 8 frames in Hierarchical B-frame GOP. Frames are ordered by prediction level.

Fig. 3 .

 3 Fig. 3. Example of MD-GOP clustering. Frames marked by the same colour are in the same cluster and share similar RD properties.

Fig. 4 .

 4 Fig. 4. Two possible schedules (first 16 packets). The numbers indicate the order in which the frame is included in the coding window. The dashed border identifies which frames have been selected for inclusion in the coding window at the 16-th packet.

Fig. 5 .

 5 Fig. 5. Simulated scenario. I(k) and I(k) are respectively the original and reconstructed frames, Sm, m = 1, . . . , M are the senders, NCm the network coding modules, Cm the channels, RX is the receiver R's buffer.

Fig. 6 .

 6 Fig. 6. Comparison of the average Y-PSNR of the decoded sequences, for M sources and packet loss probability p.

Table 1 .

 1 1) and 8 video sequences (in Tab. 2) with CIF spatial resolution at 30 frames per second. QPs used in encoding the video sequences.

	High Bitrate		16 19
	Medium Bitrate 22 25 28 31
	Low Bitrate		33 36 39 42
	akiyo	hall	foreman city
	coastguard football stefan	bus

Table 2 .

 2 Video sequences used in simulations.


Charles Perin
email: charles.perin@inria.fr

Frédéric Vernier
email: frederic.vernier@limsi.fr

Jean-Daniel Fekete
email: jean-daniel.fekete@inria.fr

Interactive Horizon Graphs: Improving the Compact Visualization of Multiple Time Series

Keywords: Visualization, Horizon Graphs, Time Series, Evaluation. ACM Classification H.5.2. Information Interfaces and Presentation: User Interfaces

Many approaches have been proposed for the visualization of multiple time series. Two prominent approaches are reduced line charts (RLC), which display small multiples for time series, and the more recent horizon graphs (HG). We propose to unify RLC and HG using a new technique-interactive horizon graphs (IHG)-which uses pan and zoom interaction to increase the number of time series that can be analysed in parallel. In a user study we compared RLC, HG, and IHG across several tasks and numbers of time series, focusing on datasets with both large scale and small scale variations. Our results show that IHG outperform the other two techniques in complex comparison and matching tasks where the number of charts is large. In the hardest task IHG have a significantly higher number of good answers (correctness) than HG (+14%) and RLC (+51%) and a lower error magnitude than HG (-64%) and RLC (-86%).

INTRODUCTION

Time series-sets of quantitative values changing over timeare predominant in a wide range of domains such as finance (e. g., stock prices) and sciences (e. g., climate measurements, network logs, medicine).

Line charts are one of the simplest ways to represent time series, and one of the most frequently used statistical data graphics [START_REF] Cleveland | Visualizing Data[END_REF]. However, using line charts to visualize multiple time series can be difficult because the limited vertical screen resolution can result in high visual clutter.

We introduce Interactive Horizon Graphs (IHG), an interactive technique for visualizing multiple time series. IHG are inspired by pan and zoom techniques and unify Reduced Line Charts (RLC) and Horizon Graphs (HG), two of the most effective techniques for visualizing multiple time series. We designed IHG to increase the number of time series one can monitor and explore efficiently. Datasets involving large numbers of time series such as stocks or medical monitoring are frequent and important [START_REF] Hochheiser | Dynamic query tools for time series data sets: timebox widgets for interactive exploration[END_REF]. We evaluate the benefits of our contribution for standard tasks on time series visualizations. While the related work has used generated time series with clear landmarks for evaluation, we used a non-synthetic dataset with both large scale and small scale variations (LSV) adapted to multi-resolution visualization techniques.

Under these conditions, we obtained results that are different from those in previous work [START_REF] Heer | Sizing the horizon: the effects of chart size and layering on the graphical perception of time series visualizations[END_REF][START_REF] Javed | Graphical perception of multiple time series[END_REF] (performances are better for HG than for RLC) and found that IHG outperform both RLC and HG for large numbers of time series. This paper first reviews related work on time series visualization techniques and then describes the two techniques that we rely on (RLC and HG) in detail. Next, it presents IHG and our variant of pan and zoom. We then describe a controlled experiment that shows how IHG handles up to 32 time series in parallel. We discuss the results of the experiment and how our technique can be combined with others to support comparison tasks in an effective way.

RELATED WORK

Since line charts have become widespread [START_REF] Playfair | The Commercial and Political Atlas[END_REF], visualization of time series has been an active research topic, moving from paper-based representations to interactive visualizations. Many design considerations exist for displaying data in the form of charts (e. g., [START_REF] Bertin | Semiology of graphics[END_REF][START_REF] Cleveland | The elements of graphing data[END_REF][START_REF] Tufte | The visual display of quantitative information[END_REF]) and for the comparison of graphical visualization techniques (e. g., [START_REF] Peterson | How accurately are different kinds of graphs read[END_REF][START_REF] Simkin | An Information-Processing Analysis of Graph Perception[END_REF]). For relevant surveys see [START_REF] Aigner | Visualization of Time-Oriented Data[END_REF][START_REF] Silva | Visualization of linear time-oriented data: A survey[END_REF].

Visualization Of Multiple Time Series

Visualizing multiple time series in a small space (where the vertical resolution is smaller than the series variations one may be looking for) has led to techniques that use space-filling [START_REF] Wattenberg | A note on space-filling visualizations and space-filling curves[END_REF] and multi-resolution representations [START_REF] Lam | Overview use in multiple visual information resolution interfaces[END_REF]. [START_REF] Javed | Graphical perception of multiple time series[END_REF]. In shared-space techniques, time series are overlaid in the same space (e. g., line

Javed et al. classified visualization techniques for multiple time series into two categories

t v 1 v 2 t v 1 v 2 t v 1 v 2 (a) (b) (c)
Figure 1. Two time series visualized in parallel using Reduced Line Charts (RLC), Horizon Graphs (HG) and Interactive Horizon Graphs (IHG). The degree of difficulty when determining which of the series has the highest value at point t (marked by a vertical black line) is different for each technique: (a) Using RLC, it is very difficult to compare v 1 and v 2 . (b) Using HG with standard baseline at half the y axis and with two bands, we can barely see that v 1 > v 2 : since both charts are blue at that point (i. e., under the baseline), the highest value is the lowest blue one. (c) Using IHG, setting the baseline at 28% of the range of values and a zoom factor of 6, it is clear that v 1 > v 2 : only v 1 is shown in red, i. e., above the baseline. graphs [START_REF] Playfair | The Commercial and Political Atlas[END_REF], braided graphs [START_REF] Javed | Graphical perception of multiple time series[END_REF], stacked graphs [START_REF] Byron | Stacked graphs geometry & aesthetics[END_REF]). In splitspace techniques, the space is divided (usually horizontally) by the number of time series and each one occupies its own reduced space (e. g., RLC [START_REF] Tufte | The visual display of quantitative information[END_REF], HG [START_REF] Few | Time on the horizon[END_REF][START_REF] Reijner | The development of the horizon graph[END_REF]). Shared-space techniques can support only a limited number of time series (considering more than four involves too much visual clutter [START_REF] Javed | Graphical perception of multiple time series[END_REF]). Because we focus on large numbers of time series, we only consider split-space techniques. Also, while most of prior techniques are static, we focus on evaluating the benefits of adding interaction.

Reduced Line Charts (RLC)

RLC are small multiples for time series using line charts. To perform comparison tasks on different RLC, they must all share the same range of values (Figure 1(a)).

Horizon Graphs (HG)

HG is a recent split-space technique intended to display a large number of time series. It was originally introduced under the name "two-tone pseudo-coloring" [START_REF] Saito | Two-tone pseudo coloring: Compact visualization for one-dimensional data[END_REF] and was later developed by the company Panopticon under the name "horizon graph" [START_REF] Few | Time on the horizon[END_REF][START_REF] Reijner | The development of the horizon graph[END_REF]. This technique uses two parameters: the number of bands b and the value of the baseline y b separating the chart horizontally into positive and negative values. Heer et al. [START_REF] Heer | Sizing the horizon: the effects of chart size and layering on the graphical perception of time series visualizations[END_REF] evaluated the use of HG focusing on how chart-reading performance changed using different parameters. They provide some recommendations, such as the optimal chart height and the number of bands which should be used. They limited their study to two simultaneous time series and the number of bands to four. Javed et al. [START_REF] Javed | Graphical perception of multiple time series[END_REF] compared HG with other visualization techniques for higher numbers of time series. They limited the HG parameters to those recommended by Heer et al. and did not highlight any considerable advantage of the technique. In particular, they did not find critical differences between RLC and HG. However, they found that the number of time series seriously impacted the visual clutter and played a very important role in the performance of the visualization techniques. In their experiments, both pieces of prior work used synthetic data that included clear landmarks, which may have aided visual search tasks. As HG is a multiresolution visualization technique, we can expect different results for the more difficult LSV datasets.

Large Scale and Small Scale Variations Datasets

Techniques such as stack zooming [START_REF] Javed | Stack zooming for multi-focus interaction in time-series data visualization[END_REF] and dual-scale data charts [START_REF] Isenberg | A study on dual-scale data charts[END_REF] use focus+context [START_REF] Cockburn | A review of overview+detail, zooming, and focus+context interfaces[END_REF] techniques to visualize time series data containing regions with high variations. These techniques magnify and increase the readability of regions of interest by modifying the x axis (time scale), but not the y axis (value scale). We only found one article [START_REF] Lam | Overview use in multiple visual information resolution interfaces[END_REF] that explored LSV datasets exhibiting both large and small variations visible at low and high resolutions. However, time series with these properties are common-for example, one may observe the temperature of a city along one year according to different variation scales: large (seasonal), medium (daily), small (hourly).

According to Bertin, the scale of time series with small variations must be adjusted to get closer to the optimum angular legibility, which is 70 degrees [START_REF] Bertin | Semiology of graphics[END_REF] and multi-scale banking to 45 degrees has been extensively studied in order to improve the graphical perception of time series [START_REF] Cleveland | Graphical Perception: The Visual Decoding of Quantitative Information on Graphical Displays of Data[END_REF][START_REF] Heer | Multi-scale banking to 45 degrees[END_REF][START_REF] Talbot | An empirical model of slope ratio comparisons[END_REF]. While several tasks can be accomplished on time series where each chart has its own y axis (e. g., compare the trend of two time series during a period of time), related work [START_REF] Few | Time on the horizon[END_REF][START_REF] Heer | Sizing the horizon: the effects of chart size and layering on the graphical perception of time series visualizations[END_REF][START_REF] Javed | Graphical perception of multiple time series[END_REF] suggests that the best configuration for multiple time series consists of sharing the same y axis, i. e., using the same scale of values and baseline. Max is, for instance, executed to find the hottest city in a country for a given date. This task can be very easy to achieve if there are clear differences between the cities but becomes difficult when both the differences and the vertical resolution are small. Figures 1(a) and 1(b) illustrate Max using RLC and HG, respectively. This example highlights the difficulty of such a simple task using LSV datasets.

Discriminate ( Disc)

Disc is an elementary task for relation-seeking, similar to Max. However, instead of having to find the highest value at a marked point t shared by all the time series, each time series has its own marked point. Disc is more difficult than Max [START_REF] Heer | Sizing the horizon: the effects of chart size and layering on the graphical perception of time series visualizations[END_REF][START_REF] Javed | Graphical perception of multiple time series[END_REF][START_REF] Simkin | An Information-Processing Analysis of Graph Perception[END_REF] and HG has been evaluated for this task in two recent studies:

Heer et al. have studied the impact of the number of bands in HG [START_REF] Heer | Sizing the horizon: the effects of chart size and layering on the graphical perception of time series visualizations[END_REF] for Disc. They found that time and error increased with the number of bands. However, these results were obtained for value estimation tasks and they aptly noticed that these increases were due to the mental math implied.

For their Disc task, Javed et al. asked subjects to answer by selecting the time series with the highest value, rather than by estimating the highest value. They did not find any significant difference in terms of Correctness or Time between RLC and HG for Disc.

Evaluate the Slope

Slope is a synoptic task for pattern comparison proposed by Beattie et al. [START_REF] Beattie | The impact of graph slope on rate of change judgments in corporate reports[END_REF]. It consists of determining which time series has the highest increase during a given time period. For this task, Javed et al. found no significant results for Correctness and found HG to be slower than RLC [START_REF] Javed | Graphical perception of multiple time series[END_REF]. We believe that these results were also due to the synthetic dataset they used and we expect different results from a more difficult dataset.

In conclusion, previous studies on multiple time series had two main limitations: they only studied small numbers of time series (≤ 8), when much larger numbers are available in popular datasets, and used synthetic datasets, with features simpler than those typically found in these popular datasets.

INTERACTIVE HORIZON GRAPHS

Interactive Horizon Graphs (IHG) unify RLC and HG by introducing interactive techniques to control the baseline position and the zoom factor applied to values. Interaction is meant to allow HG to remain effective even while exploring larger numbers of time series. Baseline panning and value zooming can be seen as variants of the commonly used pan and zoom interaction techniques [START_REF] Bederson | Pad++: A zoomable graphical sketchpad for exploring alternate interface physics[END_REF]-the baseline is controlled through a variant of panning and the number of bands through a variant of zooming. Thus, the pan and zoom interaction techniques are related to the y axis of the visualization instead of the x axis as described in [START_REF] Isenberg | A study on dual-scale data charts[END_REF]. We detail our interaction techniques in the following subsections.

Baseline Panning

Baseline panning allows users to interactively move the baseline along the y axis-in our implementation, this is achieved by dragging the mouse up/down with the right button pressed. Note that baseline panning does not change the positions on the x axis at all, unlike regular panning, and it does not change the height of the chart. The user's interaction with a single chart simultaneously changes the baselines on all small multiples. Because the baseline is always at the bottom of the chart, it does not move in response to the interaction. Rather, the series appear to shift up or down as the baseline changes and colors change as points in the series move from one band to the next (Figure 3).

Interactively changing the baseline overcomes a limitation of the fixed baseline used in traditional HG-because preattentive color perception (distinguishing between red and blue) is only effective for values around the baseline, points far from the baseline are more difficult to discriminate. Baseline panning allows a user to make transitions around a value of interest more salient. This can be particularly valuable if one is interested in identifying deviations from a specific baselinefor comparing the in body temperature for a patient against the patient's expected value. Meanwhile, finding a maximum value becomes a comparison of intensity of red plus height (y) estimation (first search the most red-saturated areas, then find the highest value which belongs to one of these areas).

Value Zooming

Value zooming allows users to specify the zoom factor using a continuous interaction-in our case, dragging the mouse up/down with the left button pressed. Note that value zooming does not change the scale of the x axis, unlike regular zooming, and it does not change the height the of chart, since the values will wrap around the lower border of the chart.

HG use a discrete number of bands, so changing from 2 to 3 bands triggers a sudden transition. The continuous interaction we propose prevents this abrupt change, resulting in a smooth and continuous zoom, as seen in the three zoom levels shown in Figure 4. The chart can be seen as if drawn on a tall sheet of paper which is wrapped around its baseline according to the zoom factor: when the shape of the chart reaches the top of the y axis, it is cut and appears at the bottom of the y axis, with a more saturated hue. The appropriate zoom factor depends on the scale of the variations one wants to analyze: observing small variations will result in a high zoom value and large variations in a low zoom value. Using Heer et al. [START_REF] Heer | Sizing the horizon: the effects of chart size and layering on the graphical perception of time series visualizations[END_REF] terminology, our zooming implementation keeps the height of the horizon graph fixed but increases the virtual resolution of the underlying chart.

We were interested in observing how users would adapt and understand this unusual metaphor. We believe that this interactive virtual resolution control provided by our zoom can be easily understood thanks to the paper-wrapping metaphor, and that this interaction can lead to substantially higher numbers of bands than the recommended two. However, increasing the number of bands makes it more difficult for users to discriminate the different color intensities. This trade off rests in the user's hands, according to the task and/or the data. While standard zooming techniques consist of focusing on a specific area and losing context information, our zooming implementation for IHG preserves both the visibility of the context and the details of small variations around the baseline.

The range r i of each band b i is computed differently for HG and IHG because of the different values for y b and because HG use a discrete number of bands b, while IHG use a continuous zoom value z:

r i = [y b + i h 2K , y b + (i + 1) h 2K ], with (a) (c) (b) (d)

HG

i ∈ [-b, b[ h = y M -y m K = b IHG i ∈ [-z , z [ h = max(|y b -y m |, |y b -y M |) K = z

Combination Of Pan And Zoom

The technique we provide never leads to loss of information thanks to the HG properties. Moreover, for both our pan and zoom interaction techniques, the visual feedback is different from a standard pan and zoom along the x axis and results in user-controlled transitions instead of sudden changes.

To illustrate the effectiveness of our technique, let's consider the basic task of finding the global maximum over multiple time series. This task is accomplished in two steps: first, the baseline is set at y M so that all the values are colored blue. Then, the value of the baseline is progressively decreased by the user until red values appear in one or several charts. The global maximum belongs to one of these charts. If two or more time series turn red for the same value of the baseline, the user will zoom in to enlarge these areas and the differences in magnitude will be visible.

Another typical use of our technique consists of locking the pan to a reference value of interest and zooming to highlight the differences with the other values. This case is illustrated in Figure 5: let's consider a time series with small variations around a specific value except during a period of time containing higher values, resulting in a high bump (5(a)). Using the recommended parameters (z = 2.0, y b = y M -ym 2 , 5(b)) slightly increases the small variations but the baseline separating the chart in two brings no interesting information because the value of interest is not near y b and HG is not adapted to such a case. With a well-chosen value for y b (5(c)) one can focus on the value of interest. Still, the differences between values are difficult to estimate. Combining pan and zoom (z = 8.5, y b = 0.08 × (y M -y m ), 5(d)) makes the small variations easy to read and compare. Furthermore, Figure 1(c) illustrates how Max can be easily accomplished using IHG in comparison to RLC and HG. These examples illustrate the importance of properly setting the number of bands and the value of the baseline. Those settings need to be interactively set because they depend on which part of the chart and on which type of variations (large or small) one is interested in.

Finally, we designed our pan and zoom interaction techniques keeping real-world scenarios in mind. For instance, baseline panning would let a doctor specify the base value for the body temperature of patients according to their health.The continuous zoom provides an effective way of exploring the temperatures of a city during one year; according to the zoom factor, seasonal, daily, or hourly variations may be observed.

USER STUDY

We designed an experiment to determine the usefulness of adding interactivity to HG. In the study we asked users to examine LSV datasets and perform three kinds of tasks using RLC, HG, and IHG. To quantify the impact of each approach, we measured the Time, Correctness, and Error magnitude for each visualization technique.

Data

We used several datasets, including unemployment rates and temperatures, during our pilot studies. However, for the main experiment we chose real-world data from Google Finance [START_REF]Google finance[END_REF]. We used the stock market history during February 2012 from 182 banks with no missing data for that period. We chose these datasets because they are LSV time series that evolve in a close range, making it necessary to use a common scale for all visualized charts. Because LSV time series have different levels of detail, we expected that HG would outperform RLC and that we would be able to differentiate HG and IHG, since both are multi-resolution visualization techniques.

Hypotheses

Our hypotheses for this experiment were as follows:

H 1
The benefits in terms of Time, Correctness and Error of IHG compared to RLC and HG will increase with the number of time series . This hypothesis is based on the intuition that the task becomes more difficult with larger numbers of time series but that interaction will help deal with the increasing scale. To test this hypothesis, we designed variants of the task using 2, 8, and 32 time series. We also predicted that the greater the number of time series, the less efficient RLC will be. H 2 IHG will be faster for all the tasks. H 3 HG with its recommended parameters (y b = y M -ym 2 and b = 2) will be less efficient than IHG for LSV time series.

Experimental Factors

We describe in the next subsections our experimental factors: visualization technique, number of time series N and task.

Visualization Techniques

Across all three visualization conditions (RLC, HG and IHG), each of the charts was given the same height and all charts shared the same value range and the same baseline value.

Based on previous work, we chose a constant height of 24 pixels for the charts, regardless of the number of displayed time series. Heer et al. found this height to be optimal for both RLC and 1-band mirrored HG [START_REF] Heer | Sizing the horizon: the effects of chart size and layering on the graphical perception of time series visualizations[END_REF], and using this size allows us to compare our results to theirs. We also made several specific choices in the design of each condition: RLC: for consistency with HG and IHG, the charts were filled in with the color corresponding to values above the baseline. Although the data values were not all positive, the baseline was at the overall dataset minimum value y m . HG: we reversed the meaning of red/blue in our color map because, during the experiment design and pilots, we tested datasets with temperatures that are usually encoded using blue for cold and red for warm. This flipping of colors does not bias the experiment since the coding is consistent over the three techniques. We used the recommended values y b = y M -ym 2 and b = 2. IHG: to facilitate learning, we chose the value of the baseline and the zoom factor at the initial stage to be the same as the ones for RLC, i. e., y m and 1.0, respectively. The color coding was identical to the one used for HG. During the experiment, the value of the baseline and zoom factor were displayed.

Numbers Of Time Series (N)

The related work on graphical perception of multiple time series often considered only two time series at a time [START_REF] Heer | Sizing the horizon: the effects of chart size and layering on the graphical perception of time series visualizations[END_REF][START_REF] Simkin | An Information-Processing Analysis of Graph Perception[END_REF]. More recently, Javed et al. compared different visualization techniques with higher values for N : their main study dealt with 2 to 8 time series and their follow-up included up to 16 time series [START_REF] Javed | Graphical perception of multiple time series[END_REF]. We considered sets of N=2 and N=8 time series so that we could compare our results against prior work. In addition, because one of our goals was to deal with larger numbers of time series and test the scalability of split-space techniques, we also considered sets of N=32 series.

Tasks

Based on the task taxonomy for time series developed by Andrienko et al. [START_REF] Aigner | Visualization of Time-Oriented Data[END_REF][START_REF] Andrienko | Exploratory Analysis of Spatial and Temporal Data: A Systematic Approach[END_REF], we chose one elementary task for direct comparison (Max), one elementary task for relationseeking (Disc), and one synoptic task for relation-seeking (Same) (Figure 6).

The Find the same (Same) task is a variant of the Andrienko et al.'s Slope task. Users are asked to select the time series that is exactly the same as a specified reference time series. We chose this alternative because of the very high difficulty in discerning the slope of time series using RLC with LSV datasets. Our selection of this particular set of tasks was motivated by our pilot studies and was designed to allow us to compare our results against prior work. We also discarded several other tasks from our experiment based on the results of pilot studies. For example, we did not ask users to find the global maximum across all the time series because IHG were clearly better for this task than the two

t (a) v 1 v 2 v 3 t 1 (b) v 1 v 2 v 3 t 2 t 3 (c) Figure 6
. Narrower visuals of the three tasks. (a) Max: select the time series having the highest value at t. Disc: select the time series i having the highest value at t i . Same: select the time series i, i > 1, being the copy of the reference time series i.

other techniques in terms of Correctness and Time. Furthermore, automatic techniques would outperform any interactive technique for this kind of basic task.

Find the Maximum (Max): We chose to have more control on the task than previous experiments to adapt it to LSV time series. A reference time series is randomly picked from the dataset and assigned a random position in the display order. This reference is marked at a random point in time t. Its associated value is V t . The other time series are then selected in the dataset if they satisfy the following condition: being v t the value of each additional time series at t, the time series is said to be comparable with the reference if:

V t -v t > 2% × (y M -y m ) V t -v t < 10% × (y M -y m )
By imposing these conditions, the minimum visual difference between the reference value and the remaining time series values at the shared marked point t is in the range [0.5, 2.5] pixels for the RLC technique. For HG and IHG, the difference in pixels is proportional to the virtual resolution [START_REF] Heer | Sizing the horizon: the effects of chart size and layering on the graphical perception of time series visualizations[END_REF], i. e., the number of bands. Discriminate (Disc): The time series are selected in the same way as in Max but each has its own random time-point t. Find the Same (Same): There is one more time series displayed for this task than for the two others (the reference).

Because we are focused on assessing visual perception of time series, we did not include additional features such as sorting or highlighting maximum values that might help users perform operations like Max and Disc. As in Javed et al.'s study [START_REF] Javed | Graphical perception of multiple time series[END_REF] we provided no scale or tick marks and displayed no numerical values. Participants were only able to analyze the shape and colors of the time series. Note that these tasks are very difficult to perform if the differences in magnitude between the values are small, which is the case for LSV datasets.

Overall Experiment Design

The dependent variables we measured are Time (continuous) and Correctness (binary). Because Correctness does not capture the error's magnitude, for Max and Disc we also measured the Error (continuous), which is defined as 100×e (e M -em) , where e is the absolute error measured, and e M and e m are the maximum and minimum possible errors. Error expresses the difference in percentage between the correct maximum value and the value chosen by the user. For Same, this additional measure has no meaning unless we subjectively define a similarity measure. Therefore, we only recorded the Correctness of the answer in Same. For IHG, we also measured how long each participant took to perform the pan and the zoom interactions, as well as their values at the end of each trial. Each participant performed four trials per technique × task × N combination.

The order of technique and task was counterbalanced using a Latin square to minimize learning effects.

Because the difficulty of the task is highly correlated with the number of time series [START_REF] Javed | Graphical perception of multiple time series[END_REF], the order of N was gradually increased instead of being randomized (first 2, then 8, and finally 32). In summary, the design included (3×techniques)×(3× tasks) × (3 × N ) × (4 × trials) = 108 trials per participant. For each, the time series were randomly selected in the dataset. The experimental session lasted about 45 minutes in total.

Participants finished the trials for a particular technique, separated into task blocks, before moving on to another one. Each time a new task began (three times for each technique), participants went through a short training for that block. This training consisted in a reminder of the task and four training trials, not limited in time to let participants establish their strategy for the task. During the training as well as the actual trials, participants received feedback as to whether their answer was correct or not. There were told that the Correctness of the answer was more important than the Time.

Participants

Nine participants (7 males, 2 females) were recruited from our research institute. Participants ranged from 23-36 years in age (mean 27, median 26), had normal or corrected-tonormal vision and were not color blind. Participants were all volunteers and were not paid for their participation in the experiment. All the participants (students as well as nonstudents) had a background in computer science and good chart reading skills. Six participants had already heard of RLC and only one knew HG.

Procedure

The participants watched a short introductory video explaining the RLC and HG techniques and illustrating the possibility of modifying the baseline to separate the values below and above it by coloring a standard line graph. They sat in front of a 19 inch LCD monitor (1280x1024 pixels) at a distance of approximately 50 cm and used only the mouse during the experiment. To select an answer time series, they had to double-click on it. To avoid accidental clicks, after having selected the time series, a dialog asked them to confirm their choice while the time kept running. This interaction was the only one available for RLC and HG. For IHG, pan and zoom were provided using the mouse by dragging vertically anywhere on the screen with one of the two mouse buttons pressed. The left button triggered the zoom and the right button the pan. Participants were able to practice until they understood the interface well. After each task and for each visualization technique, participants were asked to give a score for difficulty and describe the strategy they used. [START_REF] Cohen | Statistical power analysis for the behavioral sciences[END_REF] computed using the pooled standard deviation:

x < y for a small effect (.2 < d < .3), x y a medium effect (.3 < d < .8), x ≪ y a large effect (.8 < d < ∞).

RESULTS

All data were analyzed using repeated ANOVA measures. We applied a log transform to the measures of Time to obtain a quasi-normal distribution. Pairwise t-tests were done with the Bonferroni adjustments. Effect sizes were computed using the unbiased estimate of Cohen's d [START_REF] Cohen | Statistical power analysis for the behavioral sciences[END_REF], with the pooled standard deviation. We only report on significant effects that are summarized in Table 1, along with their effect size.

Use Of Pan And Zoom For Interactive Horizon Graphs

Table 2 presents participants' use of pan and zoom for IHG. For N=2, half the participants did not use any interaction at all. For N=8, 71.7% used both types of interaction. For N=32, 86.7% used both. The harder the task, the more interaction was used. We also observed that for all N , few participants used only pan or only zoom-both seem useful to most participants.

We also recorded the values of the baseline and the zoom factor at the end of each trial for IHG (Figure 8(a) and (b)) and the percentage of total time participants used pan and zoom (Figure 9(b)) using our kinematic logs. The end values are important measures because they correspond to the number of bands and the value of the baseline the participants estimated to be the best for each trial.

Questionnaire Results

For each technique × task × N , we asked participants to give a score between 1 and 4 for difficulty (1: very easy, 2: easy, 3: difficult, 4: very difficult). Mean difficulty by task and N is reported Figure 9(a). With 9 participants we could not perform a reliable ANOVA, but consistent ranking can be reported: all the 9 participants ranked the techniques in the same order regardless of the task and N : they ranked IHG first, HG second and RLC third.

SUMMARY AND DISCUSSION

The results confirmed our hypotheses that IHG were better than RLC and HG for large numbers of LSV time series.

Influence of Number of Time Series

In this subsection we detail the statistically significant differences between RLC, HG, and IHG for each N , and provide recommendations for the use of each technique.

For N=2: For Same, HG are faster than both RLC and IHG. This improvement is likely due to the fact that HG use colors that allow pre-attentive perception and recognition of key features. With IHG, participants lost time using the interactions, looking for recognizable shapes using pan and zoom. For Max and Disc, both RLC and HG are faster than IHG: participants had been told that Correctness was more important than Time and we observed that they double-checked their answers using pan and zoom whenever they were in doubt. Because there is no difference in Correctness or Error for N=2, we recommend using HG for N=8 or fewer. RLC can be used for elementary comparison and relation-seeking tasks such as Max and Disc. However, we do not recommend IHG for such small numbers of series because the interaction technique distracts users and does not bring any benefit.

For N=8: For both Max and Disc, HG are faster than IHG. The rationale is likely the same as for N=2-participants lost time using the interactions. Moreover, since the initial state of IHG was identical to RLC (z = 1, y b = y m ), participants had to interact to obtain a visualization similar to HG, while for HG the default configuration was readily available. The remarkable distinction between N=2 and N=8 is that, in the latter, there are significant differences in Correctness and Error. For Max, IHG have higher Correctness than RLC because the zoom allows users to discern fine differences between charts. Since IHG and HG amplify the small variations, both techniques induce lower Error than RLC. For Disc, IHG have higher Correctness and lower Error than RLC for the same reasons.

In summary, IHG are 1.2 and 1.02 times more correct than RLC and HG for Same and 1.2 and 1.06 times more correct than RLC and HG for Disc. All participants completed the tasks with no error using IHG.

We recommend using IHG or HG and avoiding RLC for medium numbers of time series when performing elementary comparison and relation-seeking tasks. The difference between HG and RLC was not highlighted in previous studies and is almost certainly due to the properties of our datasets.

For N=32, both IHG and HG have higher Correctness and lower Error than RLC for all tasks except for Same where there is no difference in Correctness between HG and RLC. RLC are clearly limiting for large numbers of time series, regardless of the task. Interestingly, for Disc, IHG have higher Correctness and lower Error than HG. For this task-which is the hardest, involving visually browsing the charts vertically and horizontally-IHG exhibit better results than HG.

IHG are more correct than both RLC and HG for Same (1.4 and 1.1 times more), for Max (1.5 and 1.03 times more), and for Disc (2.4 and 1.2 times more). Not only are there significant differences between the techniques, but the effect size indicates that these differences are substantial.

The Error measure also shows substantial differences: for Max, the Error for IHG is 9.6 times less than for RLC and 1.3 times less than for HG. For Disc, Error for IHG is 7.5 times less than RLC and 2.7 times less than for HG. This confirms that IHG leads to more correct answers and that, even when an answer is wrong, the Error is lesser than when using RLC and HG.

For Time, there is no significant difference between IHG and HG regardless of the task. This is in contrast to the results for smaller N , where IHG were usually slower than the other techniques. Here, the overhead of interaction with the charts was less than that of visual search.

We strongly recommend using IHG for large numbers of time series and avoiding RLC. We also found that for large and medium numbers of time series, HG are more efficient than RLC, in contrast to previously published studies. Our work is the first to reveal these advantages of HG.

Time vs. Accuracy

The Time to perform Max and Disc is similar for all three techniques for N=32 (Figure 7(b)) but the Correctness for RLC decreases severely between N=8 and N=32 (Figure 7(a)). Participants answered as quickly as in HG and IHG, but with very low Correctness. Participants' answers to our questionnaire explain this effect-for the RLC technique, their strategy was to quickly identify potential answers and to pick one randomly, without being sure of the answer. Clearly, regardless of how much time users take with RLC for N=32, they cannot perform Max and Disc correctly. We observed the same effect for HG, to a lower extent, but not for IHG.

Tasks

As expected, Correctness decreases when N increases for all tasks. Furthermore, task difficulty can be clearly seen from the trends in Error: Same is the easiest task, followed by Max, with Disc being the hardest. Participants' questionnaire responses corroborate these results-they found Disc to be the hardest task and found that the difficulty dramatically increased with the number of time series (Figure 9(a)). These results are in agreement with Javed et al. [START_REF] Javed | Graphical perception of multiple time series[END_REF]. However, our results do not show that HG are slower than RLC for Max, probably due to our use of LSV datasets.

Hypothesis Control

We confirm H 1 : N=32 is the only value of N that showed clear differences between the three techniques. IHG have the highest Correctness and the lowest Error, followed by HG, while RLC was much worse. HG also have significantly better scores than RLC for both Correctness and Error. This difference had not been highlighted in previous studies and is explained by our use of LSV data-suggesting a need for multi-resolution techniques.

We reject H 2 : our results show that at least for task Same, IHG are significantly faster than RLC, but there is no significant difference with HG. This is due to the fact that, unlike HG, IHG require users to interact with the chart to obtain a useful configuration, which takes additional time.

We partially confirm H 3 : the Correctness for HG decreases when N increases and is lower than when using IHG. We did not find any significant difference between HG and IHG for Max, but IHG have substantially higher Correctness and less Error than HG for Disc. We were however surprised to see how robust HG are with respect to the number of time series; we did not expect such good results for this technique.

Pan And Zoom

End-values: Contrary to [START_REF] Heer | Sizing the horizon: the effects of chart size and layering on the graphical perception of time series visualizations[END_REF], the most useful zoom level can be well above 2. This can be seen in Figure 8(b), which shows z at the end of each trial. We interpret the final value as being the most comfortable zoom level for answering the task.

For Max and Disc users' final zoom value is frequently the maximum zoom we allowed-10 bands. The recommended number of bands was rarely the one chosen for N=8 and N=32. Our conclusion is that there is no default value for this parameter-the need for a higher or lower number of bands is related to the task, the dataset, and N . Conversely, the use of lower zoom values when completing Same can be explained by the strategy the participants adopted. Most participants modified the value of y b until a specific composition of color and shape appeared in the reference time series. Then they visually browsed all the time series to search this feature.

The baseline end value (Figure 8(a)) was rarely at the classic value of the baseline (50% of the chart height). This result is certainly due to the datasets, but confirms that if users have the possibility of modifying the baseline, they will choose a value which can be in a continuous range and will not limit their choice to a single value.

Interactions: The percentage of interaction time (Figure 9(b)) for N=2 is low and does not linearly increase with N . Rather, it is about the same for both N=8 and N=32-around 50% of the total time. This confirms that IHG are more useful for large numbers of time series but are distracting for N=2.

Comparison With Previous Studies

The differences between our study and the previous ones can be attributed to three factors: the use of interaction in IHG, the use of LSV datasets, and the use of the Same task instead of Slope. For N=8, contrary to previous studies [START_REF] Javed | Graphical perception of multiple time series[END_REF], HG are significantly more efficient than RLC, likely because we used LSV datasets. Previous studies never tried N=32 when all tasks become very difficult and interaction helps immensely. As for the choice of tasks, we have not compared IHG with the other techniques for Slope since this task was too hard to perform on LSV datasets, especially for RLC; the benefit of IHG on more uniform datasets remains to be studied.

Heer et al. recommended not to use too many bands [START_REF] Heer | Sizing the horizon: the effects of chart size and layering on the graphical perception of time series visualizations[END_REF] for value estimation tasks, not considered in our experiments. We are not sure value extraction would be accurate on LSV datasets, even with few bands.

General Implications

We used LSV datasets which are usually more challenging than the synthetic datasets used in previous studies, and also ecologically more valid. Our results show that more varied datasets should be used for future experiments to obtain more generalizable results.

Finally, we believe that IHG can decrease the learning curve of HG because they start with the familiar RLC representation and, with continuous interactions using the pan and zoom, show novice users how HG are constructed. Our results highlight the fact that adding interaction to existing techniques can notably improve their performance as well as their usability.

Limitations and future work

Our recommendations for design are valid under some conditions that we detail below.

Participants: Our participants were students and researchers from HCI and Infovis and additional studies are required to evaluate IHG for novice users. N: We constrained the number of time series to the height of a standard screen without having to scroll and more than 32 time series would require a larger screen. Datasets: Our results are valid for LSV datasets, for which HG and IHG perform well. Having shown that IHG are efficient for at least one category of datasets, in future work we plan to investigate a deeper range of datasets. Tasks: We did not consider value estimation tasks, since it requires users to perform a considerable amount of mental math using HG and IHG. However, alternative interaction techniques can be designed specifically to support value reading and extraction.

CONCLUSION

We have presented Interactive Horizon Graphs (IHG), an efficient interactive technique for exploring multiple time series which unifies two split-space visualization techniques: Reduced Line Charts (RLC) and Horizon Graphs (HG). We have shown that IHG outperforms RLC and HG for several tasks in the most difficult conditions, thanks to interactive control of its two parameters: the baseline value and the zoom factor. Both relate to the number of bands traditionally used by HG. We have shown that IHG perform well with up to 32 time series, when previous work only tested up to 16. We also found that HG perform better than RLC for our datasets.

We conclude that systems visualizing time series using small multiples should provide our interaction techniques as a default. Our techniques generally improve performance on visual exploration tasks, except during the learning phase or for very small sets where interactions can be distracting.

Our contributions are: (i) the unification of RLC and HG by using interactive pan and zoom, (ii) a demonstration that IHG can scale up to 32 time series, and (iii) an evaluation using real LSV datasets rather than synthetic datasets with clear landmarks that help visual search tasks.

In the future we plan to investigate displays with more than 32 time series using larger screens and specialized hardware such as wall-sized displays. We are also interested in evaluating the benefits of our pan and zoom techniques individually.

This work has shown that our simple interactions can unify two visualization techniques and substantially improve their efficiency. We hope it will be adopted to limit the proliferation of slightly different visualization techniques currently provided to explore multiple time series.

Figure 2 .

 2 Figure 2. The construction of a Horizon Graph with 3 bands, adapted from [12, 19]. (a) Values are colored (blue and red) according to their value compared to the baseline: blue below and red above. (b) The chart is split in 3 bands (3 reds and 3 blues). (c) Values below the baseline are mirrored. (d) The bands are wrapped.

Figure 2

 2 Figure 2 illustrates the construction of HG from a line chart centered around a baseline. First, the values are colored ac-

For 2 (

 2 RLC, HG, and IHG, all the charts have the same range of values for the y axis: [y m , y M ], with y m and y M being the minimum and the maximum values in the visualized dataset. The three techniques have different values for the baseline y b : y bRLC = y m (the baseline is always at the bottom of the chart), y bHG = y M -ym the baseline crosses the y axis at its middle point), and y bIHG ∈ [y m , y M ] (the baseline can take any value in the range of values).

Figure 3 .

 3 Figure 3. Baseline panning: The bottom charts represent the view of the time series using IHG for 4 different values of y b overlaying the original line chart (for a constant zoom factor z = 2). Dragging upwards the mouse with the right button pressed increases the value of y b (sequence from left to right) and values going under y b become blue. The original line chart is presented above each step for better understanding.

Figure 4 . 2 )

 42 Figure 4. Value zooming: (a) From a standard mirrored line chart, the zoom value z is progressively increased by dragging upwards the mouse with the left button pressed (for a constant baseline y b = y M -ym 2 ): (b) z = 1.0, (c) z = 1.35, (d) z = 1.70. Values reaching the top of the y axis appear at the bottom of the chart, with a more saturated hue. The original chart (deformed according to z) is overlaid for each step, for better understanding.

Figure 5 .

 5 Figure 5. Four views of a time series illustrating the importance of the interactive settings of the baseline value y b and the zoom factor z. (a) y b = ym, z = 1.0; (b) y b = y M -ym 2 , z = 2.0; (c) y b = 0.08(y M -ym), z = 2.0; (d) y b = 0.08(y M -ym), z = 8.5.

Figure 7 .

 7 Figure 7. (a) Correctness and (b) completion time plots for each technique for the overall study (all tasks combined) as a function of N .

Figure 8 .Figure 9 .

 89 Figure 8. (a) Pan and (b) zoom values at the end of the trials by task and number of time series N for IHG. In (a), the grey horizontal line at 0.5 indicates the value of the baseline using HG (50% of the chart height). In (b), the grey horizontal lines at z = 2 and z = 4 are the recommended and the maximum values of b.

Figure 9 (

 9 Figure 9(b) illustrates this observation-even for N=2, the use of pan and zoom represents up to 50% of the trials' time.

Figure 7 (

 7 a) illustrates the scalability of each technique as a function of N , showing a clear advantage for IHG.

Figure 7 (

 7 Figure 7(b) illustrates the Time to accomplish the task as a function of N . This shows a different trend than for Correctness-the Time for IHG and HG increases similarly with larger N , whereas the increase for RLC is much greater.

Tasks on multiple time series

	Time series visualization techniques have been studied exten-
	sively and prior work has evaluated their use for a variety of
	different tasks. According to Andrienko et al. [2], tasks on
	multiple time series can be of two types: elementary (about
	individual data elements) or synoptic (about a set of values).
	For each type, the tasks can be direct/inverse comparison tasks
	or relation-seeking tasks. The closest study to our work, that
	inspired us [19], evaluated RLC and HG considering three
	tasks: Maximum, Discriminate and Slope.
	Find the Maximum ( Max)
	Max is an elementary task for direct comparison. It consists
	of determining which of several time series has the highest
	(or lowest) value at a shared marked point [19, 20]. Javed et
	al. compared RLC and HG using this task for 2,4 and 8 time
	series. Their study revealed that RLC were faster than HG but
	they did not find any significant result for Correctness.

Table 1 .

 1 Significant results for each factor by N and task. The best value for each line is in bold. ≤ 0.05, ** for p ≤ 0.001, *** for p ≤ 0.0001 We report Cohen-d's effect size

	N	Factor	Task F 2,16	p	Pairwise mean comparisons	RLC	Mean HG	IHG
			Same 7.71	*	HG	RLC & HG	IHG	4.45s	2.78s	3.80s
	2	Time	Max	7.08	*	RLC	IHG & HG	IHG	2.77s	3.02s	4.93s
			Disc	4.15	*	RLC	IHG & HG	IHG	3.30s	3.74s	5.49s
		Time	Max 10.87 ** Disc 5.45 *	RLC	HG ≪ IHG IHG & HG	IHG	7.69s 9.59s 10.18s 14.45s 5.73s 11.40s
	8	Correc-tness	Max Disc	4.96 9.45	* *		RLC RLC < IHG IHG		0.833 0.972 0.805 0.944	1.0 1.0
		Error	Max Disc	5.17 6.15	* *	IHG	RLC & HG IHG RLC	RLC	7.43 7.82	0.73 1.43	0.0 0.0
		Time	Same 7.38	*	IHG ≪ RLC & HG	RLC	30.06s 20.99s 18.17s
	32	Correc-tness	Same 6.52 Max 10.20 ** * Disc 13.36 ** RLC ≪ IHG & HG < IHG & RLC RLC ≪ IHG RLC ≪ IHG & RLC HG	0.694 0.639 0.916 0.944 0.92 1.0 HG 0.361 0.722 0.871
		Error	Max Disc 29.44 *** IHG ≪ RLC & IHG 9.61 ** IHG ≪ RLC & HG HG & HG RLC	12.9 RLC 24.15	2.01 9.01	1.34 3.23
					* for p

Table 2 .

 2 Percent of participants using no interaction, only the pan, only the zoom, and both interaction by N, all tasks combined.

	N None Only Pan Only Zoom Both
	2	46.7	6.6	10	36.7
	8	3.3	6.7	18	71.7
	32	3.3	0	10	86.7

ACKNOWLEDGMENTS

The authors thank P. Irani for introducing Horizon Graphs to them, P. Dragicevic for his constructive suggestions, A. Bezerianos, A. Spritzer, B. Bach, J. Boy and W. Willett for their help proofreading the document.