Ngoc Le

Luyen
email: luyenln@dlu.edu.vn

Anne Tireau
email: anne.tireau@supagro.inra.fr

Aravind Venkatesan
email: aravind.venkatesan@lirmm.fr

Pascal Neveu
email: pascal.neveu@supagro.inra.fr

Pierre Larmande
email: pierre.larmande@ird.fr

Development of a knowledge system for Big Data: Case study to plant phenotyping data

Keywords: Knowledge base, Ontology, Reasoning, Inference, SPARQL, xR2RML, Benchmark, NoSQL, Big Data, Triplestore

In the recent years, the data deluge in many areas of scientific research brings challenges in the treatment and improvement of agricultural data. Research in bioinformatics field does not outside this trend. This paper presents some approaches aiming to solve the Big Data problem by combining the increase in semantic search capacity on existing data in the plant research laboratories. This helps us to strengthen user experiments on the data obtained in this research by infering new knowledge. To achieve this, there exist several approaches having different characteristics and using different platforms. Nevertheless, we can summarize it in two main directions: the query re-writing and data transformation to RDF graphs. In reality, we can solve the problem from origin of increasing capacity on semantic data with triplets. Thus, data transformation to RDF graphs direction was chosen to work on the practical part. However, the synchronization data in the same format is required before processing the triplets because our current data are heterogeneous. The data obtained for triplets are larger that regular triplestores could manage. So we evaluate some of them thus we can compare the benefits and drawbacks of each and choose the best system for our problem.

INTRODUCTION

Research in agronomy aims to address challenges in improving crop productivity, resistance to diseases, minimize the impact of drastic climatic variations. With the vast amounts of data available today, there is potential for scientists to make use these data to understand important patterns and generate broad generalities. However, the data are highly distributed and diverse and with the exponential increase in the amount of data, there is an urgent need for efficient data integration and management. In this context, scientists must be aided to manage their own experimental data in the backdrop of prior knowledge to building consesus within the research community. The Phenome project1 was conserved at the INRA computational sciences unit2 in Montpellier, France, to efficiently manage large volumes of heterogeneous data, assessing environmental influences on plants.

This paper focuses on exploring the possibilities to, a) to store large volumes of heterogeneous data(relational and NoSQL databases); b) strengthen the ability to search different datasets by improving machine interoperability. To this end, the Semantic Web offers a solution to formally structure the data, in this way allowing the generation of new knowledge through inference rules. On the other hand, the latest big data management solutions such as MongoDB, caters to the needs of handling large amounts of data with optimized performance. Taken together, our effort explores the following aspects:

• Exploiting existing big data solutions to make semantic searches over large data.

• We propose a solution to harmonize data using RDF triple store technology.

• Benchmarking triplestores (4Store, Jena Fuseki, Virtuoso, Sesame, Stardog, GraphDB ) on: data loading, data search and on inferencing.

The paper is organized as follows: in the next section, we review the state-of-the-art in big data and semantic web. Section 3 elaborates on the proposed solution with the general model and data transformation to triples. Section 4 describes our approach towards benchmarking. The final section provides the conclusion and perspectives.

RELATED WORKS 2.1 Big Data context

Today we are in the age of Big Data posing challenges in data storage, analysis and visualization. There is a need to develop solutions to manage large amounts of data on a daily basis and extract new knowledge from them. The life sciences are no exception to this, further, the advances made in high throughput technologies at various levels (i.e genotypic, phenotypic, metabolomic, etc.) makes data interoperability essential, calling for structuring data to bridge the gap between the data and the knowledge it represents (common vocabulary, ontologies, rules, etc).

Phenomics aims at understanding of the complexity of interactions between plants and environments in order to accelerate the discovery of new genes and traits and optimize the use of genetic diversity under different environments. Conventional methods to quantify these interactions rely on a limited number of multi-environment evaluations of plants. Advances in genomics and high-throughput phenotyping tools provide a unique opportunity to discover new genes targeted at each interactions. Germplasm can now be sequenced at low cost to reveal genetic diversity in fine molecular detail. Missing are multi-environment and multitrait phenotypic data to rapidly discover gene-phenotype relationships.

The Phenome project handles a large amount of (observational)data (approximately 40 Tbytes in 2013, 100 Tbytes in 2014 and over 200 TBytes in 2015) at different levels (field, microplot, plant, organ, cell, etc). To this, the traditional relational databases lacks the capacity to handle such larg dynamic data. Often these systems become heavy and slow and don't provide required flexibility. To this end, the advent of the so called NoSQL database technologies offer several alternative options to organise and store data (see

Semantic Web context

An important aspect in efficient data management is making data interoperable enabling the of extract meaningful information from large datasets. To this end, the Semantic Web technologies proposed by Tim Berners Lee et al., [START_REF] Berners-Lee | the semantic web[END_REF] [6], offers a remedy to interlink highly distributed data and enhancing data interoperability, to share and reuse data be-tween multiple applications and help users to extract new knowledge.

Overview of existing solutions

The first solution is based on the association between MongoDB and AllegroGraph -a document store and a graph database system. AllegroGraph provides an interface to MongoDB, called MongoGraph. This tools allows the automatic conversion of JSON objects to RDF triples and can be query by both MongoDB query language and SPARQL. With these characteristics, it is possible to develop a system that combines semantic web features with MongoDB to manage voluminous data. Figure 1 shows the architecture of such this system. Here, the experimental data remains stored in MongoDB under document format. Triples linking MongoDB documents to an ontology are imported into Alle-groGraph. We use the xR2RML tool to automatically map elements of collections with the ontology [START_REF] Michel | Translation of relational and non-relational databases into rdf with xr2rml[END_REF]. This ontology allows inference by exploiting the relationship between triples. Thus the inference engine can create new relationships based on concepts defined in the ontology. • Massive database management with MongoDB

Disadvantages

• A more complex system with multiple stage requests

• No synchronization between the two databases.

In the second solution, we present Neo4j which is used to represent the data as graph. Neo4j has optimal components that come in kernel supplement [START_REF] Angles | Benchmarking database systems for social network applications[END_REF]. One can structure the graph via a meta-model, getting an implementation of RDF triplestore compliant SPARQL [START_REF] Flores | Graphium: Visualizing performance of graph and rdf engines on linked data[END_REF]. For example, with two plugins Neo-rdf-sail 3 and Neo4j sparql-and-extension 4 .

Advantages

• A graph representation of Big Data improves the performance of the system by queries based on the relationships between the objects.

• The graph representation is similar to that of ontologies and RDF data instances.

Disadvantages

• The data must be re-organized in the form of a graph, which is time consuming, depending on the complexity and size of the data.

• The data are not directly represented in RDF, thus to query with SPARQL, one needs to deploy an integrated plugin that support SPARQL.

The third solution is based on the data organization for linked data which publish and use information on the Web [START_REF] Aswamenakul | A review and design of framework for storing and querying rdf data using nosql database[END_REF]. JSON-LD is an ideal data format for programming environments such as, REST Web Service, as MongoDB or CouchDB. JSON-LD document is both a serialization of RDF and a JSON document. The RDF data format is serialized in JSON-LD is complimentary to the JSON format used in MongoDB. So we can exploit the power of MongoDB in handling big data and the flexibility provided by RDF. Moreover, we facilitate the serialization of graphs in Mon-goDB, graph data can be organized and stored in memory by using APIs such as Jena or Sesame. Such APIs allow the use of SPARQL to query and infer the new knowledge. The semantic searches will be made directly on the RDF graphs that are serialized from MongoDB. In practice this setup is time consuming. Therefore, to overcome this limitation, we developed a method to organize indexes for the data and optimize of the execution time. Figure 2 shows CRUD (Create, Read, Update, Delete) operations that run on MongoDB and semantic search conducted over RDF graphs. Thus, a middle layer is necessary to synchronize the two databases.

Advantages

• JSON-LD is both an RDF serialization format and the storage model for MongoDB.

• Operations CRUD will be quickly performed on the data in MongoDB.

• SPARQL is used to query triplets in memory.

Disadvantages

• The existence of two database will increase the system complexity.

• Loading of RDF graphs in memory will be time consuming. The updated data on RDF graphs are dependent on MongoDB. 3 https://github.com/neo4j-contrib/neo4j-rdf-sail 4 https://github.com/niclashoyer/neo4j-sparql-extension The fourth solution is based the concept of the Ontology-Based Data Access (ODBA). ODBA is a paradigm for accessing and integrating data, the key idea is to resort a threelevel architecture, constituted by the ontology, the data, and the mapping between two [START_REF] Antonioli | Ontology-based data access: The experience at the italian department of treasury[END_REF]. In the OBDA paradigm, an ontology defines a high-level global schema and provides a vocabulary for user queries, thus isolating the user from the details of the structure of data sources (which can be relational databases, triple stores, datalog engines, etc.). The OBDA system transforms user queries into the vocabulary of the data and then delegates the actual query evaluation to the source data.

An OBDA system is a triple [4] O = <T , S, M>, Where:

• T is the intensional level of an ontology. We consider ontologies formalized in description logics (DLs), hence T is a DL TBox.

• S is a (federated) relational database representing the source data.

• M is a set of mapping assertions, each one of the form Φ(x) ← Ψ(x)

Where:

-Φ(x) is a query over S, returning tuples of values for x -Ψ(x) is a query over T whose free variables are from x

