Aline Menin
email: aline.menin@univ-grenoble-alpes.fr

Sonia Chardonnel
email: sonia.chardonnel@univ-grenoble-alpes.fr

Paule-Annick Davoine
email: paule-annick.davoine@univ-grenoble-alpes.fr

Luciana Nedel
email: nedel@inf.ufrgs.br

eSTIMe: Towards an All-in-One Geovisualization Environment for Daily Mobility Analysis

Daily mobility data describes individual displacements over 24-hours periods and are an important source of information to understand the real rhythm of a city, to provide appropriate transportation policies, and to support investment decisions. Geovisualization researchers have designed multiple coordinated views environments, combining spatial and temporal dimensions, and providing indicators comparison. Daily mobility analysis is complex and requires simultaneous exploration and combination of different indicators at different spatial and temporal granularity levels. The design of effective geovisualization environments supporting this analysis evokes several challenges due to the diversity and multiplicity of indicators, the granularity of space and time, and time integration. In this paper, we propose a geovisualization approach enabling the dynamic visualization of diverse indicators, as well as the exploration of space, time, and other attributes. We use multiple screens embedding customizable dashboards and allowing the users to arrange views and compare indicators as it better fits their analysis. It also integrates a mobile device serving as a display and interaction tool to physically control the evolution of the visualization on time.

I. INTRODUCTION

The study of the forms of settlements and the organization of individuals' activity programs in space and time is important to understand and guide the development of better urban environments. In the past few years, the rise of tracking technology enabled the collection of different sorts of data describing the population's movements within a territory. The spatiotemporal Triad scheme [START_REF] Peuquet | It's About Time: A Conceptual Framework for the Representation of Temporal Dynamics in Geographic Information Systems[END_REF] is commonly used to analyze this movement data since it enables the exploration of entities of interest in time and space at different levels of aggregation.

Urban mobility data can be studied on the basis of three entities: the flows and displacements, the territory settlement dynamics, and the individual trajectories. While the flows describe the number of displacements between two spatial locations, the territory settlement dynamics consider the presence and mobility of the population. Individual trajectories describe the sequence of activities performed by someone in space and time. The analysis of these entities rely on the derivation of indicators that can be used to provide information to support decision-making for transportation policies and investments; as a basis for comparisons among metropolitan areas, and; as a sense of whether system performance is improving or getting worse [START_REF] Council | Key transportation indicators: Summary of a workshop[END_REF].

Along with the emergence of geovisualization techniques, geographers began to work with computer scientists for developing conceptual frameworks and methodologies based on a visual and exploratory analysis of spatiotemporal data [START_REF] Andrienko | Exploratory Analysis of Spatial and Temporal Data: A Systematic Approach[END_REF]. These solutions often comprise dashboards with numerous interactive and coordinated views with graphics and cartographic representations of the data. It enables the interaction with multiple dimensions of the represented phenomenon to conduct spatial, temporal, and spatiotemporal analyses.

The design of existing geovisualization environments is frequently driven by specific problems, such as traffic jam detection [START_REF] Yan | Visual analytics of bikesharing data based on tensor factorization[END_REF], usage patterns of shared bicycles systems [START_REF] Shi | The visual analysis of flow pattern for public bicycle system[END_REF], social segregation in metropolitan regions [START_REF] Le Roux | Social segregation around the clock in the Paris region (France)[END_REF], and life or individual trajectories analysis [START_REF] Cochey | Modes de représentation des trajectoires quotidiennes des habitants[END_REF]- [START_REF] Otten | Are there networks in maps? An experimental visualization of personal movement data[END_REF]. It would use data sources suitable to answer the problem-related questions, which might not require information on activity programs, for instance. It likely to favor only one form of representation, which is centered either on the territory settlement dynamics (e.g., through animated maps [START_REF] Shi | UrbanFACET: Visually Profiling Cities from Mobile Device Recorded Movement Data of Millions of City Residents[END_REF]), or the individual's movements (e.g., visualizing trajectories in 3D through the space-time cube -STC [START_REF] Tominski | Stackingbased visualization of trajectory attribute data[END_REF]). To the extent of our knowledge, there is not an unified environment (free and accessible) that gives the user the possibility to, simultaneously, explore the indicators summarizing aspects of displacements and flows, and to analyze and visualize the mobility dynamics at the individual and population levels.

The design and development of such unified environment evokes multiple challenges, such as conceiving visualization techniques suited to represent urban mobility indicators and to define interaction methods to handle the dialogue between space and time, while exploring the data at different levels of aggregation. This process should also consider the reasoning mechanisms supporting the visual analysis, which are associated with a cognitive process, resulting in different ways to which users perceive the visual representations. Hence, the proposed environment should be evaluated to guarantee its effectiveness, efficiency, and user satisfaction [START_REF] Yi | Understanding and characterizing insights: How do people gain insights using information visualization?[END_REF].

Our approach aspires the design and development of a geovisualization tool for urban mobility analysis, such as the one described above. We propose a multi-screen environment composed of customizable dashboards and a movement-based interaction technique for controlling the temporal evolution of the data. A tangible interface supported by a mobile device was designed to control space and time, and a novel visualization technique (the mobility wheel) based on a circular doublering donut diagram was proposed to represent the mobility practices of a population (see Fig. 1). We also present the development and evaluation of a prototype that supports the spatiotemporal analysis of flows and displacements and the territory settlement dynamics.

The remainder of this paper is organized as follows. Section II presents previous works on visual solutions for urban mobility data; analytical dashboards, and the use of mobile devices on information visualization. Section III presents the specifications that guided our proposal while Section IV details the eSTIMe prototype. Sections V and VI present the pilot study and the first impressions of users, and the evaluation process we used. Finally, Sections VII and VIII discuss our results, limitations, conclusions and future work.

II. RELATED WORK

Studies on urban mobility have increased in the last years, especially due to the diversity of data sources available, providing information on individuals' movements. In addition to the visualization tools mentioned earlier, Shi et al. [START_REF] Shi | UrbanFACET: Visually Profiling Cities from Mobile Device Recorded Movement Data of Millions of City Residents[END_REF] visually explore mobility metrics to identify vibrancy, fluidity, commutation, and diversity patterns. Lu et al. propose a ranking-based visual analysis method to explore vehicles travel behavior [START_REF] Lu | TrajRank: Exploring travel behaviour on a route by trajectory ranking[END_REF], and use taxis trajectories to visually explore origin-destination (OD) patterns [START_REF] Lu | Exploring OD patterns of interested region based on taxi trajectories[END_REF] .

Since the analysis of the public transportation system (PTS) passengers' behavior is valuable for transportation researchers and urban planners, visual solutions were designed to explore this data [START_REF] Wang | A Visual Analysis System for Exploring Passenger Flow Information at Multiple Levels[END_REF], [START_REF] Zhang | Peoplevis: A visual analysis system for mining travel behavior[END_REF]. Zeng et al. [START_REF] Zeng | Visualizing the Relationship Between Human Mobility and Points of Interest[END_REF] analyze the impact of mobility-related factors (riding, transfer and waiting time), and their temporal variations on the shape of passenger mobility.

Twenty-five years ago, bike-sharing systems were designed and today's technology provides usage data serving as complementary information to understand urban mobility. Shi et al. [START_REF] Shi | The visual analysis of flow pattern for public bicycle system[END_REF] propose a visual analytics system: to advice for optimal bicycle dispatch via stations categorization based on their main functions; to explore the spatial direction of biking moving via flow correlations and differences among multiple stations; and to visualize the influence of multiple factors on bicycle rental numbers. Latent user activity patterns in bike-sharing and their comparison in/between cities is also possible [START_REF] Yan | Visual analytics of bikesharing data based on tensor factorization[END_REF].

Ma et al. [START_REF] Ma | Mobility Viewer: An eulerian approach for studying urban crowd flow[END_REF] visually explore flow crowd volumes, directional dynamics, and spatiotemporal patterns to inspect human social relations and their physical movements, while Zeng et al. [START_REF] Zeng | Visualizing waypoints-constrained origin-destination patterns for massive transportation data[END_REF] propose an interactive points-of-interest (POI) mobility signature to illustrate how human mobility varies over POIs in different categories and across different areas. Techniques like Voronoi tesselations and stacked elliptical activity glyphs are employed to visualize activity regions and to detect urban regions sharing similar activity patterns [START_REF] Wu | MobiSeg: Interactive region segmentation using heterogeneous mobility data[END_REF].

These studies share the goal of exploring urban mobility patterns. Their conception is often founded on hypotheses, and they use databases describing mobility mostly through spatiotemporal data, without taking into account attributes that could explain why and how people move. Understanding the reasons for people's displacements and their modes of transportation is as relevant for understanding the urban mobility dynamics as for describing their trajectories in space and time. Therefore, the relevance of an environment that enables the exploration of every dimension of the data and their internal relations is evident.

Faceted analytical dashboards are "a set of interactive charts (primarily graphs and tables) that simultaneously reside on a single screen, each of which presents a different view of a common dataset, and is used to analyze that information" [START_REF] Few | Dashboard confusion revisited[END_REF]. These powerful decision-support tools applied to geographic information visualization have been proved to increase the spatial thinking performance, and may also improve the user performance [START_REF] Fischer | Developing and evaluating a geographic information dashboard to improve spatial task performance[END_REF].