Based on the definition of the ODBA, researchers at the University Bozen-Bolzano in Italy have developed a Framework named Ontop. It is currently used on the application Optical 5 . It aims to solve the problems of association of Big Data and semantic search capacities. The Ontop core is the query engine SPARQL QUEST that implements RDFS and OWL 2 QL by re-writing the SPARQL queries into query SQL. Ontop is able to efficiently generate and optimized SQL queries [START_REF] Muro Mariano | Evaluating sparql-to-sql translation in ontop[END_REF]. Advantages

• The data structure is stored in the database management system (no duplication, realtime data access).

• Queries are performed on the data in SPARQL.

• The compatibility with multiple relational database systems.

Disadvantages

• System complexity will increase with the organization of ODBA models.

• The increase in time and cost to build the system.

• Applied only for relational databases, no applications avialble for NoSQL systems.

In summary, in all of the above approaches, data is organized and stored in the graph oriented database management systems (Neo4j) or document oriented database systems (MongoDB), hybrid systems (MongoDB and Triple store technology) and using ODBA approach. The solutions are broadly divided in two: query re-writing and data transformation to RDF graphs. We can see that for each approach there are advantages and disadvantages. Choosing the best solution for the data, will depend on the use and the underlying questions.

PROPOSED SOLUTION

General Model

We consider a solution using the RDF data model. Here, the current heterogeneous data will be converted in RDF. This approach is at this moment the optimal solution for data organization with semantic search capabilities. Most often original data that needs to be exposed as RDF already exists in relational databases. There are several methods to translate relational database to RDF but the most used is the following: D2R 6 . D2R operates with a mapping file and one or several ontologies. The mapping file is used to make the connection between the tables, attributes on one hand and classes, properties on the other. Thus, after the mapping, data will be available via semantic web applications. There are now two additional methods: R2RML 7 and Direct Mapping 8 . Both approaches are only for relational databases. So there is a need to map RDF with documentoriented databases such as CSV, XML and JSON. Franck Michel and his colleages [START_REF] Michel | Translation of relational and non-relational databases into rdf with xr2rml[END_REF] used the mapping language R2RML and Morph-RDB 9 to develop xR2RML which is apply to documents oriented databases such as MongoDB. Precisely, xR2RML is an extension of the mapping language R2RML and relies on particular properties of the mapping language and RML [START_REF] Dimou | Rml: A generic language for integrated rdf mappings of heterogeneous data[END_REF]. R2RML covers the basic mapping relational data to RDF triples. RML extends R2RML to address mappings on heterogeneous data (XML, JSON, CSV) 6 http://d2rq.org/ 7 http://www.w3.org/TR/r2rml/ 8 http://www.w3.org/TR/rdb-direct-mapping/ 9 https://github.com/oeg-upm/morph-rdb is an implementation of mapping R2RML language for relational databases with RDF triples. xR2RML extends its scope to a wider range of basic non-relational data. Advantages

• Data are translate in RDF triples.

• Questions are performed with the query language SPARQL

• Reasoning capacity are supported by these triplestores.

Disadvantages

• Data transformation step is time consuming (i.e. reorganizing data in graph)

• A new system architecture needs to be implemented with these data.

• We encounter performance problems with large graphs Current systems able to store large volumes of data, refer mostly to NoSQL systems (eg: MongoDB). With a middleware layer, we are able to organize and synchronize the existent data like an intermediate storage for interacting with the system. Subsequently, the data will be converted into RDF triples with the use of language mapping xR2RML and the tool developed by the authors [START_REF] Michel | Translation of relational and non-relational databases into rdf with xr2rml[END_REF]. Vocabularies and triples transformation rules are provided by ontologies. Ontology are important to perform advanced search on relationships and existing hierarchies. There exist various triplestores to manage RDF. In the paper, we will focus experiments with six systems: 4Store, Virtuoso, Stardog, GraphDB , Sesame and Jena Fuseki(TDB). Considering their storage capacities and indexing are differents, we will test these systems with large RDF graphs. Thus we will test them based on the data management capabilities and data retrieval using the SPARQL query language. We will develop a search engine in order to use inference capacities. An access point will be provided to perform queries.

Data transformation to triples

Plant phenome research creates various heterogeneous data associated with observational process such as data imaging, watering, weighting process. Now, the majority of the data exists in the form of the documents JSON which are stored in MongoDB. This section will exploit stages of the RDF translation with xR2RML. Thus, a triples map specifies a rule for translating data elements of a logical source. The RDF triples generated from a data element in the logical source share all the same subject. An xR2RML triples map is represented by a resource that references the xrr:logicalSource property. It means that a logical source specifies a table mapped to triples. A subject map specifies how to generate a subject for each data element(row, document, set of XML elements, etc). A subject may be specified using the rr:subjectMap property, where value must be the subject map, or the constant shortcut property rr:subject, and zero or to many rr:predicateObjectMap properties, where values must be the predicate object maps. They specify pairs of predicate maps and object maps that, along with the subjects from one or many RDF triples.

1 @prefix xrr : < http : // i 3 s . unice . fr / xr 2 rml # >. 2 @prefix rr : < http : // www . w 3 . org / ns / r 2 rml # >. 3 @prefix rml : < http : // semweb . mmlab . be / ns / rml # >. 4 @prefix xsd : < http : // www . w 3 . org / 2 0 0 1 / XMLSchema # >. 5 @prefix rdfs : < http : // www . w 3 . org / 2 0 0 0 / 0 1 / rdf -schema # >. 6 @prefix rdf : < http : // www . w 3 . org / 1 9 9 9 / 0 2 / 2 2 -rdf -syntax -ns # >. 7 @prefix f : < http : // www . franz . com / > .

EXPERIMENTS AND COMPARISONS

We obtained 45 millions of triples for image annotation from about 3.5 millions images in the MongoDB system. This transformation required a lot of server execution time (about 20 hours). These data exist in the form of a graph with multiple instances. We first aim at realizing experiments with these triples and then compare performances of the following triplestores: 4Store, Sesame, Jena, Virtuoso, GraphDB, Stardog. The data are divided into five groups of triples 100.000, 1 million, 10 millions, 20 millions and 40 millions of triples. Data from the first to the fourth groups are distinct, while the last group is a collection of all data. These groups will allow us to evaluate the performance of these Triplestores. Here, we focus on three performance criteria: loading, queries and reasoning.

These experiments were performed on a server Ubuntu Server operating system. Below we can see the detailed configuration of this system:

Processor

Intel Xeon(R) CPU L5420 @ 2.50GHz

Front side bus 1333 MHz

Cache L2 12M

Memory 32GB

Storage 160GB

Table 2: Configuration of the Server

Data loading

With large RDF files generated, the import test data in triple store will give us a particular view of data loading performances. Each system has a particular way of organizing data indexing which impacts the data loading mechanism. Some triplestores allow users to set various configurations such as fields indexes, the order of priority for the index, peak memory used, etc. In addition, there are systems that cannot directly load large files (e.g. with Sesame, Virtuoso). In these cases, a system has been set up specifically to split the files in smaller chunks. Other systems like Fuseki, Stardog and GraphDB provide tools to able load large files.

Figure 5: Comparison of loading times on Triple Stores

The results of benchmark data on load time are obtained with the best time to 4Store while the Virtuoso system is the slowest. We can explain through their differences in the structure of the index and data storage. In Virtuoso the import is performed in RDBMS tables using ODBC protocol, while in the case of 4Store import does not require processing for the storage because of its tree structure.

Data search

The most important part in a data management system is query performances. Experimentation queries allow us to evaluate in detail the system. That is why we set up the second benchmark to test the search capacity with these systems. To ensure an equality, all the queries are launched via a unique access point where several types of search have been defined.

Example query 1

In this application, we want to find the information of the image annotation with the date created, the type of shooting (beside and above), and the camera angle. For refining the results obtained, we used a filter on the camera angle with values greater than 300°or less than 100°. For this query, the best result is obtained with 4Store while the worst is performed with Virtuoso. The difference of the execution time between the systems is great. In general, the systems have a linear increase over time of all data sets. In particular, for small sized data sets (100,000 and 1 million triples), the runtime system is not much different but it is significant with very large data sets.

Example query 2

The second request is constructed on the basis of the first with an additional part on the arrangement of the data obtained on the field angle of the camera and the created date of the image. This addition allows us to test the data search capacity and data grouping with the ORDER BY command.

In this case, there is no change in the ranking for Virtuoso, which still took a long time to execute this query. However, the system that gave the best result is Stardog. Like the previous query, all systems respond very well on small data sets. With 4Store, Sesame, Fuseki and GraphDB tools, the running time is close enough. This can be explained because they all have a tree form data organization while Virtuoso store it in relational tables.

Example query 3 This query test the search capacity of the image annotation with the date and camera angle by combining several In this query, 4Store is the best tool with the fastest query execution. On the contrary, GraphDB system gives the longest execution time, followed by Sesame and Jena. We can also see that there is an irregularity in the execution time with the two data sets 10 and 20 millions triples clearly illustrated by Virtuoso and Stardog. This difference is explained by the fact that there are two distinct sets of data in the assessment.

Example query 4

In the last query, we counted the number of triples in the systems used by the COUNT command. We used a filter on the type of view and angle of the camera to limit triples numbers in the result. There is an error on executing the 4Store tool with higher data sets to 10 million triples. We have included the value -1.0 to report this error. The best tool in this assessment is Stardog unlike Virtuoso who gets the longest running time.

Data inference