Chitarro [START_REF] Chittaro | Visualizing information on mobile devices[END_REF] discusses the challenges and advantages of visualizing information on mobile devices' screens, such as the usefulness of mobile-map applications for navigation and interaction. The transfer of multiple coordinated views (MCV) visualizations from normal-size monitors to large displays is a growing practice. Nonetheless, this requires new interaction techniques, since using the traditional mouse might be neither possible nor efficient. Langner et al. [START_REF] Langner | Multiple coordinated views at large displays for multiple users: Empirical findings on user behavior, movements, and distances[END_REF] and Kister et al. [START_REF] Kister | GraSp: Combining Spatially-aware Mobile Devices and a Display Wall for Graph Visualization and Interaction[END_REF] propose sets of interaction techniques for large displays using mobile devices. Pahud et al. [START_REF] Pahud | Mobiles as Portals for Interacting with Virtual Data Visualizations[END_REF] use the mobile device as a sort of portal through which the user can explore, interact, and annotate n-dimensional data visualizations. Pietroszek et al. [START_REF] Pietroszek | Tiltcasting: 3D Interaction on Large Displays Using a Mobile Device[END_REF] leverage the tilting movement of a mobile device to interact into a 3D space by "casting" the 2D plane of the device. Besanon et al. [START_REF] Besanc ¸on | Hybrid tactile/tangible interaction for 3d data exploration[END_REF] use complementary tangible and tactile inputs to achieve common 3D visualization tasks.

III. DESIGN RATIONALE

A. Assumptions

As stated by LeRoux et al. [START_REF] Le Roux | Social segregation around the clock in the Paris region (France)[END_REF], the rhythm of a city can change from day to nighttime. They studied the social composition of different neighborhoods over 24-hours and verified that it is similar during the night, but it evolves during the daytime, as the most favored people would move towards areas providing more local resources, while the disadvantaged people would be retained at their residential neighborhood. Therefore, the study of urban mobility through individuals' daily activity-based trips can assist public agents, e.g., urban planners, on targeting areas to implement interventions more connected with the real rhythm of the city.

Daily mobility data describes the movements of individuals throughout a studied territory along with 24-hours. It contains information on displacements performed to achieve a set of goals, such as going to work, to the school, or visiting someone. These goals describe people's motivations to move from one place to another, as well as their activities when staying at their final spatial location. In this context, an individual trajectory consists of a sequence of stops and moves. The former described a time interval when the individual was present in a spatial location performing a specific activity, while the latter represents a spatiotemporal line defined by two locations representing either two consecutive stops or a trajectory beginning or end [START_REF] Baglioni | An ontologybased approach for the semantic modelling and reasoning on trajectories[END_REF].

The mobility indicators should be easy to interpret, presenting the actual situation through a representative picture, and enabling comparisons with other indicators [START_REF] Costa | Urban Mobility Indexes: A Brief Review of the Literature[END_REF]. Data exploration from the earlier mentioned entities of interest relies on the derivation of complementary indicators. For instance, indicators summarizing the flows and displacements can help to understand the influence of population migrations on a territorial settlement. The analysis of individual trajectories through the activity-based approach [START_REF] Mcnally | The activity-based approach[END_REF] allows to identify and characterize complex travel behavior, as well as extreme profiles such as hyperactive and stationary individuals.

Many areas within urban policies benefit from daily mobility analysis, supporting decisions on transportation offers, accessibility, air quality control, public health, and wellbeing. Thus, numerous experts (e.g., researchers, diagnostic managers, local authorities) have to manipulate mobility data to extract knowledge from it, without being transportation specialists. They compose the profile of the end-users of our geovisualization environment. Thus, our proposal should enable these users to:

• describe the daily mobility according to three entities of interest: the flows and displacements, the territory settlement dynamics, and the individual trajectories • analyze and compare complementary indicators in the aggregate and individual levels • explore the temporal dynamics of indicators to identify the daily rhythms of the city and its population • compose the analytical dashboard according to their needs, choosing the indicators, spatial zones and periods

B. Our Approach

The integration of time and space dimensions is itself a challenge on cartographic and geovisual representations. Smallmultiples and animation are the foremost used techniques to dynamically explore time. The first technique displays the information changes side-by-side via time slices, which suffers from spatial limitation and resolution since each slice reduces as their number increases. The second option can be thought as a movie presenting the information as time slices one after another in a pre-defined order. Though animation does not suffers from low spatial resolution, fast animations can be difficult to understand, since the user must rely on their memory to understand the data [START_REF] Bach | A Descriptive Framework for Temporal Data Visualizations Based on Generalized Space-Time Cubes[END_REF].

The interaction method proposed by us to explore time relies on the animation concept. While we still present the information changes in the form of consecutive time slices, we allow the user to physically control it by tilting a tablet.Our inspiration comes from the use of mobile devices to interact with visualizations and 3D applications [START_REF] Grandi | Design and assessment of a collaborative 3D interaction technique for handheld augmented reality[END_REF], and the advantages of using it as a second screen [START_REF] Pagno | Guidelines for designing dynamic applications with second screen[END_REF]. Intensive bodily interaction is known to be more engaging [START_REF] Arvola | Device-orientation is more engaging than drag (at least in mobile computing)[END_REF], and proprioception (i.e. the sense of self-movement and body position) could help the user to retain information by using the position and orientation of their hands and wrists as a recall reference. More than interacting with the temporal dimension, the mobile device also serves as a second screen holding map-based views and a tactile interaction space to manipulate indicators and views.

Analytical dashboards are largely used in visualization, being designed through a set of defined and effective views to achieve the user's goals. In this work, we want to give the users a certain freedom so they can custom the dashboard as they judge suitable to their analysis. Believing that larger workspaces could improve the analysis, we adopt customizable dashboards embedded into a multi synchronized screens environment. Further, this approach provide enough space to compare indicators at different spatiotemporal granularities.

As a proof of concept we developed eSTIMe (Fig. 1), a prototype to explore daily mobility data in the aggregate level.

IV. ESTIME

A. Data Description eSTIMe aims to support different datasets describing daily mobility, regardless of their sources. Currently, we use the data from a Household Travel Survey (HTS), since it provides information on individual displacements in space and time, including their motivations and transportation modes. This enables us to derive the individual activity-based trips and to aggregate presence and mobility of the population at different spatial locations and time intervals, as well as to derive the volume of flows between different locations. We recovered the 2010 edition [START_REF] Cerema | Enquête Ménages Déplacements (EMD)[END_REF] of a survey regularly carried out in the region of Grenoble, France, since 1976.

The data includes the displacements performed by all household members aged five and older during 24-hours, from 4am (the day before) to 4am (the survey day). It details the departure and arrival location and time, transportation mode and motivation for each displacement. The locations are described by places (pulling sectors defined in the survey), and the temporal dimension is discretized into one-hour intervals. The survey provides data on about 63,000 trips performed on weekdays from 7,600 households. We provide a diverse spatial granularity through three territorial partitions (97, 39, and 12 sectors); they all contain smaller surfaces in inner Grenoble and larger ones in the mountain area.

B. Map View

Indicators summarizing population's presence in different locations are visualized through a choropleth map, a wellknown technique used for geographical data representation. We derived indicators of presence density per location, i.e. present persons per square kilometer; fluctuation measures the rising and falling of population along the day through the difference between people present and the sector population, and; attractiveness, which identify whether the real density of a sector is equivalent to the population density [START_REF] André-Poyaud | La mobilité au coeur des emplois du temps des citadins[END_REF]. Since presence density and fluctuation can be explored over 24 hours and per time interval, their maps have two legends: one explains the values for the current time interval, and the other the values for the whole day. Fluctuation values represent population gain and lost. Attractiveness indicates equilibrium between real and population density as 1 (values over 1 indicate greater real density and under otherwise). Fluctuation and attractiveness are depicted through diverging color scales, while density uses a linear color scale.

C. Mobility Wheel

Indicators summarizing the mobility practices of a population complement the presence dynamics. They reveal active persons' routines along the day through the number of people moving from one place to another at each time interval and the distribution of these movements according to different transportation modes. For each sector, the indicator represents the number of persons moving towards this location, and the transportation modes used to reach this destination. Timewheels are often used to represent time-series data [START_REF] Zhao | Activities, ringmaps and geovisualization of large human movement fields[END_REF], which inspired the design of our Mobility Wheel (Fig. 2). We adapted the view of a double-ring donut chart, forming each ring with 24 rectangles symbolizing 24-hours. Each time interval on rings display: in the outermost, people in movement per sector's population; in the innermost, the partition of movements per transportation mode. Arc charts displayed sideby-side next to the wheel allow to zoom into the transportation modes distribution, and to compare them across 6 time intervals. This view helps to identify the mobility patterns of the population over the day at a glance and to understand how they move around the territory by matching the intensity of movement and the transportation modes they engage.

D. Flows View

Representing flows without losing the spatial component and avoiding occlusion is a challenging task [START_REF] Bahoken | Mapping flow matrices, a contribution[END_REF]. Flow maps are largely used to represent the volume of flows within a territory, but they have constraints on the design of legible maps. Therefore, we adopted the origin-destination (OD) pair relationship view introduced by Shi et al. [START_REF] Shi | The visual analysis of flow pattern for public bicycle system[END_REF] to explore OD flows between spatial locations. It uses a chord diagram, where arcs represent spatial locations. The arcs are connected by ribbons, which thickness describe the flows volume exchanged between the locations. The ribbon color determine the flow origin. We provide spatial information virtually binding the chord diagram to the map view on the tablet display. Flows filtering is available by selecting a location on the map. The indicator can be explored over 24 hours or per time period. The view can display flows exchanges within the entire territory, or the user can choose a set of up to 10 locations (for the sake of readability).