The first example of inference This example was conducted to evaluate the reasoning on the relations of the properties that are defined in RDF Schema. Here, the relationship "rdfs: subPropertyOf " is used to presentation both "comesFromPlateau" and "hasSource" properties. So the query on the object "Data" can infer new information in "Image" and also "TechnicalPlateau" can be found in the object "Source". ? data : hasViewType ? hasViewType .

5

FILTER regex (? hasViewType , " side " , " i ") 6 } In general, we have good results with small sizes of data sets in all triplestores but different performances appear with large data sets. In this case, detailed results show that 4Store and Jena Fuseki are slower to perform inference. While GraphDB and Virutoso give the best execution time.

The second example of inference In this example, we have continued to test the ability of inference in RDF Schema on the domain and rank of objects values. In fact, this inference uses the relationship we define as in the first example. However, the important point of this inference is based on specific data. We can see the detail in Figure 17 Figure 17: Inferred relationships ontology in the second example

This example allows us to confirm that the two triplestores 4Store and Jena Fuseki are very slow in executing inferences of large data sets. On the contrary, Stardog, GraphDB and Virtuoso get good execution time. Sesame in both example of inferences gets decent results for an OpenSource triplestore. In some cases, it gives better results than commercial ones.

Evaluations

This section gives an overview on implementation and per- formance capacity of these systems. Each system has differences in the organization and indexation of triple data: Virtuoso uses tables as in the relational database, 4Store uses the structure of the radix tree [START_REF] Harris | 4store: The design and implementation of a clustered rdf store[END_REF], while Sesame, Jena Fuseki and GraphDB apply the structure B or B+ tree [14] [11]. These differences are important elements that impact their performances. Nevertheless, we must also consider the necessary features for a triplestore. The most important feature is the reasoning capacity with RDFS or OWL. Moreover, handle large datasets, distribute processes on multiple machines, can facilitate reasoning on large RDF graphs. In this context, the triplestores need to support management of distributed databases instead of having a network of multiple machines to communicate and exchange data [START_REF] Filali | A survey of structured p2p system for rdf data storage and retrieval[END_REF] [15] [16] [START_REF] Wu | Semstore: A semantic-preserving distributed rdf triple store[END_REF]. Above, we evaluate the three most important criteria for triplestores: loading, search and inference.

With 4Store, the advantages of indexation data with the radix tree provide a good system for loading and search data. It is always one of the best systems with the fastest execution time. In addition, the architecture of 4Store allows clustering of distributed data and used in several machines at the same time. However, the search function in 4Store is still perfectible, we can see errors in some cases (in the example query 4). In addition, the user interface has several limitations. But the biggest drawback is the reasoning support. In fact, the reasoning engine is an extended module named 4SR [START_REF] Salvadores | 4sr -scalable decentralized rdfs backward chained reasoning[END_REF] which is a branch of the 4Store project, implemented for RDFS Backward Chained Reasoning. This module supports a very weak inference capacity with class and properties: rdfs:subClassOf, rdfs:subPropertyOf, rdfs:domain et rdfs:range in RDFS. Choosing 4Store to build the system with large data volume will depend on the need of reasoning. If there is no need to infer the data, 4Store may be the right choice.

Sesame is one of the first systems that is used to manage RDF data. With this system, the results are average in the benchmarks on loading, search and inference data. These result are acceptable for an Opensource system. However, Sesame has disadvantages in large database management. Firstly, it can not be deployed in a cluster of machines with large distributed graphs, but rather allows to create federated databases with graphs which are completely distinct. Then the native RDF data model is optimized for medium sized graphs. Finally, the inference mechanism of Sesame creates many new triplets and increases the size of the database. This is manageable for medium sized graphs but reached its limit for large graphs.

Virtuoso is built on the architecture of relational database management system. This may explain its bad results on the data loading runtime and some examples of query search. On the contrary, Virtuoso has advantages in the data inferencing capacity. It can perform reasoning with data defined by RDFS or OWL. In this evaluation, Virtuoso is the best Opensource tool that completely supports essential components of a database management system, such as ACID transactions, security or the user interaction interface etc. In addition, it allows us to implement a system with a strong supporting reasoning. Finally, Virtuoso allows to deploy databases on multiple clusters of machines. However, this feature is only supported in the commercial version.

Jena Fuseki is developed on the basis of the Jena framework. It brings features of the first framework that is built for RDF data. Our benchmark is performed with the storage of the Jena TDB architecture and uses the indexing of the B + tree structure. In the evaluations, Jena shows good results in loading data. However, research data and inferences with Jena Fuseki took a long execution time. At this time, Jena can run on a cluster of several machines in different architectures (Some examples defined in this article [START_REF] Owens | Clustered tdb: A clustered triple store for jena[END_REF] ). Moreover, Jena provides APIs (Apache Jena Elephas) that allow to write embedded applications in Apache Hadoop. From the results we can say that Jena Fuseki suitable for RDF databases of medium size.

GraphDB Ontotext is built upon the Sesame framework to provide missing features of Sesame. The GraphDB improvements focus on reasoning ability, user interface and data cluster architecture. In nearly all evaluations, we can see that GraphDB gives a higher performance than Sesame in data search and inference. In fact, there is less difference in the indexing mechanism which explains the small difference in the execution time. With its inference engine, GraphDB supports reasoning in RDFS and OWL. Finally, it is possible to manage large volumes of RDF data.

Stagdog gives impressive results compared to the criteria: Data Loading, Data Search and Data Inference. It is always in the best tools that are the most effective. For the reasoning, it supports inferences in RDFS and OWL. Moreover it is build for cluster performances at a high level. We can say that Stardog is the best tool in the list of all the tools tested for our Benchmark. However, it is available only in commercial version.

CONCLUSION AND FUTURE WORKS

The efficient data management is increasingly important in conducting biological reseach. The search for optimal data management solution can help reduce time and increase the performance of database systems. The problems we encountered during this effort is the size of the data. Traditional methods have limitations in managing large amounts of data. In addition, the need to interlink and reuse data leads us to adopted methods to structure these data. There are different solutions for this problem. However, each solution described is a combination of one or more technologies. In general, we can summarize these solutions in two directions: the transformation of queries (or query rewriting) and the translation of data in RDF triples (or materialization). Each of approach has particular advantages and disadvantages. To this end we have chosen data conversion to RDF. This choice enabled us to facilitate the research on semantic data. We had to define new data models to unified and transform the experimental data in RDF. We evaluated several triplestores (4Store, Sesame, Virtuoso, Jena Fuseki, GraphDB Stardog) and carry out benchmarking based on different criterion: data loading capabilities, query search and inference on data.

The conversion of data to RDF triples is suitable to increase the semantic search capability on the data, such as performing inference tasks to extract implicit facts. However, this approach still has drawbacks including the management of large data, because until now, only few triplestores can support large volumes of data. We believe that in the future, work on query rewriting approaches (NoSQL-SPARQL) will help us to compare the advantages and disadvantages of both approaches.

Figure 1 :

 1 Figure 1: The components in a system MongoGraph

Figure 2 :

 2 Figure 2: The components in an associated system of MongoDB and JSON-LD

Figure 3 :

 3 Figure 3: General model of the system

Figure 4 :

 4 Figure 4: Mapping a json data to triples

Figure 6 :Figure 7 :

 67 Figure 6: Example query 1

Figure 8 :query 2 Figure 9 : 4 ? 5 FILTER 7 ? 8 FILTERFigure 10 : Example query 3 Figure 11 :

 829457810311 Figure 8: Example query 2

1Figure 12 : Example query 4 Figure 13 :

 12413 Figure 12: Example query 4

Figure 14 :

 14 Figure 14: Inferred relationships ontology in the first example Because the results obtained in these examples are very different between the triplestores, we use a logarithmic func-

Figure 15 :Figure 16 :

 1516 Figure 15: The query SPARQL of the first example of inference

Figure 18 :

 18 Figure 18: The query SPARQL of the second example of inference

Table 1 )

 1 .

	Type	Examples of this type
	Key-values	CouchDB, Oracle NoSQL Database,
	Store	Dynamo,	FoundationDB, HyperDex,
		MemcacheDB, Redis, Riak, FairCom c-
		treeACE, Aerospike, OrientDB, MUMPS
	Wide Column	Accumulo, Cassandra, Druid, HBase, Ver-
	Store	tica
	Document	MongoDB,	Clusterpoint,	Apache
	Store	CouchDB, Couchbase,	DocumentDB,
		HyperDex, Lotus Notes, MarkLogic,
		OrientDB, Qizx
	Graph	Allegro, Neo4J, InfiniteGraph, OrientDB,
		Virtuoso, Stardog
	Multi-model	OrientDB, FoundationDB, ArangoDB,
		Alchemy Database, CortexDB