E. Interaction

eSTIMe supports regular interactions such as pan and zoom, as well as spatiotemporal filtering. The angles produced via the tablet tilting are mapped to slots in the time picker. Since the daily mobility events generate everyday patterns, a cyclic arrangement (timewheel) seems appropriate. The existing environments often arrange time linearly in a timeline. Our interface, for the other hand, provides both formats upon choice. The user would tilt the tablet either counter-and clockwise for selecting time intervals in the timewheel, or from left to right and contrariwise in the timeline.

The main interface, so called Controller, provides a menu to choose the indicators and customize them under different spatiotemporal granularities before displaying them on a dashboard. It can hold multiple customizable dashboards. By default, each dashboard comprises four blank windows, progressively fulfilled according to the user's needs. Time and space are explored via a time picker and a map available on the Controller. The former is used to change time and to open arc charts next to Mobility Wheels. The map view supports pan and zoom; selection of locations to generate the Flows View or the Mobility Wheel; and spatial filtering on the Flows View. In case our prospect users want to create reports of their exploration, we also provide them with the possibility to download the views as an image.

F. Implementation Details

The basic setup of eSTIMe consists on instantiate it twice: one instance holds the main interface and should be displayed on the tablet, while the second one comprises a dashboard, where the views are displayed and organized. It should be displayed on a large screen for a better experience. The prototype is a Web-based application. A server was developed in Java and uses WebSocket technology to manage the communication between the Controller and the dashboards. The client was developed in JavaScript and uses D3 (Data-Driven Documents) and Leaflet libraries to generate charts and cartographic representations, respectively. The raw data was pre-treated through R scripts, and locally stored as geojson for geographical information, json for the flows data, and csv for the remaining.

V. PILOT STUDY AND REDESIGN

A first prototype was tried out by 13 volunteers aged 36 years old in average (SD = 10). This trial verified whether the prototype was usable and could assist users on answering questions on daily mobility analysis. Since the interface comprises two time pickers, we also assessed the users reaction to our movement-based time interaction. We followed a withinsubjects study design to test two conditions: timeline and timewheel. Participants were asked to answer two sets of 6 questions, one for each variable. The questionnaire contained simple (e.g. which is the presence density in sector 5 between 7am and 8am?) and complex (e.g. where are people coming from in the 3 most attractive sectors?) questions. We measured users self-reported workload for each condition through the NASA Task Load Index (TLX) [START_REF] Hart | Development of NASA-TLX (Task Load Index): Results of empirical and theoretical research[END_REF], a multi-dimensional rating procedure which provides an overall workload score based on a weighted average of ratings on six sub-scales: Mental Demand (MD), Physical Demand (PD), Temporal Demand (TD), Own Performance (OP), Effort (EF), and Frustration (FR). A post-test questionnaire collected users' subjective assessment on usability through the SUS questionnaire [START_REF] Brooke | SUS -A quick and dirty usability scale[END_REF], and their preferences over the time arrangements.

For the sake of reproducibility, the output data of the user studies and the scripts treating it are available as supplemental material. Data was submitted to a mixed design with the experimental conditions as within-subjects and the user profile as a between-subjects test. We performed a Shapiro-Wilk Normality test to verify if the data comes from a normal distribution and a Fligner-Killeen test to verify if the variances in each group are the same. When the data passes both tests we performed an One-Way ANOVA. Otherwise, we submitted the data to non-parametric tests, Friedman for paired and Kruskal-Wallis for unpaired groups. When finding statistical significance in multiple variables comparisons we ran Tukeys range test for One-Way ANOVA, and Nemenyi test for the others. We analyzed whether variables were related through Pearson correlation.

Response time and accuracy were similar in both conditions: around 26 minutes and 86% of correct answers. These variables are 56% correlated in the timewheel condition (p = 0.058). Both timeline and the timewheel induced a mean selfreported workload of 63 and were high mentally demanding. In the timewheel, the MD was significantly stronger than PD, TD, and FR (p < 0.001). For both conditions, PD was lower than EF and OP (p < 0.001). The timeline was found less frustrating than effortful (p < 0.001). The more mental demanding the task, the less physical effort it requires (R = 0.6, p < 0.05). Though PD received the lowest scores, it seems to worsen response accuracy as it increases (R = 0.69, p < 0.001). Mental demand appears to reduce users' selfperceived performance (R = -0.83, p < 0.001 for the timewheel, and R = -0.51, p = 0.078 for the timeline), yet it does not seem to affect response accuracy.

Older participants took longer to finish the experiment in the timewheel condition (R = 0.72, p < 0.01). In the same way, the mental demand is higher for older participants in the timeline (R = 0.65, p < 0.05), and it appears to happen also in the timewheel (R = 0.5, p = 0.085). Great prior knowledge on the territory mobility also increased mental demand (R = 0.58, p < 0.05) in the timeline. The longer the response time, the less frustrated users felt (R = 0.58, p < 0.05). We suppose users got comfortable with the prototype, decreasing frustration feelings. The usability of our prototype was assessed on 48/100 (SD = 8.66). The timeline was favored over the timewheel (M = 3.53, SD = 1.19 in a 5points Likert scale). Users are more familiar to it and the lower degrees-of-freedom make the timeline easier to manipulate.

Users provided satisfactory answers to the proposed questions in the pilot study, yet their response time was longer than desirable for everyday use and they reported high workload scores. The interface lacked on intuitiveness, specially regarding interaction with dashboards. To display a view, the user should select the territorial partition, the indicator, the dashboard and submit the choices. The view would be displayed in the next blank window, re-assorting the views each time the user deleted or added something. We then transformed it into a slider menu interface, where each slide corresponds to a dashboard, holding four "windows" as in the dashboard interface, and the user can directly control where and how the indicators are viewed (Fig. 3A). The charts supporting the analysis and comparison of modes of transport used by active people were designed as bar charts, which was hard to understand at a glance. We modified it into arc charts (Fig. 3B), following the color code of the wheel's inner ring, fastening information assimilation. We have represented flows exchanges through a simple chord diagram, which was hard to understand since flows direction was only pointed by ribbons color and it did not provide information on flows volume. We upgraded it to a more legible and intuitive diagram [START_REF] Shi | The visual analysis of flow pattern for public bicycle system[END_REF] (Fig. 3C).

VI. USER EVALUATION

The new version of eSTIMe was submitted to a two-part evaluation (below): to assess the movement-based interaction technique; and to evaluate effectiveness with prospect users.

A. Experiment I: Time Animation

Seventeen unpaid persons, researchers and PhD students, aged 33 years old in average (SD = 11.18), took part in a within-subjects experiment to compare 4 conditions: timewheel (A) or timeline (B) controlled by tilting, and traditional animation controlled by mouse (C) or touch (D), hypothesizing the (H1) animation performance is similar with mouse and touch interactions; (H2) tilting movement provides better answers than the traditional interaction; and (H3) movementbased interaction is preferred over the mouse.

We gave the participants four (one per condition) 3questions sets regarding different conditions (either presence density or fluctuation rate) and spatial locations (x, y, z): how the variable vary along the day in sector x?; which are the periods in sector y when the variable value decreases?; which are the periods in sector z when the variable value increases? Subjective usability of each technique was assessed via UMUX-Lite questionnaire [START_REF] Lewis | UMUX-LITE: When there's no time for the sus[END_REF]. The post-test questionnaire gathered users' preferences over the proposed techniques through a pair-wise comparison and a 4-item rating assessing the agreeableness of each technique in a 5-point Likert scale.

Response time was around 6 minutes for each experimental condition, progressively decreasing from the first to the last question (p < 0.01). Condition A (timewheel) provided a 50% response accuracy, significantly lower than the other conditions (around 85%, p < 0.05). Overall, users preferred to control animation via touches. From the pair-wise comparison, conditions B (linear movement) and C (traditional animation) were similarly appreciated, and condition D is preferred over C. The assessed usability was not significantly different between the techniques (42/100 in average). Users found the timewheel was the most frustrating and difficult to use. As expected, the traditional animation was considered easy to use, since it is well-known for time exploration and users are more familiar with mouse interaction.

Participants' prior experiences on non-conventional interaction appear to increase response accuracy (R = 0.35, p = 0.013) in condition D, and to reduce response time in condition B (R = 0.28, p < 0.05) and D (R = 0.24, p = 0.087). Similar to the pilot study, older people provided less accurate answers (R = -0.29, p < 0.05, condition D), and took longer to finish (R = 0.35, p < 0.05, condition A) it.

The cyclic tilting movement was found unnatural and the rectangles in the timewheel too small, challenging the pointer's placement. The timewheel takes about 25% of the screen's height for the sake of the map readability, which became a limitation in our approach, since we use a 9.7-inch screen tablet. Participants found hard to interpret the fluctuation map because of its diverging color scale and the proportional values (to the population). The legends changing at each time interval disturbed some participants.

In summary, since we have found similar response times and accuracy between interactive animation via mouse and touches, we accept H1. Response accuracy was lower while using the cyclic movement, but linear movement provided similar response accuracy and time as the traditional animation. We reject H2, because performance with the movementbased technique was not better, but rather similar to traditional animation. However, users enjoyed the linear movement, as well as the tangible animation, finding it easy to use. We accept H3 and consider to merge both techniques to enable the user to play the animation via device tilting and to select time intervals via touch.

B. Experiment II: The Environment

Twenty-four volunteers (21 valid), aged 22 years old in average (SD = 1.82), students with satisfactory knowledge on the target domain took part in this experiment. We followed an one-group posttest-only design to evaluate the effectiveness of our environment on assisting the analysis of daily mobility data. Participants in the pilot study mentioned one need a longer training time to master the interface. Therefore, we designed it as a two-part experiment. The first part comprised two 3-hours sessions in which users worked in pairs to answer a set of 16 questions. In these sessions, a PC monitor displayed the Controller, and a mouse supported the interaction.

The experimental (collective) sessions took place two weeks later, where 12 participants worked in parallel to answer 14 analytic questions. An automatic training phase was performed through 16 interaction-related questions. A post-test questionnaire included the SUS and a reduced version of the NASA TLX, containing only the ratings part in a 10-point scale. Scores for each sub-scale were determined as the average rating times 10, and the general score was the mean score of sub-scales. It also measured users' preference on using a PC monitor or a tablet as second screen.

Assessed usability is still moderate (40/100), while selfreported workload decreased (M = 33.3, SD = 6.8). Users strongly scored MD (M = 41.4, SD = 9.10) and OP (M = 54.3, SD = 9.78). However, no correlation was observed between OP and neither response time nor accuracy. Responses were 81% accurate, varying across spatial locations and indicators. The responses regarding the 4 th location were less accurate than the remaining (p < 0.001 against the 2 nd , and p < 0.05 against the 1 th and 3 rd ). Accuracy on questions about attractiveness was higher than presence density (p < 0.05), which also got less correct answers than flows (p < 0.001). The latest was also more accurate than fluctuation rate (p < 0.01) and population mobility (p < 0.001).

Response time was about 35 minutes (SD = 12.9), with an average of 2.49 minutes (SD = 2.26) per question. Small correlations suggest response time appears to increase FR (R = 0.12, p < 0.05), EF (R = 0.16, p < 0.01), and PD (R = 0.2, p < 0.001), and to reduce accuracy (R = -0.12, p < 0.05). Participants' prior knowledge on mobility appears to increase OP (R = 0.49, p < 0.001), and total workload (R = 0.26, p < 0.001). More experienced on nonconventional interaction users reported higher PD (R = 0.3, p < 0.001), MD (R = 0.34, p < 0.001), and total workload (R = 0.2, p < 0.001). However, it does not seem to affect response time and accuracy. Users enjoyed the tablet as a second screen (M = 3.95, SD = 1.43) and preferred using it rather than a PC monitor (M = 4, SD = 1.22), since they could display the views on a large screen while interacting on the tablet, which facilitates data exploration.

VII. DISCUSSION

We designed and developed a multi-screen geovisualization environment embedding customizable dashboards to assist daily mobility analysis. The main interface consists of a tablet integrating a movement-based interaction technique to dynamically explore time varying data. Even though the timewheel was outperformed by every other animation technique, the timeline controlled by our method was proven to be as efficient as the traditional animation (i.e. via mouse interaction), while being more engaging. Using touch to control animation was equally enjoyed by users, thus we combined physical and touch to provide more control and engagement to explore the indicators over time. Time exploration could benefit from the customizable dashboards approach. As an example, the user could view the same indicator at different time intervals side-by-side on the dashboard, as via small-multiples. Our prototype provides indicators of flows and displacements, as well as territory settlement dynamics. Despite not analyzing activities neither individual trajectories, it allows to understand how people move around on urban area. Our user studies intended to evaluate whether our design choices are useful to explore daily mobility, before fulfill the indicators.

Fifty-one volunteers, which 21 were knowledgeable on geography and mobility, used our prototype and have found it promising. Our approach is effective for assisting the visual analysis of daily mobility data (at least in the aggregate level). Participants could provide satisfactory answers to the proposed analytical questions, even those with none experience on the domain. The changes we made in our prototype from the pilot study to the evaluation phase improved efficiency, since the users answered 14 analytical questions in about 1/3 the time the participants in the pilot study took to answer 12 questions with about the same accuracy (80%).

We also interviewed a few public agents who explore HTS data to support decision-making in urban development. We demonstrate our prototype and let them test it. Though, they were excited with the idea of customizing the dashboard and using their own movement to explore time, they pointed out using a second screen (i.e. the tablet) could be a constraint in their everyday work, since it requires extra material, not needed for other tasks.

VIII. CONCLUSION AND FUTURE WORK

This paper proposes a geovisualization approach to support the (1) description of daily mobility through flows and displacements, territory settlement dynamics and individual trajectories; (2) analysis and comparison of complementary indicators in the aggregate and individual levels; (3) exploration of the time dynamics of indicators, and; (4) custom composition of the dashboard according to the user's needs, while choosing the spatial and temporal granularity to compose the indicators. eSTIMe uses a multi-screen environment embedding customizable dashboards, and a movement-based interaction to support time animation via mobile devices.

In a prototype level, it is limited by not including yet indicators on activities and individual trajectories. The exploration of the latter, while performed via survey data would not violate the data protection laws, since the spatial locations are defined by great areas, not involving specific geographical coordinates revealing individuals residences and work places, for instance. Usability issues are being solved towards a userfriendly environment. The evaluation process could demonstrate the efficacy of our approach, yet it does not evaluate the effectiveness of using customizable dashboards in comparison to the traditional ones. Therefore, future work also includes user studies to evaluate this aspect, and a validation of eSTIMe by domain experts.

Fig. 1 .

 1 Fig. 1. Our approach comprises customizable dashboards (top) embedded in a multi-screen environment. A tablet holds the main interface (middle), which interacts with the dashboards and support our movement-based technique (bottom) for time animation.

Fig. 2 .

 2 Fig. 2. The Mobility Wheel displays the movement patterns of active people, while the arc charts compare the usage of transportation modes across time intervals.

Fig. 3 .

 3 Fig. 3. Main modifications on the prototype after the pilot study results. The menu (A) have been remade into a more intuitive interface. The charts displaying the distribution of transportation modes (B) were changed from bars to arc, which also link the modes to their respective colors. The Flow View (C) was upgraded into a more intuitive and informative diagram.


Arnaud Castelltort

Anne Laurent

NoSQL Graph-based OLAP Analysis

Keywords:

published or not. The documents may come

Introduction

Graph NoSQL engines such as Neo4J are now taking more and more importance in the applications. Their capacity to scale to large databases and complex treatments are well-suited for many applications having intensive needs for graph-oriented applications, such as in chemistry, biology, social networks, etc.

Studies have shown that these technologies present good performances, much better than classical relational databases [START_REF] Board | Technology radar[END_REF] for representing and querying such large graph databases, especially for connected data.

Retrieving relevant information from such graphs in an efficient manner is a key feature. In this perspective, retrieving decisional information, as done in the OLAP framework, appears to be a promising area. OLAP allows to represent key indicators as measures (e.g., number of sales) defined over dimensions (e.g., product, time, location) and to query this information by selecting releveant pieces of information (e.g., slice and dice) or by navigating through hierarchies (e.g., from years to decades, from regions to countries), thus helping decision makers to retrieve relevant information.

We thus consider adding OLAP features to NoSQL graph databases.

In the literature, works have considered coupling graph and OLAP. Models have been proposed and have been implemented. OLAP queries have been translated to the graph framework. However, as far as we know, no work has addressed the exploitation of NoSQL graph databases for this purpose.

In this paper, we thus propose to study how NoSQL databases can help retrieving relevant information from data using the OLAP paradigms. We ad-dress both the representation of data cubes through NoSQL databases and the query processing. In our work, we consider the Neo4j engine and the declarative Cypher language.

The paper is organised as follows. Section 2 reviews the related work, namely NoSQL databases and graph OLAP databases. Section 3 introduces our proposition for modeling NoSQL graph databases while Section 4 presents the extension of Cypher queries to OLAP NoSQL data cubes.

Related Work

We introduce below the foundation of NoSQL graph databases and the existing work on graph OLAP.

NoSQL Graph Databases

Graphs have been studied for centuries.

Definition 1 (Graph).

A graph G is defined as a pair (V, E) where V is a set of nodes and E is a set of relations, with E ⊆ (V ×V ).

Most of databases consider oriented graphs [START_REF] Angles | Survey of graph database models[END_REF][START_REF] Reutter | A formalism for graph databases and its model of computation[END_REF][START_REF] Robinson | Graph Databases[END_REF] and contain elements (nodes and relations) together with properties on these elements. These properties are represented through (key, value) pairs. These concepts are often used in NoSQL databases (Han et al., 2011).

Graphs are often represented graphically and are powerful for visualising and analysing data. On the one hand, they benefit from an easy human understanding. On the other hand, they offer excellent per- formances thanks to their data structures and query tools which are very relevant for many real-world contexts [START_REF] Rodriguez | The graph traversal pattern[END_REF].

Fig. 2 shows a graph and its structure in (key, values) pairs. Their exist several NoSQL graph database engines (OrientDB, Neo4J,HyperGraphDB, etc.). Neo4J is recognised as being one of the top ones regarding performance [START_REF] Board | Technology radar[END_REF]. [START_REF] Chen | Graph olap: a multi-dimensional framework for graph data analysis[END_REF] has proposed to couple graphs with OLAP in 2008. This approach consists in studying how a set of several graphs can be aggregated into a single summary graph. [START_REF] Zhao | Graph cube: On warehousing and olap multidimensional networks[END_REF] has introduced the concept of Graph Cube. This concept stands for a modelization of data cubes from graphs where dimensions are based on node attributes (e.g., age, sex, city of birth for a people) and where facts are based on countings. Fig. 3 shows the cube from the paper example considering a low level of granularity and aggregations with OLAP operators.