Table 1 :

 1 Database management Systems in NoSQL

  8 @prefix ia : < http : // www . mistea . supagro . inra . fr / ontologies / 2 0 1 5 / 0 3 / im age Anno tati on # >.

	9	<# Image > a rr : TriplesMap ;
	10	xrr : logicalSource [
	11	xrr : query """ db . image . find ( { ' configuration . imgid '
		: { $exists : true } } ) """;
	12	] ;
	13	rr : subjectMap [
	14	rr : template " { $ . uri } ";
	15	rr : class ia : Image ;
	16	] ;
	17	rr : pre dica teO b j e c t M a p [
	18	rr : predicate ia : aboutEntity ;
	19	rr : objectMap [ xrr : reference " $ . context . plant "; ] ;
	20	] ;
	21	rr : pre dica teO b j e c t M a p [
	22	rr : predicate ia : timeStamp ;
	23	rr : objectMap [
	24	xrr : reference " $ . date ";
	25	rr : datatype xsd : date ;
	26	] ;
	27	] ;
	28	rr : pre dica teO b j e c t M a p [
	29	rr : predicate ia : hasFileName ;
	30	rr : objectMap [ xrr : reference " $ . fileName "; ] ;
	31	rr : datatype xsd : string ;
	32	] ;
	33	rr : pre dica teO b j e c t M a p [
	34	rr : predicate ia : hasPlateau ;
	35	rr : objectMap [ xrr : reference " $ . context .
		techni c al P la t ea u "; ] ;
	36	rr : class ia : T e ch n ic a lP l at e au ;
	37	] ;
	38	rr : pre dica teO b j e c t M a p [
	39	rr : predicate ia : inImagingCycle ;
	40	rr : objectMap [ xrr : reference " $ . configuration .
		taskid "; ] ;
	41	rr : datatype xsd : integer ;
	42	] ;

1

  PREFIX rdf : < http : // www . w 3 . org / 1 9 9 9 / 0 2 / 2 2 -rdf -syntax -ns # > 2 PREFIX ia : < http : // www . mistea . supagro . inra . fr / ontologies / 2 0 1 5 / 0 3 / im age Anno tati on # >

	3 SELECT ? Image ? Date ? ViewType ? hasCameraAngle WHERE
		{
	4	? Image rdf : type ia : Image .
	5	? Image ia : timeStamp ? Date .
	6	? Image ia : hasViewType ? ViewType .
	7	? Image ia : hasCameraAngle ? hasCameraAngle .
	8	FILTER (? hasCameraAngle < 1 0 0 || ? hasCameraAngle >3
		0 0 )
	9 }

1

  PREFIX rdf : < http : // www . w 3 . org / 1 9 9 9 / 0 2 / 2 2 -rdf -syntax -ns # > 2 PREFIX ia : < http : // www . mistea . supagro . inra . fr / ontologies / 2 0 1 5 / 0 3 / i mage Anno tat ion # > 3 SELECT ? Image ? Date ? ViewType ? hasCameraAngle WHERE { 4? Image rdf : type ia : Image .

	8	FILTER (? hasCameraAngle < 1 0 0 || ? hasCameraAngle >3
		0 0 )
	9 }
	10 ORDER BY ? hasCameraAngle ? Date

5 ? Image ia : timeStamp ? Date . 6 ? Image ia : hasViewType ? ViewType . 7 ? Image ia : hasCameraAngle ? hasCameraAngle .

1

  PREFIX rdf : < http : // www . w 3 . org / 1 9 9 9 / 0 2 / 2 2 -rdf -syntax -ns # > 2 PREFIX : < http : // www . mistea . supagro . inra . fr / ontologies / 2 0 1 5 / 0 3 / im age Anno tati on # > 3 SELECT ? image ? Source ? hasViewType WHERE {

	4	? image : hasSource ? Source .
	5	? image rdf : type : Image .
	6	? image : hasViewType ? hasViewType .
	7	FILTER (? Source =" http : // www . phenome -fppn . fr / m 3 p /
		phenoarch ") .
	8	FILTER REGEX (? hasViewType , " top " , " i ")
	9 }

https://www.phenome-fppn.fr/

http://www6.montpellier.inra.fr/mistea eng

http://optique-project.eu/


Vsevolod Peysakhovich
email: vsevolod.peysakhovich@isae.fr

Christophe Hurter
email: christophe.hurter@enac.fr

Alexandru Telea
email: a.c.telea@rug.nl

Attribute-Driven Edge Bundling for General Graphs with Applications in Trail Analysis

Keywords: I, 3, 3 [Computing Methodologies]: Computer Graphics-Picture/Image Generation; I, 3, 6 [Computing Methodologies]: Computer Graphics-Methodology and Techniques

Edge bundling methods reduce visual clutter of dense and occluded graphs. However, existing bundling techniques either ignore edge properties such as direction and data attributes, or are otherwise computationally not scalable, which makes them unsuitable for tasks such as exploration of large trajectory datasets. We present a new framework to generate bundled graph layouts according to any numerical edge attributes such as directions, timestamps or weights. We propose a GPU-based implementation linear in number of edges, which makes our algorithm applicable to large datasets. We demonstrate our method with applications in the analysis of aircraft trajectory datasets and eye-movement traces.

INTRODUCTION

Large attributed graphs are ubiquitous in many application domains, such as traffic analysis and planning, network analysis, and bioinformatics. They represent a special subclass of general graphs where edge directions encode essential information for the analysis task at hand. For such graphs, classical visual metaphors such as node-link diagrams produce too much clutter to generate useful pictures.

Graph bundling methods attempt to reduce clutter by grouping edges found to be compatible into so-called bundles. Yet, few such methods handle attributed graphs -edge compatibility is mainly based on spatial position and does not use attributes such as edge direction or data values. Reasoning about such attributes (seeing their values reflected in the bundling) is essential in many applications. Bundling methods for attributed graphs exist, but are computationally not scalable, and thus not usable for large-scale data exploration.

We present Attribute-Driven Edge Bundling (ADEB), a generalized edge bundling technique based on edge advection in compatible vector subspaces, which extends the recent kernel density estimation edge-bundling (KDEEB) [START_REF] Hurter | Graph bundling by kernel density estimation[END_REF] with the following contributions:

1. generation of bundled layouts where edge compatibility is defined by one or several numerical edge attributes, e.g., direction, time, or weight; 2. a simple and scalable GPU implementation of our method; 3. applications of ADEB for exploring trail (airline trajectory and eye tracking) datasets demonstrating the method's added value as opposed to classical bundling of undirected graphs.

The structure of this paper is as follows. Section 2 reviews related work on edge bundling and trail visualization. Section 3 presents ADEB's mathematical framework and its implementation. Section 4 applies ADEB to the visual analysis of traffic and eye tracking data. Section 5 discusses our method. Section 6 concludes the paper.

RELATED WORK

We next briefly review several state-of-the-art edge bundling methods and trail visualization techniques.

Edge bundling techniques

Key to edge bundling is the reduction of edge-edge clutter by grouping so-called compatible edges into spatially compact and thin bundles. This allows an easier visual detection of coarse-scale connectivity patterns in the input graph and supports tasks like finding node-groups which are connected to each other by edge-groups (bundles) [START_REF] Gansner | Multilevel agglomerative edge bundling for visualizing large graphs[END_REF][START_REF] Telea | Image-based edge bundles: Simplified visualization of large graphs[END_REF]. Such strategies are similar to cartographic map generalization, concerned with legibly depicting a complex world in static 2D views [START_REF] Buttenfield | Map Generalization: Making rules for knowledge representation[END_REF]. Clutter causes and reduction strategies are discussed by Ellis and Dix [START_REF] Ellis | A taxonomy of clutter reduction for information visualisation[END_REF] and Zhou [START_REF] Zhou | Edge bundling in information visualization[END_REF]. Edge bundling has been of increased interest in recent research. We group them according to the edge simplification level (data, geometry, and image), as follows.

Data-based methods: Such methods reduce clutter by showing a simpler graph obtained by filtering or by aggregating edges [START_REF] Ellis | A taxonomy of clutter reduction for information visualisation[END_REF]. Interactive tools, such as NodeTrix, compact dense subgraphs into matrix representations [START_REF] Hadlak | In situ exploration of large dynamic networks[END_REF][START_REF] Henry | Nodetrix: a hybrid visualization of social networks[END_REF]. Ploceus displays networks from different perspectives, at different abstraction levels, and with different edge semantics [START_REF] Liu | Network-based visual analysis of tabular data[END_REF]. Filtering can be done by user-specified queries based on multivariate criteria, or by automated methods using edge metrics such as centrality [START_REF] Van Ham | Centrality based visualization of small world graphs[END_REF] or spanning trees [START_REF] Lee | Treeplus: Interactive exploration of networks with enhanced tree layouts[END_REF].

Geometry-based methods: Large graphs can be visualized with limited clutter by edge bundling techniques. Edges found to be compatible, i.e. close in the graph drawing and (optionally) similar in attribute values are deformed to overlap, thereby increasing separating whitespace and thus reducing clutter at the expense of increasing overdraw. Dickerson et al. merge edges by reducing non-planar graphs to planar ones [START_REF] Dickerson | Confluent drawings: Visualizing non-planar diagrams in a planar way[END_REF]. Flow maps use a binary clustering of graph nodes to route curved edges along [START_REF] Phan | Flow map layout[END_REF]. Several authors use flow map control-meshes to cluster and route curved edges [START_REF] Qu | Controllable and progressive edge clustering for large networks[END_REF][START_REF] Zhou | Energy-based hierarchical edge clustering of graphs[END_REF]. Holten generalized this idea by routing edges of compound graphs along the graph's hierarchy drawing [START_REF] Holten | Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data[END_REF]. Gansner and Koren bundle edges in a circular node layout by area optimization metrics [START_REF] Gansner | Improved circular layouts[END_REF]. Edge routing can also use Delaunay [START_REF] Cui | Geometry-based edge clustering for graph visualization[END_REF] and Voronoi diagrams [START_REF] Lambert | 3D edge bundling for geographical data visualization[END_REF][START_REF] Lambert | Winding roads: Routing edges into bundles[END_REF] reflecting the node positions. The most popular (and versatile) bundling methods use force-based techniques that use a force field designed to equal the gradient of a quality function to optimize [START_REF] Dwyer | Integrating edge routing into force-directed layout[END_REF][START_REF] Holten | Force-directed edge bundling for graph visualization[END_REF], and have been adapted to separate bundles running in opposite directions [START_REF] Selassie | Divided edge bundling for directional network data[END_REF].

A major issue of geometric techniques is computational complexity.

To reduce this, graph optimization techniques and multilevel clustering numerical methods have been proposed [START_REF] Gansner | Multilevel agglomerative edge bundling for visualizing large graphs[END_REF][START_REF] Pupyrev | Edge routing with ordered bundles[END_REF].

Image-based methods: These methods exploit the parallel computing power of modern GPUs to speed up bundling and/or offer new visual metaphors for bundled graphs. Visual techniques include color interpolation to show edge directions [START_REF] Cui | Geometry-based edge clustering for graph visualization[END_REF][START_REF] Holten | Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data[END_REF]; and mapping attributes such as local edge density or edge lengths via transparency or hue maps [START_REF] Hurter | Bundled visualization of dynamic graph and trail data[END_REF][START_REF] Hurter | FromDaDy: Spreading data across views to support iterative exploration of aircraft trajectories[END_REF][START_REF] Lambert | Winding roads: Routing edges into bundles[END_REF][START_REF] Selassie | Divided edge bundling for directional network data[END_REF]. Bundles can be drawn as compact shapes emphasized by shaded cushions [START_REF] Scheepens | Composite density maps for multivariate trajectories[END_REF][START_REF] Telea | Image-based edge bundles: Simplified visualization of large graphs[END_REF]. Animated textures can be used to convey edge directions for both static and dynamic graphs [START_REF] Hurter | Smooth bundling of large streaming and sequence graphs[END_REF]. Image-based methods can also massively accelerate bundling: Skeleton-based edge bundling (SBEB) creates strongly ramified bundles by using GPU-computed skeletons or medial axes of the graph drawing's thresholded distance-transform as bundling cues [START_REF] Ersoy | Skeletonbased edge bundles for graph visualization[END_REF]. Recently, the force-directed idea of [START_REF] Holten | Force-directed edge bundling for graph visualization[END_REF] was adapted for a GPU setting, offering speed-ups of up to two orders of magnitude compared to state-of-the-art geometric bundling methods [START_REF] Hurter | Graph bundling by kernel density estimation[END_REF][START_REF] Hurter | Smooth bundling of large streaming and sequence graphs[END_REF].

Trail visualization

Trail datasets consist of sequences of points recording the motion of several objects, e.g. vehicles, or tracked trajectories of object parts, e.g. eyes or human silhouettes. Such datasets have three main features. First, they can be described as attributed graphs, where nodes represent trajectory endpoints and (curved) edge control points represent actual motion paths. Attributes include motion direction, speed, and timestamps. Secondly, they are typically large: For instance, 15 minutes of eye tracking data recorded at 50 Hz already gives 45K sample points; air traffic recorded at a country's scale over a week can yield over a million sample points [START_REF] Hurter | Bundled visualization of dynamic graph and trail data[END_REF]. Finally, they are complex, e.g. contain many intersecting trails covering large spatial domains. All these factors make trail exploration a challenging proposal with respect to attribute depiction, clutter reduction, and computational scalability. We discuss below several methods related to this task.

Trajectory exploration: Interactive brushing-and-linking techniques help locally reducing clutter when exploring large multivariate trajectory datasets, by selecting up to three dimensions to show in a single 2D view [START_REF] Hurter | FromDaDy: Spreading data across views to support iterative exploration of aircraft trajectories[END_REF]. Focus+context interaction helps further reducing clutter and posing complex spatial-and-data queries [START_REF] Hurter | MoleView: An attribute and structure-based semantic lens for large element-based plots[END_REF].

Extracting events of interest from different kinds of spatio-temporal data is discussed (but not fully implemented) by Beard et al. [START_REF] Beard | A framework for visualization and exploration of events[END_REF]. The same query idea is used to extract trajectory parts in [START_REF] Andrienko | An event-based conceptual model for context-aware movement analysis[END_REF][START_REF] Güting | Moving objects databases[END_REF]. Eye tracking exploration: Density maps tackle the visual scalability problem by aggregating spatially close information for eye track analysis [START_REF] Andrienko | Visual analytics methodology for eye movement studies[END_REF][START_REF] Andrienko | An event-based conceptual model for context-aware movement analysis[END_REF][START_REF] Marzuoli | Data visualization techniques for airspace flow modeling[END_REF]. Separately, Burch et al. transform eye tracking data into a dynamic graph to help exploration [START_REF] Burch | A dynamic graph visualization perspective on eye movement data[END_REF]. Areas of interest (AOI) analysis provides information about dwell times, transitions, fixation points, and AOI hits, but require accurate a priori knowledge to define such areas [START_REF] Duchowski | Eye tracking methodology: Theory and practice[END_REF][START_REF] Holmqvist | Eye tracking: A comprehensive guide to methods and measures[END_REF]. A few methods exist that are able to group eye-movement paths; however, they are neither visual nor intuitive to use [START_REF] Meur | Methods for comparing scanpaths and saliency maps: strengths and weaknesses[END_REF]. An overview of eye movement pattern analysis is given by Laube [START_REF] Laube | Progress in Movement Pattern Analysis[END_REF].

Given the size and clutter of trail datasets, bundling methods have emerged as an effective way to show the coarse-scale connectivity structure of these datasets [START_REF] Cui | Geometry-based edge clustering for graph visualization[END_REF][START_REF] Ersoy | Skeletonbased edge bundles for graph visualization[END_REF][START_REF] Holten | Force-directed edge bundling for graph visualization[END_REF][START_REF] Hurter | Bundled visualization of dynamic graph and trail data[END_REF][START_REF] Hurter | Graph bundling by kernel density estimation[END_REF][START_REF] Lambert | Winding roads: Routing edges into bundles[END_REF]. However, as analyzing trail datasets requires reasoning about trail attributes (e.g. timestamps, speed, and direction), undirected bundling techniques are of limited use. For instance, a bundle connecting two node-groups A and B will only tell that A and B are connected, but not in which direction(s) and at which time instant(s) objects moved from A to B. As a side effect, mixing edges of different attribute values in a bundle makes the attribute-based shading-and-blending schemes proposed by several authors [START_REF] Holten | Force-directed edge bundling for graph visualization[END_REF][START_REF] Hurter | Bundled visualization of dynamic graph and trail data[END_REF][START_REF] Lambert | Winding roads: Routing edges into bundles[END_REF] of limited effectiveness. Conversely, using bundling techniques for attributed graphs [START_REF] Holten | Force-directed edge bundling for graph visualization[END_REF][START_REF] Selassie | Divided edge bundling for directional network data[END_REF] is not practical, as these are far too slow for large datasets such as trail data.

ADEB FRAMEWORK

We next describe our ADEB method, a framework that bundles large graphs using an edge-compatibility scheme that can be flexibly controlled to include (mixes of) edge attributes. We first outline the main elements of the KDEEB algorithm from which ADEB is inspired (Sec. 3.1). Section 3.2 presents ADEB's mathematical details. Sections 3.3 and 3.4 explain how to use attributes to create various edge compatibility metrics. Implementation details are given in Sec. 3.5.

Kernel density bundling

We first review the main principles of the kernel density estimation edge bundling (KDEEB) technique. Let G = {e i } 1≤i≤N ⊂ R 2 be the drawing of a graph of N edges, where each edge e i is represented by a straight line or arbitrary 2D curve. First, an edge-density map ρ : R 2 → R + is computed using kernel density estimation

ρ(x ∈ R 2 ) = 1 h 2 N ∑ i=1 y∈e i K x -y h , (1)
where K : R 2 → R + is a bivariate radial kernel obtained from a symmetric univariate non-negative kernel function of bandwidth h > 0, e.g. Gaussian or Epanechnikov. The bundling of G is given by the fixed point of the ordinary differential equation

dx dt = h(t)∇ρ(x,t) max( ∇ρ(x,t) , ε) , ∀x ∈ G, (2)
with initial conditions given by the input graph drawing G. The regularization constant ε 1 takes care of zero gradients. After a few Euler iterations used to solve Eqn. 2, during which one resamples edges, recomputes ρ, decreases h, and makes a 1D Laplacian smoothing pass over G's edges, KDEEB converges and aggregates edges into bundles. Note that KDEEB is nothing else but the well-known mean-shift algorithm [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF] applied to the graph drawing G. Hence, KDEEB inherits smoothness, noise robustness, and convergence results proven for mean-shift. For details, we refer to [START_REF] Hurter | Graph bundling by kernel density estimation[END_REF].

Mathematical model for ADEB

We proceed by first introducing a few necessary definitions. Edge directions: Consider a given drawing G = {e i } 1≤i≤N of a directed graph or trail dataset. For each point x ∈ e i ⊂ G, we denote by d(x) the unit vector tangent to the curve representing e i , oriented in the direction given by walking on e i from its start to its end point. For our trail datasets (Sec. 2.2), e i will be typically a 2D curve rather than straight line (as in a classical node-link graph drawing), so d changes along e i . Secondly, note that d encodes the local directions of the initial graph drawing, given as input to the bundling process. Flow direction map: Given a graph drawing G as above, the flow direction map θ : R 2 → R 2 is defined as

θ (x ∈ R 2 ) = 1 h 2 N ∑ i=1 y∈e i d(y)K x -y h , ( 3
)
where K is the same kernel as in Eqn. 1. We can think of θ as being a 2D viscous fluid flow whose boundary conditions are given by the d values on G. The bandwidth h in this analogy is the fluid viscosity. Note that several points have θ (x) = 0, e.g., points equidistant from two parallel opposite-direction edges of. In our analogy, these would be flow separation lines. Points x close to an edge have values θ (x) close to the edge direction d. The flow magnitude θ decreases monotonically and smoothly away from the flow boundary G. Directional compatibility: At each point x ∈ G, we define a subspace Ω x,c of compatible directions as

Ω x,c = y ∈ R 2 \ ker(θ ) d(x) • θ (y) θ (y) ≥ c ⊂ R 2 , (4)
where ker(θ

) = {x ∈ R 2 | θ (x) = 0} and c ∈ [-1, 1
] is a compatibility factor. This factor represents the cosine of the maximum allowed angle between the edge direction and flow direction at y. Thus, Ω x,0 covers all points where the flow direction deviates from d(x) by π/2 at most, and Ω x,-1 ≡ R 2 . In general, given a point x of the initial graph drawing G, Ω x,c gives all points in R 2 where the flow map θ has roughly the same direction as x, subject to the factor c.

Given the ρ and θ maps, the subspace Ω x,c is defined at each point x ∈ G. We can now define the ADEB bundling of G as the fixed point of the ordinary differential equation

dx dt = h(t)∇ Ω x,c ρ(x,t) max( ∇ Ω x,c ρ(x,t) , ε) , ∀x ∈ G (5)
In contrast to KDEEB (Eqn. 2), the gradient ∇ Ω x,c ρ is estimated now only over the subspace of compatible directions Ω x,c . In analogy with KDEEB, we solve Eqn. 5 by a few Euler iterations, during which we resample edges, recompute ρ and θ , decrease h, and make a 1D Laplacian smoothing pass to remove small wiggles.

ADEB (c=cos π)

ADEB (c=cos π/6)

Input datasets

Figure 1: Influence of compatibility factor on bundling result.

In summary, while KDEEB advects points of a given drawing towards local maxima of its edge density, ADEB advects points towards local density maxima of compatible directions. Figure 1 shows the influence of the compatibility factor c on four simple graphs. Edges are colored using a directional colormap (see color wheel in figure: edges going west are red, edges going north are purple, edges going south are green, and edges going east are blue). Luminance is linearly increased along edges, so their direction is also shown by following the dark-to-saturated color gradient, in line with [START_REF] Holten | A user study on visualizing directed edges in graphs[END_REF]. The top row shows the input graphs, which are simple for illustration purposes. The middle row uses c = cos(π), in which case ADEB produces identical results with KDEEB. As shown by the colors, bundles contain edges running in different directions. This creates bundles which arguably do not reflect well the connectivity pattern in the input graph, see e.g. the second row from left. The bottom row shows ADEB for c = cos(π/6), which creates bundles containing only edges having similar directions. As argued also by Selassie et al., this is useful to separate a graph into several bundled 'layers', each representing the bundling of a subset of edges having locally similar directions [START_REF] Selassie | Divided edge bundling for directional network data[END_REF]. The bottom-right image in Fig. 1 shows this: The input graph (top-right image), which contains edges of alternating directions as indicated by the arrows, has been effectively bundled to yield two similar red and purple bundle structures, one for each input direction (compare this example with Fig. 7 in [START_REF] Selassie | Divided edge bundling for directional network data[END_REF]).

Attribute-based bundling

Apart from direction, we can easily use other edge attributes to define edge compatibility. Consider for instance that edge e i has, at point x, an attribute value t i (x) ∈ R. We next transform t i to a vector t i = (t x i , t y i ) ∈ R 2 by using polar coordinates, i.e. set

t x i (x) = cos t i (x) -t min t max -t min • π , t y i (x) = sin t i (x) -t min t max -t min • π (6)
with t i ∈ [t min ,t max ] over the entire G. Next, we use ADEB (Sec. 3.2) unchanged. The resulting flow direction map encodes the compatibility of our edge-attribute t i . The compatibility factor c is to be set accordingly: For instance, if edges are compatible in time when their timestamp difference is less than σ seconds and the maximum timestamp value is t max , then c should be set to cos( σ π t max ).

Multi-criteria bundling

We can use the ADEB framework to bundle graphs using compatibility criteria defined by several attributes. Suppose that we calculated two flow direction maps corresponding to edge direction and edge timestamps respectively. We can next compute two subspaces of compatible directions and compatible timestamps. Next, by computing the gradient ∇ρ over the intersection of these two subspaces, the result given by Eqn. 5 is a multi-criteria bundled layout. Figure 2 shows this for a dataset recording the gaze for a oneminute exploration of Ilya Repin's painting Unexpected Visitor. Similar to Yarbus [START_REF] Yarbus | Eye Movements and Vision[END_REF], a subject was asked to look at the painting and first assess and verbalize the age of the main characters, and next the age of secondary ones. Using time-based compatibility, ADEB successfully bundles together the trails separated in time (Fig. 2 b, trails colored by time via a blue-green-red colormap). We find that there are two main 'visual scans' in this scenario -first, a scan between the faces of foreground characters A and B (green bundle), followed by a second scan between background characters C and D (red bundle). However, since we don't use direction for bundling, we cannot tell if in these scans the eye moved from left to right, right to left, or both directions. Figure 2 b shows the result of directional bundling, colored by trail directions like in Fig. 1. We now see that both scans A-B and C-D include left-to-right (blue) and right-to-left (red) bundles of similar thickness. Hence, the eye moved in both cases in both directions, and it did so in a balanced way (comparable amount of times in both directions). However, close to character C, the ends of the C-D bundles are pulled towards and mixed with the A-B bundles, even though the two scans are temporally separated. Using time-anddirection based compatibility, we can obtain both desirable effects shown before (Fig. 2 d): Each scan is separated in a left-to-right and right-to-left bundle, and temporally different scans are not mixed.

Implementation details

We evaluate the two components θ x and θ y of the flow direction θ by using Eqn. 3 twice, for the two corresponding components d x and d y of the edge direction vector d respectively. We implement this on the GPU by splatting the kernel K at all edge sample points using additive blending, and accumulating the resulting θ x and θ y values in two floating-point textures. Next, we compute the density gradient ∇ Ω x,c ρ by finite differences, on a compatible subspace Ω x,c ∩ ν ε (x), where ν ε (x) is a neighborhood of x of radius ε ≥ h > 0. While covering the neighborhood ν ε (x), each point y of it is tested for directional compatibility. The finite differences are computed only on points that pass the compatibility test in Eqn. 4. Finally, while doing the bundling iterations that solve Eqn. 5, we relax the user-given compatibility value c so it reaches cos π at the last iteration. This way, the first iterations force edges to aggregate into compatible bundles, while the last iterations 'compact' edges already found to be compatible into smoother final bundles.

Our method has similar complexity and computational performance with KDEEB. Specifically, computing the flow direction map θ takes twice the time required for KDEEB's density map computation. Estimating the directional compatibility criterion adds only a simple logical condition for the density gradient computation. Memory-wise, our method requires two floating-point buffers of the size of the graph drawing G, which is a negligible cost increase as compared to KDEEB. Compared to FDEB [START_REF] Holten | Force-directed edge bundling for graph visualization[END_REF] and divided edges [START_REF] Selassie | Divided edge bundling for directional network data[END_REF], two other prominent directional bundling techniques, our method is over one order of magnitude faster (see also Sec. 5).

We render the bundled edges as curves colored by the value of one attribute of interest, e.g. time or direction. We also scale the curve thickness at each point x with the local edge-density value ρ(x) (Eqn. 1). Bundles (or bundle fragments) thus appear locally thicker in areas where they contain many edges, thereby enabling users to estimate the importance of the respective connection patterns.

APPLICATIONS

We next present two applications of ADEB for the qualitative analysis of trail datasets represented by directed attributed graphs.

Aircraft traffic exploration

Our first application concerns the exploration of aircraft traffic. Given a geographical region (e.g., a country), aircraft position is periodically recorded over a given time interval (e.g., days or weeks) by a mix of observations from ground radar stations and signals emitted by onboard transceivers. This generates a set of trails, attributed by the measured quantities (aircraft timestamp, position, speed, height, and ID). Considering landing and takeoff points as nodes and trails as edges, such data can be modeled as a directed attributed graph. Such data is used by air traffic controllers both online (to keep safe distances between flying aircraft) and offline (to optimize air traffic flows, e.g., minimize delays and optimize flight routes).

Edge bundling has already been used to highlight coarse-scale connection patterns in air traffic data [START_REF] Hurter | Graph bundling by kernel density estimation[END_REF][START_REF] Hurter | Bundled visualization of dynamic graph and trail data[END_REF]. However, this causes problems when tasks at hand involve reasoning about flight directions. Indeed, existing directional bundling techniques are either not scalable enough [START_REF] Selassie | Divided edge bundling for directional network data[END_REF] or need expensive preprocessing steps [START_REF] Ersoy | Skeletonbased edge bundles for graph visualization[END_REF]. To separate different directions mixed in the same bundle, interaction can be used, e.g. the MoleView semantic lens that smoothly interpolates between bundled and unbundled trails at locations of inter-est [START_REF] Hurter | MoleView: An attribute and structure-based semantic lens for large element-based plots[END_REF]. However, this approach only provides local insights. Dataset: The analyzed dataset is 24 hours (February 8 th , 2009) of recorded aircraft trails over France (Fig. 3, 18858 trajectories, 415257 records or sample points). We detail below two exploration scenarios, performed by an ATC expert, using our ADEB bundling technique, embedded in the FromDaDy visual exploration tool [START_REF] Hurter | FromDaDy: Spreading data across views to support iterative exploration of aircraft trajectories[END_REF]. Findings have been cross-checked by a separate air traffic controller. Overview analysis: Exploration started by analyzing an overview of the flight patterns. Figure 3 a shows the input trail set. Trails are color-coded based on direction, as in Fig. 2. To emphasize direction, we made them dark and saturated at the start points and bright and desaturated at end points. Figure 3 b shows the directionally bundled trails, color-coded as above. Compared to the unbundled image, we can now see the different incoming and outgoing aircraft 'flows' at several main European cities (Paris, London, Zürich). We'll explore these further below. Secondly, we notice the complex flight pattern over Lyon, which differs significantly from the pattern above Paris. Indeed, while Paris does not have transit traffic (aircrafts that fly over a given area without landing), Lyon has major transit flows. One such example is formed by the red and blue bundles linking Zürich to Spain (Fig. 3 b,bundle b). Over the entire image, we see several such bundle-pairs having similar thickness in the two directions, e.g. the one ending in London (Fig. 3 b, bundle a). Since bundle width maps the number of bundled trails (Sec. 3.5), this shows us that such paired flows contain balanced traffic in the two directions. Such flows correspond to daily commuting flights. Detailed analysis: We next zoom to explore flight details in a circle of about 100 km around the Paris area (Fig. 3 c). We discover that this flow pattern has four main incoming and four outgoing flows (see arrows in the figure). Also, we see that there are only a few thin bundles whose endpoints are not in the center of the imagethus, we confirm the overview finding that Paris has little transit traffic. Most bundles start/end at two concentrated locations (dotted circles in the figure). These correspond to the two main Paris airports, Roissy and Orly. The detail analysis also shows us facts that were not visible on the overview: For Roissy, the thickness of the main bundles (marked by arrows) show that west and north departures are far fewer than south and east ones. More interestingly, we see that, at this scale, bundle-pairs corresponding to departurearrival flows in the same main direction, are far less parallel than in the coarse-scale visualization. This matches existing knowledge that landing-departing patterns close to airports are much wider spread (in direction) than in-flight patterns, as the former need all to share a smaller geographical area. For Orly airport, we immediately see that traffic is far smaller than for Roissy, and it goes mainly to the south and south-west (bundles sw and s). Only a thin bundle goes from Orly to the north (arrow n). This matches known evidence on this airport: Orly mainly serves domestic flights and is in the north of France; as such, its traffic goes mainly to the south and south-west. Such insights cannot be obtained with a direction-agnostic bundling method. To illustrate this, Fig. 4 shows the same zoom-in as in Fig. 3 c, bundled with KDEEB. The north departure bundle is now mixed with north-east arrivals, and east departures get mixed with south-east arrivals. Also, the several thin traffic bundles (aircraft that do not start/stop at Paris) visible in Fig. 3 c get now aggregated. In other words, undirected bundling keeps the very-coarse connection patterns, but eliminates the finer ones that depend on direction.

Eye tracking exploration

Recent eye-tracking technology developments made eye movement data increasingly used in applications in neuroscience, psychology, human factors, training, and marketing. Such data consists of sampled trails giving the motion of the subject's gaze while completing a given task. Its two most important elements are fixations and saccades. Fixations describe points that the eye is attracted to (thus, where attention is drawn). Saccades link fixations and model how one 'scans' the image to link information given by fixations.

For fixation events, studied more often, attention and saliency maps are often used to show regions of interest by locating highdensity fixation areas. However, the saccades linking such points are also of great importance, especially to understand how low-level fixation information is aggregated to form a higher-level understanding of the picture. Specifically, spatially and temporally close saccades are to be grouped into so-called scanpaths, and further analyzed to understand how the image was processed [START_REF] Yarbus | Eye Movements and Vision[END_REF]. Two kinds of visualizations exist for scanpaths: either the gaze is dynamically played back, or the sequence of saccades is depicted statically by connecting consecutive fixation points by arrows. Both visualizations are quite inconvenient for pattern analysis. Playback is necessarily local in both time and space, and thereby cannot show the grouping. Playback is also time-consuming. Static drawings of raw scanpaths generate cluttered images, especially when analyzing data produced by lengthy experiments containing thousands of saccades [START_REF] Burch | A dynamic graph visualization perspective on eye movement data[END_REF][START_REF] Jarodzka | A vector-based, multidimensional scanpath similarity measure[END_REF].

We next describe the use of attribute-based bundling for analyzing such eye tracking datasets. First, we outline how we extracted an attributed graph from raw eye-tracking data. Next, we detail two experiments where our bundling proved to be an effective aid for getting insight into the recorded data (Secs. 4.2.1 and 4.2.2). Preprocessing: Raw gaze data, recorded at 50 Hz, was preprocessed to extract fixations and saccades as follows. Consecutive sample points located in a square of 20×20 pixels and separated by at least 200 ms were considered to be a fixation event. Points marked as a one fixation event were replaced by their average. This reduces small-scale noise (scattered close fixation points) generated by micro-saccades and eye tracking device imprecision during a fixation. Clustering algorithms could be used [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF] to further reduce clutter and aggregate adjacent fixations corresponding to one object of interest but separated spatially due to the imprecision of human visual system. Next, trails formed by consecutive sample points were cut between fixations, yielding the saccades. Finally, a graph was created using fixations as nodes and saccades as curved edges. Note that since human eye does not encode any information during the saccadic movement, curved edges of our graph do not have direct attentional interpretation and thus could be distorted.

Multitask experiment

Eye tracking technology can be used to study repartition of visual attention. Consider, for example, how a pilot watches the cockpit instruments during a certain maneuvre (task). Such tasks, e.g. take-off or landing, are typically split into multiple subtasks, each involving several instruments between which the pilot has to allocate attention. For each subtask, instruments have to be watched in appropriate order and with a given frequency. For instance, the priority of the Primary Flight Display (PFD) instrument with respect to Flight Control Unit (FCU) will be different for the final landing approach as compared to the cruise phase [START_REF] Matton | Resource allocation strategies in multitasking after switch in task priorities[END_REF]. Data and tasks: This dataset is part of the priority management testing of the pilot selection at French Civil Aviation School [START_REF] Matton | Resource allocation strategies in multitasking after switch in task priorities[END_REF]. The subject has to perform a main task containing four concurrent subtasks of different nature (tracking, monitoring, target detection, mental computing), with two priority conditions: (a) all subtasks have even priorities, and (b) two high-priority and two low-priority subtasks (uneven priorities). Tasks are performed using a dashboard-like multitask interface on which several instruments show dynamicallychanging data. The interface and location of the various instruments used for each task is shown in the background of Fig. 5a. The top bar widgets let subjects monitor their performance (four bars for each task, and one aggregated-performance bar). For the uneven condition, subtask priorities are shown in Fig. 5b. A detailed description of this experiment and the multitask design are given in [START_REF] Matton | Resource allocation strategies in multitasking after switch in task priorities[END_REF]. Two subject groups, one formed by experienced pilots, and the other one formed by novices, performed the task under both priority conditions, while their gaze was continuously recorded. For each such run, which took 4 minutes, we used the described above preprocessing to obtain a graph having 234 saccades of 24 samples each on average. Using this data, we next try to find similarities and differences in task execution across users and priority conditions. Results: Figure 5 shows the result of applying directional bundling on four sample test runs, involving both priority conditions and user groups, colored by direction as in earlier figures. Directional bundling allows us to identify the main scanpaths (characteristic sequences of saccades) involved in each run, and also to compare these scanpaths across users and conditions. Data is normalized in the sense that all runs are of the same length (in time and number of sample points), and also contain similar numbers of fixation points. As such, differences between such bundled images reveal both intersubject and intra-subject similarities and differences. Let us first analyze the influence of expertise level on the visual attention distribution. The expert has more pronounced transitions between the four subtasks as compared to the novice (Figs. 5a,5b), as shown by the thicker bundles in Figs. 5c,5d. Given that the average saccade speed is similar over humans, and the experiment duration is identical for both user types, we deduce that the expert needs less time to perform a subtask and spends more time to switch between the four screen areas to update his knowledge about subtasks. He also largely ignores the performance bar in his 'attentional walk' as compared to a novice. This way of scanning an image, also called ocular strategy, leads to better performance [START_REF] Matton | Resource allocation strategies in multitasking after switch in task priorities[END_REF].

The ocular strategy changes when the priorities of the four subtasks are uneven, as shown by the different structure of the bundles in Figs. 5b,5d as compared to Figs. 5a,5c. Yet, the priority condition affects novices and experts differently. The expert shifts his attention to the more important subtasks, as shown by the increased bundle coverage in right part of Fig. 5d. In contrast, the novice almost abandons the monitoring task and spends most of the time on the two high-priority subtasks. For the uneven priority case, the tracking task induces significant attention for both the expert and novice. This can be due to the fact that, in this experiment, the user's right hand always rests on the joystick that controls the tracking subtask, so they unconsciously dedicate significant attention to this task, even when they are instructed that tracking is a low-priority subtask.

Directional bundling also shows us the sequence (order) of atten-dance of different instruments. Consider the expert participant with even priorities (Fig. 5c). The main transitions between subtasks, covering about 80% of the entire set of saccades, are captured by the following thick bundles: tracking to monitoring (green bundle 1), monitoring to computing (two merging blue bundles 2), computing to target detection (purple bundle 3), computing to tracking (red bundle 4). Hence, a special order of subtask monitoring can be deduced. First, we deduce that the expert monitored information in anticlockwise order (tracking, then monitoring, then computing, then tracking again). We also see, for the even priority case, that neither the expert nor the novice do have significant transitions between target detection and monitoring. For the uneven priority case, however, the expert has many transitions from monitoring to target detection (Fig. 5d, blue bundles 1). This shows that the expert remembered that target detection is of high priority, and periodically switches attention to it from the less important monitoring.

Landing experiment

Data and tasks: This dataset is part of a study conducted at the French Aerospace Engineering School. During the experiment, a pilot performed a landing manoeuvre in a flight simulator. The experiment lasted 15 minutes. The aim was to test a new cockpit instrument providing landing assistance, which we next call the Landing Aid Instrument (LAI). More specifically, we wanted to understand whether (and how) the new LAI is used along the other instruments.

Eye tracking recording resulted in a graph with 1194 saccades of 8 samples each on average. Results: Figure 6 shows the raw trails from this experiment, the results of our ADEB bundling, and those of undirected (KDEEB) bundling. Bundles are directionally colored, as in earlier figures. The background image shows the cockpit dashboard. Carefully inspecting the raw trails (Fig. 6 a) reveals several saccades connecting the Primary Flight Display (PFD, left), Navigation Display (ND, center), Flight Control Unit (FCU, top-right), and the new Landing Aids Instrument (LAI, bottom-right). However, the raw trails display is too cluttered. We cannot be sure that we found all instrumentto-instrument trails, and we cannot see high-level scanpath patterns. When using ADEB bundling (Fig. 6 b), the following connections become obvious: faint purple bundle 1 LAI→FCU, blue bundle 2 PFD→LAI passing by ND, red bundle 3 in the opposite direction, red bundle 4 FCU→PFD, and blue bundle 5 in the opposite direction. The bundle PFD-ND is denser than the PFD-FCU one, and much denser than the PFD-LAI one. Thus, the main pattern in the pilot's gaze can be deduced: PFD→ND→FCU→PFD. The LAI is rarely consulted because of its novelty -the pilot is used to land the aircraft without this instrument. In more detail, we see that there is no dense connection FCU→LAI. The pilots explained that, after entering flight parameters on the FCU, they are used to check them immediately on the PFD (as shown by the red bundle 4). Thus, to better integrate the new LAI in this maneuvre, a new training protocol should be designed in which pilots are specifically told when to add the visual consultation of the LAI in their action sequence.

Figure 6 c shows the results of undirected bundling. We see, as in our earlier aircraft trail-analysis (Fig. 3 c vs Fig. 4), that undirected bundling highlights only coarse-level connection patterns and smooths our finer-grained ones. For example, the red LAI→PFD and FCU→PFD bundles visible with ADEB (Fig. 6 b) are now hard to see, as they appear to end at ND. More problematically, we notice a quite thick bundle between FCU and LAI (Fig. 6 c, bundle 1), which suggests that the subject did in fact frequently use the LAI in conjunction with the FCU, which we know is not true. ADEB bundling does not show this bundle, as there are not enough saccades coherent in both space and time between FCU and LAI, and thus conveys us the correct insight (LAI rarely used).

DISCUSSION

We discuss next several technical aspects of our method. Generality: Most earlier bundling methods use only edge length, absolute angles, and relative distances (the latter which we also use). So far, only [START_REF] Selassie | Divided edge bundling for directional network data[END_REF] explicitly shows directional bundling; [START_REF] Holten | Force-directed edge bundling for graph visualization[END_REF] mentions this possibility, but does not actually demonstrate it. Separately, attribute-based bundling is noted as a possibility in [START_REF] Telea | Image-based edge bundles: Simplified visualization of large graphs[END_REF], but not actually demonstrated. In contrast to all above, our ADEB demonstrates how both local edge direction and edge attributes can be added to earlier geometric compatibility metrics. Scalability: The most prominent bundling techniques using edge compatibility measures (beyond edge distance) are [START_REF] Holten | Force-directed edge bundling for graph visualization[END_REF][START_REF] Selassie | Divided edge bundling for directional network data[END_REF]. Both have a complexity of O(E 2 C) where E is the number of edges in the input graph, and C the number of edge sampling-points. In contrast, our method, just as KDEEB [START_REF] Hurter | Graph bundling by kernel density estimation[END_REF], is O(C). This makes our method considerably more scalable than [START_REF] Holten | Force-directed edge bundling for graph visualization[END_REF][START_REF] Selassie | Divided edge bundling for directional network data[END_REF], and of about the same scalability as [START_REF] Hurter | Graph bundling by kernel density estimation[END_REF]. In detail, FDEB takes 19 seconds on a graph of 2101 edges and 205 nodes (the well-known US airlines dataset), with 12 sample-points/edge on average (thus, roughly 25K sample points in total); the method in [START_REF] Selassie | Divided edge bundling for directional network data[END_REF] takes 24 seconds for the same graph, for a sampling of up to 25 points/edge (up to 75K sample points), excluding preprocessing costs which authors note to be 10% of the total cost. For the same graph, KDEEB takes 0.5 seconds, at 86K sample points. ADEB takes 1.3 seconds for the same amount of sampling points. Overall, ADEB is roughly twice as slow as the undirected KDEEB, but about 18 times faster than the directional method in [START_REF] Selassie | Divided edge bundling for directional network data[END_REF].

Interaction: Edge bundling aims to create simplified overviews of complex graphs. To solve specific tasks, extra tools such e.g. local levels-of-detail [START_REF] Hurter | MoleView: An attribute and structure-based semantic lens for large element-based plots[END_REF], attribute-based selection [START_REF] Hurter | FromDaDy: Spreading data across views to support iterative exploration of aircraft trajectories[END_REF], or interactive aggregation [START_REF] Van Den Elzen | Multivariate network exploration and presentation: from detail to overview via selections and aggregations[END_REF], are obviously beneficial. Such tools can be easily added to ADEB. In line with earlier bundling papers [START_REF] Cui | Geometry-based edge clustering for graph visualization[END_REF][START_REF] Ersoy | Skeletonbased edge bundles for graph visualization[END_REF][START_REF] Holten | Force-directed edge bundling for graph visualization[END_REF][START_REF] Hurter | Graph bundling by kernel density estimation[END_REF][START_REF] Lambert | Winding roads: Routing edges into bundles[END_REF][START_REF] Selassie | Divided edge bundling for directional network data[END_REF], we do not detail such extensions here, so that our contribution on directional bundling is more focused and easier to separate from such additional tooling mechanisms.

Limitations: Our attribute-based bundling implies that we can map distances between attribute-values (in their original space) to angle distances (Eqn. 6). This is immediate for quantitative and ordinal attributes, but is not evident for categorical attributes. For the latter case, such a mapping would require an algebra definition on the category space. Hence, for categorical attributes, we suggest to cluster trails according to their category and perform separate bundling computations for each such cluster (much like [START_REF] Telea | Image-based edge bundles: Simplified visualization of large graphs[END_REF]). Separately, we showed the added-value of ADEB vs a single undirected bundling method (KDEEB). This leaves the open question whether other undirected bundling methods would be comparably better. While such

comparisons are yet to be done, we argue that, for tasks that require seeing and analyzing bundles of different directions, all undirectedbundling methods would exhibit similar limitations as KDEEB. Finally, we note that our use-cases of ADEB for analyzing eye-tracking data do not imply that ADEB is the ultimate technique to gain all types of insights from such data, as compared to e.g. areas of interest (AOIs), dwell-time-per-AOI, or transition matrices. Rather, we employ this use-case to show how ADEB can be of added value as opposed to a raw or undirected-bundling display of trails (Fig. 6).

CONCLUSION

In this paper, we proposed ADEB, a method that creates edge bundles from attributed graphs where edge compatibility can be defined by one or several attributes. ADEB is fast, simple to implement, scalable, generic, and could be easily extended to handle dynamic graphs. We demonstrated ADEB, and implicitly the added-value of directional bundling, by showing two applications in the analysis of aircraft trails and eye movement recordings. Future work can target several aspects. Refined compatibility metrics (based on graph attributes) and visual metaphors could allow users to better spot specific patterns of interest in large eye-tracking datasets. Secondly, ADEB could be adapted to target additional domains, such as creating simplified attribute-based visual representations of DTI fiber tracts. Finally, we aim to explore how ADEB can be extended to handle attribute-based bundling of dynamic graphs.

Figure 2 :

 2 Figure 2: Multi-criteria bundling of an eye tracking dataset.

Figure 4 :Figure 3 :

 43 Figure 4: Aircraft traffic over Paris (bundled with KDEEB). Compare with the ADEB directional bundling in Fig. 3 c.

  Expert performance with uneven priorities

Figure 5 :

 5 Figure 5: Bundled eye-tracking trails of novice and expert subjects for a multitask experiment done with two priority conditions.

1 Figure 6 :

 16 Figure 6: Raw and bundled eye trails, landing scenario (Sec. 4.2.2).

ACKNOWLEDGEMENTS

The authors thank Nadine Matton, Frederic Dehais and Sebastien Scannella for providing gaze datasets.