Graph OLAP

These propositions are enhanced regarding performances in [START_REF] Denis | A distributed approach for graph-oriented multidimensional analysis[END_REF] with the use of distributed computer architectures. [START_REF] Li | Infonetolaper: Integrating infonetwarehouse and infonetcube with infonetolap[END_REF] proposes a method for modelizing cubes from network data, as for instance the network of co-authors. Meta-data are distinguished depending on the elements they are linked to dimensions or facts. If they depend on dimensions, then they are considered as informational dimension tables as for instance spatio-temporal dimensions or as topological dimension tables. If they depend on facts, they are said to be frame fact table or clique fact table. Every cell in the cube contains a network. For instance, with the dimensions conference and year, the cell at position (VLDB,2010) contains the graph of all coauthors from the papers at this event. The system has been implemented in SQL Server and precomputations are possible in order to get better performances. Two types of operations are proposed: I-OLAP operations (Informative OLAP) when dimensions are taken from node attributes and T-OLAP (Topological OLAP) described in [START_REF] Qu | Efficient topological olap on information networks[END_REF] when dimensions are taken from nodes and relations attributes. These operations allow to perform classical OLAP operations such as roll-up, drill-down, for instance for navigating through decades and years, slice/dice, etc.

Regarding OLAP operators, [START_REF] Etcheverry | Qb4olap: A vocabulary for olap cubes on the semantic web[END_REF] works on the RDF Cube vocabulary called QB to extend it. [START_REF] Beheshti | A framework and a language for on-line analytical processing on graphs[END_REF] extends the QB syntax in the so-called QB4OLAP for supporting OLAP operators directly in RDF. [START_REF] Kampgen | Interacting with statistical linked data via olap operations[END_REF] considers the execution of OLAP queries through SPARQL over RDF data. Unfortunately, the paper does not demonstrate in details how to express OLAP queries and how queries are processed. [START_REF] Petermann | BIIIG: enabling business intelligence with integrated instance graphs[END_REF] discusses the concept of Business Intelligence in the context of graphs (storing information on commercial processes in this case, within Business Transaction Graphs). [START_REF] Bachman | GraphAware: Towards Online Analytical Processing in Graph Databases[END_REF] addresses the implementation of precomputation componants over Neo4j databases and also addresses efficient computation of node arity. This work is very important for OLAP features as many operations rely on counting incoming and outgoing relations, as for instance for counting the number of friends in a social network. However, this work is a low level implementation and does not detail how OLAP queries can be written.

Our proposition in this paper is quite different from the literature as we propose to use the graph structure as a basis for OLAP analysis.

This original contribution relies on the use of the performances and efficiency of NoSQL graph databases engines to store and query OLAP data. We first show how such NoSQL Graph OLAP data can be modelised and we then address OLAP queries over such data structures. [START_REF] Zhao | Graph cube: On warehousing and olap multidimensional networks[END_REF] 3 NoSQL Graph OLAP Databases

In this section, we present our contribution for modelising cubes in NoSQL graph databases. The case below serves as a running example. Example 1. We consider a classical database describing sales of products in cities at given dates. The dimensions are: the products described by their ProductId regrouped into Categories, the cities organised along a hierarchy City-Region-Country and the days organised along a hierarchy Day-Month-Year.

NoSQL Graph Cubes

Our model relies on the modelisation of dimensions and facts with typed nodes. These types represent the granularity levels of the dimension, taking advantage from the best practices from NoSQL graph databases experts 1 . It should be noted that OLAP theoretical models consider such granularity levels in the literature [START_REF] Gyssens | A foundation for multi-dimensional databases[END_REF]. Nodes are linked by relations describing:

• links of type hierarchy (HIER) in the case of dimensions,

• links or type fact (FACT ) in the case of a link from a dimension to a fact.

. Our solution presents many advantages :

• Multidimensionsal data are easily ploted on the user's screen, as demonstrated by Fig. 5. Every dimension can be colored so as to ease the user visualization.

• The nodes can be adjusted (enlarged or reduced) according to their value.

• Cells can be organized so as to cluster them and/or bring them closer or farther.

• Only non null cells are managed, thus avoiding sparse tables.

• OLAP navigation is eased. In particular, graph queries can be used, as well as filters that can help hiding or coloring in a different manner the data being relevant for the user (e.g., displaying only cells for low level of sales, or only sales associated to NYC). The operators are detailed below. Facts are represented by nodes of type :NFACT labeled (a label is a graph construct that is used to group nodes into sets) by the type of fact they represent and are linked to dimension nodes through relations of type :FACT . Ony the cells for which values are known are modelised, thus copping with the problem of cube sparsity [START_REF] Niemi | Normalising olap cubes for controlling sparsity[END_REF].

It should be noted that the value in the node is valid only if it is considered in relation with all the dimensions. For instance, as stated above, Fig. 5 shows that there have been 5 units of Sales of Canoes in New York City on March 3, 2014. This value of 5 must be associated with all these three dimension values, i.e. Canoes, NYC, March3, 2014.

If a dimension is omitted, then the value must be re-computed. In such a case where one (or several) dimension is omitted, a roll up operator has been ap- plied. In the OLAP framework, data analysis are indeed performed regarding dimensions in a so-called data cube. Sales can be analysed with respect with the three dimensions, or with respect with two dimensions out of these three, or with respect with one dimension out of the three dimensions. The combinations of dimensions are called cuboids, the set of cuboids being the cube, as shown by Fig. 7 for the Sales example. This example shows that in such a case with 3 dimensions, there are 2 3 = 8 cuboids. All cuboids form a lattice.

More complex schemas (e.g., constellations) are easily modeled with the same concepts.

More formaly, we consider the definitions below.

Definitions

Definition 2 (NoSQL Graph -Dimension Level). Let G be a NoSQL graph database. A dimension level of G is defined as a possible value associated with the property key Type.

For instance, we consider the dimension level City.

Definition 3 (NoSQL Graph -Dimension Node). Let G be a NoSQL graph database and L a set of associ-ated dimension levels. A dimension node n is defined as a node such as n.type ∈ L.

We consider for instance the set of levels {City} and NYC as a node, with NYC.type = City.

Definition 4 (NoSQL Graph -Dimension Relation).

Let G be a NoSQL graph database and N a set of dimension nodes. A dimension relation r is defined as a pair (n 1 , n 2 ) ∈ N 2 such that:

• r.type=HIER

• n 1 .type = n 2 .type .

We consider for instance:

• the set of levels {City, Region},

• the nodes NYC, East,

• the types NYC.type = City and East.type = Region, and

• the hierarchical relation (NYC) -[: HIER]-> (East).

Definition 5 (NoSQL Graph -Dimension). A NoSQL graph dimension D is defined as a triplet (L, N, R) with L a set of dimension levels, N a set of dimension nodes defined over L and R a set of dimension relations defined over N.

Definition 6 (NoSQL Graph -Type of Fact). Let G be a NoSQL graph database. A type of fact is defined as a possible value on the key T Fact.

For example, we consider the type of fact Sales which records the number of sales.

Definition 7 (NoSQL Graph -Fact). Let F be a set of types of facts. A fact is defined as a pair (n, r d ) with n a node such that n.type = NFACT , n.t f act ∈ F and r d a set of dimension relations {r = (n, x) s.t. r.type = FACT } r∈r d .

The fact is said to be defined over dimensions D = {x.type}.

Definition 8 (NoSQL Graph -Cube). A NoSQL graph cube of type t is defined as

• the set of facts f such that f .t f act = t,

• the set of paths from the f nodes having type FACT and HIER.

For example, the Sales cubes is the set of nodes where the value for key value T Fact is Sales and the set of paths from these nodes traversing relations of type FACT and HIER, thus traversing (through hierarchies) nodes of type Cities, Region, Country, ProductId, Category, Month, Year.

Computing NoSQL Graph Cubes

OLAP engines are distinguished whether they precompute or not all parts of the cubes, i.e. all the cuboids from the lattice shown in Fig. 7. Models where all cuboids are pre-computed are known as MOLAP models (Multidimensional OLAP), while models where no cuboid is pre-computed are considered as ROLAP models (Relational Models). Hybrid models are possible (HOLAP) where highly requested cuboids are pre-computed while other ones are not. MOLAP engines are faster to deliver the information but have some limits as they require large volumes of memory to load pre-computations, while ROLAP engines can scale more easily as no memory is required to store pre-computations, but they are slower.

The model we propose is similar to a MOLAP representation as links are materialized. We indeed claim that the performances of NoSQL databases allow for reconsidering MOLAP models. This model has proven his capacity to scale to very large volumes of data.

As a MOLAP model, our contribution is thus very suitable for navigating through data and hierarchies.

The computation of such NoSQL graph cubes is meant to be performed by importing source data within the model. Hypergraphs may be built if the data are already in NoSQL graph databases. Due to lack of space, OLAP graph-ETL tools are not explored in this paper.

Extension of the Cypher Language to OLAP queries

The model of OLAP cubes in NoSQL graph databases proposed above allows us to define how to navigate through such data structures in an OLAP manner. OLAP has defined several operators, the most common ones being Slice, Dice, Roll Up [START_REF] Cabibbo | Querying multidimensional databases[END_REF]. Many works have addressed how to query graphs [START_REF] Wood | Query languages for graph databases[END_REF]. In this paper, we consider the Cypher syntax, Cypher being the declarative query language over Neo4J.

Basic Operators

Slice

In OLAP, the slice operator allows to select the data with respect to a condition on the dimension values. It is for instance used to reduce the data to the information related to one city (e.g., New York) or to one region (e.g., East). Note that the Cypher queries we propose below in Listings 1 and 2 return the cell with all its dimensional context.

Listing 1: Slice -Selecting Sales Results from the New York City

1 MATCH ( n ) -[ r1 : FACT ] -> ( x ) , ( n ) -[ r2 : FACT ] -> ( y ) 2 WHERE x . name = ' NYC ' 3 RETURN n , r1 , r2 , x , y
Listing 2: Slice -Selecting Sales Results from the East

1 MATCH ( n ) -[ r1 : FACT ] -> ( x ) -[ h : HIER * ] -> ( e ) , ( n ) -[ r2← : FACT ] -> ( y ) 2 WHERE e . name = ' East ' 3 RETURN n , r1 , r2 , x , e , y

Dice

In OLAP, the dice operator allows to select the data with respect to a condition on the cell values. It is for instance used to reduce the data to the information related to sales greater than 7 units.

The Dice operator does only apply on fact nodes by specifying the possible values in the ARG clause below in Listing 3.

Roll Up

In the case of the roll up operator, the computation of aggregated facts with respect to hierarchy levels and :FACT links is modelised at the upper-level. All the fact node values are aggregated by respecting the semantic and the additivity properties of the measures [START_REF] Lenz | A formal framework of aggregation for the olap-oltp model[END_REF].

For instance, the sum will be considered for summing up all number of sales from the fact Sales. A new node is created for storing the new aggregate integrate this new node at the upper level of hierarchy with relation FACT as shown in Listing 4. Precomputations can be considered in the same way as the cuboid materialisation in order for instance to precompute the number of sales per year, per category, per region, etc.

Implementation Issues

The model we propose can be implemented in the Neo4j graph engine.

As depicted by Fig. 8 and discussed in (Castelltort and Laurent, 2014), regarding queries, there exist several ways to implement the extension of Cypher:

1. Creating a specific language (Cypher OLAP) extending the Cypher syntax and rewriting these queries into well-formatted Cypher queries;

2. Extending the Cypher syntax and rewriting the queries using the low level API which can interact with the Neo4j engine;

3. Extending the API with advanced querying features and proposing this extension to developers;

4. Combining the above-mentioned options for developing an OLAP extensions based on the OLAP API.

Whatever the choice may be, the type of rewriting is similar. This is the reason why we do not address this topic in this paper. However, the impacts on performances and on the user experience may be very different depending on this choice. Cubes can be created in the Neo4j engine by respecting the model proposed in this paper. Nodes and relations are considered with their respective types, depending on the case that they are facts, dimensions or hierarchy. They can then be queried regarding

Conclusion and Further Work

In this paper, we address the topic of coupling NoSQL graph databases and OLAP. These two scientific domains are very active and important in many real-worl applications. We claim that NoSQL graph databases are a perfect candidate for supporting OLAP features, as they are both efficient and suitable for representing data in a very intuitive manner for decisional purposes. Analysing data and retrieving relevant information indeed rely on the capacity to deal with big data and the capacity to help the decision makers.

For this purpose, we propose an OLAP data structure based on NoSQL graph databases and we introduce OLAP queries based on the Cypher declarative language.

Some tests have been performed with the Neo4j engine, showing the feasability of our proposition.

Further work will help us strengthening the implementation and tests over large databases and complex OLAP queries. Both incoming processes and queries will be enhanced, by defining specific ETL componants and by implementing the extension of the Cypher language.

We also aim at exploiting the NoSQL graph databases and the attributes on relationships in order to better represent and manage fuzzy hierarchies [START_REF] Rogova | Flexible hierarchies and fuzzy knowledge-based olap[END_REF][START_REF] Laurent | A new approach for the generation of fuzzy summaries based on fuzzy multidimensional databases[END_REF] that are very difficult to deal with in existing engines.

Figure 1 :

 1 Figure 1: Graph of a Company

Figure 2 :

 2 Figure 2: Properties of Nodes and Relations

Figure 3 :

 3 Figure 3: Graph Cube Model from[START_REF] Zhao | Graph cube: On warehousing and olap multidimensional networks[END_REF]

Fig. 4

 4 shows such a representation and Fig. 5 displays an example of such a cube with three dimensions (Time, Product, City) organized through hierar-1 http://blog.neo4j.org/2010/03/modeling-categories-ingraph-database.html

Figure 5 :

 5 Figure 5: A NoSQL Graph OLAP Cube

Figure 4 :

 4 Figure 4: Modelising cubes and dimensions in a NoSQL Graph (Neo4J)

Figure 7 :

 7 Figure 7: Lattice of Cuboids

Listing 3 :

 3 Dice -Selecting Sales Results Greater than 7 units 1 MATCH ( n ) 2 WHERE n . value > 7 3 RETURN n

Listing 4 :

 4 Roll Up -Summing up all number of sales from the East 1 MATCH ( n ) -[ r1 : FACT ] -> ( x ) -[ h : HIER * ] -> ( East ) 2 WHERE East . name = ' East ' 3 WITH sum ( n . value ) as aggregateValue , East 4 CREATE ( aggregate { value : aggregateValue } ) -[ : ← FACT ] -> ( East ) 5 RETURN aggregate , East

Figure 8 :

 8 Figure 8: Alternatives for Extending the Cypher Language within Neo4J

Figure 10 :

 10 Figure 10: A Slice Operation over the NoSQL Graph Cube in Neo4J

(

  East : Region { name : ' East ' } ) , ( West : Region { name : '← West ' } ) , 11 ( NYC : City { name : ' NYC ' } ) , ( LA : City { name : ' LA ' } ) ← , 12 ( Boston : City { name : ' Boston ' } ) , ( SF : City { name : ← ' SF ' } ) , 13 ( East ) -[ : HIER ] -> ( US ) , ( West ) -[ : HIER ] -> ( US ) , 14 ( NYC ) -[ : HIER ] -> ( East ) , ( Boston ) -[ : HIER ] -> ( East ) , 15 ( LA ) -[ : HIER ] -> ( West ) , ( SF ) -[ : HIER ] -> ( West ) , 16 ( Y2014 : Year { name : ' Y2 0 1 4 ' } ) , 17 ( Jan 14 : Month { name : ' Jan 1 4 ' } ) , ( Feb 1 4 : Month { ← name : ' Feb 1 4 ' } ) , 18 ( Jan 0114 : Day { name : ' Jan 0 1 1 4 ' } ) , ( Jan 0 2 1 4 : Day {← name : ' Jan 0 2 1 4 ' } ) , 19 ( Feb 0114 : Day { name : ' Feb 0 1 1 4 ' } ) , ( Feb 0 2 1 4 : Day {← name : ' Feb 0 2 1 4 ' } ) , 20 ( Jan 0114 ) -[ : HIER ] -> ( Jan 1 4 ) , ( Jan 0 2 1 4 ) -[ : HIER ] -> ( ← Jan 14 ) , 21 ( Feb 0114 ) -[ : HIER ] -> ( Feb 1 4 ) , ( Feb 0 2 1 4 ) -[ : HIER ] -> ( ← Feb 14 ) , 22 ( Jan 14 ) -[ : HIER ] -> ( Y2 0 1 4 ) , ( Feb 1 4 ) -[ : HIER ] -> ( Y2 0 1 4← ) , 23 ( TJ 0114 Boston { name : ' TJ 0 1 1 4 Boston ' , tfact : ' Sales ← ' , value : 9} ) , 24 ( CaF 0314 NYC { name : ' CaF 0 3 1 4 NYC ' , tfact : ' Sales ' , ← value : 5} ) , 25 ( CuJ 0214 LA { name : ' CuJ 0 2 1 4LA ' , tfact : ' Sales ' , ← value : 3} ) , 26 ( CuF 0114 LA { name : ' CuF 0 1 1 4LA ' , tfact : ' Sales ' , ← value : 3} ) , 27 ( TJ 0114 Boston ) -[ : FACT ] -> ( Tent ) , 28 ( TJ 0114 Boston ) -[ : FACT ] -> ( Boston ) , 29 ( TJ 0114 Boston ) -[ : FACT ] -> ( Jan 0 1 1 4 ) , 30 ( CaF 0314 NYC ) -[ : FACT ] -> ( Canoe ) , 31 ( CaF 0314 NYC ) -[ : FACT ] -> ( NYC ) , 32 ( CaF 0314 NYC ) -[ : FACT ] -> ( Feb 0 3 1 4 ) , 33 ( CuJ 0214 LA ) -[ : FACT ] -> ( Cupboard ) , 34 ( CuJ 0214 LA ) -[ : FACT ] -> ( LA ) , 35 ( CuJ 0214 LA ) -[ : FACT ] -> ( Jan 0 2 1 4 ) , 36 ( CuF 0114 LA ) -[ : FACT ] -> ( Cupboard ) , 37 ( CuF 0114 LA ) -[ : FACT ] -> ( LA ) , 38 ( CuF 0114 LA ) -[ : FACT ] -> ( Feb 0 1 1 4 ) 39 RETURN *

APPENDIX

Below is the script for creating the database from Fig. 5.


A Castelltort
email: castelltort@lirmm.fr

A Laurent
email: laurent@lirmm.fr

Fuzzy Queries over NoSQL Graph Databases: Perspectives for Extending the Cypher Language

Keywords: Fuzzy Queries, NoSQL Graph Databases, Neo4j, Cypher, Cypherf

When querying databases, users often wish to express vague concepts, as for instance asking for the cheap hotels. This has been extensively studied in the case of relational databases. In this paper, we propose to study how such useful techniques can be adapted to NoSQL graph databases where the role of fuzziness is crucial. Such databases are indeed among the fastest-growing models for dealing with big data, especially when dealing with network data (e.g., social networks). We consider the Cypher declarative query language proposed for Neo4j which is the current leader on this market, and we present how to express fuzzy queries.

Introduction

Graph databases have attracted much attention in the last years, especially because of the collaborative concepts of the Web 2.0 (social and media networks etc.) and the arriving Web 3.0 concepts. Specific databases have been designed to handle such data relying on big dense network structures, especially within the NoSQL world. These databases are built to remain robust against huge volumes of data, against their heterogeneous nature and the high speed of the treatments applied to them, thus coping with the so-called Big Data paradigm.

They are currently gaining more and more interest and are applied in many real world applications, demonstrating their power compared to other approaches. NoSQL graph databases are known to offer great scalability [START_REF] Rodriguez | The graph traversal pattern[END_REF].

Among these NoSQL graph databases, Neo4j appears to be one of the most mature and deployed [START_REF] Board | Technology radar[END_REF]. In such databases, as for graphs, nodes and relationships between nodes are considered. Neo4j includes nodes and relationships labeling with the so-called types. Moreover, properties are attached to nodes and relationships. These properties are managed in Neo4j using the key:value paradigm.

Fig. 1 shows an example of hotels and customers database. The database contains hotels located in some cities and visited by some customers. Links are represented by the :LOCATED and :VISIT relationships. The hotels and people and relationships are described by properties: id, price, size (number of rooms) for hotels; id, name, age for people. One specificity is that relationships in Neo4j are provided with types (e.g., type "hotel" or "people" in the example) and can also have properties as for nodes. This allows to represent in a very intuitive and efficient manner many data from the real world. For instance, :LOCATED has property distance, standing for the distance to city center. All NoSQL graph databases require the developers and users to use graph concepts to query data. As for any other repository, when querying such NoSQL graph databases, users either require specific focused knowledge (e.g., retrieving Peter's friends) or ask for trend detection (e.g., detecting trends and behaviours within social networks).

Queries are called traversals. A graph traversal refers to visiting elements, i.e. nodes and relations. There are three main ways to traverse a graph:

programmaticaly, by the use of an API that helps developers to operate on the graph; by functional traversal, a traversal based on a sequence of functions applied to a graph;

by declarative traversal, a way to explicit what we want to do and not how we want to do it. Then, the database engine defines the best way to achieve the goal.

In this paper, we focus on declarative queries over a NoSQL graph database. The Neo4j language is called Cypher.

For instance on Fig. 1, one query is displayed to return the customers who have visited the "Ritz" hotel.They are both displayed in the list and circled in red in the graph.

We consider in this paper the manipulating queries in READ mode. This need has nevertheless been intensively studied when dealing with other database paradigms, especially with relational databases.

In this paper, we thus focus on the declarative way of querying the Neo4j system with the Cypher query language and we extend it for dealing with vague queries.

The rest of the paper is organised as follows. Section 2 reports existing work from the literature regarding fuzzy queries and presents the Cypher language. Section 3 introduces the extension of the Cypher language to Cypherf and Section 4 shows how such an extension can be implemented. Section 5 concludes the paper and provides some ideas for future work.

Related Work

Neo4j Cypher Language

Queries in Cypher have the following syntax1 :

[START] [MATCH] [OPTIONAL MATCH WHERE] [WITH [ORDER BY] [SKIP] [LIMIT]] RETURN [ORDER BY] [SKIP] [LIMIT]
As shown above, Cypher is comprised of several distinct clauses:

-START: Starting points in the graph, obtained via index lookups or by element IDs.

-MATCH: The graph pattern to match, bound to the starting points in START.

-WHERE: Filtering criteria.

-RETURN: What to return.

-CREATE: Creates nodes and relationships.

-DELETE: Removes nodes, relationships and properties.

-SET: Set values to properties.

-FOREACH: Performs updating actions once per element in a list.

-WITH: Divides a query into multiple, distinct parts.

Fuzzy Queries

Many works have been proposed for dealing with fuzzy data and queries. All cannot be reported here. [START_REF] Meng | A knowledge-based fuzzy query and results ranking approach for relational databases[END_REF] proposes a survey of these proposals. [START_REF] Bosc | Sqlf: a relational database language for fuzzy querying[END_REF][START_REF] Takahashi | A fuzzy query language for relational databases[END_REF] consider querying regular databases by both extending the SQL language and studying aggregating subresults. The FSQL/SQLf and FQL languages have been proposed to extend queries over relational databases in order to incorporate fuzzy descriptions of the information being searched for.

Some works have been implemented as fuzzy database engines and systems have incorporated such fuzzy querying features [START_REF] Zadrozny | Implementing fuzzy querying via the internet/www: Java applets, activex controls and cookies[END_REF][START_REF] Galindo | A server for fuzzy sql queries[END_REF].

In such systems, fuzziness in the queries is basically associated to fuzzy labels, fuzzy comparators (e.g., fuzzy greater than) and aggregation over clauses. Thresholds can be defined for the expected fulfillment of fuzzy clauses.

For instance, on a crisp database describing hotels, users can ask for cheap hotels that are close to city center, cheap and close to city center being fuzzy labels described by fuzzy sets and their membership functions respectively defined on the universe of prices and distance to the city center.

Many works have been proposed to investigate how such fuzzy clauses can be defined by users and computed by the database engine, especially when several clauses must be merged (e.g., cheap AND close to city center).

Such aggregation can consider preferences, for instance for queries where price is prefered to distance to city center using weighted t-norms.

Thresholds can be added for working with α-cuts, such as searching for hotels where the degree cheap is greater than 0.7.

As we consider graph data, the works on fuzzy ontology querying are very close and relevant for us [START_REF] Pan | Scalable querying services over fuzzy ontologies[END_REF][START_REF] Cheng | f-sparql: A flexible extension of sparql[END_REF]. [START_REF] Pan | Scalable querying services over fuzzy ontologies[END_REF] proposes the f-SPARQL query language that supports fuzzy querying over ontologies by extending the SPARQL language. This extension is based on threshold query (e.g., asking for people who are tall at a degree greater than 0.7) or general fuzzy queries based on semantic functions.

It should be noted that many works have dealt with fuzzy databases for representing and storing imperfect information in databases: fuzzy ER models, fuzzy object databases, fuzzy relational databases, fuzzy ontologies-OWL [START_REF] Stoilos | Fuzzy owl: Uncertainty and the semantic web[END_REF], etc. Fuzziness can then impact many levels, from metadata (attributes) to data (tuples), and cover many semantics (uncertainty, imprecision, inconsistency, etc.) as recalled in [START_REF] Meng | A knowledge-based fuzzy query and results ranking approach for relational databases[END_REF]. These works are not reported here as we consider fuzzy queries over crisp data.

3 Fuzzy Queries over NoSQL Graph databases: Towards the Cypherf Language

In this paper, we address fuzzy READ queries over regular NoSQL Neo4j graph databases. We claim that fuzziness can be handled at the following three levels:

over properties, over nodes, over relationships.

Cypherf over Properties

Dealing with fuzzy queries over properties is similar to the queries from the literature on relational databases and ontologies. Such queries are defined by using linguistic labels (fuzzy sets) and/or fuzzy comparators.

Such fuzzy queries impact the ST ART , M AT CH, W HERE and RET U RN clauses from Cypher.

In the W HERE clause, it is then possible to search for cheap hotels in some databases, or for hotels located close to city center2 . Note that these queries are different as the properties being addressed are respectively linked to a node and a relationship.

Listing 1.1. Cheap Hotels

1 MATCH ( h : Hotel ) 2 WHERE CHEAP ( price ) > 0 3 RETURN h 4 ORDER BY CHEAP ( h ) DESC Listing 1.2. Hotels Close to City Center 1 MATCH ( c : City )< -[ : LOCATED ] -(h : Hotel ) 2 WHERE CLOSE ( c , h ) > 0 3 RETURN h 4 ORDER BY CLOSE ( c , h ) DESC
In the ST ART clause, it is possible to define which nodes and relationships to start from by using fuzzy labels, as for instance: In the RET U RN clause, no selection will be operated, but fuzzy labels can be added in order to show the users the degree to which some values match fuzzy sets, as for instance: It would thus be interesting to investigate how fuzzy queries over graph may be displayed, showing the graduality of membership of the objects to the result. For this purpose, we propose to use the work from the literature on fuzzy graph representation and distored projection as done in anamorphic maps [START_REF] Griffin | Cartographic transformations of the thematic map base[END_REF].

Cypherf over Nodes

Dealing with fuzzy queries over nodes allows to retrieve similar nodes. It is set at a higher level from queries over properties although it may use the above-defined queries.

For instance, it is possible to retrieve similar hotels: In this framework, the link between nodes is based on the definition of measures between the descriptions. Such measures integrate aggregators to deal with the several properties they embed. Similarity measures may for instance be used and may all the more be considered as their prices and size are similar.

It should be noted that such link could be materialized by relationships, either for performance concerns, or because it was designed this way. In the latter case, such query amounts to a query as defined above.

Cypherf over Relationships

As for nodes, such queries may be based on properties. But it can also be based on the graph structure in order to better exploit and benefit from it.

In Cypher, the structure of the pattern being searched is mostly defined in the M AT CH clause.

The first attempt to extend pattern matching to fuzzy pattern matching is to consider chains and depth matching. Chains are defined in Cypher in the M AT CH clause with consecutive links between objects. If a node a is linked to an object b at depth 2, the pattern is writen as (a) -[ * 2]-> (b). If a link between a and b regarding the depth in-between is searched, then it is writen (a) -()-> (b). The mechanism also applies for searching objects linked trough a range of nodes (e.g., between 3 and 5):

(a) -[ * 3..5]-> (b).
We propose here to introduce fuzzy descriptors to define extended patterns where the depth is imprecisely described. It will then for instance be possible to search for customers linked through almost 3 hops. The syntax * * is proposed to indicate a fuzzy linker.

Listing 1.8. Fuzzy Patterns

1 MATCH ( c1 : customer ) -[ : KNOWS ** almost3 ] -> ( c2 : customer ) 2 RETURN c1 , c2
It is related to fuzzy tree and graph mining [START_REF] López | Ftmnodes: Fuzzy tree mining based on partial inclusion[END_REF] where some patterns emerge from several graphs even they do not occur exactly the same way everywhere regarding the structure.

Another possibility is not to consider chains but patterns where several links from and to nodes.

In our running example, popular hotels may for instance be chosen when they are chosen by many people. This is similar as the way famous people are detected if they are followed by many people on social networks.

In this example, a hotel is popular if a large proportion of customers visited it.

In Cypher, such queries are defined by using aggregators. For instance, the following query retrieves hotels visited by at least 2 customers:

Listing 1.9. Aggregation 1 MATCH ( c : Customer ) -[ : VISIT ] -> ( h : Hotel ) 2 WITH c AS cust , count ( * ) AS cpt 3 WHERE cpt>1 4 RETURN cust
Such crisp queries can be extended to consider fuzziness: All fuzzy clauses described in this section can be combined. The question then risen is to implement them in the existing Neo4j engine.

Implementation Challenges 4.1 Architecture

There are several ways to implement fuzzy Cypher queries:

1. Creating an overlay language on top of the Cypher language that will produce as ouput Cypher well formatted queries to do fuzzy work; 2. Extending the Cypher queries and using the existing low level API behind; 3. Extending the low level API with optimized functions, offering the possibility only to developpers to use it;

4. Combining the last two possibilities: using an extended cypher query language over an enhanced low level API. Every possibility is debated in this section. The reader will find at the end of this section a summary of the debates.

Creating an Overlay Language

Concept The concept is to create a high-level fuzzy DSL language that will be used to generate Cypher well-formed queries. The generated Cypher queries will be executed by the existing Neo4j engine.

A grammar must be defined for this external DSL which can rely on the existing Cypher syntax and only enhance it with new fuzzy features. The output of the generation process is pure Cypher code. In this scenario, Cypher is used as a low level language to achieve fuzzy queries.

Discussion This solution is a cheap and non intrusive solution but has several huge drawbacks:

-Features missing, indeed every fuzzy query shown in Section 3 cannot be expressed by the current cypher language (e.g., listing 1.4); -Performance issue, Cypher is not designed for fuzzy queries neither for being used as an algorithmic language. All the fuzzy queries will produce Cypher query codes that are not optimized for fuzzy tasks;

-Lack of user-friendliness, Each query cannot be executed directly against the Neo4j environnement, it needs a two-step process: (i) write a fuzzy query, then compile it to get the cypher query; (ii) use the cypher generated queries on the Neo4j database

Extending the Cypher Queries

Concept The idea is to extend the Cypher language to add new features. Cypher offers various types of functions: scalar functions, collection functions, predicate functions, mathematical functions, etc. To enhance this language with fuzzy features, we propose to add a new type of functions: fuzzy functions. Fuzzy functions are used in the same way as other functions of Cypher (or SQL) as shown in section 3.

Cypher is an external DSL. Therefore, somewhere it needs to be parsed. The query correctness must be checked and then it should be executed. In the Cypher case, retrieving the results we asked for.

In order to write Cypher, the Neo4j's team had defined its grammar, which gives the guidelines of how the language is supposed to be structured and what is and isnt valid. In order to express this definition, we can use some variation of EBNF syntax [START_REF] Pattis | Teaching ebnf first in cs 1[END_REF], which provides a clear way to expose the language definition. To parse this syntax, Cypher uses Scala language Parser Combinator library.

Then, to extend the Cypher engine, the Cypher grammar must be extended regarding the current grammar parser. Once the cypher query is parsed, the code has to be bound on the current programmatic API to achieve the desired result.

Discussion This work needs a deeper comprehension of the Neo4j engine and more skills on Java/Scala programming language (used to write the Neo4j engine and API) than the previous solutions. The main advantage of this is to offer an easy and userfriendly way to use the fuzzy feature. The disavantages of this solution are:

-Performance issue. This solution should have better performance than the previous one but it stills built on the current Neo4j engine API that is not optimized for fuzzy queries (e.g., degree computing); -Cost of maintenance. Until Neo4j accepts to inlude this contribution to the Neo4j project, it will be needed to upgrade each new version of Neo4j with these enhancements. If this feature is built in a plugin, it will be necessary to check that the API has not been broken by the new version (if so an upgrade of the fuzzy plugin will be required).

Extending Low Level API Concept

The scenario is to enhance the core database engine with a framework to handle efficiently the fuzzy queries and to extend the programming API built on it to provide to developpers access to this new functionnality.

Discussion This solution offers a high performance improvment but needs high Neo4j skills, possibly high maintenance costs, a poor user friendly experience (only developpers can use it) and a costly development process.

Extending Cypher Over an Enhanced Low Level API

Concept The last and not the least possibility is to combine the solutions from Sections 4.3 and 4.4: adding to the database engine the feactures to handle the fuzzy queries, extending the API and extending the Cypher language.

Discussion This solution is user-friendly, provides optimized performance but has a heavy development cost (skills, tasks, etc.) and a high cost of maintenance.

Summary and Prototype

The first solution is a non intrusive solution with limited perspectives. It is more a hack than a real long termes solution. The best, but most costly, solution still the last one: extend cypher query language and build a low level API framework to extend the Neo4j database engine to support such kind of queries.

A prototype based on the extension of cypher over an enhanced API is under developement, fuzzy queries can be run, as shown in Fig. 5.

Conclusion

In this paper, we propose an extension of the declarative NoSQL Neo4j graph database query language (Cypher). This language is applied on large graph data which represent one of the challenges for dealing with big data when considering social networks for instance. A protoype has been developed and is currently being enhanced.

As we consider the existing Neo4j system which is efficient, performance is guaranteed. The main property of NoSQL graph databases, i.e. the optimized O(1) low complexity for retrieving nodes connected to a given one, and the efficient index structures ensure that performances are optimized.

Future works include the extension of our work to the many concepts possible with fuzziness (e.g., handling fuzzy modifiers), the study of fuzzy queries over historical NoSQL graph databases as introduced in [START_REF] Castelltort | Representing history in graph-oriented nosql databases: A versioning system[END_REF] and the study of definition fuzzy structures: Fuzzy Cypher queries for Data Definition or in WRITE mode (e.g., inserting imperfect data). The implementation of the full solution relying on our work, currently in progress, will be completed by these important extensions.

Fig. 1 .

 1 Fig. 1. Neo4j database console user interface: Example for Hotels and Customers

Fig. 2 .

 2 Fig. 2. Displaying the Result of a Cypher Query

Listing 1 . 3 .

 13 Starting from Cheap Hotels 1 START h : Hotel ( CHEAP ( price ) > 0 ) 2 RETURN h 3 ORDER BY CHEAP ( h ) DESC Listing 1.4. Starting from location links close to city center 1 START l=relationship : LOCATED ( CLOSE ( distance )>0 ) 2 MATCH ( h : Hotel ) -[ : LOCATED ] -> ( c : City ) 3 RETURN h 4 ORDER BY CLOSE ( h , c ) DESC In the M AT CH clause, integrating fuzzy labels is also possible: Listing 1.5. Matching Hotels Close to City Center 1 MATCH ( h : Hotel ) -[ : LOCATED {CLOSE ( distance )>0} ] -> ( c : City ) 2 RETURN h 3 ORDER BY CLOSE ( h , c ) DESC

Listing 1 . 6 .

 16 Fuzziness in the Return Clause 1 MATCH ( h : Hotel ) -[ : LOCATED ] -> ( c : City ) 2 RETURN h , CLOSE ( h , c ) AS ' ClosenessToCityCenter ' 3 ORDER BY ClosenessToCityCenter DESC When considering fuzzy queries over relational databases, the results are listed and can be ranked according to some degrees. When considering graph data, graphical representations are of great interest for the user comprehension and interaction on the data. For instance, Fig 2 shows how a result containing two items (the two customers who went to Ritz hotel) is displayed in the Cypher console, demonstrating the interest of the graphic display.

Listing 1 .

 1 10. Aggregation 1 MATCH ( c : Customer ) -[ : VISIT ] -> ( h : Hotel ) 2 WITH c AS cust , count ( * ) AS cpt 3 WHERE POPULAR ( cpt ) > 0 4 RETURN cust

Fig. 4 .

 4 Fig. 4. Implementation Ways

Fig. 5 .

 5 Fig. 5. Protoype Developed

http://docs.neo4j.org/refcard/2.0/ http://docs.neo4j.org/chunked/milestone/cypher-query-lang.html

For the sake of simplicity, the fuzzy labels and membership functions are hereafter denoted by the same words.