Lyes Attouche

Mohamed-Amine Baazizi

Dario Colazzo

Francesco Falleni

Giorgio Ghelli

Christiano Landi

Carlo Sartiani

. . . . . . . . . . . . Stefanie Scherzinger

Angelos-Christos Anadiotis

Oana Balalou

Théo Bouganim

Francesco Chmienti

He- Nena Galhardas

Yamen Haddad

Stéphane Horel

Ioana Manolescu

Youssr Youssef

Adesit

Pierre Faure-Giovagnoli

Marie Le Guilly

Vasile-Marian Scuturici

Jean-Marc Petit

Anastasia Ailamaki

Nikolaos Myrtakis
email: myrtakis@csd.uoc.gr

Vassilis Christophides
email: vassilis.christophides@ensea.fr

TABLE DES MATIÈRES

Keywords: Anomaly Explanation, Predictive Explanation, Anomaly Interpretation, Explainable AI

Conférences invitées

Nothing is for granted : Making wise decisions using real-time intelligence Anastasia Ailamaki

In today's ever-growing demand for fast, data-driven decisions, heterogeneity severely undermines performance and fragments efforts for building unified data exploration tools. The variety in data formats and workloads forces data pipelines to be manually split across a variety of task-specialized systems and combined through expensive ETL and orchestration processes, or to adapt both the data and the workloads to match the requirements of a single-system, sacrificing expressiveness and structural information. Furthermore, the ever-increasing hardware heterogeneity causes task-based specialization of the tools to specific hardware such as CPUs or GPUs, forcing a trade-off : designing optimized hardware often means wasting accelerator-level parallelism (ALP) opportunities or tolerating slow and unnecessary communication between devices. In general, data processing is adapted to the pre-determined data processing system architecture, losing valuable information in the translation.

Real-time intelligence means to make all decisions during execution, when all relevant information is available for optimal utilisation of resources, while it also learns and extracts information about the query requests, instead of depending on pre-determined workload expectations. I will show how designing top-down the system architecture to allow a data-and workload-driven just-in-time specialization enables fast query execution over unprepared, potentially dirty data without time consuming preparation, as well as efficient orchestration and utilization of heterogeneous hardware devices.

Message du Président et des organisateurs

La conférence BDA : Gestion de Données -Principes, Technologies et Applications est le rendezvous annuel incontournable de la communauté en gestion de données en France. Sa 37ème édition s'est tenue du 25 au 28 octobre 2021. A cause de la crise sanitaire liée au COVID-19, elle s'est déroulée en ligne du 27 au 27 octobre et en présentiel le 28 octobre à Paris dans les locaux de ENS Paris.

Poursuivant la tradition des rencontres annuelles de la communauté de gestion de données francophone, BDA 2021 a invité les acteurs académiques et industriels de la recherche en gestion de données à soumettre leurs travaux récents afin de présenter les défis et les avancées scientifiques dans ce domaine extrêmement dynamique.

Avec plus de 200 participants (dont 80 en présentiel), BDA atteste une nouvelle fois du dynamisme de notre communauté et de l'importance de la gestion de données. La recherche en gestion de données n'a jamais été aussi active, variée et ouverte sur d'autres champs de l'informatique. L'omniprésence des données massives change en profondeur la manière dont les différentes phases du processus d'acquisition et de valorisation des données sont mises en oeuvre. Ces données sont volumineuses, hétérogènes, incomplètes, imprécises, produites dynamiquement et avec divers degrés de structuration. L'exploitation de ces données par des applications issues de domaines scientifiques et métiers très variés pose de nombreux défis pour la communauté de recherche en informatique tant sur le plan fondamental qu'appliqué. Cette évolution s'inscrit aujourd'hui dans le contexte de la science des données, avec le cercle vertueux entre données massives et apprentissage automatique, apportant de nouveaux défis à notre communauté.

Le programme scientifique final a comporté 33 articles de recherche, dont 25 longs et 8 courts, 6 démonstrations et 8 articles de doctorants. Il a été complété par trois conférences invitées sur des sujets d'actualité. Un objectif important de BDA est de donner la possibilité aux chercheurs, et surtout aux doctorants, de présenter leurs travaux à la communauté, ce qui inclut également des travaux récents déjà publiés dans d'autres conférences. Les actes de la conférence proposent ainsi des résumés de toutes les contributions publiées et non-publiées et sont complétés par une édition spéciale du journal Transactions on Large-Scale Data and Knowledge-Centered Systems (TLDKS), qui rassemble les versions étendues de quelques articles sélectionnés. Comme les années précédentes, BDA 2011 a proposé également des prix pour des contributions exceptionnelles, récompensant quatre articles de recherche, une démonstration, ainsi qu'une thèse de la communauté indiquée à la fin de ces actes.

Nous tenons à remercier tous les auteurs pour la qualité de leurs contributions et présentations, les membres de l'équipe d'organisation, les membres des comités de programme et du prix de thèse. Nous remercions en particulier les conférenciers invités Anastasia Ailamaki, Georgia Koutrika et Benjamin Nguyen, pour avoir illuminé la conférence par l'excellence de leurs présentations. Nous sommes également reconnaissants envers nos soutiens qui ont permis d'organiser cette manifestation, en particulière ENS Paris, l'équipe Valda (DI ENS Paris, PSL), l'équipe BD, LIP6 Sorbonne Universités, l'équipe DRUID, IRISA and 26 patent applications in the US and worldwide, and published in more than 90 papers in toptier conferences and journals. Georgia is an ACM Senior Member, IEEE Senior Member, and ACM Distinguished Speaker. Her recent academic activities include : Editor-in-chief for VLDB Journal, PC co-chair for VLDB 2023, Co-EiC of Proceedings of the VLDB (PVLDB) Vol 16, and associate editor for TKDE, SIGMOD2022 and VLDB2022.

Privacy Preserving Contact Tracing : a case of privacy driven data analysis Benjamin Nguyen

Classical contact-tracing is a technique during an epidemy to slow down contamination. Classical contact tracing is organized by medical personnel during an (intrusive) interview with a patient suffering from the disease, in order to trace back all the other people whom the patient was in contact with, in order to informe them of the possibility of contamination.

During the Covid19 pandemic, contact tracing has been pushed to a new level, via automation. However, due to the sensitive nature of the information that is manipulated in order to achieve good tracing, building a privacy preserving solution, while still maintaining the quality of the results proved to be a compelling research challenge. During this presentation, we will present the data management and privacy issues around privacy preserving contact tracing, and discuss in more detail the two main solutions deployed in Europe, the French lead ROBERT (aka StopCovid/TousAntiCovid) proposal, and the Swiss lead DP3T, later adapted by Apple and Google.

Benjamin

Résumés des articles long 1 INTRODUCTION

Detection of "anomalous" samples (records, instances), called anomaly detection, is an important problem in machine learning. It is conceptually related to outlier and novelty detection in several application settings. The anomalous samples may indicate mislabelled data, catastrophic measurements or data entry errors, bugs in data wrangling and preprocessing software, or other interesting phenomena.

Numerous unsupervised algorithms (e.g., IF [4], LOF [1], LODA [7]) to detect anomalies (hereafter detectors) have been proposed. The most advanced ones detect anomalies in a multi-dimensional fashion, simultaneously considering all feature values. Unfortunately, detectors, in general, do not explain why a sample was considered as abnormal, leaving human analysts with no guidance about their root causes, insight to take corrective actions, or remedy their effect.

Several methods for explaining anomalies have been proposed, hereafter explainers. The explanations often take the form of a subset of features called a subspace in the literature. The idea is that by examining only the explaining features suffices to determine whether the sample is an anomaly or not according to the detector.

Existing methods can be categorized to those that provide local explanations (point-based) that pertain to a single sample, or global explanations (a.k.a. set-based) to simultaneously explain all training samples. The latter is important in order to reduce the burden of human analysts to inspect possibly different explanations for each anomaly. We should stress that global explanation is different from clustering as the former's objective is to provide a subspace segregating the anomalous from normal samples. Explainers may be specific to a detection algorithm or detector-agnostic, hence applicable post-hoc to any detection algorithm. As reported by several independent experimental studies, e.g. [2], there is no detector outperforming all others on all possible datasets. Hence, researchers cannot just design a specific explainer for the optimal detector; it may thus be preferable to design optimal agnostic explainers. Explainers may also be categorized as descriptive in the sense that they explain the samples used to train the detector. Explainers that return explanations that generalize to unseen data are predictive ones. The importance of predictive explanations has been recognised in Explainable AI to avoid recomputing explanations on every new batch of data.

Figure 1 illustrates how predictive explanations can be used in data validation pipelines monitoring the data fed to downstream ML models. Given that in real application settings it is difficult or even impossible to label data as anomalous or normal [2], unsupervised detectors are initially used to spot anomalies. Then, a predictive anomaly explainer could be used by human analysts to reveal the root causes of the detected anomalies and decide subsequent corrective actions. It is essentially a surrogate model, trained with a small subset of the original features that serve as explaining feature subspace. Depending on the quality of the approximation of the decision boundary of an unsupervised detector, the surrogate model can be also used to detect anomalies in fresh data, i.e., new batches of data, by completely bypassing the need to rerun the detector.

In this paper, we propose a novel method to produce global, predictive explanations called PROTEUS 1 . PROTEUS is detector agnostic, and can be used to approximate the decision boundary of any detector. We should stress that prior work on detector agnostic explainers like CA-Lasso [6] and SHAP [5] but also detector specific explainers like LODA [7] produce explanations that are only local and descriptive. PROTEUS essentially constructs a reduced-dimensionality, surrogate model that approximates the behavior of a detector with fewer features. Since the detector is labelling the samples as anomalies or not, the problem of finding such a model reduces to a supervised predictive modeling with feature selection problem. In order for the surrogate model to also explain unseen samples, it has to approximate the detector's decision boundary and not simply interpolate the anomalies (overfit) in the training data. To this respect, the

INTRODUCTION

Nowadays, we are witnessing the production of large volumes of continuous or real-time data in many application domains like traffic monitoring, medical monitoring, social networks, weather forecasting, network monitoring, etc. For example, every day around one trillion messages are processed through Uber data analytics infrastructure 1 while more than 500 million tweets are posted on Twitter [6]. Efficient streaming algorithms are needed for analyzing data streams in such applications. In particular, aggregations [12], having the inherent property of summarizing information from data, constitute a fundamental operator to compute real-time statistics in this context. In the streaming setting, aggregations are typically computed over finite subsets of a stream, called windows. In particular, Sliding-Window Aggregation (SWAG) [10,11,14,16] continuously computes a summary of the most recent data items in a given range 𝑟 (aka window size) and using a given slide 𝑠. If the range and slide parameters are given in time units (e.g., seconds), then the sliding window is time-based, otherwise, i.e, if these parameters are given as the number of values, it is count-based. Fig. 1 1 AthenaX: SQL-based streaming analytics platform, https://eng.uber.com/athenax presents an example of computing sum over the count-based sliding window with a range of 10 values and a slide of 2 values.

Stream processing systems (SPSs) [1,4,9,17,19] are ubiquitous for analyzing continuously unbounded data. However, one of the challenges faced by SPSs is to efficiently compute aggregations over sliding windows. This requires the ability of such systems to incrementally aggregate moving data, i.e., inserting new data items and evicting old data items when a window is sliding without recomputing the aggregation from scratch. High throughput and low latency are essential requirements as SPSs are typically designed for real-time applications [7].

Two orthogonal techniques have been proposed to meet such requirements: slicing (aka partial aggregation) [5,8,10,18], and merging (aka incremental final aggregation) [13][14][15][16]. Slicing techniques focus on slicing the windows into smaller subsets, called slices, and then computing partial aggregation over slices, called slice aggregations. The benefit of the slicing technique is that slice aggregations (i.e., partial aggregations over slices) can be shared by different window instances. For example, in Fig. 1, a slice aggregation over a slice of 2 values can be shared by 5 windows. On the basis of a slicing technique, final aggregations over sliding windows are computed by merging slice aggregations, e.g., in Fig. 1, SWAG is computed by merging 5 slice aggregations. During the merging phase, each insertion or eviction is processed over a slice aggregation rather than a value. In modern SPSs, practical sliding windows can be very large [16], thereby making the merging phase non-trivial. To efficiently merge slice aggregation, incremental computation is necessary because an approach that recalculate slice aggregations from scratch (hereafter called Recal) is very inefficient [10,11,14,16].

The difficulty of incremental merging depends on the considered class of aggregations: invertible or non-invertible. An aggregation is invertible if the merging function for its partial aggregations has an inverse function. For example, 𝑠𝑢𝑚 is clearly invertible, because it has the arithmetical subtraction as the inverse function. Similarly, 𝑎𝑣𝑔 and 𝑠𝑡𝑑 are invertible because they use addition as merging function. Partial aggregations of invertible aggregations can be efficiently merged using the subtract-on-evict algorithm [7,15], i.e., maintaining a running sum over a sliding window by subtracting evicted values and adding inserted values. However, this is not the case for non-invertible aggregations, e.g., max, min, and bloom filter, where the subtract-on-evict algorithm cannot be applied at the merging phase. Incremental merging of continuous data in the context of non-invertible aggregations is challenging and requires more sophisticated algorithms (e.g., see [3,[13][14][15][16]). This paper focuses on merging slice aggregations for computing non-invertible aggregations over FIFO sliding windows with an arbitrary range and an arbitrary slide. We propose PBA (Parallel Boundary Aggregator), a novel algorithm that computes incremental aggregations in parallel. PBA groups continuous slices into chunks, and maintains two buffers for each chunk containing, respectively, the cumulative slice aggregations (denoted as 𝑐𝑠𝑎) and the left cumulative slice aggregations (denoted as 𝑙𝑐𝑠) of the chunk's slices. Using such a model, SWAGs can be computed in constant time bounded by 3 for both amortized and worst-case time. Interestingly, the required 𝑐𝑠𝑎 and 𝑙𝑐𝑠 for each window aggregation are completely independent from each other, so the incremental computation of 𝑐𝑠𝑎 and 𝑙𝑐𝑠 can be achieved in parallel. These salient features put PBA ahead of state-of-the-art algorithms in terms of throughput and latency.

In this paper, we make the following main contributions:

• We propose a novel algorithm, PBA, to efficiently compute SWAGs. PBA uses chunks to divide final aggregations of window instances into sub-aggregations that are elements of 𝑐𝑠𝑎 and 𝑙𝑐𝑠 buffers. These two buffers can be computed incrementally and in parallel.

• We analyze the latency caused by SWAG computations with different chunk sizes in PBA, and propose an approach to optimize the chunk size leading to the minimum latency.

• We conduct extensive empirical experiments, using both synthetic and real-world datasets. Our experiments show that PBA behaves very well for average and large sliding windows (e.g., with sizes higher than 1024 values), improving throughput up to 4× against state-of-the-art algorithms while reducing latency. For small-size windows, the results show the superiority of the non-parallel version of PBA (denoted as SBA) that outperforms other algorithms in terms of throughput.

• To show the benefit of our approach in modern streamprocessing frameworks, we implemented PBA on top of Apache Flink [2,4], called FPBA. Our empirical evaluation shows that FPBA scales well as increasing the parallelism of Flink in both local and cluster modes.

All technical details are included in the full version of this paper [20].

ACKNOWLEDGMENTS

Incremental Schema Discovery at Scale for RDF Data Redouane Bouhamoum, Zoubida Kedad and Stéphane Lopes

INTRODUCTION

The Web of data represents a huge information space consisting of an increasing number of interlinked datasets described using the Resource Description Framework (RDF). These datasets contain both the data and the schema describing the data. However, the schema may be incomplete or missing which limits the use of RDF data. Indeed, it is not obvious to explore a dataset without a schema describing its contents.

We have proposed in previous works a schema discovery approach suitable for very large datasets, which relies on a scalable density-based clustering algorithm [1]. However, RDF datasets are subject to frequent evolutions over time, and new instances may be inserted. Due to such evolution, the ability to perform incremental updates on the schema has emerged as a new challenge.

In this work, we propose an incremental schema discovery approach for large RDF datasets. Our contribution is an incremental density-based clustering algorithm for building and updating the clusters that represent the classes of the schema. Our algorithm incrementally updates the classes to keep them consistent with the evolution of the data and ensures providing the same result as a sequential clustering algorithm. In addition, the incremental clustering process is parallelized and implemented using Spark to be efficient on large datasets.

AN INCREMENTAL SCHEMA DISCOVERY APPROACH

We present in this paper an incremental, distributed, density-based clustering algorithm to extract a schema from large and evolving RDF datasets. It allows to keep the schema coherent with the dataset when new entities are added. In order to efficiently manage incrementally growing big datasets, the clustering is restricted to new entities and their neighborhood within the old entities. Clustering new entities and updating the clusters within their neighborhoods ensures that the result is the same as the one provided by the execution of DBSCAN on the global data [3]. Our approach is composed of three main steps described hereafter, and parallelized as illustrated in figure 1.

Data Distribution

Computing the neighborhood of the new entities may require a very high number of comparisons. In our incremental algorithm, we propose to distribute these new entities over the different processes according to the distribution principle introduced in [1], where the dataset is split into subsets called chunks according to the properties of the entities. The intuition behind our distribution method is to group entities sharing some properties into chunks to ensure that all the pairs of similar entities will be detected. This distribution principle may duplicate the entities in several chunks. To optimize the distribution, we do not consider all the properties of the entities and reduce the cost of the comparison process by skipping useless comparisons.

To this aim, we adapt the notion of prefix-filter [2]. The intuition behind this notion is that, in order to be similar, two sets have to share a sufficient number of elements. Thus, We define a dissimilarity threshold for an entity 𝑒 as 𝑑𝑡 𝜖 (𝑒) = |𝑒 | -⌈𝜖 × |𝑒 |⌉ +1, considering 𝜖 as the similarity threshold and 𝑒 as the set of properties of the entity 𝑒. This threshold represents the number of properties to consider while distributing the entities.

The clusters that might be updated after the insertion of entities are those within the neighborhood of the new entities. Therefore, the old entities in the neighborhood of a newly inserted entity have to be identified. In our approach, we distribute old entities that share common properties with the new ones over the generated chunks according to our distribution principle.

Neighborhood Computation

As the chunks contain entities which are likely to be similar, the neighborhood of a new entity is identified by computing the similarity between this new entity and all the other ones in the same chunk. We evaluate the similarity between two entities 𝑒 𝑖 and 𝑒 𝑗 using the Jaccard index [4]. The comparisons are performed within each chunk in parallel, thus speeding up the clustering process. Since the neighborhood of entities can be distributed over chunks, the neighbors discovered in each chunk are consolidated, and the list of neighbors for each entity in the whole dataset is built. We identify the core entities which have a number of neighbors greater or equal to the density parameter 𝑚𝑖𝑛𝑃𝑡𝑠, and from which the clusters will be initiated. In addition, the insertion of new entities changes the neighborhood of old ones. As a consequence to such change, the clusters existing prior to the insertion of the new entities have to be updated.

Generating the New Schema

In order to update the schema, we first modify the clusters locally in the chunks based on the neighborhood of the new entities. After adding the set of entities, existing clusters could be updated and new clusters could be created. Based on the core entities, the following change operations can be performed:

• If the neighborhood of a new entity core 𝑒 ′ contains an old core entity which belongs to an old cluster 𝐶, then 𝑒 ′ is assigned to 𝐶 and 𝐶 is also expanded with entities that are density-reachable from 𝑒 ′ .

• If a core entity 𝑒 has no old core entity in its neighborhood, then a new cluster is created and the entities that are densityreachable from 𝑒 are added to this cluster.

• If the neighborhood of a core entity 𝑒 contains two of more old core entities, which belong to distinct clusters, then these clusters are merged and the resulting cluster is expanded with the entities that are density-reachable from 𝑒.

• If an old core entity has a new entity which is not a core within its neighborhood, then the corresponding new entity is absorbed by the cluster containing this old core entity. These rules are executed in parallel in the different chunks providing local clusters. The final clusters are then built by merging the local clusters which share a common core entity within the newly inserted entities. Finally, the new clusters are added to the old ones to build the new schema.

EXPERIMENTS

In our experiments, we evaluate the efficiency of our incremental clustering algorithm compared to the scalable DBSCAN proposed in [1], and derive the speed-up factor of the incremental approach.

Figure 2 illustrates the ability of our incremental algorithm to cluster massive datasets, such as DBpedia, from which we have extracted more than 1.2 million entities. At each insertion, we have added a set of 100k entities to the initial dataset. Then we have compared the execution time of the incremental algorithm to the scalable DBSCAN when executed on the entire dataset. This evaluation shows that the incremental algorithm overcomes the scalable algorithm in terms of performances. In addition, we can observe that the bigger the dataset, the larger the gap between the execution time of both algorithms, and the higher the gain achieved by the incremental approach.

CONCLUSION

In this work, we have addressed the problem of incremental evolution of the schema of large RDF datasets as new entities are inserted. We have proposed a novel incremental density-based clustering algorithm which builds groups of similar entities by updating the existing clusters or creating new ones according to the neighborhood of the newly inserted entities. The resulting clusters represent the classes of the schema.

As future works, we could explore the ways of enriching the set of classes with the semantic links between them, and providing semantic annotations for each one. Our algorithms could also be extended in order to exploit partially available schema-related declarations to guide the discovery process, which could improve the quality of the resulting schema.

PROBLÉMATIQUE

Comment décider que deux valeurs x et y sont égales ? Cette question, simple en apparence, admet en réalité de nombreuses réponses dépendantes de la manière dont l'égalité est définie. En outre, elle se pose implicitement en base de données quand il s'agit de traiter l'inconsistance [3], les données probabilistes [10], les réponses aux requêtes [1,2,6], l'intégration de données [7] ou encore le design des bases de données [8]. La question de l'égalité est également cruciale pour la qualité des données.

En pratique, seule l'expertise du domaine permet de donner une définition de l'égalité qui soit adaptée aux données et au contexte. Malheureusement, il n'existe pas à notre connaissance de cadre formel permettant aux experts du domaine de déclarer, à un haut niveau d'abstraction, différentes sémantiques pour l'égalité (prenant en compte les erreurs de mesure, les valeurs nulles, etc.). De ce fait, la gestion de l'égalité est laissée aux programmeurs qui doivent prendre en compte ces différentes possibilités dans leur code.

Dans cet article (voir [9]), nous cherchons à palier ce problème. Nous utilisons les treillis pour introduire un cadre permettant de définir différentes versions de l'égalité à un haut niveau d'abstraction. Ensuite, nous étudions les dépendances fonctionnelles à la lumière de ce cadre déclaratif.

CONTRIBUTIONS

D'abord nous introduisons et illustrons le cadre déclaratif général, puis nous résumons les résultats de son application aux dépendances fonctionnelles.

Le contexte associé à un schéma. Considérons un schéma de relation R. Nous attribuons à chaque attribut A de R un contexte (d'attribut) comportant une fonction de comparabilité f A et un treillis de vérité L A . La fonction f A mesure la ressemblance entre les valeurs du domaine de A : elle assigne à chaque paire de valeurs un niveau de similarité représenté par un élément de L A . En particulier, deux valeurs égales au sens strict (mathématique) du terme ont le plus haut niveau de similarité possible, correspondant à l'élément maximal de L A . L'apposition des contextes d'attributs donne naissance au contexte (de schéma) de R, ainsi qu'à sa fonction de comparabilité f R . En comparant deux tuples sur R avec f R , on obtient alors le tuple abstrait qui leur est associé. En pratique, ce contexte devrait être donné par les experts du domaine.

Ensuite, nous introduisons la notion d'interprétation du contexte associé à A. Une interprétation est une application h A qui attribue à chaque élément de L A la valeur 0 ou 1. Cette fonction h A est une sémantique pour l'égalité sur A : deux valeurs u, v du domaine de A sont considérées égales (pour h A ) si h A (f A (x, y)) = 1. Elles sont différentes sinon. Pour représenter au mieux la notion d'égalité, la fonction h A doit être croissante, assigner 1 à l'élément maximal de L A (le plus haut niveau de similarité possible) et 0 à l'élément minimal de L A (le plus faible niveau de similarité). Une interprétation д du contexte associé à R résulte de la combinaison d'interprétations pour chacun des attributs de R. Deux tuples sont alors considérés égaux (pour д) si leurs valeurs attributs à attributs sont considérées égales. Ainsi, une interprétation д est une sémantique possible pour l'égalité sur R.

Dans l'article, nous nous intéressons à des interprétations particulières que nous appelons réalités et réalités fortes. Une réalité est une interprétation qui garantit pour chaque attribut que si deux éléments u et v du treillis de vérité associé sont interprétés à 1, alors u ∧ v est aussi interprété à 1 (∧-homomorphisme). Intuitivement, une réalité préserve l'opération de ET logique : la conjonction de 1 et 1 est à 1. Une réalité est forte si elle respecte aussi l'opération OU : la disjonction de 0 et 0 reste à 0 (homomorphisme).

Example 1. Imaginons que des experts aient fourni des données médicales sur certains patients : leur niveau de triglycéride (en mmol/L), leur sexe (H/F) et leur tour de hanche (en cm). Un extrait de ces données (la relation r ) est présenté dans la Figure 1 De surcroît, les experts ont fourni les fonctions de comparabilités suivantes, pour chacun de ces paramètres : Application aux dépendances fonctionnelles. À l'aide d'un contexte, il est possible de calculer tous les tuples abstaits d'une relation r . Ceux-ci définissent le treillis abstrait L r associé à r , qui peut être représenté par un ensemble d'implications de treillis [4], nommées dépendances fonctionnelles abstraites. Plus précisément, une dépendance fonctionnelle abstraite est une expression u → v où u et v sont des tuples abstraits issus du produit des treillis de vérité du contexte. Le treillis abstrait associé à la relation r de l'Exemple 1 est illustré dans la Figure 3.

f A (x, y) =              g si x = y ou x, y ∈ [0, 2[ gb si x, y ∈ [2, 5[, x y u si (x, y) ou (y, x) ∈ [0, 2[×[2, 5[ b sinon. f B (x, y) = t si x = y d si x y f C (x, y) =          c si x = y null ou x, y ∈ [70, 80] u si x = null ou y = null i sinon.

Les treillis de vérités associés à ces fonctions sont les treillis L

A , L B et L C donnés dans la Figure 1. L'ensemble {{ f A , L A }, { f B , L B }, { f C , L C }}
t 4 = 3.5, F, 76 comparaison avec f R t 2 = 1.5, F, null tuple abstrait g 1 (f R (t 2 , t 4 )) = 0, 1, 0 interprétation g 1 t 2 = t 4 avec g 1 interprétation g 2 g 2 (f R (t 2 , t 4 )) = 1, 1, 1 t 2 = t 4 avec g 2 f R (t 2 , t 4 ) = u, t, u
Une interprétation д du contexte devient ainsi une interprétation du treillis abstrait de r . Il apparaît cependant que le résultat д(L r ) de l'interprétation de L r par д peut préserver la sémantique classique des dépendances fonctionnelles (i.e. être un système de fermeture sur R [5]) ou non. La question suivante s'en suit : quelles sont les interprétations qui garantissent que l'interprétation de n'importe quel treillis abstrait préserve la sémantique des dépendances fonctionnelles ? Nous montrons que ces interprétations sont précisément les réalités. Ensuite, nous étudions plus en détails le lien qui unit treillis abstrait, réalités et dépendances fonctionnelles (dont abstraites). En particulier, nous montrons que si une dépendance fonctionnelle X → A est vraie dans l'interprétation de L r par une réalité д, elle est en fait l'interprétation d'une dépendance fonctionnelle abstraite x → a valide dans L r . Nous prouvons également qu'il existe toujours une réalité qui interprète une dépendance fonctionnelle abstraite x → a valide dans L r en une dépendance fonctionnelle

u, d, u b, d, c f R (t3, t4) = gb, d, c f R (t3, t4) ∧ f R (t1, t2) = gb, d, u f R (t1, t2) = g, t, u u, t, u b, t, u b, t, i b, d, u g, t, c b, d, i u, d, c u, t, c
X → A valide dans д(L r ).
Enfin, en s'inspirant des réponses possibles et certaines [1,2,6], nous étudions la plausibilité d'une dépendance fonctionnelle : existet-il une réalité (forte) dans laquelle la dépendance fonctionnelle goldMEDAL: A Data Lake Generic Metadata Model

INTRODUCTION

The rise of big data has revolutionized data exploitation practices and led to the emergence of new concepts. Among them, data lakes are large heterogeneous data repositories that can be analyzed by various methods [1].

An efficient data lake requires a metadata system that addresses the many problems arising when dealing with big data. The study of data lake metadata models is currently an active research topic and many proposals have been made [2][3][4].

However, existing metadata models (including the most recent cited above) are either tailored for a specific use case or insufficiently generic to manage different types of data lakes. To address this issue, we propose goldMEDAL, a generalization of MEDAL, the MEtadata model for DAta Lakes [4]. This new metadata model is specified through a classical three-level modeling process, i.e., conceptual, logical and physical.

GOLDMEDAL CONCEPTUAL MODEL

goldMEDAL's conceptual conceptual model features four main concepts: data entity, grouping, link and process (Figure 1).

• Data entities are the basic units of our metadata model.

They are flexible in terms of data granularity. For example, a data entity can represent a spreadsheet file, a textual or semistructured document, an image, a database table, a tuple or • A grouping is a set of groups, with a group bringing together data entities based on common properties. For example, the raw and preprocessed data zones common in data lake architectures are the groups of a zone grouping. Another example is a grouping of textual documents according to the language of writing.

• Links are used to associate either data entities with each other or groups of data entities with each other. They can be oriented or not. They allow the expression of, e.g., simple similarity links between data entities or hierarchies between groups. For example, a temporal hierarchy month → quarter would have the months of January, February and March linked to the first quarter of a given year.

• A process refers to any transformation applied to a set of data entities that produces a new set of data entities.

GOLDMEDAL PHYSICAL MODELS

At the physical level, we implemented goldMEDAL into three usecases/data lakes dedicated to social housing, management sciences and archaeology, respectively. Metadata are managed with dedicated tools (the Neo4J1 graph database management system or the Apache Atlas2 data governance and metadata management) or a combination of such tools, i.e., Neo4J, the MongoDB3 documentoriented database management system (for handling non-atomic metadata) and Elasticsearch4 search engine (for indexing textual documents).

CONCLUSION

Through the three physical models implemented with goldMEDAL, we demonstrated the feasibility and flexibility of our metadata model. Moreover, we demonstrate that goldMEDAL's concepts generalize those of the most recent models from the literature [2][3][4], which makes of goldMEDAL the most generic metadata model for data lakes as of today.

Another particularity of goldMEDAL is the explicit possibility of data lineage tracing with the concept of process. Thus, goldMEDAL can manage the dynamics of data, while the most recent metadata model, HANDLE [2], does not natively support it.

Future research and open issues include the "industrialization" of data lakes, i.e., providing a software layer, connected to the metadata system, which allows non-data or non-computer scientists to transform and analyze their own data in autonomy.

Furthermore, exploiting a data lake and its metadata system may contribute to open data and open science. A well-designed data lake should indeed readily enforce the four FAIR principles 5 . Justifications are minimal subsets of an ontology that entail a given conclusion. The interest for justification comes from the conciseness of the explanation it provides for a given conclusion. Computing justifications has been widely explored for different tasks, for instance for debugging ontologies [1,5,7] and computing ontology modules [4]. For a given conclusion, there may exist more than one justification. Extracting one justification can be easy for tractable ontologies, such as EL + [11]. For instance, we can find a justification by deleting unnecessary axioms one-by-one. However, computing all justifications is complicated and reveals itself to be a challenging problem.

A Hyper-graph Approach for Computing EL + -Ontology Justifications

There are mainly two different approaches [11] to compute "all" justifications, the black-box approach and the glass-box approach. The black-box approach [7] relies only on a reasoner and as such can be used for ontologies in any existing Description Logics. For example, a simple (naive) black-box approach would check all the subsets of the ontology using an existing reasoner and then filter the subset-minimal ones (i.e., justifications). Many advanced and optimized black-box algorithms have been proposed since 2007 [6]. Meanwhile, the glass-box approaches have achieved better performances over certain specific ontology languages (such as EL + -ontology) by going deep into the reasoning process. Among them, the class of SAT-based methods [1-3, 9, 10] performs the best. The main idea developed by SAT-based methods is to trace, in a first step, a complete set of inference rules (complete set for short) that contribute to the derivation of a given conclusion, and then, in a second step, to use SAT-based resolution tools to extract all justifications from these inference rules.

In this paper, we improve the state-of-the-art SAT-based approach PULi [9] based on a representation of EL + -ontologies by hyper-graphs. The main idea is to reformulate justifications as special paths called H-paths in the hyper-graph associated with a given ontology. The advantage of this setting is that, most of the time, it reduces the number of the inference rules applied to derive a given conclusion, and this accelerates the enumeration of justifications relying on these inference rules. We validate our approach by running real-world ontology experiments. Our hyper-graph based approach outperforms PULi [9], the state of the art algorithm. For instance, for the ontology galen7, for which PULi performed the worst, our method generated ten times fewer inference rules on average and accelerated PULi up to three times. [12]. As for regular graphs, a simple-path from nodes 𝑁 𝑋 to 𝑁 𝑌 in a hyper-graph is a sequence of edges:

HYPER-GRAPH OF ONTOLOGY

𝑒 0 =(𝑆 0 1 , 𝑆 0 2 ), 𝑒 1 =(𝑆 1 1 , 𝑆 1 2 ), • • • , 𝑒 𝑛 =(𝑆 𝑛 1 , 𝑆 𝑛 2 ) (1)
where 𝑁 𝑋 ∈𝑆 0 1 , 𝑁 𝑌 ∈𝑆 𝑛 2 and 𝑆 𝑖-1 2 ∩𝑆 𝑖 1 ≠∅, 1≤𝑖≤𝑛. For the sake of simplicity, next we regard all paths as sets of edges. Then the H-path is defined inductively by using simple-paths and the construction structures as illustrated in Figure 2.

The main result of our study states that the existence of H-path and the ontology entailment match.

Theorem 1. For any EL + ontology O, O|=𝑋 ⊑ 𝑌 iff. there exists a H-path from 𝑁 𝑋 to 𝑁 𝑌 on G O . Now, we can transpose the problem of finding justification to that of finding minimal H-paths. The algorithm we derive to find minimal H-paths is called minH.

EVALUATION

We compare minH with PULi [9] on four different ontologies: goplus, galen7, snomedct 2015 and snomedct 2021. Both methods compute all justifications based on resolution but with different sets of inference rules generated in different ways. The inference rules of PULi are generated by the ELK reasoner [8] and denoted by elk. We call U the extracted subset of clauses based on our H-rules. To analyze the performance of our setting, we make the following two measures:

• Size of Inference Rules We say that a conclusion 𝐴 ⊑ 𝐵 is trivial iff all minimal H-paths from 𝑁 𝐴 to 𝑁 𝐵 are simplepaths, non-trivial otherwise. The size of inference rules are summarized bellow. It shows that on all four ontologies, U is much smaller than elk on average. • Time Cost of Enumerating Justifications Part of comparisons are illustrated in Figure 3. It shows that minH performs better than PULi, in most of the cases. To address that, we propose COVER_𝛼, a heuristic algorithm that builds on 𝛼-investing [1], an adaptive sequential method that controls mFDR, the ratio of the expected number of false rejections to the expected number of rejections. The key idea of COVER_𝛼 is to invest more significance, referred to as 𝛼-wealth, on candidates with the highest coverage. This decision relies on tuning a hyper parameter 𝜆 whose value determines the speed at which the 𝛼-wealth is consumed, and needs to be explored empirically. COVER_𝛼 is efficient and runs in 𝑂 (𝑚 • 𝑛), where 𝑛 is the number of desired results and 𝑚 is the number of candidates.

RELATED WORK

Our work is closely related to multiple hypothesis testing in which a large number of data samples are encountered and need to be considered in testing a given hypothesis. Similarly to existing work on combining data mining, data exploration or machine learning with hypothesis testing, we propose to leverage hypothesis test correction methods to control the risk of false discoveries. Existing work on customer segment discovery [2,3] combines the computational power of pattern mining with multiple hypothesis testing to find meaningful patterns in the data.

PROBLEM

Given a set of users U and a set of items

, 𝐷) | |𝐶 | = 𝑛 subject to ∀𝑐 ∈ 𝐶 c.pval ≤ 𝜃 (1)
Our problem formulation is generic and aims to accommodate existing significance adjustment procedures by adapting the definition of the significance threshold 𝜃 as follows:

• For Bonferroni (BN): 𝜃 = 𝛼 𝑚 • For Benjamini-Yekutieli (BY): 𝜃 = 𝛼×𝑘 𝑚 𝑚 𝑖=1 1/𝑖 -1
, where

𝑘 = 𝑚𝑎𝑥 𝑖 : 𝑝 𝑖 ≤ 𝛼×𝑖 𝑚× 𝑚 𝑖=1 1/𝑖 , 𝑝 𝑖 the 𝑖 𝑡ℎ smallest p-value.
where 𝑚 is the number of groups in Candidates and 𝛼 is the significance level usually set to 0.05

ALGORITHMS

To solve CoverTest, we first propose COVER_G (Algorithm 1), a greedy algorithm that scans candidate groups and at each step

3 𝐿 = 𝑆𝑜𝑟𝑡𝑏𝑦𝑝𝑣𝑎𝑙 (Candidates) 4 𝐶 ← ∅ 5 𝑚 ← |𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠 | 6 𝑘 = argmax 0≤ 𝑗 ≤𝑚 𝐿 [ 𝑗 ] ≤ 𝛼 ×𝑗 𝑚 𝑚 𝑖=1
Output: 𝐶 1 Candidates ← GenerateCandidates(𝑅, 𝐷) 2 𝑊 (0) ← 𝛼 3 𝛼 * = 𝑊 (0) 𝜆+𝑊 (0) 4 𝐶 ← ∅ 5 𝑗 ← 1 6 while 𝑊 ( 𝑗 -1) > 0 and |𝐶 | ≤ 𝑛 do 7 𝑐 * = argmax 𝑐∈Candidates 𝑐𝑜𝑣𝑒𝑟 (𝐶 ∪ {𝑐 }, 𝐷) 8 𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠 ← 𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠 \ {𝑐 * } 9 𝛼 𝑗 = 𝛼 * ( |𝑐𝑜𝑣𝑒𝑟 (𝑐 * ,𝐷 ) | |𝐷 | ) 1/2 10 if 𝑊 ( 𝑗 -1) - 𝛼 𝑗 1-𝛼 𝑗 ≥ 0 then 11 if 𝑐 * .𝑝𝑣𝑎𝑙 ≤ 𝛼 𝑗 then 12 𝑊 ( 𝑗) ← 𝑊 ( 𝑗 -1) + 𝛼 13 𝐶 ← 𝐶 ∪ {𝑐 * } 14 else 15 𝑊 ( 𝑗) ← 𝑊 ( 𝑗 -1) - 𝛼 𝑗 1-𝛼 𝑗 16 𝑗 ← 𝑗 + 1 17 return C
selects the candidate with a maximal coverage. The Benjamini-Yekutieli significance adjustment procedure is used to accept or not the selected candidate if its p-value is under the Benjamini-Yekutieli threshold.

We propose a more efficient algorithm COVER_𝛼, that relies on 𝛼-investing [4]. The key idea is to re-adjust the quantities of the 𝛼-wealth that are invested according to the coverage of each selected candidate.

EXPERIMENTS

Datasets. We report results on the MovieLens'1M dataset. Similar results were observed on other datasets: Yelp, TAFENG, and BookCrossing 1 .

Algorithm variants. We compare COVER_G and COVER_𝛼 against the traditional correction methods (referred to as TRAD). Results. We examine simultaneously the evolution of the cumulative coverage and p-values. Results are depicted in Figure 1. The graph clearly shows that COVER_𝛼 200 performs closely to COVER_G_BY and reaches full coverage by iteration 22. We also notice that COVER_𝛼 20 and COVER_𝛼 50 invest most of the 𝛼-wealth in testing insignificant hypotheses. As a result, COVER_𝛼 50 is no longer capable to add new candidates after its iteration 7.

We study the evolution of response time as a function of number of results 𝑛 (Figure 2). It shows that COVER_𝛼 200 clearly outperforms COVER_G and TRAD. Unlike TRAD and COVER_G, COVER_𝛼 computes p-values only for candidates with the highest coverage.

Our experiments demonstrate the importance of optimizing coverage in large scale group testing. Our code and complete results are available on our anonymized Github repository. We consider the problem of automatically identifying the k most interesting aggregate queries that we can evaluate on an RDF graph, given an integer k and a user-specified interestingness function. Aggregate queries are routinely used to learn insights from relational data warehouses, and some prior research has addressed the problem of automatically recommending interesting aggregate queries. However, the RDF setting presents several differences from the traditional data warehouse setting:

(1) In an RDF graph, we are not given but we must identify the facts, dimensions, and measures that compose aggregate queries; (2) Classical relational OLAP algorithms for efficiently evaluating multiple aggregates cannot handle the presence of multi-valued dimensions for a given fact; such dimensions are quite frequently found in RDF data facts and may have zero, one, or more values for dimensions.

To address these challenges, we devise Spade, an extensible endto-end framework that enables the identification and evaluation of interesting aggregates based on MVDCube, our new RDF-compatible one-pass algorithm for efficiently evaluating a lattice of aggregates, and a novel early-stop technique (with probabilistic guarantees) that prunes uninteresting aggregates and, as a result, reduces the aggregate evaluation cost. Our experiments demonstrate the merit of our approach. Using both real and synthetic graphs, we show the ability of our framework to find interesting aggregates in a large search space, the efficiency of our algorithms (with up to 2.9× speedup over a similar pipeline based on existing algorithms), and scalability as the data size and complexity grow. This work has originally appeared in SIGMOD 2021 [1]. In this paper, we take a major step towards filling this gap by proposing HADAD, an extensible lightweight approach for optimizing hybrid complex analytics queries, based on a common abstraction that facilitates unified reasoning: a relational model endowed with integrity constraints. Our solution can be naturally and portably applied on top of pure LA and hybrid RA-LA platforms without modifying their internals. An extensive empirical evaluation shows that HADAD yields significant performance gains on diverse workloads, ranging from LA-centered to hybrid.

The paper appeared in ACM SIGMOD 2021 [1]; it is available online at https://arxiv.org/abs/2103.12317.

RÉSUMÉ

Les approches existantes pour le calcul de similitude entre séries temporelles sont au coeur de nombreuses tâches d'analyse de données. Étant donné les volumes de données considérés, ou simplement le besoin de les traiter rapidement, ces approches s'appuient souvent sur des représentations alternatives, plus courtes, qui résument les séries d'origine avec une perte d'information acceptable. Les comparaisons de séries temporelles qui se basent sur ces représentations sont alors approximatives, ce qui fait de la précision un enjeu majeur. Nous présentons et évaluons expérimentalement ASAX, une nouvelle approche pour la segmentation de séries temporelles avant qu'elles soient transformées en représentations symboliques. ASAX réduit de manière significative la perte d'information due aux fractionnements dans les différentes étapes du calcul de la représentation. Nous fournissons des garanties théoriques sur la borne inférieure des mesures de similitude entre séries temporelles, et nos expériences illustrent l'intérêt de notre méthode sur l'état de l'art, en particulier avec un gain de précision significatif.

Cardinality Queries over DL-Lite Ontologies (Extended abstract)

A major topic in ontology-mediated query answering (OMQA) research has been to understand the complexity of OMQA and identify tractable settings [6,11,12]. Nowadays, for the most commonly considered query language, namely, conjunctive queries (CQs), we have an almost complete picture of the complexity landscape for ontologies formulated in a wide range of different description logics (DLs) [2] and rule-based languages [3,7]. In particular, it has been shown that CQ answering is tractable in data complexity for ontologies expressed in the most commonly considered dialects of the DL-Lite family [1,9], which are often employed in OMQA. A crucial property of such DL-Lite dialects and other Horn DLs is that they admit a canonical model, which is a single (possibly infinite) model that, by virtue of being homomorphically embeddable into every model, is guaranteed to give the correct answers to all CQs.

While CQs are a natural and well-studied class of queries, there are many other relevant forms of database queries that could be potentially be employed in OMQA. In the present work, our focus will be on counting queries, which together with other forms of aggregate queries, are widely used for data analysis, yet still not well understood in the context of OMQA. A natural way to equip CQs with counting is to count the number of distinct query matches for each answer. As the count value may differ between models, [10] advocated a form of certain answer semantics that considers lower and upper bounds on the count value across different models. Their work provided the first investigation of the complexity of answering counting CQs in the presence of ontologies, revealing such queries to be much more challenging to handle than plain CQs: coNP-complete in data complexity for the well-known DL-Lite 𝑐𝑜𝑟𝑒 and DL-Lite H 𝑐𝑜𝑟𝑒 dialects. A recent work by [4] refined and generalized the complexity results from [10] to a wider class of counting queries and identified a restricted scenario with very low (TC 0complete) data complexity: rooted CQs coupled with DL-Lite 𝑐𝑜𝑟𝑒 ontologies. A similar tractability result for connected rooted CQs was proven independently by [8], who also initiated a study of the impact of other restrictions on query shape and developed the first query rewriting procedure for counting CQs. Notably, both the aforementioned TC 0 result and the rewriting procedure crucially relied upon showing that the canonical model gives the right answers under the considered restrictions.

While recent studies have improved our understanding of the complexity of counting CQs, there nevertheless remain many unanswered questions. In this work, we focus on Boolean atomic counting queries of the form ∃𝑧.A(𝑧) and ∃𝑧 1 , 𝑧 2 .R(𝑧 1 , 𝑧 2 ), which we term cardinality queries as they correspond to the natural task of determining (bounds on) the cardinality of a given concept or role name. The data complexity of answering such basic counting queries remains completely open for DL-Lite 𝑐𝑜𝑟𝑒 ontologies, whilst for DL-Lite H 𝑐𝑜𝑟𝑒 , the problem is known to be P-hard and in coNP [8]. The main results of our investigation are displayed in Table 1. We show that when ontologies are expressed in DL-Lite 𝑐𝑜𝑟𝑒 , cardinality query answering is tractable in data complexity and enjoys the lowest possible complexity (TC 0 -complete). For cardinality queries based upon a concept atom, TC 0 membership holds even for the fragment of DL-Lite H 𝑐𝑜𝑟𝑒 obtained by disallowing negative role inclusions. By contrast, for role cardinality queries, we show that coNP-hard situations arise in DL-Lite H 𝑝𝑜𝑠 , which allows only positive concept and role inclusions. In fact, we obtain a complete data complexity classification for DL-Lite H 𝑝𝑜𝑠 , showing that every ontology-mediated query is either TC 0 -complete, coNP-complete, or is in P and logspace-equivalent to the complement of Perfect Matching (whose precise complexity is a longstanding open problem). The preceding classification does not extend to DL-Lite H 𝑐𝑜𝑟𝑒 : we identify new sources of coNP-hardness and further exhibit Lcomplete cases. We find it intriguing that such complex behaviour arises in what appears at first glance to be a simple OMQA setting. Moreover, in all of the tractable cases we identify, the canonical model may not yield the minimum cardinality, and query answering involves solving non-trivial optimization problems. This led us to devise an entirely new approach based upon exploring a space of strategies to find the optimal way of merging witnesses for existential axioms.

Concept

Role 3 , etc. A platform allows employers to post tasks, that are then realized by workers hired from the crowd in exchange for some incentives [3,19]. Common tasks include image annotation, surveys, classification, recommendation, sentiment analysis, etc. [7].

DL-Lite 𝑐𝑜𝑟𝑒 TC 0 -c TC 0 -c DL-Lite H 𝑝𝑜𝑠 TC 0 -c † TC 0 -c | co-PM-c | coNP-c DL-Lite H 𝑐𝑜𝑟𝑒 TC 0 -c | L-c TC 0 -c | L-c | coNP-c | ? | co-PM-c | coNP-c | ?
The existing platforms support simple, repetitive and independent micro-tasks which require a few minutes to an hour to complete. However, many real-world problems are not simple micro-tasks, but rather complex orchestrations of dependent tasks, that process input data and collect human expertize. Existing platforms provide interfaces to post micro-tasks to a crowd, but cannot handle complex tasks. The next stage of crowdsourcing is to build systems to specify and execute complex tasks over existing crowd platforms. A natural solution is to use workflows, i.e., orchestrations of phases that exchange data to achieve a final objective. Figure 1 is an example of complex workflow depicting the image annotation process on SPIPOLL [5], a platform to survey populations of pollinating insects. Contributors take pictures of insects that are then classified by crowdworkers. Pictures are grouped in a dataset 𝐷 𝑖𝑛 , input to node 𝑝 0 . 𝐷 𝑖𝑛 is filtered to eliminate bad pictures (fuzzy, blurred,...) in phase 𝑝 0 . The remaining pictures are sent to workers who try to classify them. If classification is too difficult, the image is sent to an expert. Initial classification is represented by phase 𝑝 1 in the workflow, and expert classification by 𝑝 2 . Pictures that were discarded, classified easily or studied by experts are then assembled in a result dataset 𝐷 𝑜𝑢𝑡 in phase 𝑝 𝑓 , to do statistics on insect populations.

Workflows alone are not sufficient to crowdsource complex tasks. Many data-centric applications come with budget and quality constraints: As human workers are prone to errors, one has to hire several workers to aggregate a final answer with sufficient confidence. An unlimited budget allows hiring large pools of workers to assemble reliable answers for each micro-task, but in general, a client for a complex task has a limited budget. This forces to replicate micro-tasks in an optimal way to achieve the best possible quality, but without exhausting the given budget. The objective is hence to obtain a reliable result, forged through a complex orchestration, at a reasonable cost.

Several works consider data centric models, deployment on crowdsourcing platforms, and aggregation techniques to improve data quality (see [11] for a more complete bibliography). First, coordination of tasks has been considered in languages such as BPMN

Expert

𝑝 𝑓 𝐷 𝐴𝑛𝑛𝑜𝑡𝑎𝑡𝑒𝑑 𝐷 Figure 1: A workflow from SPIPOLL [18], BPEL [17], or workflow nets [START_REF] Van Der Aalst | Soundness of workflow nets: classification, decidability, and analysis[END_REF], a variant of Petri nets dedicated to business processes. They allow parallel or sequential execution of tasks, fork and join operations to create or merge a finite number of parallel threads. Some works propose empirical solutions for complex data acquisition, mainly at the level of microtasks [7,15]. Crowdforge uses Map-Reduce techniques to solve complex tasks [13]. Turkit [16] builds on an imperative language, that allows for repeated calls to services provided by a crowdsourcing platform. Turkomatic [14] implements a Price, Divide and Solve loop, that asks crowd workers to split task into orchestrations of subtasks, and repeats this operation up to the level of micro-tasks.

In this work, we assemble answers returned by workers with socalled aggregation techniques. The simplest aggregation is majority voting (MV), a mechanism that considers the most returned answer as ground truth. MV can be improved by giving more weight to competent workers. Other approaches use Expectation Maximization (EM), and consider workers competences to synthesize the most probable correct answer. Competences are expressed in terms of accuracy (ratio of correct answers) or in terms of recall and specificity (that considers correct classification for each possible type of answer). It is usually admitted [START_REF] Zheng | Truth inference in crowdsourcing: Is the problem solved?[END_REF] that recall and specificity give a finer picture of worker's competence than accuracy. Zencrowd [6] uses EM to aggregate answers, and defines competences via accuracy. Workers accuracy and ground truth are hidden variables that must be discovered in order to minimize the deviations between workers answers and aggregated conclusion. D&S [4] uses EM to synthesize answers that minimize error rates from a set of patient records. It considers recall and specificity, but not the difficulty of tasks. [12] proposes an algorithm to assign tasks to workers, synthesize answers, and reduce the cost of crowdsourcing. It assumes that all tasks have the same difficulty, and that workers reliability is a static probability to return a correct value (i.e., the ground truth) that applies to all types of tasks. EM is used by [20] to discover recall and specificity of workers, discover the best experts, and estimate the ground truth. Most of the works cited above consider expertise of workers but do not address tasks difficulty. Approaches such as GLAD [START_REF] Whitehill | Whose vote should count more: Optimal integration of labels from labelers of unknown expertise[END_REF] or [2] also estimate tasks difficulty to improve quality of answers aggregation on a single batch of Boolean tagging tasks.

A few papers on data aggregation focus on costs optimization. CrowdBudget [START_REF] Tran-Thanh | Efficient budget allocation with accuracy guarantees for crowdsourcing classification tasks[END_REF] is an approach that divides a budget 𝐵 among 𝐾 existing tasks to replicate them and then aggregate answers with MV. Crowdinc [21] is an EM-based aggregation technique that considers task difficulty, recall and specificity of workers to realize a single batch of micro tasks with a good trade-off between costs and Conference'17, July 2017, Washington, DC, USA Loïc Hélouët, Zoltan Miklos, Rituraj Singh data quality. It computes accuracy of an aggregation, and launches new tasks dynamically. Some works consider deployment of tasks, i.e., synthesis of strategies to hire workers and parallelize realization of batches of tasks. The objective is to improve costs and latency, i.e., the time needed to treat a complete batch with an optimal deployment. CLAMSHELL [10] focuses on latency improvement. It affects workers to batches of tagging tasks and detects staggers. To speed up tasks completion, some batches are replicated. Pools are assembled and maintained by rewarding workers for waiting. This approach improves latency, but increases costs. [8] proposes to compute the best static deployment policies in order to achieve an optimal utility (i.e., a weighted sum of overall cost and accuracy) using sequencing or parallelization of tasks. This approach uses a costly exhaustive search which limits the size of deployment problems that can be considered. [START_REF] Wei | Recommending deployment strategies for collaborative tasks[END_REF] is a recommendation technique for deployments, that allows parallelization of tasks, sequential composition, and use of machines to solve open tasks such as translation or text writing. This approach builds on optimization techniques to find deployments that reduces latency and improves quality of data.

In this work we propose a solution for the efficient realization of complex tasks. We use a workflow model to orchestrate complex tasks, replicate/distribute them and aggregate the returned results before passing the forged dataset to the next tasks. We extend the complex workflow model of [1], and use the aggregation technique of Crowdinc [21] to forge reliable answers. Our workflow model orchestrates tasks and work distribution according to a dynamic policy that considers confidence in aggregated data and the cost to increase this confidence. A workflow can be seen as an orchestration of phases, where the goal of each phase is to tag records from its input dataset. The output of a phase is used as input for the next ones in the workflow. A complex task terminates when the last of its phases has completed its tagging. For simplicity, we consider simple Boolean tagging tasks that associate a tag in {0, 1} to every record in a dataset. Each tagging task on each record is performed by several workers to reduce errors, and the answers are assembled using an aggregation technique. We assume that workers are uniformly paid. For each record, one of the possible answers (the ground truth) is correct, and an aggregated answer is considered as reliable if its probability to be the ground truth (computed with aggregation) is high. Hiring more workers to tag records increases the reliability of the aggregated answer. The overall challenge is hence to realize a workflow within a given budget 𝐵 0 , while guaranteeing that the final dataset forged during the last phase of the workflow has a high probability to be the ground truth.

Design choices influence realization and quality of workflows realization. First, the chosen aggregation technique influences the quality of the final results. Furthermore, the mechanisms used to hire workers impacts costs and accuracy of answers. The simplest way to replicate micro-tasks is static execution, i.e., affect an identical fixed number of workers to each micro-task in the orchestration without exceeding budget 𝐵 0 . On the other hand, one can allocate workers to tasks dynamically. One can wait in each phase to achieve a sufficient reliability of answers for all records of the input before forwarding data. This is called a synchronous execution of a workflow. Last, one can eagerly forward records with reliable tags to the next phases without waiting for the total completion of a phase. This is called an asynchronous execution.

We then study execution strategies for complex workflows in different contexts. We consider several types of workflows, different aggregation mechanisms (namely Majority Voting (MV) and Expectation Maximization (EM) [9]), several distributions of data, difficulty of tasks and workers expertize. We evaluate the cost and accuracy of workflows execution in these contexts under static, synchronous and asynchronous assignment of workers to tasks. Unsurprisingly, dynamic distribution of work saves costs in all cases. A more surprising result is that synchronous realization of complex tasks is in general more efficient than asynchronous realization. Nowadays, those streaming systems handle events with a lifespan, such as phone calls, as points in time. They also mainly assume streams with no delay. Both spanning events and out-of-order events undoubtedly yield to noisy aggregates.

Ultimately, multi-ACQs requires near real-time processing and is prone to duplicate computation of aggregates in every query due to overlapping and containment of windows. It then gives the opportunity to save execution cost by sharing sub-aggregates through slicing techniques.

In this communication, we develop an engine for Aggregate Continuous Query (ACQ), which is able to (i) incorporate lifespan to provide exact aggregate computation, (ii) properly manage outof-order events, and (iii) follow a cost-based policy that elaborates at run-time the most efficient query execution plan of multiple ACQs. The query engine is supported by data structures dedicated to spanning and out-order events and a hybrid sharing schema that aggressively saves computation cost among multiple queries. A lot of experiments have been conducted to show the efficiency of the approach in a large variety of settings and stream profiles.

SLICING TECHNIQUE

Up to now, shared execution of ACQs followed two distinct paths: pooling or feeding. Both approaches are based on the slicing technique, which subdivides the windows into non-overlapping time ranges. Each slice then incorporates events in the form of a single partial aggregate. At window release those partial aggregates are combined to form a final aggregate. For a single ACQ, size of the slices is driven by the ACQ's parameters: the range defining window size and the step representing the window sliding frequency.

POOL SHARING

The pooling approach focuses on sharing a common slice set among several ACQs. It requires to create fine-grained slices to fit each and every ACQ. At any time, the system maintains a set of slices that cover all the ongoing windows, as shown in Figure 1, with an obvious slice width of 10 on the {a, b, c} example. Such an approach allows reducing insertion cost since only one insertion per pool of ACQs is needed, instead of one insertion per ACQ, but it also increases release cost as slices are smaller. The straightforward way of sharing slices is to consider all the ACQs at once, and then build one single slice set. However, if the ACQ steps do not match, it can drastically increase the number of slices required to compute the aggregates. To mitigate that drawback, it is possible to partition the ACQs set into pools of queries. Each pool of ACQs shares a common slice set, while there is no sharing among pools.

Using spanning and out-of-order events in such a pooling configuration is possible, it only requires to insert in several slices for spanning events (as one event may now span over multiple slices), and to scan past slices for out-of-order events. However, without any adaptation, characteristics of such events may also induce errors in results. Indeed, spanning events must be finished in order to release the window. Hence, we add a Time-to-Postpone (TTP) parameter which delays the window release by a fixed amount of time. This TTP is a property of an ACQ, which allows the user to fine tune the delay of each query. For example, one would have a BDA '21, October 25-28, 2021, Suzanne and Raschia and Martinez small TTP for small range ACQs, while a larger TTP is acceptable for longer ranges.

FEED SHARING

The feeding approach is based on the idea that in many real-life examples, sliding window queries are not completely unrelated to each other and one ACQ answer might benefit to another ACQ. For example, the aggregates of the sliding window (15 min, 5 min) may be reused by the sliding window (1 hour, 15 min). Thus feed sharing allows feeding a slice set dedicated to an ACQ from the partial results of another slice set, as shown in Figure 2. The main idea is to reduce the number of insertions as the subscriber slice sets Γ b and Γ c receive a few slices from the publisher Γ a rather than the whole event stream. While this idea is quite simple, its application with spanning and out-of-order events needs to be handled with care. Firstly, insertion in a feeding setting with non-delayed point events is always done in the first slice set of the feeding chain. With spanning and out-oforder events, insertion might, however, continue after the first slice set to active subscribing slice sets. Secondly, at window release, slices read will depend on the subscriptions made by a slice set, as an ACQ might read slices only in its slice set, or also in the feeding slice sets.

HYBRID SHARING

Pooling and feeding strategies can cohabit such that slice sets are shared among multiple ACQs and subscribe to other slice sets, as a straightforward extension from feeding. An example of such sharing is shown in Figure 3. However, not all combinations are consistent. For two slice sets to be joined they need not to break the subscription chain already in place, and for one slice set to subscribe to another one all its slice bounds must be marked in the feeding slice set.

COST ESTIMATION

In order to decide for the best partition, i.e., pooling schema, of the ACQs combined with a relevant feeding schema, one needs to elaborate a cost function that estimates the number of aggregation operations of a specific distribution.

This cost is composed of three parts: insertion, release and shift cost. Insertion cost depends on event size and input rate of the stream. It uses those parameters and the query plan to identify how many slices are used for event insertion per time unit. Release cost uses the range and TTP of the ACQs to count the number of slices read at window release. Finally, the shift cost solely depends on the query plan generated to estimate the number of slices which will be transferred to subscribers at each time unit.

Figure 4 shows a toy example of execution plans given for three queries with different optimization strategies: no-sharing, poolsharing, feed sharing and the hybrid pool-feed policy. Cost values are given by our cost estimation measure. It also shows promises for the hybrid technique as it exhibits the lowest cost. As exhaustive search for the best query plan is not possible for medium to large workloads, our system uses a greedy algorithm which starts with all ACQs separated in their own slice set. Then the algorithm tests all the pooling and feeding possibilities between two slice sets and applies the best one. This procedure is done recursively until no option improves the overall cost.

EXPERIMENTS

We validate the efficiency of our approach with a set of experiments. In those experiments, we demonstrate the validity of our cost estimation with increasing event size. We also show that under varying settings, our hybrid approach is the most relevant one and provides results better than pooling or feeding approaches.

CONCLUSION

In this paper we study multi-ACQ optimization and propose slicing schemes to build efficient query plans in order to leverage shared processing of ACQs. Novelty of that line of work has two dimensions: (i) the assumptions about the data stream: it deals with spanning events and it allows for delays, and (ii) the fully fledged cost measure under those assumptions. Our technique proposes a hybrid schema that supports both pool and feed schemes and adapts to almost any kind of workload.

Évaluez l'Existence d'une Fonction dans votre Jeu de Données avec l'Indicateur 𝑔 3 Pierre Faure--Giovagnoli 1,2

RÉSUMÉ

La prise en compte de la connaissance métier dans l'IA est un problème connu, surtout de nos jours où d'énormes quantités de données sont collectées dans l'espoir d'offrir de nouvelles perspectives de valorisation. Considérons le scénario suivant : soit 𝐷 (𝑦, 𝑥 1 , . . . , 𝑥 𝑛 ) un jeu de données, Alice une experte en science des données, Bob un expert du domaine et 𝑦 = 𝑓 (𝑥 1 , . . . , 𝑥 𝑛 ) une fonction connue par Bob grâce à sa connaissance du métier. Nous nous intéressons aux questions suivantes, simples mais cruciales pour Alice : comment définir la satisfaction de f dans D ? Quelle est la difficulté de mesurer cette satisfaction ? Il s'avère que ces problèmes sont liés aux dépendances fonctionnelles (DFs) et surtout aux mesures de DFs permettant de quantifier leur satisfaction dans un jeu de données tel que l'indicateur 𝑔 3 .

Dans cet article, nous étudions le calcul de 𝑔 3 avec des DFs strictes et une large classe de DFs non-strictes remplaçant l'égalité stricte par des prédicats plus flexibles. Si le calcul de 𝑔 3 avec des DFs strictes peut-être réalisé en temps polynomial, il s'avère être NP-Hard pour les DFs non-strictes. Ainsi, nous proposons différentes solutions exactes et approximées pour le calcul de 𝑔 3 pour les deux types de DFs. Tout d'abord, pour les très grands jeux de données, nous proposons des solutions basées sur de l'échantillonnage aléatoire, uniforme et stratifié, pour les DFs strictes. Nous présentons également des algorithmes d'approximation et l'adaptation des progrès récents dans les algorithmes sublinéaires dans le cadre des problèmes NP-Hard pour les DFs non-strictes.

Nous introduisons également FASTG3, une bibliothèque Python open-source qui sera utilisée pour proposer une étude expérimentale approfondie des algorithmes présentés en termes de performances temporelles et de précision d'approximation. 𝜑 𝑠𝑡𝑟𝑖𝑐𝑡𝑒 : flow, elevation → power Cependant, cette définition de la satisfaction est connue pour être trop stricte pour de nombreux scénarios de la vie réelle. Ainsi, il est souvent nécessaire de quantifier l'accord partiel d'une DF dans les données plutôt que de se contenter d'évaluer sa satisfaction parfaite pour tous les tuples. La mesure la plus utilisée à cet égard est l'indicateur 𝑔 3 [3] avec son opposé (1 -𝑔 3 ) parfois appelé la confiance. Étant données une relation 𝑟 et une DF 𝜑, 𝑔 3 (𝜑, 𝑟 ) correspond à la plus petite proportion de tuples à enlever de 𝑟 pour que 𝜑 soit vérifiée dans 𝑟 .

De plus, il est intéressant d'étendre l'utilisation de 𝑔 3 à d'autres types de DFs. Dans cet article, nous nous concentrons sur les relaxations de la comparaison de valeurs d'attributs où l'égalité stricte imposée par les DFs strictes (aka exacte) est remplacée par des prédicats. Cette importante relaxation permet de capturer une notion plus raffinée de proximité directement liée au problème à résoudre et à la connaissance du domaine disponible. Par exemple, connaissant les incertitudes des capteurs de la turbine, il est possible de proposer une DF non-strictes telle que :

𝜑 𝑛𝑠𝑡𝑟𝑖𝑐𝑡𝑒 : [debit±0.05•debit], [elevation±0.05] → [puissance±0.01]
Dans ce papier, nous proposons plusieurs algorithmes pour calculer 𝑔 3 avec les DFs strictes et non-strictes. Chaque optimisation est détaillée puis comparée à travers une série détaillée d'expérimentations. Ainsi, nous offrons des solutions concrètes permettant de calculer 𝑔 3 pour de grands jeux de données, notamment grâce à Fastg3, une nouvelle librairie Python open-source disponible sur GitHub basée sur des implémentations rapides en C++.

APERÇU TECHNIQUE 2.1 Dépendances fonctionnelles strictes

Vue générale. Le calcul de 𝑔 3 avec DF stricte est similaire à une opération de GROUP-BY. Il s'agit de grouper ensemble tous les tuples ayant les mêmes valeurs sur la partie gauche de la DF et de trouver les tuples ayant une partie droite majoritaire dans chaque groupe. 𝑔 3 correspond alors au nombre normalisé de tuples nonmajoritaires dans chaque groupe.

Calcul exact. Nous proposons tout d'abord deux algorithmes exacts. L'un est basé sur du hachage avec une complexité linéaire mais un usage mémoire élevé alors que le deuxième utilise un algorithme de tri pour une complexité logarithmique mais un usage mémoire flexible.

Approximation. Pour les grands jeux de données, nous comparons deux algorithmes utilisant les échantillonnages uniforme et stratifié. L'algorithme stratifié est tiré de [1] et nous proposons une amélioration de cet algorithme basée sur une technique d'échantillonnage avec un terme de correction pour population finie permettant des gains importants dans la qualité de l'approximation.

Dépendances fonctionnelles non-strictes

Vue générale. Notre approche pour le calcul exact de g3 avec une DF non-stricte est composée de deux étapes (généralisation d'un approche proposée dans [5]) : (1) création d'un graphe via l'énumération des paires de tuples ne respectant la DF (aka contre-exemple) et (2) la résolution du minimum vertex cover (MVC) sur le graphe créé. 𝑔 3 correspond alors à la taille normalisée de la couverture du MVC. On comprend alors que le calcul de 𝑔 3 est coûteux car (1) est quadratique dans le nombre de tuples et (2) requiert la résolution d'un problème NP-Hard de complexité exponentielle dans le nombre de contre-exemples.

Calcul exact. Pour l'opération (1), des optimisations tirées du record linkage ou encore des similarity joins sont étudiées. Pour la résolution du MVC, Fastg3 propose un algorithme de résolution à l'état de l'art combinant multiples techniques d'optimisation [2].

Approximation. Dans cette étude, nous ne considérons pas d'approximations pour l'opération (1) du calcul. Cependant, une fois le graphe construit, de nombreux algorithmes d'approximation existent pour le MVC permettant d'accélérer l'opération (2). Nous en comparons deux dans les expérimentations : un algorithme avec un très bon ratio d'approximation théorique (2-approché) mais des performances pratiques souvent décevantes et un algorithme avec un mauvais ratio d'approximation théorique mais donnant en pratique des approximations quasi-parfaites.

Approche sublinéaire. Finalement, nous proposons l'alternative des algorithmes sublinéaires pour le MVC permettant d'effectuer les opérations (1) et (2) simultanément et de ne parcourir qu'un sous-ensemble du graphe. Pour ce faire, le graphe est construit à la demande en énumérant les contre-exemples d'un tuple donné uniquement quand c'est nécessaire. Ainsi, en utilisant un système de requête de graphe dissimulant ce système d'énumération à la demande, la plupart des algorithmes sublinéaires peuvent être adaptés pour le calcul du 𝑔 3 . Nous étudions notamment [6] et [4].

EXPÉRIMENTATIONS

Dans le cas des DFs strictes, le calcul de 𝑔 3 dépend principalement du nombre de tuples et le temps de calcul reste raisonnable dans l'ordre du million. Néanmoins, les algorithmes d'approximation présentés peuvent être utilisés pour éviter d'itérer sur tous les tuples, permettant ainsi d'accélérer le calcul. Ces algorithmes d'approximation sont particulièrement efficaces pour les petites valeurs de 𝑔 3 . L'échantillonnage uniforme propose une qualité d'approximation insuffisante mais les algorithmes stratifiés et notamment la version améliorée permettent d'obtenir de très bonnes approximation en un temps raisonnable.

Avec des DFs non-strictes, le calcul de 𝑔 3 dépend du nombre de tuples mais aussi du nombre de contre-exemples. Lorsque l'énumération des contre-exemples peut être réalisée en un temps raisonnable, un algorithme du MVC exact peut être utilisé pour calculer exactement 𝑔 3 pour un petit nombre de contre-exemples. Sinon, les algorithmes d'approximation du MVC proposent des alternatives efficaces. Lorsque l'énumération devient trop longue, les algorithmes sublinéaires offrent une alternative plus rapide au détriment de la qualité de l'approximation.

TRAVAUX FUTURS

Les algorithmes sublinéaires pour le MVC de la littérature adaptent un algorithme 2-approché qui offre, dans les faits, des approximations souvent mauvaises. Nous travaillons sur l'adaptation de l'algorithme GIC en sublinéaire qui permettrait d'obtenir des approximations bien meilleures en pratique.

REMERCIEMENTS

Nous remercions Graham Cormode et Divesh Srivastava pour la qualité de notre échange sur leur article [1]. Merci également à Krzysztof Onak pour avoir aimablement répondu à nos questions sur [4]. Enfin, nous remercions Datavalor de l'INSA Lyon et la Compagnie Nationale du Rhône pour avoir financé une partie de ce travail.

RÉFÉRENCES

ABSTRACT

Designing software architectures for Big Data is a complex task that has to take into consideration multiple parameters, such as the expected functionalities, the properties that are untradeable, or the suitable technologies. Patterns are abstractions that guide the design of architectures to reach the requirements. One of the famous patterns is the Lambda Architecture, which proposes realtime computations with correctness and fault-tolerance guarantees. But the Lambda has also been highly criticized, mostly because of its complexity and because the real-time and correctness properties are each effective in a different layer but not in the overall architecture. Furthermore, its use cases are limited, whereas Big Data need an adaptive and flexible environment to fully reveal the value of data. Nevertheless, it proposes some interesting mechanisms. We present a renewal of the Lambda Architecture: the Lambda+ Architecture, supporting both exploratory and real-time analyzes on data. We propose to study the conservation of properties in composition of components in an architecture using the category theory.

KEYWORDS

Architecture pattern, Category theory, Lambda Architecture

INTRODUCTION

All information systems have a common point: they need an architectural design before being developed and deployed. The architecture must guarantee some properties and guide the consistency of the overall structure of the information system. In this context, architectural styles and patterns are used to build a system having the expected characteristics for each of its part as well as for its entirety, and to state the requirements of the technologies and programming techniques needed to achieve the goal sought. Thus, global requirements such as scalability, performance, reliability must be clearly identified to select the style of architecture, the different components and the interactions among them [6], and then choose technologies with properties (such as ACID for databases or micro batch capabilities for stream processing) that fit all of the previous choices. The absence of coherence in a definition of an architecture can lead to the dreaded Big Ball of Mud [3], that reduces greatly the maintenance and evolutivity capabilities of the system.

Recent researches in software architecture try to formally define styles and patterns, to anticipate effects of the composition of components, and thus knowing beforehand the result of the evolution of a part of the architecture [1,5]. When architectures evolve and grow, they can combine several smaller parts of architectures developed separately. When building a large scale, complex and distributed architecture, its parts can embed architecture styles on their own. These different cases can result in compositions of smaller architecture parts with their proper styles and patterns, so formalization should be able to express and control these compositions. Category theory [2] is a promising approach for formalization, due to its ease to represent compositions as it considers morphims and functors as first class citizens, and to its already existing proximity to the engineering software world, particularly with functional programming. Moreover, its graphical representation is a visual help to understand the formalization, and leads to a better comprehension of the system [9].

We propose the Lambda+ Architecture pattern, an update of the Lambda Architecture, and a formalization to study the conservation of properties in compositions of components using the category theory. For more details on this work, see [4].

THE LAMBDA ARCHITECTURE PATTERN

The properties of correctness, low latency and fault-tolerance have always been a major concern when designing architectures. In [6], Lampson sketches some suggestions that are still relevant today, and that can be found, among others, in the Lambda Architecture, introduced by Marz in 2011 [7,8]. The objective of the Lambda is simple: to compute predetermined queries with a very low latency and to ensure the correctness of the processing. To do so, the Lambda is composed of three layers: the batch layer, that takes care of storing raw data in the master dataset and of executing the computations on the batch of data while preserving the correctness property, the speed layer, that performs the same computations as the batch layer but with an incremental processing to support the low latency property but not the correctness one, and the serving layer, that puts the results to disposal.

With these specifications, the advantages of the Lambda Architecture are a strong fault-tolerance for machine and human faults, a guarantee of a correct result with the batch layer and a low latency with the speed layer. However, the Lambda has also been criticized a lot, due to its complexity to maintain and to evolve both the speed and the batch layers, that have to perform the same computations, but with different paradigms. It also lacks in flexibility, as its goal is to answer only predetermined queries. Thus, alternative use cases such as exploratory analyzes require to modify the pattern. Furthermore, by delegating the correctness property only to the batch layer and not to the speed layer, the low latency and the correctness properties cannot be obtained simultaneously. To clarify this statement, the Lambda has to be replaced in the context of its creation. At this time, streaming systems were only at their early stages, and thus did not have all the capabilities that they have today. It includes the correctness property, that have since been integrated into the stream processing systems. So, the Lambda can be seen as a mean to compensate flaws of an emerging technology, rather than a pattern that fully exploits it.

THE LAMBDA+ ARCHITECTURE PATTERN

To improve the Lambda Architecture, the correctness property should hold for all the components. Furthermore, the fault-tolerance should be kept, but as the reprocessing of data in a batch fashion is incompatible with the real-time property, it should be integrated as an alternative running composition of components, activated only in case of a technical failure or to satisfy new needs. Use cases should also gain in flexibility, and the complexity induced by the development of the same process with different paradigms in different layers should be avoided. The Lambda+ Architecture (figure 1) is meant to be a renewal of the Lambda Architecture, by improving the support of the correctness property and by leveraging two main functionalities: 1) storing data in a way that allows flexible and exploratory data analyzes ; and 2) computing in real-time predefined queries on data streams in order to have insights on well-known and identified needs. The duality between exploratory analyzes and predefined queries is of primary importance in a Big Data context, where the combination of volume and variety of data overcomes the capability of finding all the insights hidden in data. The fault-tolerance mechanism of the Lambda is kept, but is only activated when needed.

The Lambda+ is composed of a set of components interacting together asynchronously with messages. This pattern borrows its principles from the Event-Driven Architecture style, which is wellsuited for achieving performance, scalability and evolutivity. The trade-offs of this architecture style is a lack of simplicity and the difficulty of testing the whole architecture, due to the dynamic nature of the messaging workflow and the chaining of various processing components.

USING THE CATEGORY THEORY TO STUDY CONSERVATION OF PROPERTIES

In the research field of software engineering for architecture design, the need for proper theory and formalization has raised importance in the last decade [1,5]. Designing, specifying and implementing software architectures are complex tasks, that require careful specifications to link and preserve characteristics through all the steps of creation. The development of theory in this field requests both practical and theoretical skills, in order to propose a model suited to the expectations, that takes into consideration the imperfections of the real-world of engineering.

To fill this need, category theory [2] is a promising approach: it allows to switch from a model to another or to navigate among abstraction levels [9]. By focusing on relations (the morphisms) and compositions, it proposes powerful mechanisms that can be applied to architectures: the behaviour of functors combined with preorders allows the study of the conservation or the discarding of properties in compositions of components.

CONCLUSION

We proposed the Lambda+ Architecture pattern, the successor of the Lambda Architecture, that gets rid of its flaws and fits more various use cases by handling both exploratory and real-time analyzes. We used the category theory to study the conservation of properties in compositions of components.

For future work, we plan to develop our formalization to study more various aspects of architectures: 1) to navigate among abstraction levels (i.e., the level of detail of the representation of the architecture) ; 2) to verify if an architecture follows a given style or pattern by using full functors (i.e., surjective functors) ; and 3) to extend the property description, including numerical values (e.g., the execution time to deduce if it can be considered as real-time).

Threats Modeling And Anomaly Detection In The Behaviour Of

A System -A Review Of Some Approaches

ABSTRACT

With the increase of Big Data, cybersecurity is undergoing massive changes, especially when attacks process differently and use different strategies.

Because of the vast volume of data, it becomes harder and harder to detect anomalies, it is complex to manage with traditional systems, and therefore to devise techniques to automatically identify malicious behaviours, even though it is a crucial task. However, Big Data also enables the development of new anomaly detection approaches, based on data analysis and especially machine learning and data mining. With this perspective, it becomes possible to propose solutions that are more flexible and better suited to the new threats that are constantly evolving. In this paper, our objectives are to first define some concept in cybersecurity, describe a model for identifying computer security threats, a model for assessment and prevention tool with CyberKill Chain (CKC), give a general overview of the current techniques used for anomaly detection in the context of cybersecurity. Then, implement and test some machine learning techniques for this task, in order to compare their performances. Experiments were carried on the CICIDS2017 dataset, using traditional anomaly detection techniques based on clustering algorithms like K-Means and Classification algorithms such as SVM, decision tree, and neural networks algorithms.

To better understand the section presented in our paper, Algorithm 1 describes the process and the main idea we wanted to convey :

Algorithm 1: Process of the paper Personal data are increasingly disseminated over Internet through mobile devices and smart environments, and are exploited for developing more and more sophisticated services and applications. All these advances come with serious risks for privacy breaches that may reveal private information wanted by users to remain undisclosed. It is therefore of utmost importance to help data producers to keep the control on their data for their privacy protection while preserving the utility of disclosed data for service providers.

1 if
In this paper, we approach the problem of utility-aware privacy preservation in the setting of applications where service providers (e.g., power suppliers) perform data analytics on data concerning their customers (e.g., smart home occupants) for optimization or recommendation purposes. In such settings, (sensor) data are gathered, abstracted and transferred through internet protocols from data producers environment (e.g., smart home, smart personal devices) to a centralized data consumer in charge of aggregating data for conducting varied analytics tasks.

Sensitive data leakage can occur at different stages and places due to security vulnerabilities of (1) the network, (2) the centralized server used by the data consumer for collecting data outsourced by the different data producers, and (3) the local servers of each data producer.

Following the vision of [1], we propose, first, to rely on data encryption to secure data exchange through the network and, second, to avoid the privacy risks of data centralization by keeping the data produced by each data owner decentralized in secure personal data servers.

The approach that we promote to face the privacy versus utility dilemma in this setting can be summarized as follows:

(1) Data producers keep the control on the data they accept to transmit to the data consumer according to their own privacy policy.

(2) The data consumer makes explicit his/her utility policy to explain for which task or service s/he requests data from data producers. (3) In case of incompatibility of the utility policy with the privacy policy of a data producer, the data producer negotiates with the data consumer to find an acceptable privacy-utility trade-off. Our contribution is twofold. First, we extend the framework proposed in [3] to formalize privacy and utility policies as temporal aggregate queries. Second, we formally define and study the compatibility problem in this query-based framework. More details can be found in [2].

QUERY-BASED SPECIFICATION OF POLICIES

We define utility and privacy policies in the form aggregated conjunctive queries that are built upon a common temporal knowledge graph. Definition 3 (Privacy policy). A privacy policy is defined by a set of TACQ queries, called privacy queries. A privacy policy, specific to each data producer, is satisfied when all the answers of all the privacy queries remain undisclosed for any temporal RDF graph storing her/his data.

COMPATIBILITY CHECKING

Incompatibility between privacy and utility policies should be defined and checked independently of any data graph and should express that no answer of a privacy query can be inferred from answers to some utility queries. This is formalized in Definition 4 in which the logical signature of an answer to a query is the logical formula built from the query expression that characterizes all the (unknown) data graphs leading to this answer (for this query).

Definition 4 (Incompatibility between privacy and utility). A privacy policy is incompatible with a utility policy iff the logical signature of an answer to a privacy query can be logically entailed by the union of logical signatures of answers sets of utility queries.

Theorem 3.1 provide a full characterization of incompatibility for privacy and utility queries without aggregate. It is based on building all the data graphs that are representative of the different ways of joining answers of utility queries. Each of these data graph is obtained by 𝑓 𝑟𝑒𝑒𝑧𝑖𝑛𝑔 the variables in the union of graph patterns in the utility queries, in a way that allows to replace distinct output variables with a same constant. Theorem 3.1 (Incompatibility without aggregate). A privacy query without aggregate is incompatible with a set of utility queries without aggregate if and only if there exists a freezing of the union of the graph patterns in the utility queries on which the evaluation of the privacy query returns a non-empty set of answers.

In the worst case, this may lead to iterating an exponential number of times the evaluation of each privacy query over small RDF graphs, since the number of possible freezings is 2 𝑂𝑉 𝑢 where 𝑂𝑉 𝑢 is the number of output variables in the utility queries.

In the following, we give sufficient conditions of (in-)compatibility that are easier to check.

Theorem 3.2 (Sufficient condition of compatibility). A privacy query is compatible with a set of utility queries if

• the graph pattern of the privacy query is disjoint from the union of the graph patterns of the utility queries, • or if the conjunction of the FILTER condition of the privacy query and of all the FILTER conditions in the utility queries is unsatisfiable, • or if no boundary of a time window of any utility query corresponds to a boundary of a time window of the privacy query, except of course for the first ones starting at query evaluation time.

For the case of privacy and utility queries with aggregates, since the aggregate values are computed based on groups that are specific to each query, checking compatibility can be restricted to checking compatibility between each privacy query and each utility query. Theorem 3.3 (Sufficient condition of incompatibility). Let consider a privacy query 𝑄 𝑝 and an utility query 𝑄 𝑢 with aggregates on a same time window. 𝑄 𝑝 is incompatible with 𝑄 𝑢 if there exists a (possibly empty) freezing 𝑓 𝑝 of output variables in 𝐺𝑃 𝑝 with constants of 𝐺𝑃 𝑢 , or a (possibly empty) freezing 𝑓 𝑢 of output variables in 𝐺𝑃 𝑢 with constants in 𝐺𝑃 𝑝 such that 𝑓 𝑝 (𝐺𝑃 𝑝 ) and 𝑓 𝑢 (𝐺𝑃 𝑢 ) are isomorphic.

When 𝑄 𝑝 and 𝑄 𝑢 have no FILTER conditions and the same aggregate functions, they are incompatible if and only if the above condition is satisfied.

CONCLUSION AND FUTURE WORK

In this paper we have proposed a query-based declarative framework for a formal specification and verification of privacy and utility policies expressed as temporal aggregate conjunctive queries.

We do think that this framework is well suited for guaranteeing data producers to keep the control and protect their data in many real-world situations where sensitive data are collected by mobile personal devices or smart environments.

Based on the implementation of this framework, we plan to design and implement a negotiation mechanism that will be triggered when a utility policy turns out to be incompatible with a privacy policy. New relaxed utility queries will be automatically computed to restore compatibility with the privacy policy of a given data producer. They will be the formal basis of a dialogue between each data producer and the service provider in order to find a trade-off acceptable in terms of utility while guaranteeing privacy preservation for each data producer.

We also plan to extend our framework to take into account ontological knowledge in the possible inference of answers of privacy queries by answers of utility queries. This will bring stronger constraints on compatibility between privacy and utility policies.

Processing SPARQL Property Path Queries Online with Web Preemption

Julien Aimonier-Davat

ABSTRACT

Description Logics (DLs) are a family of knowledge representation and reasoning formalisms that have been proven useful in many application domains [2]. They provide means for well-structured and formal representation of the conceptual knowledge of an application domain and various inference procedures to reason about the represented knowledge. Description logics enable to describe a universe of discourse in terms of concept descriptions, i.e., expressions built from atomic concepts (unary predicates) and atomic roles (binary predicates) using the constructors of the considered description logic. For example, using the atomic concept 𝑃𝑒𝑟𝑠𝑜𝑛 and the atomic role ℎ𝑎𝑠𝑐ℎ𝑖𝑙𝑑, the concept of 𝑃𝑎𝑟𝑒𝑛𝑡 can be represented by the concept description 𝑃𝑒𝑟𝑠𝑜𝑛 ⊓ ∃ℎ𝑎𝑠𝑐ℎ𝑖𝑙𝑑.𝑃𝑒𝑟𝑠𝑜𝑛 While subsumption reasoning, i.e., the ability to determine subconcept-superconcept relationships, is a traditional reasoning in DLbased system additional inference mechanisms, such as matching [4] and unification [3], that go beyond subsumption, have been proposed in the literature. In this latter non-standard forms of reasoning, concept description with not completely specified form (incomplete information) can be specificed using the so-called concept patterns, i.e., concept descriptions containing variables. As an example, consider the following pattern which defines an 𝐴𝑐𝑎𝑑𝑒𝑚𝑖𝑐 as a 𝑃𝑒𝑟𝑠𝑜𝑛 with a certain relationship with a 𝑈 𝑛𝑖𝑣𝑒𝑟𝑠𝑖𝑡𝑦. 𝐴𝑐𝑎𝑑𝑒𝑚𝑖𝑐 ≡ 𝑃𝑒𝑟𝑠𝑜𝑛 ⊓ ∃𝑥 .𝑈 𝑛𝑖𝑣𝑒𝑟𝑠𝑖𝑡𝑦 Here, the variable 𝑥 takes its values from a set of possible atomic role names. The concept description 𝐴𝑐𝑎𝑑𝑒𝑚𝑖𝑐 ≡ 𝑃𝑒𝑟𝑠𝑜𝑛 ⊓ ∃𝑤𝑜𝑟𝑘𝑠𝐼𝑛.𝑈 𝑛𝑖𝑣𝑒𝑟𝑠𝑖𝑡𝑦 matches this pattern. Indeed, if we replace the variable 𝑥 by the role 𝑤𝑜𝑟𝑘𝑠𝐼𝑛, the pattern becomes equivalent to the description. Replacing a variable 𝑥 with a value is called variable substitution. Given a description 𝐶 and a pattern 𝑃, the matching problem asks then whether there is a variable substitution such that 𝐶 matches 𝑃. The unification extends the matching to the case where 𝐶 is itself a pattern. Consider now the case of a cyclic description: 𝐴𝑐𝑎𝑑𝑒𝑚𝑖𝑐 ≡ 𝑃𝑒𝑟𝑠𝑜𝑛 ⊓ ∃𝑥 .𝑈 𝑛𝑖𝑣𝑒𝑟𝑠𝑖𝑡𝑦 ⊓ ∃𝑦.𝐴𝑐𝑎𝑑𝑒𝑚𝑖𝑐 and the following concept descriptions:

𝐴 ≡ 𝑃𝑒𝑟𝑠𝑜𝑛 ⊓ ∃𝑤𝑜𝑟𝑘𝑠𝐼𝑛.𝑈 𝑛𝑖𝑣𝑒𝑟𝑠𝑖𝑡𝑦 ⊓ ∃ℎ𝑎𝑠𝐴𝑑𝑣𝑖𝑠𝑒𝑟 .𝐵 𝐵 ≡ 𝑃𝑒𝑟𝑠𝑜𝑛 ⊓ ∃𝑝𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡𝑂 𝑓 .𝑈 𝑛𝑖𝑣𝑒𝑟𝑠𝑖𝑡𝑦 ⊓ ∃ℎ𝑎𝑠𝐶ℎ𝑖𝑙𝑑.𝐵
Using standard semantics of variable substitution, 𝐴 do not match the pattern academic. However, if we exploit a different semantics that enables to refresh the values of the variable 𝑥 and 𝑦 in each description of the pattern 𝐴𝑐𝑎𝑑𝑒𝑚𝑖𝑐, in this case it becomes possible to compute a matcher that makes the concept 𝐴 match the pattern 𝐴𝑐𝑎𝑑𝑒𝑚𝑖𝑐 (i.e., the first occurrences of 𝑥 and 𝑦 are respectively mapped to 𝑤𝑜𝑟𝑘𝑠𝐼𝑛 and ℎ𝑎𝑠𝐴𝑑𝑣𝑖𝑠𝑒𝑟 while their second occurrences are respectively mapped to 𝑝𝑟𝑒𝑠𝑖𝑑𝑒𝑛𝑡𝑜 𝑓 and ℎ𝑎𝑠𝐶ℎ𝑖𝑙𝑑).

This paper studies the extension of description logics with variables equipped with refreshing semantics. More specifically, we focus on a new description logic, called EL 𝑉 , that extends the description logic EL with refreshing variables. Our definition of EL 𝑉 -patterns deviates from the one used in the literature with respect to the following features:

(1) our definition of concept patterns use role variables while the literature mainly focuses on concept variables, (2) we support cyclic pattern definition and allow two different types of semantics for variables (i.e., refreshing and not refreshing semantics), We consider in particular a new reasoning mechanism in this context, called weak-subsumption, which extends matching and unification to logics with refreshing variables. Our main technical result is to show that testing weak-subsumption between EL 𝑉 -patterns with role variables is EXPTIME-complete. Our approach to test weaksubsumption exploits the link between subsumption and the simulation relation between the so-called description graphs introduced in [1]. The main steps of our approach are as follows:

• We associate with each EL 𝑉 -pattern 𝑃 a description automaton 𝐴 𝑃 . This automata corresponds to a compact representation of all possible substitutions of 𝑃. • We extend the notion of simulation relation, used in [1] to characterize weak-subsumption between EL-patterns.

Our main technical results consists in characterizing weaksubsumption between EL 𝑉 -patterns in terms of existential simulation between EL 𝑉 -description automata. • We devise an algorithm to test existential simulation between EL 𝑉 -description automata and prove its correctness. We show its optimality by demonstrating that the proposed algorithm has exponential time complexity in the worst case.

Creating Embeddings of Heterogeneous Relational Datasets for Data Integration Tasks

Riccardo Cappuzzo cappuzzo@eurecom.fr EURECOM Paolo Papotti papotti@eurecom.fr EURECOM Saravanan Thirumuruganathan sthirumuruganathan@hbku.edu.qa QCRI, HBKU

The problem of data integration concerns the combination of information from heterogeneous relational data sources, which is recognized as an expensive task for humans [12]. While traditional approaches require substantial effort from domain scientists to generate features and labeled data or domain specific rules, there has been increasing interest in achieving accurate data integration with deep learning methods to reduce the human effort. Embeddings have been successfully used for this goal in data integration tasks such as entity resolution [1,4,8,10,11], schema matching [6,9], identification of related concepts [5], and data curation in general [12]. Typically, these works fall into two dominant paradigms based on how they obtain word embeddings. The first is to reuse pre-trained word embeddings computed on a generic corpus for a given task. The second is to build local word embeddings that are specific to the dataset. These methods treat each tuple as a sentence by reusing the same techniques for learning word embeddings employed in natural language processing. However, both approaches fall short in some circumstances. Enterprise datasets contain custom vocabulary, as in the small datasets in the left-hand side of Figure 1. The pre-trained embeddings do not capture the local semantics expressed by these datasets and do not contain embeddings for the word "Rick". Also, the embedding for token "Steve" is closer to tokens "iPad" and "Apple" even though it is not implied in the data. Approaches that treat a tuple as a sentence miss a number of signals such as attribute boundaries, integrity constraints, and so on. Moreover, existing approaches do not consider the generation of embeddings from heterogeneous datasets, with different attributes and alternative value formats. These observations motivate the generation of local embeddings for the relational datasets at hand. We advocate for the design of such local embeddings that leverage both the relational nature of the data and the downstream task of data integration. Tuples are not sentences. Embedding techniques originally developed for textual data ignore the richer set of semantics inherent in relational data. Consider a cell value 𝑡 [𝐴 𝑖 ] of an attribute 𝐴 𝑖 in tuple 𝑡, e.g., "Mike" (in italic) in the first relation from the top. Conceptually, it has semantic connections with other attributes of tuple 𝑡 (such as "iPad 4th") and other values from the domain of attribute 𝐴 𝑖 (such as "Paul", also in italic in the figure).

Embedding generation must span different datasets. Embeddings must be trained using heterogeneous datasets, so that they can meaningfully leverage and surface similarity across data sources. A notion of similarity between different types of entities, such as tuples and attributes, must be developed. Tuple-tuple and attributeattribute similarity are important features for data integration. Any solution satisfying these requirements must overcome multiple challenges. First, it is not clear how to encode the semantics of the relational datasets in the embedding learning process. Second, datasets may share limited amount of information, have different schemas, and contain a different number of tuples. Finally, datasets are often incomplete and noisy. The learning process is affected by low information quality resulting in embeddings that do not correctly represent the semantics of the data.

We address these challenges with EmbDI, a framework for building relational, local embeddings for data integration that introduces a number of innovations to effective model heterogeneous tuples. We identify crucial components and propose effective algorithms for instantiating each of them. EmbDI is designed to be modular so that anyone can customize it by plugging in other algorithms and benefit from the continuing improvements from the deep learning and database communities. The two main components in our solution are the following.

1. Graph Construction. We use a compact tripartite graph-based representation of relational datasets that effectively represents syntactic and semantic data relationships. Specifically, we use three types of nodes. Token nodes correspond to the unique values found in the dataset. Record Id nodes (RIDs) represent a unique token for each tuple. Column Id nodes (CIDs) represent a unique token for each column/attribute. These nodes are connected by edges based on the structural relationships in the schema. This graph is a compact representation of the original datasets that highlights overlap and explicitly represent the primitives for data integration tasks, i.e., records and attributes.

2. Embedding Construction. We formulate the problem of obtaining local embeddings for relational data as a graph embeddings generation problem. We use random walks to quantify the similarity between neighboring nodes and to exploit metadata such as tuple and attribute IDs. This method ensures that nodes that share similar neighborhoods will be in close proximity in the final embeddings space. The corpus that is used to train our local embeddings is generated by materializing these random walks.

In this short paper, we give an overview of the solution and report results for the entity resolution task. We refer the reader to the extended version for more details and full experimental results [2].

Overview

Our framework, EmbDI, consists of three major components, as depicted in the right-hand side of Figure 1.

(1) In the Graph Construction stage, we transform the relational dataset in a compact tripartite graph that encodes various relationships inherent in it. Tuple and attribute ids are treated as first class citizens. (2) Given this graph, the next step is Sentence Construction through the use of biased random walks. These walks are carefully constructed to avoid common issues such as rare words and imbalance in vocabulary sizes. This produces as output a series of sentences.

(3) In Embedding Construction, the corpus of sentences is passed to an algorithm for learning word embeddings. Depending on available external information, we optimize the graph and the workflow to improve the embeddings' quality.

Experiments

We used 8 datasets from the literature and a dataset with a larger schema (IM) that we created from open data (https://www.imdb. com/interfaces/, https://grouplens.org/datasets/movielens/). For the majority of the scenarios, less than 10% of the distinct data values are overlapping across the two datasets.We relied on state of the art methods to combine words in tuples and to obtain embeddings for words that are not in the pre-trained vocabulary [4]. We test four algorithms for the generation of local embeddings. All methods make use of our tripartite graph and exploit record and column IDs in the integration tasks. The first method (Basic) creates embeddings from permutations of row tokens and sentences with samples of attribute tokens. The second method (N2V [7]) is a widely used algorithm for learning node representation on graphs. Given our graph as input, it learns vectors for all nodes. The third method is Harp [3], a state of the art algorithm that learns embeddings for graph nodes by preserving higher-order structural features. The fourth method is EmbDI (https://gitlab.eurecom.fr/cappuzzo/embdi), with walks (sentences) of size 60, 300 dimensions for the embeddings space and the Skip-Gram model in word2vec with a window size of 3. We also use different tokenization strategies to convert cell values in nodes (Simple, Flatten and Overlap whose details are reported in the full paper). As baseline for this unsupervised case, we use our matching algorithm with pre-trained embeddings obtained from fastText (fTxt).

Results in [3,9,10,12] ont montré que les outils d'analyse de sentiment ne respectent pas ce consensus et attribuent des polarités différentes aux paraphrases générant des incohérences intra algorithme. Ainsi, des algorithmes différents attribuent des polarités différentes au même texte créant ainsi des incohérences inter-algorithmes. Dans ce papier, nous présentons une étude empirique détaillée afin de trouver les causes de ces incohérences et déterminer les facteurs d'influence. Notre étude porte sur 4 axes : une étude statistique pour qualifier les incohérences, une étude structurelle pour déterminer les liens entre la structure du texte et les incohérences, et une étude sémantique pour voir les liens entre la subjectivité du texte et les incohérences. Nous avons aussi étudié la relation entre les hyperparamètres dans les algorithmes d'apprentissage profond pour l'analyse de sentiment, la précision et l'incohérence dans ces algorithmes. Les travaux existants comme [1,6,11,16], se sont intéressés à la génération des exemples contradictoires (adversarial exemples) pour tester la robustesse des algorithmes envers les incohérences. D'autres travaux comme celui de [11] se sont intéressés à la proposition d'algorithmes permettant aux outils d'analyses de sentiment d'éviter les incohérences intra-algorithmes.

Dans notre travail [8], nous nous intéressons à détecter les causes et les facteurs qui impactent les incohérences dans les outils d'analyse de sentiment. A notre connaissance, le travail présenté dans ce papier est le premier en soi qui propose une étude de la cohérences des outils d'analyses de sentiment couvrant plusieurs algorithmes et sur une large échelle de données.

Dans ce qui suit, nous présentons les contributions majeures ainsi que les résultats clés de notre étude.

CONTRIBUTIONS 2.1 Des algorithmes génériques pour les outils d'analyse de sentiment

Nous avons effectué, dans un premier temps une étude bibliographique des méthodes d'analyse de sentiment de la littérature, proposé des abstractions algorithmiques pour chaque catégorie d'algorithmes et sélectionné six algorithmes représentatifs à évaluer.

Évaluation Empirique

Nous avons mené une étude empirique qui qualifie les incohérences et explique la non robustesse des algorithmes d'analyse de sentiment en présence d'exemples contradictoires (adversarial exemples).

Proposition d'un benchmark de test

Afin d'évaluer des incohérences, nous avons construit un benchmark de paraphrases étiquetées avec des polarités. Le benchmark est construit à partir de cinq corpus de données pour l'analyse de sentiment disponibles publiquement que nous avons augmenté avec des paraphrases en utilisant la méthode [6]. La méthode que nous avons utilisée a une précision de 80%. Afin d'augmenter la qualité de notre benchmark, nous avons proposé une heuristique qui permet de réduire la marge d'erreur en gardant que les paraphrases valides. Cette heuristique permet de minimiser l'effort humain pour la vérification de la qualité de donnée et assure un benchmark de qualité avec un taux d'erreur réduit.

Recommandations.

En se basant sur les résultats d'évaluation, nous proposons un ensemble de recommandation pour choisir des algorithmes d'analyse de sentiment adapté à un scénario donné et avec différents types de données.

ABSTRACT

Les

CCS CONCEPTS 1 INTRODUCTION

Les modèles de langue probabilistes sont depuis longtemps utilisés pour de très nombreuses tâches du traitement automatique du langage naturel et de la recherche d'information. Nous nous intéressons à l'adaptation de ces modèles pour la classification multilabels où différentes parties du texte contribuent différemment pour la prédiction des labels. L'adaptation de l'apprentissage profond pour la modélisation séquentielle du langage a débuté avec l'utilisation des réseaux de neurones récurrents (RNN). L'entraînement de ces réseaux se fait d'une manière itérative où un état caché ℎ est mis à jour à partir de chaque nouveau mot d'une séquence d'entrée. Les informations contenues dans chaque composante de la phrase sont ainsi préservées tout au long du traitement de celle-ci, mais avec une contribution qui diminue proportionnellement à la longueur de la séquence.

Les réseaux récurrents de longue mémoire à court terme (LSTM) [START_REF] Hochreiter | Long Short-term Memory[END_REF]] ont été conçus pour remédier à ce problème en ajoutant, en plus des états cachés ℎ , des cellules de mémoire qui permettent de réguler le flux d'information et de retenir ou "oublier" les éléments des étapes antérieures selon leur importance. Ce mécanisme a des limitations car l'importance donnée à un mot n'est pas relative au reste de la phrase.

Le mécanisme d'attention [START_REF] Bahdanau | Neural Machine Translation by Jointly Learning to Align and Translate[END_REF]] a été ensuite introduit dans l'utilisation des RNNs. Il permet de donner une importance (poids) relative à chaque mot de la séquence calculée à l'aide d'un réseau de neurones feed-forward (propagation avant). Ces modèles permettent une bonne modélisation du langage et réussissent à capturer la nature séquentielle des phrases, mais avec un temps d'entraînement relativement long. En n'utilisant que le mécanisme d'attention, les transformeurs [START_REF] Vaswani | Attention Is All You Need[END_REF]] peuvent être entraînés en parallélisant le traitement d'une séquence tout en gardant l'information sur l'ordre des mots. Ces transformeurs disposent d'une partie "encodeur" et une autre "décodeur" [START_REF] Sutskever | Sequence to Sequence Learning with Neural Networks[END_REF]], composée chacune de plusieurs couches. Les plongements de mots (embeddings), l'entrée de ces modèles, passent par des couches d'attention (ou self-attention) où ils sont mis à jour en fonction des scores d'attention calculés à partir des autres parties de la séquence, et cela pour avoir une représentation contextualisée pour chaque composante des phrases.

Les transformeurs sont actuellement les meilleures implantations des modèles de langue. Le modèle BERT, pour Bidirectional Encoder Representations from Transformers [START_REF] Devlin | BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding[END_REF]], et ses variantes sont parmi les plus récents. BERT se différencie des autres transformeurs par sa capacité à traiter la séquence de texte d'une manière bi-directionnelle à l'opposé de GPT-2 [START_REF] Radford | Language Models are Unsupervised Multitask Learners[END_REF]] qui ne regarde que la partie gauche du mot en cours de traitement, ou ELMO [START_REF] Peters | Deep contextualized word representations[END_REF]] qui concatène la représentation gauche et droite de la séquence, ce qui rend l'apprentissage plus lent. Cette bi-directionnalité de l'apprentissage améliore les représentations linguistiques du modèle car le sens d'un mot de la phrase peut dépendre non seulement des mots qui le précèdent mais aussi de ceux qui le suivent. Ces modèles sont très utiles compte tenu de leur ré-utilisabilité, en pré-entraînant un modèle en nonsupervisé sur un large corpus de texte, puis en l'adaptant pour la tâche de traitement de texte souhaitée. Le mécanisme d'attention peut être très performant pour capturer l'importance de certaines parties de l'entrée par rapport à d'autres.

La classification multilabels de texte est une tâche de traitement automatique du langage où un texte en entrée peut être associé à plusieurs classes. Le but étant de pouvoir extraire tous les sujets, prédéfinis ou non, contenus dans ce texte. Plusieurs approches d'apprentissage machine ont été proposées pour aborder ce problème. À notre connaissance, aucun benchmark officiel n'existe pour la classification multilabels de texte, et cela en dépit du fait que cette tâche ait des applications concrètes et importantes dans le monde industriel. Parmi ces applications on retrouve l'indexation multicritères, la recommandation de contenu, ou même l'extraction des méta-données pour l'enrichissement des bases de données applicable sur divers types de corpus, à l'instar des articles scientifiques. Les travaux présentés dans cet article sont réalisés dans le cadre d'une thèse CIFRE en collaboration avec Hyperbios, une société de services informatiques, pour la classification et la segmentation des demandes clients exprimées par mail pour le compte de plusieurs agences d'assurance. La classification multilabels permettra d'identifier les sujets contenus dans chaque mail, et déclencher les actions correspondantes par les systèmes d'automatisation de tâches et de proposition de réponses. Exemple : Madame, Suite à notre conversation téléphonique je vous adresse en pièces jointes la photo du compteur kilométrique du véhicule xxxx ainsi que la photo de la plaque d'immatriculation. J'ai bien noté que le véhicule pouvait être conduit par un tiers, et qu'en cas de sinistre il n'y aurait pas de franchise. Je vous remercie de bien vouloir m'adresser aussi rapidement l'attestation d'assurance. Classifications : Envoi de documents, informations relevé compteur, demande d'attestation. Cette exemple illustre la complexité du problème qui consiste à extraire tous les labels possibles depuis un texte de taille réduite, ayant peu d'éléments contextuels et sémantiques. Les différents styles d'écritures ainsi que l'emploi de termes qui diffèrent selon le niveau d'expertise du client pour désigner le même concept rajoutent des contraintes supplémentaires à cette problématique.

Dans cet article, nos contributions concernent essentiellement :

• La création d'un corpus de données de classification de texte multilabels en français, contenant les résumés d'articles scientifiques obtenus à partir de l'archive ouverte "HAL";

• L'évaluation des performances des modèles de langue disponibles : BERT et ses variantes DistilBERT, RoBERTa et De-BERTa pré-entraînés principalement sur des corpus en anglais, ainsi que CamemBERT et FlauBERT, deux autres variantes de BERT pré-entraînées sur des corpus en français;

• L'étude des méthodes de sélection de seuil pour une exploitation plus efficace des résultats de ces modèles, notamment le choix d'un seuil global qui optimise les performances de toutes les classes, ou le calcul d'un seuil propre à chaque classe pour l'optimisation individuelle des labels;

• La proposition de deux approches alternatives au seuillage pour la sélection des classes pertinentes. La première consiste à introduire un paramètre à la dernière couche du transformeur qui sera entraîné pour le calcul du nombre de classes présentes dans un exemple, la valeur de ce paramètre sera utilisée pour sélectionner les labels ayant les activations les plus fortes; La deuxième consiste à rajouter une couche finale au modèle, qui aura le même nombre de paramètres que l'avant dernière couche (égal au nombre de classes), dans le but d'obtenir des valeurs d'activation plus discriminantes pour l'exemple donné, ie. activation élevée si présence de label, faible dans le cas contraire.

Nous évaluons ces approches sur des corpus comparables d'articles scientifiques, HAL-Dataset pour le français et AAPD pour l'anglais, mais aussi sur des articles d'actualité en anglais (corpus de Reuters). Les modèles et les architectures proposés sont comparés à des approches de référence, performantes et plus transparentes sur les critères de classification appris, comme les arbres de décision et les machines à vecteur support (SVM).

L'article est organisé de la façon suivante : la section 2 présente les approches qui abordent la classification multilabels, les sections 3 et 4 décrivent la méthodologie suivie et les approches proposées et la section 5 est dédiée aux expérimentations.

TRAVAUX ANTÉRIEURS

Dans la classification multiclasses, chaque exemple (instance) 𝑋 du jeu de données est associé à un label unique. La classification multilabels (CMLT) consiste en plus à pouvoir associer chaque entrée avec plusieurs labels Y, plutôt qu'un seul.

Méthodes de classification multilabels

Les méthodes de classification multilabels peuvent être classées en trois catégories principales : par transformation du problème, par adaptation ou par des méthodes d'ensembles. L'adaptation des algorithmes d'apprentissage profond pour le multilabels reste de manière générale une voie avec peu de contributions. Une adaptation de ces approches pourraient contribuer à une augmentation significative des performances pour la tâche de classification multilabels. L'utilisation d'un seul modèle sans le recours à une transformation préalable des données constitue une méthode efficiente pour essayer de répondre au problème du multilabels.

Approches de seuillage

Plusieurs méthodes de seuillage ont été proposées pour les approches citées précédemment, ce sont des méthodes qui impactent Des variations de ces méthodes visant à améliorer leur performance et pallier aux problèmes qu'elles peuvent poser ont été suggérées [START_REF] Yang | A study of thresholding strategies for text categorization[END_REF]]. Les méthodes axées sur les scores de classification sont les meilleures parmi les approches de seuillage [?]. Nous choisissons dans cet article la méthode SCut pour l'évaluation des modèles de langues étudiés.

Utilisation de l'apprentissage profond

Les modèles d'apprentissage profond ont aussi été utilisés pour répondre au problème de la classification de texte dont les CNN [START_REF] Kim | Convolutional Neural Networks for Sentence Classification[END_REF]], RCNN [START_REF] Lai | Recurrent convolutional neural networks for text classification[END_REF] et HAN [START_REF] Yang | Hierarchical Attention Networks for Document Classification[END_REF]] mais sans se focaliser sur le problème multilabels.

[ [START_REF] Gan | Multi-label Classification with Optimal Thresholding for Multi-composition Spectroscopic Analysis[END_REF]] utilise un réseau de neurones pour la classification multilabels dans le cadre de l'analyse multi-composition spectroscopique, un réseau composé d'une partie classificateur à laquelle un paramètre est ajouté pour l'apprentissage du seuil d'activation optimal pour la classification. Ce paramètre sera optimisé en fonction du seuil calculé en appliquant le modèle en cours d'apprentissage sur le jeu de données d'entraînement, la valeur cible du seuil sera donc différente pour chaque itération de la phase Les transformeurs ont été utilisés pour la classification multilabels de texte dite 'extrême' [START_REF] Chang | X-BERT: eXtreme Multi-label Text Classification with using Bidirectional Encoder Representations from Transformers[END_REF][START_REF] Gong | Hierarchical Graph Transformer-Based Deep Learning Model for Large-Scale Multi-Label Text Classification[END_REF]] où sont traités des corpus très larges de textes ayant un nombre de labels pouvant atteindre les dizaines de milliers. De telles architectures ne sont pas adaptés à la problématique de textes courts.

Les tentatives d'utiliser les réseaux de neurones pour la classification de texte ne se focalisent pas sur la classification multilabels. Celles qui traitent ce problème ne donnent généralement pas d'importance à la manière dont sont exploitées les activations de la couche de sortie (e.g utilisation de seuil) ou en modifiant l'architecture du réseau pour essayer de l'adapter à cette tâche.

ADAPTATION DES MODÈLES DE LANGUE PRÉ-ENTRAÎNÉS

Nous nous intéressons dans cet article à l'adaptation des modèles transformeurs, notamment BERT et ses variantes, pour la classification multilabels de texte.

2 𝐹 1 -𝑠𝑐𝑜𝑟𝑒 = 2 × 𝑝𝑟 é𝑐𝑖𝑠𝑖𝑜𝑛×𝑟𝑎𝑝𝑝𝑒𝑙 𝑝𝑟 é𝑐𝑖𝑠𝑖𝑜𝑛+𝑟𝑎𝑝𝑝𝑒𝑙

Adaptation de BERT pour la classification multilabels

Pour les réseaux de neurones, le texte d'entrée doit être segmenté et converti en une liste de symboles (appelés tokens) pour le traitement. Ces tokens sont par la suite associés à des identifiants uniques, définis dans le dictionnaire utilisé par le modèle, et aux plongements (word embeddings) de mots qui leur correspondent. Ces derniers constituent les données de la couche d'entrée de ces modèles. L'architecture des modèles de langue à base de transformeurs se différencie de leurs prédécesseurs par leur capacité à paralléliser le processus d'entraînement en traitant tout le vecteur (tous les tokens) de l'entrée simultanément. L'entraînement est réalisé en masquant des tokens (de façon aléatoire ou non) et en essayant ensuite de les prédire en utilisant principalement le mécanisme d'attention, processus appelé modélisation masquée du langage.

Le modèle BERT introduit la bi-directionnalité dans la prédiction des tokens masqués, où les deux contextes sémantiques gauche et droit du mot à prédire sont pris en compte. En plus de la modélisation masquée du langage, BERT est entraîné pour la prédiction de la phrase suivante, une tâche où le modèle reçoit une paire de phrases et essaie de prédire si la deuxième phrase de la paire suit la première dans le texte original.

BERT introduit aussi un token spécial de classification [CLS] (possédant aussi un identifiant et un vecteur d'embedding) contenant un état caché de la phrase, mis à jour dans chacune des couches du modèle. Un réseau linéaire de 𝐿 couches denses (généralement 𝐿=2) constitue les dernières couches du modèle avec le token Le choix des fonctions d'activation et des fonctions de coût dépend de la nature de la tâche de classification. Dans le cas de la classification multiclasses où les classes sont mutuellement exclusives (une instance doit appartenir à une et une seule classe) on utilise classiquement la fonction Softmax comme fonction d'activation de la dernière couche du modèle (𝐶 [𝐿] ). Elle a pour but de convertir le vecteur de sorties, les activations de 𝐶 [𝐿] , en un vecteur de probabilités proportionnelles aux valeurs de ces activations. L'entropie croisée (Cross Entropy) est utilisée comme fonction d'erreur du modèle.

Dans le cas de la classification multilabels, la nature de l'architecture des réseaux de neurones peut être exploitée de telle manière à utiliser les valeurs des activations 𝐴 [𝐿] de la couche de sorties 𝐶 [𝐿] pour déterminer la présence ou non d'un label, et cela en introduisant un seuil. Ce seuil, s'il est dépassé, permettra de considérer ou non le label étudié. Le but n'étant pas d'avoir une distribution de probabilités en fonction de toutes les classes, la fonction Softmax n'est pas adaptée. La fonction d'activation Sigmoid 𝜎 est plus appropriée pour cette tâche. Elle convertit chaque activation de 𝐴 [𝐿] en une valeur comprise entre 0 et 1, calcule une probabilité de présence de chaque label 𝑦 𝑖 en fonction des valeurs de l'activation qui lui correspond 𝑎

[𝐿]

𝑦 𝑖 de la couche 𝐿. Cela implique l'utilisation de l'entropie croisée binaire (Binary Cross Entropy -BCE) comme fonction de coût qui vise à réduire l'écart entre 𝑎

[𝐿]

𝑦 𝑖 et la vraie valeur de sortie (0 ou 1 selon la présence ou non du label 𝑦).

Cette approche ne peut être considérée complètement comme une transformation du problème car la méthode ne requiert pas une transformation du jeu de données ou la création de multiples classifieurs binaires, ni une adaptation complète de l'apprentissage profond pour la classification multilabels car les résultats du réseau de neurones doivent être traités en aval pour avoir les classifications finales.

Apprentissage profond et méthodes de seuillage

Les approches de seuillage peuvent être appliquées au transformeur, si l'on considère que chaque activation de la couche finale est un classifieur binaire de la classe qu'il représente.

Seuil global de classification (SGO). Le seuil de classification

𝑠 peut être choisi de façon à maximiser l'ensemble des scores de classification. Pendant l'entraînement du modèle et après chaque itération, la valeur de 𝑠 est variée de 0 à 1, avec un pas défini au préalable (10 -2 ). Le score micro-F1 est ensuite calculé pour chaque seuil 𝑠. On obtient au final le seuil global optimal 𝑠 𝑔𝑜 qui permet d'obtenir les meilleures performances sur le jeu de données d'entraînement. Ce seuil est ensuite utilisé pour les jeux de données de validation et de test. L'ensemble des labels 𝐿 présents pour un exemple 𝑥 peut être exprimé sous la forme:

𝑌 𝑥 ∈𝑋 = ∪ 𝑦 ∈𝑌 {𝑦 𝑖 } : 𝜎 (𝑎 [𝐿]) 𝑦 𝑖 ) ≥ 𝑠 𝑔𝑜 𝑎 [𝐿]
𝑦 𝑖 étant l'activation qui correspond au label 𝑦 𝑖 parmi les activations 𝐴 [𝐿] .

Une autre variation la méthode SCut (avec seuil global) consiste à affiner le seuil optimal à partir du jeu de données de la validation pour ensuite l'appliquer au jeu de données de test. Seule la première approche a été étudiée dans cet article.

Seuils individuels (SI)

. L'utilisation d'un seuil 𝑠 commun pour toutes les classes suppose que les descripteurs et les poids directement liés aux activations 𝐴 [𝐿] soient les mêmes pour chaque classe/label. Ce qui n'est pas le cas, l'intensité d'activation d'un neurone de la dernière couche 𝑎

[𝐿]

𝑦 𝑖 , lors de la présence du label 𝑦 pour une instance donnée, varie d'une classe à l'autre, un effet qui s'accentue si le jeu de données est peu équilibré.

Nous proposons donc d'évaluer la méthode SCut (avec seuils individuels) en mettant en place un seuil 𝑠 𝑦 pour chaque label 𝑦 du jeu de données, attribué aux activations 𝑎

[𝐿]

𝑦 𝑖 de 𝐶 [𝐿] . Les valeurs de 𝑠 𝑦 sont les valeurs qui maximisent les scores de classification pour un label 𝑦. Ces seuils sont calculés comme pour le 𝑠 𝑔𝑜 pendant la phase d'entraînement du modèle, et sur le jeu de données d'entraînement, en faisant varier chaque seuil de façon à maximiser le score F1 de chaque label.

𝑌 𝑥 ∈𝑋 = ∪ 𝑦 ∈𝑌 {𝑦 𝑖 } : 𝜎 (𝑎 [𝐿]
𝑦 𝑖 ) ≥ 𝑠 𝑦 Comme pour le seuil global, les seuils individuels peuvent être calculés à partir du jeu de données de validation.

APPROCHES PROPOSÉES

Nous proposons deux méthodes alternatives au seuillage pour une exploitation plus efficace des valeurs des activations 𝐴 [𝐿] de la couche de sortie. Ces approches ont pour but de s'affranchir d'un calcul de seuil en apprenant des caractéristiques propres au texte permettant la bonne sélection des labels pertinents.

N plus grandes activations (NPA)

L'utilisation d'un seuil pour déterminer la présence ou non d'un label entraîne dans plusieurs cas une sous classification (respectivement sur classification) d'une instance quand le nombre prédit de labels est inférieur (respectivement supérieur) au nombre effectif de labels présents. La première alternative proposée consiste à introduire un paramètre (neurone) à la dernière couche de classification et qui sera utilisé uniquement pour le calcul du nombre de labels 𝑦 présents pour une instance. Soit 𝐴 ′[𝐿] la liste des 𝑁 plus grandes activations pour un exemple donné, 𝑁 étant le nombre effectif des labels présents pour cet exemple :

𝑌 𝑥 ∈𝑋 = ∪ 𝑦 ∈𝑌 {𝑦 𝑖 } : 𝑎 [𝐿]) 𝑦 𝑖 ∈ 𝐴 ′[𝐿])
L'optimisation de ce paramètre se fera en utilisant le nombre de classes présentes pour une instance comme valeur cible, et une fonction d'erreur adaptée au problème de régression (par ex. l'erreur absolue moyenne MAE ou l'erreur quadratique moyenne MSE).

Nous utilisons un optimiseur unique pour la propagation arrière (calculs des gradients des fonctions d'erreurs et mise à jour des poids du modèle), par conséquent, l'erreur de la régression doit être mise à la même échelle que l'erreur de la classification, ceci est fait en réduisant l'erreur de régression par un facteur de 5. La valeur de ce paramètre sera utilisée pour récupérer les 𝑁 plus grandes activations 𝑎

[𝐿]

𝑦 𝑖 qui seront considérées comme labels prédits. La figure 2 présente l'architecture du modèle pour cette approche. Le token [CLS], la sortie finale des couches transformeurs, contient une représentation du texte riche en informations. L'objectif de cette architecture est de pouvoir extraire à partir de ce token, et de l'état caché de la phrase qu'il contient, des critères ou des informations sur le nombre de sujets distincts présents dans le texte. Des critères qui serviront au calcul du paramètre.

Couche de seuillage (Threshold Layer TL)

La deuxième approche proposée se caractérise par l'ajout d'une couche dense à l'aval du classifieur, pour un total de 𝐿 = 3 couches, ayant 𝑛 𝑦 neurones pour correspondre à la dernière couche de classification du modèle. Cet ajout a pour but de faire rapprocher les valeurs des activations finales le plus possible de 1 dans le cas de la présence du label, ou d'une valeur nulle dans le cas contraire. Par conséquent, le seuil trivial de 0, 5 peut être utilisé comme seuil pour la classification.

L'ajout de cette couche pourrait avoir comme effet l'augmentation du rappel du classifieur car plusieurs activations des labels non présents ne dépasseront plus le seuil de classification défini du fait qu'elle se rapprocheront le plus possible de 0. Un gain en précision peut aussi être espéré du fait que les activations des labels présents seront renforcées et mises plus en avant par rapport aux activations des labels non pertinents.

Pour cette approche, nous utilisons deux optimiseurs, un premier qui englobe et optimise toutes les couches du transformeurs ainsi que les deux premières couches du classifieur, et un autre dédié à l'optimisation de la dernière couche que l'on a rajoutée. La fonction d'erreur utilisée est la même pour les deux parties du classifieur, la BCE en l'occurrence. L'architecture finale du classifieur est présentée dans la figure 3 5 EXPÉRIMENTATIONS Nous présentons dans cette section les résultats de l'évaluation de plusieurs modèles de langue transformeurs, principalement BERT et ses variantes, sur trois jeux de données de textes multilabels, dont le jeu de données français "HAL-Dataset" que nous avons conçu et mis à disposition. Nous comparons les différentes méthodes citées, ie. les méthodes de seuillage ainsi que les alternatives proposées à des approches de références, le tout mis en perspective avec des résultats cibles optimaux (approches oracles).

Modèles de langue évalués

Pour l'évaluation des méthodes proposées, nous utilisons la version base de BERT, avec 12 couches transformeurs et une taille du vecteur d'embeddings de 768, ainsi que quelques-unes de ses variantes :

• La comparaison des différents modèles de langue nous semble intéressante pour pouvoir évaluer les performances de nos approches ainsi que leur réutilisabilité et leur transposabilité sur différentes architectures de réseaux de neurones.

C (1) C (2) C (0) ([CLS])

Corpus de textes utilisés

Comme nous l'avons déjà signalé, aucun LeaderBoard dédié à cette tâche n'existe. On retrouve peu de corpus multilabels utilisés d'une manière fréquente dans la littérature pouvant servir à l'évaluation et la comparaison des modèles, et ceci d'autant plus pour la langue française. Pour y remédier, nous avons constitué notre propre corpus de résumés d'articles scientifiques écrits en français à partir de HAL, corpus que nous mettons à disposition de tous.

Dans cette section, nous fournissons des détails concernant les différents jeu de données utilisés4 pour l'évaluation des différents modèles :

• HAL-Dataset est un jeu de données en français que nous avons extrait de la plateforme d'archives ouvertes "HAL". Il contient les résumés de publications scientifiques de trois domaines (mathématiques, physique et informatique), publiées entre 1950 et 2020. L'extraction de ces résumés a été faite grâce à l'outil mis en disposition par HAL 5 , en ne gardant que les articles pour lesquels le champs "résumé" français est présent. Ce qui représente 12 430 documents répartis sur 194 classes différentes, ici découpés en jeux d'entraînement, de validation et de test;

• Reuter-215786 est une collection d'articles du fil d'actualités de Reuters de l'année 1987 et publiée à l'année 1990. C'est un jeu de données qui a beaucoup été utilisé pour évaluer les modèles pour la CMLT de textes. Un article peut appartenir à un ou plusieurs domaines parmi 90;

• AAPD (ou ArXiv Academic Paper Dataset) est, comme pour le jeu de données "HAL-Dataset", une collection de la section "Résumé" (abstract) de plusieurs publications scientifiques. Un article scientifique peut avoir une ou plusieurs classifications parmi 54 classes. On utilise la même répartition entraînement, validation et test que [START_REF] Yang | SGM: Sequence Generation Model for Multi-label Classification[END_REF]].

Le tableau 1) et la figure 4 présentent plus en détail les différentes caractéristiques de ces jeux de données.

Méthode d'évaluation

Nous allons comparer les deux approches proposées ainsi que l'application des méthodes de seuillage aux transformeurs à des méthodes plus transparentes sur les critères de sélection, mais aussi avec des adaptations des modèles d'apprentissage profond à la classification multilabels de texte. Nous proposons aussi de comparer l'ensemble de ces méthodes à plusieurs bornes supérieures qui représentent les résultats optimaux que l'on peut atteindre. des critères de classification interprétables, d'apprentissage machine, en utilisant les pondérations TF-IDF des documents comme entrées :

Approches de références. Nous proposons dans un premier temps une comparaison avec des approches non-neuronales, avec

• Les arbres de décision en utilisant le critère "Gini" et sans imposer une profondeur maximale des arbres. Le nombre minimal utilisé pour les échantillons est de 2;

• Random Forest avec les mêmes paramètres utilisés dans la méthode précédente;

• le Bagging en utilisant les arbres de décision comme estimateur prinicipal (au nombre de 10);

• le GradientBoosting avec la régression logistique comme fonction d'erreur et une cadence d'apprentissage de 0,1;

• Support Vector machine (SVM) en utilisant RBF comme noyau et un paramètre de régularisation de 1,0.

Nous prenons aussi des approches neuronales comme éléments de comparaison pour l'évaluation de nos approches :

Résultats

Dans cette partie, nous présentons les performances de toutes les approches citées dans les sections précédentes, testées sur les différents transformeurs présentés dans la section 5.1. Nous proposons les notations suivantes pour ces approches :

• "𝑆𝐺𝑂" pour la méthode du Seuil Global Optimal (cf. section 3.2.1);00

• "𝑆𝐼 " pour la méthode Seuil individuels (cf. section 3.2.2);

• "𝑁 𝑃𝐴" pour désigner l'approche des N plus grandes activations (cf. section 4.1);

• "𝑇 𝐿" pour dénoter l'approche "couche de seuillage" (cf. section 4.2).

Les approches oracles quant à elles seront désignées en ajoutant

𝑜𝑟𝑎𝑐𝑙𝑒 à la suite des approches concernées : 𝑆𝐺𝑂 𝑜𝑟𝑎𝑐𝑙𝑒 , 𝑆𝐼 𝑜𝑟𝑎𝑐𝑙𝑒 et 𝑁 𝑃𝐴 𝑜𝑟𝑎𝑐𝑙𝑒 . La longueur maximale des séquences considérée est de 512 tokens ainsi qu'un batch size de 8, et ce pour tous les jeux de données. Les tableaux 2 et 4 présentent les scores de micro-F1 (avec précision et rappel) et Accuracy pour le jeu de données de test des corpus en anglais et français respectivement. Les tableaux 3 et 5 présentent les optimaux à atteindre des différentes approches pour les corpus en anglais et celui en français. Les résultats des méthodes de seuillage ainsi que les architectures proposées ont été obtenus à partir des versions base des transformeurs utilisés, qui diffère de la version large de part le nombre des couches transformeurs (12 pour Architectures Transformeurs pour la classification multilabels de textes BDA 2021, 25-28 octobre, 2021, ENS, Paris Pour le corpus AAPD, les méthodes de seuillage ainsi que l'approche TL réussissent à obtenir de bonnes performances comparées aux autres méthodes, mais le modèle 𝐷𝑜𝑐𝐵𝐸𝑅𝑇 𝑙𝑎𝑟𝑔𝑒 reste le plus performant parmi toutes les approches étudiées. La nature complexe du vocabulaire scientifique de ce corpus souligne l'apport que peut avoir l'augmentation de la taille des modèles transformeurs (rajout de plusieurs couches et augmentation de la taille des embeddings).

L'approche SI 𝑜𝑟𝑎𝑐𝑙𝑒 est la plus performante des approches oracles étudiées. En effet, le calcul d'un seuil individuel pour chaque label à partir du jeu de test conduit vers un optimal général pour toutes les Architectures Transformeurs pour la classification multilabels de textes BDA 2021, 25-28 octobre, 2021, ENS, Paris classes qui dépassent l'optimal de la méthode SGO. Mais cela n'est pas le cas pour son équivalent expérimental. SGO reste la méthode qui s'approche le plus de son optimal théorique (cf. tableaux 3 et 2).

Chose qui peut être expliquée par le fait que pour la méthode SI plusieurs seuils doivent être calculés pour chaque label à partir du jeu d'entraînement, ce qui ne garantit par un optimal général sur l'ensemble des classes pour le jeu de test. Cet effet est accentué si le nombre de classes est grand. Pour l'optimal théorique de la méthode NPA, fournir le nombre effectif de labels pertinents pour une instance permet de considérer présents de nouveaux labels, ce qui augmente le taux de vrais positifs et baisse celui des faux négatifs. Mais cela a pour effet d'augmenter aussi le risque de faux positifs car ces nouveaux labels sont dans certains cas des prédictions non valides. Les instances pour lesquelles cette approche réduit le nombre de labels précédemment prédits sont rares. Donc le score micro F1 reste inchangé ou peut baisser par rapport aux optimaux théoriques des approches de seuillage. D'autre part, une augmentation considérable de l'exactitude est constatée, c'est d'ailleurs l'approche qui réussit à obtenir les scores d'exactitude les plus élevés (cf. tableau 3 et 5). L'implantation effective de cette approche quant à elle n'a pas permis d'obtenir les même performances que son optimal théorique. L'état caché de la phrase contenu dans le token [CLS] n'est peutêtre pas suffisant pour le calcul du nombre de classes présentes. Dans le futur, l'exploitation des scores d'attention obtenus dans les différentes couches du modèle pourrait être une méthode plus efficace pour accomplir cette tâche.

On note aussi que les deux architectures proposées obtiennent des scores de micro-précision plus élevés que les approches de seuillage. Pour l'approche NPA, cela est dû au fait que la sélection des labels est réalisée suivant l'approximation du nombre de classes calculé. Pour TL cela peut être dû au fait que les valeurs des activations des labels considérés comme présents sont accentuées, contre l'atténuation des labels considérés comme non pertinents.

Les mêmes tendances sont observées pour notre corpus de texte en français "HAL-Dataset". Les méthodes de seuillage obtiennent les scores micro-F1 les plus élevés, 74,47 pour SGO et 74,06 pour SI, (cf. tableau 4) suivies de l'architecture TL avec un score de 73,38. Un score proche des méthodes précédentes avec une architecture qui ne requiert pas une phase de recherche de seuils optimaux.

On note tout de même que l'approche NPA, que ce soit l'optimal théorique ou l'implantation expérimentale, n'est pas aussi performantes que les autres méthodes. Cela pourrait être dû à la difficulté de l'apprentissage du nombre de label compte tenu du déséquilibre du jeu de données. Environ 82% des instances n'ont qu'un seul label (cf. figure 4).

DeBERTa est la variante de BERT la plus performante parmi tous les modèles évalués, les changements qu'apportent cette variante compte tenu de l'ajout de l'information concernant la position relative du mot par rapport à la phrase, semblent améliorer les performances de BERT. Cette amélioration du rendement vient au détriment de la vitesse d'entraînement et d'inférence du modèle qui devient plus lent que les autres variantes. DistilBERT quant à lui obtient des résultats au même niveau que sa version originale, malgré sa taille réduite (moins de couches transformeurs). La distillation des connaissances semble être une méthode efficace pour pallier à l'inconvénient majeur des transformeurs et des réseaux neuronaux : la nécessité d'un temps d'entraînement très élevé.

Pour la tâche de classification multilabels de texte, RoBERTa n'est pas aussi performant que les autres variantes. Cela peut être dû à l'absence de la partie "prédiction de la phrase suivante", une partie qui peut avoir une importance pour la classification multilabels, dans la mesure où elle peut permettre au modèle d'apprendre la manière dans les idées d'un même domaine se succède et de pouvoir faire la différence entre plusieurs champs lexicaux.

CamemBERT qui est une variante basée sur RoBERTa, hérite des mêmes problématiques face à la classification multilabels, et se voit dépassée par FlauBERT dont la force réside dans le fait qu'il soit entraîné sur des corpus très variés, avec des styles d'écritures diverses.

On note aussi que les SVM et les forêts d'arbres décisionnels obtiennent les scores de micro-précision les plus élevés, au détriment du taux de rappel, faisant ainsi baisser le score micro F1. Mais la précision n'est pas un facteur suffisant pour la mesure des performances. SVM peut être considéré comme l'approche non neuronale la plus performante en vu de son score d'exactitude élevé, mais qui reste en dessous des autre méthodes testées.

CONCLUSION ET TRAVAUX FUTURS

Les modèles de langue à base de transformeurs surpassent les autres architectures neuronales profondes et constituent une base solide adaptable pour une multitude de tâches de traitement automatique des langues et la classification de textes, c'est la direction que nous avons suivie dans cette étude.

Tout d'abord, nous avons testé et montré dans cet article que les approches de seuillage sont très performantes pour la classification multilabels. Le calcul d'un seuil global obtient des résultats plus élevés que le calcul d'un seuil individuel pour chaque classe. L'optimisation faite sur chaque classe ne garantit pas un optimal général pour tous les labels. Nous avons par la suite proposé des modifications sur l'architecture des transformeurs. Ceci par le rajout d'une couche supplémentaire, avec un nombre d'activations égal au nombre de classes, à l'aval du modèle pour s'affranchir d'une optimisation sur les seuils. Une approche qui, en moyenne, est aussi performante que les approches de seuillage. L'étude des optimaux à atteindre a montré que l'utilisation du nombre de classes pour la sélection des labels pertinents augmente de façon considérable les performances de la classification multilabels. Cependant, la différence entre ces optimaux et les résultats effectifs de nos expérimentations montrent que notre proposition doit être améliorée dans le cas des jeux de données déséquilibrés. Au final les deux familles d'approches, seuillage et modification de l'architecture des transformeurs, sont des méthodes qui améliorent les performances des réseaux d'apprentissage profond pour la classification multilabels de texte.

La langue des corpus de texte, anglais pour AAPD et Reuters, ou français pour le corpus HAL-Dataset que nous avons construit, ainsi que leur nature (article scientifiques ou dépêches journalistiques) ne semblent pas être des facteurs qui impactent les performances des approches proposées. Ce sont d'ailleurs des approches qui peuvent être utilisées pour tout problème de classification multilabels. Dans le contexte applicatif de nos travaux de thèse, nous construisons un jeu de données à partir des mails clients de l'agence, et sur lequel nous testerons toutes ces approches.

Chaque variante de BERT cherche à améliorer les aspects contraignants de ce modèle. DistilBERT, malgré sa taille réduite, obtient des résultats aussi élevés que la version originale. DeBERTa se positionne comme étant la variante la plus performante, en compagnie de FlauBERT qui dépasse CamemBERT, la version basée sur RoBERTa dont les performances restent derrière les autres variantes.

Nous avons montré l'intérêt réel que peuvent avoir les approches d'exploitation des activations des couches de sorties. D'autres méthodes d'adaptation des réseaux neuronaux pour la classification multilabels peuvent être explorées, dans la mesure où les seuils de détection peuvent être des paramètres appris du modèle lors de la phase d'entraînement. Des améliorations peuvent être faites sur les architectures alternatives au seuillage proposées, notamment la recherche d'une méthode plus efficace pour le calcul du nombre de classes présentes pour la méthode NPA ainsi que l'augmentation du nombre de couches de seuillage pour l'approche TL. Toutes ces approches peuvent être utilisées pour l'optimisation de tout modèle d'apprentissage profond. En ce qui concerne le domaine d'application, la classification multilabels est une tâche pertinente dans le monde industriel. Cependant la CMLT n'est pas une tâche si fréquente et on regrette qu'elle ne figure pas parmi les comparatifs les plus en vue comme GLUE.

IOPE: Interactive Ontology Population and Enrichment Guided by Ontological Constraints

Shadi Baghernezhad-Tabasi 1 , Loïc Druette 2 , Fabrice Jouanot 1 , Celine Meurger 2 , Marie-Christine Rousset 1,3

1 Université Grenoble Alpes, CNRS, LIG, Grenoble, France, 2 Université Claude Bernard Lyon 1, SAMSEI, Lyon, France, 3 Institut Universitaire de France, Paris, France 1 firstname.lastname@univ-grenoble-alpes.fr, 2 firstname.lastname@univ-lyon1.fr

ABSTRACT

In this paper, we focus on the construction of specialized ontologies that capture skills of experienced experts in a particular domain with the goal of sharing them with a larger community of trainees or less experienced experts in the domain. Our main contribution is the automatic construction of a Graphical User Interface (GUI) named IOPE built from the ontological constraints of an input ontology, as the support for the controlled update process of the considered ontology. The resulting GUI functions as a guidance for the experts with no knowledge of OWL/RDFS, which enables them to easily explore and update their ontologies. We illustrate the functionality of IOPE on an ontology for simulation-based medical workshops called OntoSAMSEI.

INTRODUCTION

Ontologies are the backbone of many information systems that require access to structured knowledge. By their very nature, realworld ontologies are dynamic artifacts that evolve both in their structure (the data model) and their content (instances). Keeping them up-to-date is a critical operation for most applications which rely on semantic Web technologies. Ontology updates encompass both enrichment and population. Ontology updates are often performed manually, as the non-documented knowledge of the domain expert is required to be taken into consideration. However, this manual updates put burden on the experts and render the whole ontological ecosystem inefficient. In this paper, we advocate for an alternative and more effective approach, and propose to handle updates automatically through a few interactions with the expert, using a Graphical User Interface (GUI).

The challenges associated to interaction-based automatic updates are two-fold: (𝑖) While ontologies are typically represented in the form of graphs, it is inherently difficult and counter-intuitive to provide a graphical graph-based representation of ontologies for the consumption of experts. While there exist several methods to visualize a graph structure [1,2], the outcome is often hard to digest by domain experts. (𝑖𝑖) It is unclear how experts should perform ontology updates through the interactions, without the prior knowledge of the formal syntax and the semantics of ontology languages. In this paper, we demonstrate IOPE (Interactive Ontology Population and Enrichment), a framework for the automatic construction of a GUI using prefilled Web forms. We leverage Web forms as a natural interaction means to tackle the challenge of counterintuitive ontology representations. IOPE generates the Web forms from ontological constraints, which support the controlled update process of a given ontology, and prefills the generated forms. While IOPE is generic and can be applied to ontologies from a variety of domains, we employ an ontology called OntoSAMSEI [3] for demonstration purposes, whose content helps the domain experts design teaching units for learning skills in simulation-based Medicine. OntoSAMSEI's IOPE GUI is accessible via the following link: http://iope.tabasi.info (in French).

INTERACTIVE ONTOLOGY UPDATE

Our approach consists of transposing the RDF data and the ontological constraints of a given domain ontology into a GUI named IOPE GUI. It functions as a guidance for domain experts to easily explore the ontology and update it through interactive graphical widgets. The input entered by domain experts through the IOPE BDA 2021, Paris, 25-28 octobre Baghernezhad-Tabasi et al.

Demo form2

SimulaDon training session of Port-a-cath placement

Equipment and supplies: (*)

Other :

Provide the label(s) (separated by a comma).

Fenestrated disposal drape

Select exis@ng item(s) or enter new item(s):

Enter the new item(s) (separeted by a comma).

Resources

Sterile compress (Bandage material) (*) Protec@ve supplies (*)

Disposable drape

Simulator-type resources: (*)

Venous-access chest simulator manikin (*) Other :

Provide the label(s) (separated by a comma).

Warning! To save the informa/on entered on this page, you must click on "Save".

Save

IOPE:label

Enter the new item(s) (separated by a comma).

IOPE:placeholder

Mapping rule

Figure 2: An instance of a pre-filled Web page generated by applying the mapping rules to ontological constraints, and the transformation of interactions with the binding rules.

GUI is transformed into RDF triples that must be verified by an ontology engineer before being added effectively in the domain ontology. Figure 1 is an overview of our interactive IOPE system. In the following, we describe the components of IOPE workflow.

Input: A domain ontology is the input for GUI construction. The ontological constraints of the input ontology have been automatically saturated by a reasoning algorithm, detailed in [4].

IOPE GUI:

The GUI consists of automatically generated pre-filled Web pages which represent domain ontological constraints. We specify a set of 16 mapping rules to generate pre-filled Web pages [4]. The domain expert is guided using the generated pages, where she interacts with the GUI to explore and update the ontology through interactive graphical widgets. Those interactions must be bound to RDF data corresponding to new instances or new constraints submitted for populating or enriching the domain ontology. We specify a set of 9 binding rules to generate RDF graphs from user entries [4]. The resulting RDF graphs should be verified by an ontology engineer before adding to the domain ontology.

Output: The output is the updated RDF data and the updated ontological constraints.

Figure 2-right illustrates one of the resulting pre-filled Web pages generated by applying the mapping rules to OntoSAMSEI's ontological constraints, to represent information about the workshop required resources, e.g., equipment and supplies, and simulator-type resources. At the top-left of the figure, an ontological constraint is mentioned in Turtle format 1 , conveying that at least one equipment of type "protective supply" is mandatory for this workshop. Obviously, the Turtle format is difficult to be comprehended by users without OWL/RDFS knowledge. The graph-based result of a mapping rule applied on the constraint is shown in the middle-left part of the figure, whose HTML implementation is highlighted with a red-border square on the right side. The user interactions with the pre-filled Web page are highlighted in blue, where the educator selects a sub-class Disposable Drape from the Protective Supplies hierarchy, and picks the instance Simple disposable drape from the provided list of instances. The interactions are transformed into RDF graphs using the binding rule shown in the bottom-left part of the figure. This transformation results in two RDF triples which declare relations between an instance of the workshop and the selected instance, and between the selected instance and its class.

Résumés des articles courts 1 INTRODUCTION

Today, we live in an increasingly digital society. Thus, preservation of digital data has emerged as an important problem. In order to preserve digital data, it is necessary to first store the data safely over a long time frame. Historically, this task has been complicated due to several issues associated with digital storage media. All current media technologies suffer from density scaling limitations resulting in storage capacity improving at a much slower rate than the rate of data growth. All current media also suffer from media decay that can cause data loss due to silent data corruption, and have very limited lifetime compared to the requirements of digital preservation. In project OligoArchive, we are exploring a radically new storage media that has received a lot of attention recently-Deoxyribo Nucleic Acid (DNA). DNA possesses several key advantages over current storage media.It is an extremely dense three-dimensional storage medium, very durable and can last millennia in a cold, dry, dark environment. In this work, we provide an overview of the ongoing collaboration between the Danish National Archive and project OligoArchive in demonstrating a holistic solution for long-term preservation of culturally significant data using DNA.

DESIGN

The Danish National Archives is a knowledge center documenting the historical development of the Danish society. A huge part of their work includes the preservation of digitally created and retrodigitized data securely and cost-effectively. As the vast majority of data in the Danish public sector are organized as databases with or without files in various formats, the focus has been on archiving these data in a standardized, system-independent and cost efficient manner. As a result, the archive has implemented a Danish version of the SIARD format named SIARD-DK for storing of such data.

SIARD is an open format, designed for archiving relational database snapshots in a vendor-neutral form and is used in the CEF building block "eArchiving".

The archival material used for this work consists of selected hand-drawings made by the Danish king Christian IV and its related database information in SIARD format. The first step in preserving data is taking a snapshot of the database and creating an SIARD-DK Archival information Package (AIP). In the creation of this particular AIP, the digitized image was converted to TIFF format. Information relevant to the images stored in a database such as the preservation format of the files, their title, creator and original size, descriptive information, etc., was extracted and packaged together with relevant documentation in the AIP-format. The resulting AIP is a single ZIP64 file that internally contains the TIFF images, in addition to XML and XSD files that store the schema of the archive and metadata information. Traditionally, the SIARD file is stored on tape, which is internally organized as a sequence of blocks. Thus, the main research challenges are (i) developing a reliable block abstraction for DNA, (ii) developing a serialization and coding strategy for mapping the binary SIARD file to DNA blocks.

DNA data storage pipeline

The end-to-end DNA media storage pipeline is presented in Figure 1. In the rest of this section, we will provide an overview of both the write path that takes as input the SIARD zip file and stores it in DNA, and the read path that restores back the zip file from DNA.

Write Path.

In order to store the archive on synthetic DNA, the zip file is first encoded from binary into a quaternary sequence of oligonucleotides, and then synthesized to generate synthetic DNA. During encoding, the file is read as a stream of bits and pseudo randomized. Randomization is applied to reduce the number of homopolymer repeats within oligos, and similarity across oligos when generating the oligos at a later stage. After randomization, error correction encoding is applied to protect the data against errors. We use large-block length Low-Density Parity Check (LDPC) codes with a block size of 256,000 bits as the error correction code, as it has been shown to be able to recover data in the presence of intra-oligo errors, or even if entire oligos are missing. We configure LDPC to add 10% redundancy to convert each sequence of 256,000 bits into 281,600 bits with data and parity. Each 281,600 bit sequence is then used to generate a set of 300-bit sequences, where each 300bits is composed of 281 data bits and a 19-bit index that is used to order the sequences. Each 300-bit sequence is then passed to a constrained code that converts it into an oligonucleotide sequence.

We provide a practical overview of the constrained code here, deferring rigorous mathematical definition to future work. The constrained code is essentially a finite state machine that views each oligo as a sequence of short symbols that are concatenated together. In our current configuration, the constrained code breaks up each 300-bit sequence into a series of ten 30-bit integers. Each 30-bit integer is fed as input to a deterministic finite state machine that takes as input the previous 16-nucleotide sequence, and a set of constraints (homopolymer repeat, GC ratio, etecetera) that each symbol must meet and produces a valid 16-nucleotide sequence corresponding to the 30-bits as output. Thus, each 300-bit sequence is encoded as concatenation of ten such symbols, each with a length of 16 nucleotides, leading to an oligo that is 160 nucleotides long. We would like to explicitly point out here that the length of an oligo is a configurable parameter.

Read Path.

To retrieve back the SIARD archive, the DNA is sequenced in order to retrieve back the nucleotide sequence of oligos. As mentioned before, sequencing produces noisy copies of the original oligos that can contain insertion, deletion, or substitution errors, which are referred to as reads. In order to infer the original oligos from the reads, we use a consensus procedure. Concretely, we structure this process as sequence of three algorithms. First, we identify all pairs of strings that are similar to each other. As modern sequencers produce hundreds of millions of reads, this first task is an extremely computationally intensive due to use of edit distance as a metric for comparing strings. Thus, we have developed an efficient similarity join algorithm, called OneJoin, that exploits the fact that due to randomization during encoding, reads corresponding to the same original oligo are "close" to each other despite some errors and "far" from the reads related to other oligos. The results obtained from the join algorithm are then used to quickly identify clusters of strings that are similar to each other. Each cluster thus groups all reads belonging the same oligo. Finally, we apply a position-wise consensus procedure that uses multiple reads to infer the original oligo in each cluster using a sequence alignment procedure. We would like to point out here that not all oligos need to be correctly inferred. In fact, some original oligos might not appear at all in the inferred set, and other inferred oligos might have errors. We rely on the parity added by LDPC codes at a higher level to recover data despite these errors.

The inferred oligos are then passed to the decoder which reverses the encoding steps. The constrained code is first used to convert each 160nt oligo back into 300 bit sequences. The index stored in each 300 bits is used to reassemble bits back in the correct order. The LDPC decoder is then used to recover back data even if some bits were wrongly decoded, or some bits were zeroed out as corresponding oligos were missing. The decoded data is then derandomized to obtain a stream of bits that corresponds to the SIARD zip file.

EVALUATION

We provide a preliminary, simulation driven evaluation where we encode/decode the real dataset using our pipeline. The raw SIARD archive that is fed as input to our pipeline is 12.9MB in size. With redundancy added by LDPC, the resulting binary data to be stored on DNA is 14.19MB in size. We encode the SIARD archive generating 404,863 oligos, each with a length of 160 nucleotides. We then generate five million reads by using a short-read simulator tool, that adds random errors such as insertion, substitution, and deletion in each read to mimic the actions of an Illumina DNA sequencer. This corresponds to an average coverage of 11×, meaning that each oligo, on average is covered by 11 noisy copies. Using the consensus procedure described earlier, we obtain the inferred oligos using this simulated dataset. We then use the constrained code to convert these inferred oligos into 300-bit sequences, and reassemble them in order based on the 19-bit index. At this stage, we can have a situation where an oligo is missing but we rely on the redundancy added by LDPC to recover back the original archive.

CONCLUSION

In this work, we provided an overview of the ongoing collaboration between project OligoArchive and the Danish National Archive in using DNA to preserve culturally significant digital data. Building on prior work on molecular information storage and digital preservation, we presented a holistic, end-to-end pipeline for preserving both data and the meaning of data on DNA, and tested the pipeline using simulation studies.

Vers une modélisation du paysage médiatique français

Contexte

Avant de modéliser un domaine, il convient de définir son périmètre [1]. Celui-ci ne se limite pas aux médias traditionnels (presse écrite, télévision, radio) mais inclut aussi tous les nouveaux médias liés à Internet. Benoit Lafon a utilisé le concept de médiatisation pour élargir le périmètre «La médiatisation consiste en la mise en média d'individus, de groupes ou d'institutions par la construction de produits médiatiques formalisés, dans une visée stratégique, impliquant des pratiques collectives de consommation» [2, p163]. De nombreux chercheurs en sciences de l'information et de la communication ont qualifié les dimensions constitutives des médias. Force est de constater que le terme média renvoie généralement à cinq référents distincts (technique, contenu, organisation, modèle économique, usage) sur lesquels peut reposer la grille d'observation. En ce qui concerne les ontologies déjà existantes, Emilio Sanfilippo [3] a effectué un état de l'art assez général de celles dédiées aux entités d'information. Plusieurs sont spécialisées dans les systèmes documentaires (Dublin Core, CIDOC CRM, FRBR, PRESSOO, BibFrame…) mais aucune ne répond totalement à nos besoins de finesse de description et de diachronicité.

Grille d'observation

La grille d'observation détaille cinq aspects des médias. L'aspect technique décrit les supports, formats et moyens de diffusion. L'aspect contenu repose de son coté sur la ligne éditoriale du média. C'est elle qui définit le fond des contenus proposés, qui est lié au sens, ainsi que leur forme, qui est liée à la présentation. La presse dispose déjà de nombreux systèmes de classification, suivant la cible du public, la thématique, la périodicité et le périmètre. Il existe aussi un grand nombre de familles de presse qui proposent des classifications exclusives [4], tout comme pour la radio et la télévision. En revanche, pour Internet, il n'existe pas de famille officiellement reconnue. Nous pouvons nous inspirer de la littérature [5] pour proposer une taxonomie. L'aspect organisation recouvre le cadre légal dans lequel le média doit exercer son activité. Il est important de distinguer les éditeurs de contenu des éditeurs de services. L'aspect économique décrit quant à lui les modèles de financement des médias (lecteurs, annonceurs, subventions), le modèle d'économie de l'attention ainsi que les solutions adoptées par les médias face au bouleversement médiatique (optimisation des coûts, concentration des médias, diversification des supports et services…). Enfin l'aspect usage repose sur la finalité des messages transmis par les médias (intérêt social, politique et financier) qui peut être discernée à partir des genres de contenu et des types de producteurs d'information.

Modélisation du domaine médiatique

Le modèle doit décrire de manière homogène des médias très divers et tenir compte de contraintes spécifiques :  Niveau très fin de description (blog d'un site de presse).  Aspect diachronique (fusion de médias).  Notion de provenance (plusieurs familles de presse). plusieurs sortes de relations (en rouge) : des relations « partonomiques » (tout-partie) qui permettent de décrire finement une publication ; des relations associatives qui permettent d'associer plusieurs concepts entre eux ; des relations hiérarchiques (« est un ») qui peuvent décrire des liens d'appartenance pour définir une typologie. Les relations peuvent aussi être spécialisées en sous-relations. Pour terminer, les attributs (en bleu) s'appuient sur les différents aspects des médias que nous avons vus dans la grille. En ce qui concerne la modélisation du temps, il s'agit de poser un intervalle temporel sur chaque propriété.

Conclusion

Les journalistes professionnels n'ont plus le monopole de l'information, l'éditeur de contenu se voit concurrencé par des éditeurs de service, et les supports de diffusion se sont multipliés. Afin de pouvoir modéliser ce nouveau paysage médiatique protéiforme, il faut tout d'abord définir son périmètre, puis observer son fonctionnement, identifier les entités à décrire. La particularité du modèle obtenu repose sur un très fin niveau de description et sur l'évolution diachronique des entités. La démarche mise en place s'appuie sur trois spécificités : l'analyse très fine du domaine médiatique, l'utilisation de ressources disponibles sur le web (relations, classes, URIs) et le développement à la main de typologie à l'aide d'une liste d'autorité. Dans un futur travail, ce modèle devra être implémenté sous la forme d'une base de données ou d'une base de connaissances. La recherche diachronique sera une question importante à évaluer. The new privacy-protection regulations (e.g., GDPR) and smart disclosure initiatives in the last decade have boosted the development and adoption of Personal Data Management Systems (PDMSs) [1]. A PDMS (e.g., Cozy Cloud, Nextcloud, Solid) is a data platform allowing users to easily collect, store and manage into a single place data directly generated by user devices (e.g., quantified-self data, smart home data, photos) and data resulting from user interactions (e.g., social interaction data, health, bank, telecom). Users can then leverage the power of their PDMS to benefit from their personal data for their own good and in the interest of the community [2].

Consequently, the PDMS paradigm leads to an important shift in the personal data ecosystem since data becomes massively distributed, at the user-side. It also holds the promise of unlocking innovative usages. An individual can now cross her data from different data silos, e.g., health records and physical activity data. Moreover, individuals can cross data within large communities of users, e.g., to compute statistics for epidemiological studies or to train a machine learning model (ML) for recommender systems or automatic classification of user data. However, these exciting perspectives should not eclipse the security issues -user data must be kept private-and the right for any PDMS user to consent, or not, in participating in each computation.

Aggregation primitives (e.g., sum or average) are obviously essential to compute basic statistics on user data but are also a fundamental building block for machine learning algorithms. Thus, to enable such new usages, we need scalable, privacy-preserving protocols implementing data aggregation primitives with selective (i.e., consenting) participants. Ideally, the proposed protocol should provide an accurate result that fully takes advantage of high-quality data available in PDMSs. Efficiency (i.e., protocol latency and total load of the system) is of prime importance and the protocol should adapt to several contexts: the PDMSs could be limited by their communication speed or by their computation power. Finally, given the scale of such decentralized aggregation, such protocols must also be robust to node failures. To summarize, our goal is to propose an aggregation protocol for basic aggregate functions that fulfills the following properties:

• fully decentralized and highly scalable, with the number of participants.

• privacy-preserving, i.e., it protects the confidentiality of user data.

• accurate, i.e., it does not require a trade-off between accuracy and privacy.

• adaptable, i.e, it can adapt to a large spectrum of computation selectivity values (reflecting the subset of contributor nodes) and system configurations (network and cryptographic latency).

• reliable, i.e., it handles node failures or voluntary disconnections.

Un cadre orienté graphe bien fondé pour le résumé de bases de données en logiques de description Potential users need to understand a dataset in order to decide if it is useful for their goal. While some datasets come with a schema and/or documentation, this is not always the case. Data summarization or schema inference tools have been proposed, specializing in XML, or JSON, or the RDF data models. In this work, we present a dataset abstraction approach, which (𝑖) applies on relational, CSV, XML, JSON, RDF or Property Graph data; (𝑖𝑖) computes an abstraction meant for humans (as opposed to a schema meant for a parser); (𝑖𝑖𝑖) integrates Information Extraction data profiling, to also classify dataset content among a set of categories of interest to the user. Our abstractions are conceptually close to an Entity-Relationship diagram, if one allows nested and possibly heterogeneous structure within entities.

Efficiently identifying disguised nulls in heterogeneous text data

ABSTRACT

Digital data is produced in many data models, ranging from highly structured (typically relational) to semi-structured models (XML, JSON) to various graph formats (RDF, property graphs) or text. Most real-world datasets contain a certain amount of null values, denoting missing, unknown or unapplicable information. While some data models allow representing nulls by special tokens, socalled disguised nulls are also frequently encountered: these are values that are not syntactically speaking nulls, but which do, nevertheless, denote the absence, unavailability or unapplicability of the information.

This paper describes our ongoing work toward detecting disguised nulls in textual data, encountered in ConnectionLens graphs. Driven by journalistic applications, we focus for now on large, semistructured datasets, where most or all data values are freeform text. We show that the state-of-the-art methods for detecting nulls in relational databases, mostly tailored towards numerical data, do not detect disguised nulls efficiently on such data. Then, we present two alternative methods: (i) leveraging Information Extraction, and (ii) text embeddings and classification. We detail their performance-precision trade-offs on real-world datasets.

The paper is available at https://hal.inria.fr/hal-03347947v1

Using projection to improve Differential Privacy on RDF graphs

ABSTRACT

Differential privacy is one of the most popular and prevalent definitions of privacy, providing a robust and mathematically rigid definition of privacy. In the last decade, adaptation of differential privacy to graph data has received growing attention. Most efforts have been dedicated to unlabeled graphs, homogeneous graphs, while labeled graphs with an underlying semantic have been mildly addressed.

In this paper, we present a new approach based on graph projection to adapt differential privacy to edge-labeled directed graphs, i.e. RDF graphs, while reducing query sensitivity. We propose three edge-addition based graph projection methods that transform the original RDF graph into a graph with bounded degree, bounded out-degree, and bounded typed-out-degree and characterize their influence on differential privacy. We thus propose a general method to expand the domain of any differentially private algorithm from graphs with bounded (out/typed-out) degree to any arbitrary RDF graph. We illustrate our approach under a realistic tweeter use-case.

ACKNOWLEDGMENT

Work supported by the French National Research Agency, under grant ANR-18-CE23-0010

CONTEXT

In the last decades, the data has become a valuable property for organizations and is considered as digital oil in the big data environment. To make capital from this precious product, proper equipment is required [6]. Traditional data management tools have inadequacies in gathering, storing, processing, and visualizing all types of data in an integrated manner in the big data arena. Therefore, the term " Data lake " has been emerged to address the shortcomings flaws and meet all the challenges related to the data lifecycle [10].

Data lakes are the developed, affordable, and agile generation of centralized data management systems that provide plenty of faculties to conduct the procedures of storage and knowledge mining from a huge amount of heterogeneous data [4,9,12]. However, welcoming all kinds of data in their native formats increases the risk of saturation with unmanageable or useless data; a phenomenon is known as "data swamp"; and threatens the security of sensitive data. For this reason, data management strategies and architecture design are more highlighted in data lake productivity. The architecture of the data lake and the administration regulations could have significant impacts on the efficiency of data lake performance. Thus, an optimized architecture under proper managerial disciplines enhances the data lake credibility and reinforces its reliability as a new component of the information systems to support decision-making processes in the organizations.

CHALLENGES

Data lake architecture design and data management are problematic issues for the implementation of an efficient data lake infrastructure. Based on these requirements, many studies in the field of the data lake architecture design have been conducted in parallel with the technical implementation [5, 7-9, 11, 12]. Despite many types of researches on the data lake architecture and with regard to their cons and pros, optimization of the data lake structure and performance based on managerial and mathematical viewpoints has been less considered. For this reason, we suggest logistical approaches like product lifecycle management and hybrid decisionmaking strategies (like facility location-allocation problems) based on supply chain management principles to design and optimize the data lake architecture. The significant principle of supply chain management is to minimize the total costs related to the flow of products in such a way that profitability of the chain and quality of the service requirement, will be maximized. We intend to implement this principle for data lake management due to the new proposed architecture and imitated strategies.

METHODS

Since the data could be considered as a valuable product, we can imagine that a data lake performs like a logistic system that manages the data throughout its life cycle. This viewpoint brings about a great deal of systematic and managerial strategies to develop data lake architecture and gain the integrated manner to manage and govern the data in a cost-effective platform. Based on this requirement, the supply chain is one of the well-known logistic systems that present a systematic view of logistic parties who are integrated into a unified network to produce a commodity or provide a service [1,2]. To design the profitable supply chain network, each level of this chain is managed by tactical and strategic strategies. Thus, the supply chain management strategies prepare the suitable guidelines to design and manage the data lake architecture in general or in detail scales.

The processes of designing a data lake architecture are related to positioning the different components like data ingestion, data storage, data process, and data access stages and defining the proper strategies and protocols to govern the data like metadata management or data democracy. For this reason, the data lake platform based on systematic definitions and network design concepts could 37ème Conférence sur la Gestion de Données -Principes, Technologies et Applications, BDA 2021, Derakhshannia and Laurent be an effective step in the evolution of data lake architecture. Regarding the analogy of data lake and supply chain, we consider the data like a product or service that should be monitored through several stages in the data lake architecture from data entering until data consumption. With respect to this point of view, we can benefit from some management tools to improve data lake functionality. For example, we can use the policies of product lifecycle assessment that is employed in logistic systems, for data governance in data lake or hybrid decision-making problems that are essential in supply chain network design, for implementation and optimization of the data lake platform.

As figure 1 shows the simple analogy of supply chain structure and data lake architecture, data are supplied, stored, manipulated, monitored, and delivered in data lake as a product that is managed throughout the supply chain. In this architecture, data are produced and supplied from different sources and are entered in the data lake by the ingestion stage, then they are stored in their raw formats at the storage level, and finally, they are sent to the processing stage for further procedures based on users requirements. In this architecture, each level of data life cycle could be managed by mimetic logistical patterns. For example, the ingestion strategies are related to the optimal decisions about metadata management and data modeling, like supply and product design management in the supply chain. The storage strategies concentrate on selecting cost-effective storage strategies (single-store systems or multi-store systems) and data integration, just like decision-making about the number, the location, and the type of the warehouses and inventory management in the supply chain. The process strategies are the vital decisions that impact on quality of data and veracity of extracted knowledge. Therefore, the main goal of process strategies is related to choose the data processing methods that prepare the data with the fastest time and the least cost possible for data queries. Based on this requirement, the hybrid decision-making models like location-allocation problems; that bring about the best solution to optimize the supply chain networks [3]; could be a logical solution to design the affordable data lake architecture. For instance, we can use the techniques of supply chain network design (like optimization mathematical models) to determine the structure of data lake with a variety of strategic decisions such as determining the number of proper processing jobs, tactical decisions like data governance all over the data lake just like product quality assessment in the supply chain, and operational decisions like fulfilling user demands. The main objective of designing the logistical data lake architecture is to minimize further costs related to the data ingestion, storage, and processing and maximize the level of data lake performance.

CONCLUSION

In the direction of mentioned goals, we focus on data lake architecture design due to the mathematical optimization models that are inspired by hybrid problems in supply chain network design. The accomplished studies showed that these interdisciplinary methods smooth the path of presenting data lake optimization models and guarantee to obtain the affordable data lake architecture as a logistic system. In recent years, JSON has become the de facto standard data interchange format, and is now widely used for exchanging data between web applications and remote servers, for exporting and importing data, as well as inside complex ML pipelines for combining different stages, as in Google TFX [8].

Despite its great popularity, there is no consensus about a standard schema language for JSON yet. Indeed, in many cases, JSON datasets come without a schema, and the end user or application has the duty to infer or guess a new schema, if required. In many other cases, however, several and vastly different schema languages are used for describing the structure of JSON data, ranging from Apache Avro [3], to the MongoDB internal schema language [5], and to JSON Schema [9].

Differently from what happened with XML, whose standard schema languages (DTDs and XML Schema) reached quickly a wide diffusion, JSON Schema is not being adopted at the same pace. Many reasons are slowing down its adoption, but, according to our observations, a major obstacle is the fact that, while extremely powerful, JSON Schema is -frankly -hard to use. Indeed, a schema is a logical combination of implicative assertions, and some of them may produce side effects on previous ones.

As a consequence, leaving the realm of plain vanilla schemas may expose the programmer to many risks, such as the definition of a schema with unintended semantics, or one that is even empty.

Example 1.1. Consider the following schema.

{

"type": "object", "properties": { "x": { "type": "integer" } }, "required": [ "x" ] } This schema declares that all instances are JSON objects, and that each object has a mandatory member whose name is 𝑥 and whose type is 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 . This schema, however, does not impose further constraints on object values; therefore, an object may also have supplementary and unconstrained members.

Example 1.2. Consider now the following schema, differing only in the next-to-last line.

{

"type": "object", "properties": { "x": { "type": "integer" } }, "not": { "required": [ "x" ] } } One may assume that this specifies that 𝑥 is "not required", hence is optional. However, given the semantics of JSON Schema, negating a required member does not make it optional: indeed, the final effect is to actually forbid the presence of the member, hence excluding any JSON object having a member whose name is 𝑥 (this example is inspired by a discussion on Stack Overflow [1], where the confusing effect of this schema is testified).

Given the complex and non-trivial interplay between schema assertions, designing a rich yet sound schema is challenging, especially when other powerful mechanisms of JSON Schema are involved, such as negation, mutual exclusion, recursion, union and conjunction, as well as array constraints controlling array length and content, possibly requiring uniqueness of elements.

Motivating Witness Generation. The state-of-the-art approach for exploring JSON Schema semantics is ultimately a manual trial and error: using a JSON Schema validator, a schema designer can test whether a JSON document is valid w.r.t. the schema. That is, the designer must come up with suitable witness documents.

Yet, in this demo, we present a tool capable of automatic witness generation. For instance, for the schema from Example 1.1, our tool generates the witness {"x": 0}, as any valid instance must be an object, where member 𝑥 is mandatory and integertyped. For Example 1.2, our tool generates the witness {}, since the empty object is valid. For the schema designer, this valuable feedback may well increase the overall productivity.

Moreover, upon the push of a button, the designer can generate further witnesses. In the example just discussed, the designer would be provided with {"0": null}. Thus, by interactive iteration, the designer ensures that he or she "gets it right".

Moreover, our tool allows the comparison of two schemas: for a witness that is valid w.r.t. the schema from Example 1.2, but not w.r.t. the schema from Example 1.1, the tool returns the JSON document {}. For the other way round, a witness is {"x": 0}. Again, the designer can request further witnesses, as needed.

Contributions. The goal of this demonstration is to showcase a tool allowing the schema designer to investigate the formal properties of a schema, and even to compare schemas. Our tool is based on our earlier contributions on algebraic manipulations of JSON Schema [6]. With our tool, the designer can:

• obtain an algebraic representation of the input schema;

• generate a witness for the schema, to verify whether the schema is empty or not, and to gain insights into the actual semantics of a given schema;

• exploit witness generation for checking whether a schema 𝑆 1 is a subtype of a schema 𝑆 2 , and hence, whether it represents a conservative and not disruptive evolution.

DEMONSTRATION OVERVIEW

Our demo can be tried online https://jsonschematool.ew.r.appspot. com/. Its setup includes two datasets: schemas from the JSON Schema Test Suite [2], a collection of small schemas that serve as unit tests for JSON Schema validators (and explore different operators), and real-world schemas from SchemaStore.org [4]. Naturally, our attendees may also formulate their own schemas. Typically, the user will first enter a JSON Schema document (or load one of the provided schemas), and then convert the schema (shown in the midsection of our screenshot) into our algebra (shown in the bottom section). Our algebra has been designed to be close to the original language, to be intuitive for practitioners. Yet different from the JSON Schema language, our algebra enjoys substitutability, that is, the semantics of an operator does not depend on its context, which eases manipulation.

The user may then choose to generate a first JSON witness. If the system finds no witness, it will alert the user that the schema is empty, otherwise, a witness is generated.

If there is a witness, the user can generate a further ("yet another") witness, that is different from all those previously seen. Alternatively, the user can edit the original JSON Schema, or directly the algebraic expression, and request that a new first witness is generated (disregarding witnesses already seen).

The schema designer can choose to convert back from the algebra to JSON Schema. Thus, the schema designer can interactively explore the semantics of a given schema, switch between the JSON Schema representation and the (often more compact) representation in our algebra, and iteratively revise the schema.

To allow interested demo attendees to inspect the internals of witness generation, as outlined in the previous section, our tool can also perform negation elimination on algebraic expressions. This feature would not be included in a tool targeted at end users.

Comparing schemas. Our tool offers a second screen (not shown here) where two schemas may be compared. Rather than computing a boolean answer to the question whether one schema subsumes the other, as done in state-of-the-art tools today [7], our tool can generate a witness that exemplifies a JSON document which is valid w.r.t. the one schema, but not the other.

ABSTRACT

Investigative Journalism (IJ, in short) requires combining highly heterogeneous digital datasets coming from a wide variety of sources. We have developed ConnectionLens, a system that integrates such sources into a single heterogeneous graph and enables users to query the graph using keywords. The first iteration of the system [3] followed a mediator architecture which severely constrained its query scalability. Thus, we fully re-engineered the system, moving it to a warehouse architecture, and replacing its core components (information extraction, data querying, and interactive interfaces), which allowed us to handle uses cases orders of magnitude larger than the previous platform [2]. In a consortium of computer scientists and investigative journalists, we propose to demonstrate ConnectionLens' capability to integrate arbitrary heterogeneous datasets and query them flexibly by means of keywords. Among several scenarios, our main focus will be on a real-world journalistic use case about situations which may lead to Conflicts of Interest between biomedical experts and various organizations, such as corporations, lobbies, etc. The demonstration will showcase the end-to-end data analysis pipeline, illustrate each system component, and the different parameters governing graph creation and querying.

The demonstration appears in CIKM 2021 [1]. A demonstration video is available at: https://youtu.be/5B0KRow0dv8.

RÉSUMÉ

Grâce aux nombreux outils d'apprentissage machine dont nous disposons aujourd'hui, il est plus facile que jamais de produire un modèle à partir d'un jeu de données dans le cadre d'un problème d'apprentissage supervisé. Cependant, lorsque ce modèle se comporte mal par rapport aux performances attendues, la question sous-jacente de l'existence d'un tel modèle est souvent négligée et l'on peut être tenté de choisir directement une autre architecture ou d'essayer d'autres paramètres d'entraînement. C'est pourquoi la qualité des exemples d'apprentissage doit être prise en compte le plus tôt possible car elle agit comme un go/no-go pour le processus d'apprentissage subséquent qui peut se révéler coûteux.

Avec ADESIT, nous proposons un moyen d'évaluer la capacité d'un jeu de données à donner de bons résultats pour un problème d'apprentissage supervisé à travers des statistiques et une exploration visuelle. Notamment, nous basons notre travail sur des études récentes proposant l'utilisation des dépendances fonctionnelles et spécifiquement l'analyse des contre-exemples. Ainsi, nous fournissons des statistiques sur la propreté du jeu de données mais aussi une limite supérieure théorique sur la précision de prédiction directement liée aux paramètres du problème (incertitude de mesure, généralisation attendue...). En bref, ADESIT est destiné à faire partie d'un processus itératif de raffinement des données, juste après la sélection et juste avant le processus d'apprentissage. Avec une analyse plus poussée pour un problème donné, l'utilisateur peut caractériser, nettoyer et exporter des sous-ensembles sélectionnés dynamiquement, permettant de mieux comprendre quelles régions des données pourraient être affinées et où la précision des données doit être améliorée en utilisant, par exemple, des capteurs nouveaux ou plus précis.

KEYWORDS

contre-exemples, apprentissage machine, visualisation, graphe, données massives, fastg3, modèle

INTRODUCTION

Considérons un problème d'apprentissage supervisé (AS) où la tâche est de prédire un attribut cible 𝐶 à partir d'un ensemble d'attributs 𝑋 en utilisant un ensemble d'exemples d'apprentissage. Le but est de trouver une fonction 𝑓 (aussi appelée modèle) telle que 𝑓 (𝑋 ) ≃ 𝐶. Pour ce faire, des exemples d'entraînement sont donnés à un algorithme d'apprentissage pour déduire une telle fonction qui peut ensuite être évaluée sur des exemples de test. Supposons que la précision obtenue soit inférieure aux attentes : que faut-il remettre en question ? On pourrait être tenté d'essayer différents paramètres d'apprentissage ou même de modifier l'architecture du modèle. Si cette approche peut fonctionner dans certains cas, remettre en question l'existence même de 𝑓 devrait également être l'une des principales préoccupations pour éviter un processus d'AS infructueux ou, inversement, pour aider les experts du domaine à faire confiance au modèle obtenu. Dans la pratique, la qualité et l'exhaustivité des exemples d'apprentissage sont parmi les principaux facteurs de réussite de l'AS. Des données bruitées, imprécises ou incomplètes peuvent conduire à des modèles médiocres et il est parfois même difficile de comprendre que les données d'apprentissage elles-mêmes sont à blâmer.

Dans cette étude, nous reprenons des travaux récents proposant l'utilisation des dépendances fonctionnelles (DFs) et spécifiquement l'analyse des contre-exemples pour trouver des contradictions dans un jeu de données. Pour le cas spécifique de l'AS, on comprend intuitivement que l'entraînement à partir d'exemples ayant des causes égales (𝑋 ) et des cibles différentes (𝐶) est susceptible de poser problème. En tant que fonction, 𝑓 doit donner une réponse unique pour une entrée donnée. Ce type de contradiction peut être dû à du bruit dans les données (précision du capteur, erreur d'entrée...) mais il peut aussi révéler des attributs manquants ou simplement la nature stochastique du phénomène. Par conséquent, trouver des régions avec une forte densité de contre-exemples est d'un grand intérêt pour le prétraitement des données, pour mieux comprendre les limites du jeu de données brute et de la formulation du problème, mais aussi pour guider les interactions avec les experts du domaine. Si les limites données par l'analyse des contre-exemples ne sont pas adaptées aux besoins métiers, il faut affiner le processus en travaillant sur l'acquisition ou le traitement des données.

Ainsi, nous présentons ADESIT (Advanced Data Exploration and Selection Interactive Tool), un application Web graphique et intuitive permettant d'évaluer les limites d'un jeu de données pour un problème d'AS en collaboration avec les experts métiers. Basée sur les contre-exemples, cette évaluation est faite par des mesures statistiques et une exploration visuelle interactive. Pour un jeu de données, un ensemble d'attributs 𝑋 et un attribut à prédire 𝐶, ADESIT aide l'utilisateur à comprendre le pouvoir prédictif du jeu de données mais aussi les raffinements et améliorations potentiels Si visualiser les contre-exemples permet déjà de mieux comprendre ses données, ADESIT propose également 3 indicateurs basés sur les contre-exemples (issus de [2]). Étendus à la famille des DF non-strictes pour cette étude (similaire à [4]), ces indicateurs sont définis comme suit : 𝑔 1 la proportion de contre-exemples, 𝑔 2 la proportion de tuples impliqués dans au moins un contre-exemple et 𝑔 3 la proportion de tuples à enlever de 𝑟 de sorte à ce qu'il n'y ait plus de contre-exemples. 𝑔 3 est notamment une limite supérieure sur la précision de n'importe quel modèle dans le cas des DF strictes [3].

Aperçu technique

Pour énumérer les contre-exemples, les tuples doivent être comparés deux à deux et sont ajoutés à l'ensemble des contre-exemples s'ils sont en accord sur 𝑋 et en désaccord sur 𝐶. Comme cette opération est quadratique par rapport au nombre de tuples, elle n'est pas facilement adaptable aux grands jeux de données. Néanmoins, cette énumération deux à deux a été largement étudiée pour le record linkage et les similarity joins où des optimisations ont été proposées. Selon le type d'attribut, des techniques telles que le blocking et/ou un algorithme de fenêtre glissante peuvent être utilisées pour des gains remarquables en temps de calcul.

Une fois les contre-exemples trouvés, 𝑔 1 est leur nombre et 𝑔 2 le nombre de tuples impliqués dans un contre-exemple. En revanche, 𝑔 3 nécessite de trouver le nombre minimum de tuples à supprimer de la relation 𝑟 pour satisfaire 𝑋 → 𝐶. Si son calcul est trivial dans le cas de DFs classiques [1], l'utilisation de DFs non-strictes le rend NP-Hard (preuve similaire à [4]). De plus, en utilisant une représentation sous forme de graphe où les noeuds correspondent à des tuples et les arêtes relient les noeuds impliqués dans un contreexemple, le calcul de 𝑔 3 devient équivalent au Minimum Vertex Cover, ce qui permet de bénéficier de l'importante littérature sur le sujet. Nous proposons à la fois un algorithme d'approximation et un algorithme exact (pour les petits jeux de données).

ADESIT

ADESIT est une application Web (adesit.datavalor.com) permettant un collaboration aisée entre les spécialistes en données et les experts métiers. Son interface est présentée en Figure 1. Ainsi, SaGe-Path propose une approche pay-as-you-go qui permet d'évaluer efficacement des requêtes SPARQL property path sur des données en ligne, avec la garantie d'obtenir des résultats complets. L'objectif de cette démonstration est de montrer comment des requêtes qui ne terminent pas sur Wikidata, un SPARQL endpoint publique, terminent en utilisant SaGe-Path. Une interface utilisateur permet de suivre l'évaluation d'une requête en temps réel, afin de comprendre les overheads de l'approche et l'impact des différents paramètres sur l'exécution de la requête.

different pollutants such as Nitrogen dioxide (NO2), Particulate Matters (PMS), Black Carbon (BC), Temperature, etc. . . independently form their environment either indoor or outdoor.

Air quality strongly depends on the context of the participant, thus in order to understand and identify participants' exposure to pollution, it is essential to identify the context of the participants. To avoid miss-classification of the exposure wrt the context (microenvironment), the participants need to fill a time-use diary, but in real-life, they rarely thoroughly do this self-reporting task. Therefore, mining the context of participants based on the data collected from the crowd is an attractive solution. But, it is challenging due to the imperfection of the data as shown in [6]. Consequently, learning from individual sensor data fails to identify the micro-environment. This classification might be improved by combining multiple sensor data. However, this is not straightforward due to the complexity and interdependence of such multi-dimensional time series [3].

This task is more or less related to human activity recognition, where there exists a long established research, and a wide range of applications. Different types of data are used ranging from GPS only, to one or many accelerometers, sound or combinations. An attempt to work with environmental data was introduced by Asimina et al. [2] where the authors explore the capability of predicting location from sensors data using an Artificial Neural Network (ANN) model. The authors use low-cost individual sensors and GPS for data collection, and provide a location predictive model based on Artificial Neural Network (ANN) to derive the time-space activity daily profile of the individuals. Although their approach predicts very well indoor locations, however, there is still room for improvement in discriminating between in transit and outdoor locations.

Furthermore, there is a need for a full-fledged implementation that can be used in real-world applications to fill the gap between data collection and context recognition using environmental data. In our case, the input is both GPS and environmental sensor data. We formulate the task of recognition of micro-environment as a multivariate time series classification (MTSC) [5]. In a previous work [1], we've proposed a multi-view stacking generalization approach in order to detect the micro-environments from the air pollution data collected based on different learners.

In this demonstration, we include time series segmentation based on change point detection to emphasize the automatic detection of the change in the user's context. Furthermore, we develop a visualization tool COMIC (Context Of MobIle Crowdsensing) showing the different recognized contexts and illustrating the importance of multi-view approach when compared to single view approach and other baseline learners. This visualization interface highlights also the importance of our approach vis-a-vis users' declared contexts.

For more information, refer to our paper in [4], and the presentation here ( or in this URL: https://youtu.be/jgWPlxJ4-ms).

7 Résumés des articles de doctorant contributes to the emergence of what is called the Computing Continuum [2]. It seamlessly combines resources and services at the center (e.g., in Cloud datacenters), at the Edge, and in-transit, along the data path. Typically data is first generated and preprocessed (e.g., filtering, basic inference) on Edge devices, while Fog nodes further process partially aggregated data. Then, if required, data is transferred to HPC-enabled Clouds for Big Data analytics, AI model training, and global simulations.

PROBLEM STATEMENT

Despite an always increasing number of dedicated systems for data processing on each component of the continuum, this vision of ubiquitous computing remains largely unrealized. This is due to the complexity of deploying large-scale, real-life applications on such heterogeneous infrastructures, which breaks down to configuring a myriad of system-specific parameters and reconciling many requirements or constraints, e.g., in terms of communication latency, energy consumption, resource usage, data privacy.

A first step towards reducing this complexity and enabling the Computing Continuum vision is to enable a holistic understanding of performance in such environments. That is, finding a rigurous approach to answering questions like: (1) Which system parameters and infrastructure configurations impact on performance and how? (2) Where should the workflow components be executed to minimize communication costs and end-to-end latency?

STATE OF THE ART

Approaches based on workflow modelling [6] and simulation [7] raise some important challenges in terms of specification, modelling, and validation in the context of the Computing Continuum. For example, it is increasingly difficult to assess the impact of the inherent complexity of hybrid Edge-Cloud deployments on performance. At this stage, experimental evaluation remains the main approach to gain accurate insights of performance metrics and to build precise approximations of the expected behavior of large-scale applications on the Computing Continuum, as a first step prior to modelling.

CHALLENGES

A key challenge in this context is to be able to reproduce in a representative way the application behavior in a controlled environment, for extensive experiments in a large-enough spectrum of potential configurations of the underlying Edge-Fog-Cloud infrastructure. In particular, this means rigorously mapping the scenario characteristics to the experimental environment, identifying and controlling the relevant configuration parameters of applications and system components, defining the relevant performance metrics. The above process is non-trivial due to the multiple combination possibilities of heterogeneous hardware/software resources, system components for data processing, analytics or model training.

PHD OBJECTIVES

In order to allow other researchers to leverage the experimental results and advance knowledge in different domains, experimental methodologies need to enable three R's of research quality: Repeatability, Replicability, and Reproducibility (3R's). This translates to establishing a well-defined experimentation methodology and providing transparent access to the experiment artifacts and experiment results.

The Computing Continuum vision calls for a rigorous and systematic methodology to map real-world application components and dependencies to infrastructure resources, a complex process that can be error prone. Key research goals are: 1) to identify relevant characteristics of the application workloads and of the underlying infrastructure as a means to enable accurate experimentation and benchmarking in relevant infrastructure settings in order to understand their performance; and 2) to ensure research quality aspects such as the 3R's.

OUR CONTRIBUTION: E2CLAB

E2Clab [5] implements a methodology that supports the complete experimental cycle across the edge-to-cloud continuum, including deployment, configuration, optimization, and experiment execution in a reproducible way. It may be used by researches to deploy reallife applications on large-scale testbeds and perform meaningful experiments in a systematic manner. The main contributions of this work are:

A rigorous methodology for designing experiments with real-world workloads on the Computing Continuum spanning from the Edge to the Cloud; this methodology provides guidelines to move from real-world use cases to the design of relevant testbed setups for experiments enabling researchers to understand performance and to ensure the 3R's properties.

A novel framework named E2Clab that implements this methodology and allows researchers to deploy their use cases on real-world large-scale testbeds, e.g., G5k [1]. To the best of our knowledge, E2Clab is the first platform to support the complete analysis cycle of an application on the Computing Continuum: (i) the configuration of the experimental environment; (ii) the mapping between the application parts and machines on the Edge, Fog and Cloud; (iii) the deployment and monitoring of the application on the infrastructure; and (iv) the automated execution and gathering of results.

A large scale experimental validation on the G5K [1] testbed with Pl@ntNet [3], a real-life use case. E2Clab allows optimizing the Pl@ntNet's performance based on the analysis of the parameter settings and correlation to processing time and resource usage [4].

PRELIMINARY RESULTS

We illustrate [5] E2Clab usage with a real-life Smart Surveillance System deployed on the Grid'5000 testbed, showing that our framework allows one to understand how the Cloud-centric and the hybrid Edge-Cloud processing approaches impact performance metrics such as latency and throughput.

Besides, we validate [4] E2Clab with Pl@ntNet, another reallife use case. We demonstrate that E2Clab guides on the optimization of the Pl@ntNet performance based on the analysis of the parameter settings and correlation to processing time and resource usage. Preliminary results show that Pl@ntNet's deployment configurations found by E2Clab perform better than the current ones used in the production servers.

NEXT RESEARCH STEPS

We are exploring parallel and scalable optimization techniques that supports surrogate modeling optimization for large-scale multiobjective optimization problems. In this direction, we have an ongoing collaboration with Argonne National Laboratory members, where we are discussing potential solutions to support the optimization of complex application workflows on the Edge-to-Cloud Continuum.

Furthermore, since E2Clab supports reproducible experiments, we will explore and propose techniques for runtime provenance collection in large-scale and distributed experimental environments. The goal is to provide additional context that more accurately explains the experiment execution and results. This research direction is a collaboration with the Federal University of Rio de Janeiro, Brazil.

from one-time training (typically used for static data) to approaches capable of learning from incoming flows of data. Incremental learning is such an emerging DL method where progressively available data is used to extend the model's knowledge.

CHALLENGES

Distributing DL training across fog mini-clusters and cloud data centers poses several challenges: Network heterogeneity. Distributed DNNs suffer from lowspeed and high-latency wide-area networks (WANs) connecting distant nodes. These heterogeneous links lead to stragglers, making it challenging for DL algorithms to perform efficient training.

Compute heterogeneity. As Moore's law came to an end, GPUs and other specialized accelerators emerged alongside traditional CPUs to train DNNs. In practice, clusters provide a different number of nodes equipped with different hardware or virtualized resources, leading to heterogeneous performance across and within clusters.

Scale. By nature, edge-to-cloud computing is geo-distributed. At scale, this characteristic aggravates network heterogeneity, leading to communication bottlenecks on multiple low-bandwidth nodes.

PROBLEM STATEMENT

Conciliating both network and compute heterogeneity to distribute the DL training efficiently in large-scale scenarios is therefore a problem gaining more and more interest from both the DL and the HPC -Big Data communities. Strategies at system and algorithmic levels should be explored as users might want to optimize different objectives based on their high-level goals, such as minimizing the time to complete the job (makespan), costs, or improving fairness.

PHD OBJECTIVES

During my PhD (started in 2021), I will study the following research questions: 1) How much can one improve (or degrade) the efficiency of DL training by performing it in the fog (closer to the edge) rather than performing it in the cloud? and 2) How to account for the heterogeneous network and compute capabilities of the processing units across the Computing Continuum?

In order to answer these questions, I plan to devise a set of strategies and algorithms optimizing DL workloads in heterogeneous settings. More specifically, in order to assess their impact, I plan to study how the proposed techniques affect the accuracy in classifying new data and to what extent they apply to incremental learning.

BDA 2021, October 25-28, 2021, Paris, France Bouvier et al.

STATE OF THE ART

Parallel stochastic gradient descent (PSGD) and its variants have been widely used to train large DNNs. Current approaches allow training model subsets on their local data asynchronously, and exchange gradients via peer-to-peer communication to synchronize local subsets. Techniques like bounded staleness, backup workers and synchronization queues [4] have been devised to account for dynamic network heterogeneity, whereas the selection of the fastest links [2,3], prevent the emergence of deterministic stragglers. Skipping SGD iterations and optimizing the partitioning of input data [1] help with deterministic compute heterogeneity. At the cluster level, heterogeneity-aware schedulers [5] allow sustaining heavier workloads than agnostic ones.

However, these approaches do not comprehensively consider the challenges posed by the continuum. In particular, they enable DL deployments on distributed platforms by addressing the issues of network and compute heterogeneity separately.

CONTRIBUTIONS

A first step towards executing efficient DL training in heterogeneous settings is to get a holistic understanding of performance. For this purpose, we will leverage E2Clab [6], a framework supporting the complete experimental cycle across the continuum, including configuration, deployment and execution in a reproducible way. We will extend it to identify inefficient gradients computation and propagation across nodes.

The next step is to devise novel intra-and inter-cluster strategies to address the above observations. In particular, the following facets should be considered:

• Coarse-grained compute capacity. The compute capacity of clusters should be estimated to adjust the initial data parallelism batch size accordingly. Input data migration could be performed at runtime.

• Fine-grained compute capacity. DNN training proceeds in iterations. Within a cluster, heterogeneity-aware scheduling strategies should improve utilization and optimize fairness by time-multiplexing jobs over CPUs and GPUs.

• Deterministic network capacity. Fast links should be favored to exchange data. Limiting communication to certain links requires ensuring the convergence of the SGD algorithm across nodes.

• Dynamic network capacity. Temporary network slowdowns should be detected in real time and countered by decentralized asynchronous SGD methods.

The main contribution of my PhD will be the design of a prototype framework helping to distribute DL training (Figure 1), accounting for deterministic and dynamic of both network and compute heterogeneity.

METHODOLOGY & ROADMAP

During the first year, I plan to conduct experiments on Grid'5000, a large-scale testbed for distributed computing. The methodology implemented in E2Clab will help reproduce both relevant behaviors of the given DL workloads and representative settings of the physical infrastructure underlying the continuum. The goal is to identify the The outcomes will drive the design of a framework mitigating the identified infrastructure bottlenecks in DL scenarios. By explicitly considering heterogeneity, various policies should improve the following objectives:

• Makespan refers to completing the training process as soon as possible.

• Cost is relevant when using elastic resources from public clouds. It specifically aims to minimize communication and resource usage costs.

• Fairness aims to optimize the fair sharing of processing units across the continuum. Eventually, it will be interesting to study the extent to which these strategies apply to incremental learning. The makespan should be largely improved by deferring the global model synchronization across more distant nodes.

Towards designing a temporal graph management system

ABSTRACT

Temporal graphs are useful for modelling the dynamic behavior of relationship-centered domains. Analyzing these graphs paves the way to the extraction of meaningful insights such as detecting anomalies or forecasting future behavior of underlying systems. In this context, the need of a temporal graph management system that handles not only the structural dimension but also the temporal one becomes highlighted. However, designing such a system imposes a number of challenges such as the storage and querying of temporal graphs which we mainly address in this PhD thesis.

KEYWORDS

Temporal Graphs, Graph management systems, Graph querying language

INTRODUCTION

Graphs are used in a myriad of application domains to model relationship-centered data. In this context, Thing'in1 is a platform that uses a graph to model the connections between connected (smoke detector, cameras, printers, etc.) and non-connected (rooms, tables, roads, etc.) objects. However, smart devices embed a highly dynamic behavior leaving the graph of Thing'in to be naturally modeled as a temporal graph. Indeed, analyzing such a dynamic behavior opens the way to promising applications such as the prevention of critical situations and forecast of future behaviors. In order to keep pace with this demand, a graph management system with an optimized time-version support is needed. For argumentation sake, we showcase in the following example the advantages of a temporal graph management system as compared to conventional (non-temporal) systems.

Example 1.1. A motivational use case is that of smart transportation networks. Figure 1 shows a toy graph modelling the connections of transportation network. In such a graph vertices model smart vehicles, radars, traffic lights, etc. and edges represent the temporary connections between vehicles and their surrounding such as connected sensors, objects connected to a road (cameras, traffic lights, etc.). A temporal graph management system should be able to query not only the structural dimension of underlying graphs but also the temporal one. For instance, non-temporal queries permit to extract: Sensors that are connected to a vehicle, Radars that are connected to a road or owners of a vehicle. However, adding the temporal dimension enrich the expressiveness of queries. That is, it permits the expression of the following queries:

• 𝑄 1 : Neighborhood of a car or health status (monitored by smart watch) right before an accident.

• 𝑄 2 : Speed recorded by a radar when the latter has detected a certain vehicle.

• 𝑄 3 : Average waiting time of a vehicle at a traffic light.

• 𝑄 4 : Time during which a sensor connected to a car indicates a value that is higher than a threshold knowing that the vehicle was turned on for less than an hour.

Regarding the additional expressiveness of temporal graph queries, particularly in the analysis of IoT domains, our main motivation is the design and integration of a temporal graph management system into the Thing'in platform. Towards accomplishing this goal, we mainly tackled two challenges that are: the storage techniques and querying languages of temporal property graphs that will be discussed more in details in sections 2 and 3, respectively.

CLOCK-G

In this section, we present Clock-G: a temporal graph management system implementing a space-efficient storage technique. A key concept in the design of such a system is the data model. Hence, we have formally defined a temporal property graph as a collection of vertices, edges and values of properties having each a sequence of validity intervals. To clarify, a validity interval refers to the time interval during which an entity was valid. Regarding the outgrowing size of temporal graphs, a crucial consideration is the storage technique of such graphs. One of the proposed methods is the Copy+Log [3,4,7] that consists of storing graph updates in temporally disjoint chunks known as time windows along with valid states of the graph known as snapshots. These snapshots represent a materialization of the graph states that are valid between the boundaries of two successive time windows. The advantages of this solution is that recovering the state of the graph at a given time instant requires at most reading a snapshot and the graph updates contained in a single time window. However, snapshots are space consuming because they materialize the state of every existing vertex or edge at a single time instant. This problem becomes even more exacerbated in case of growth-mostly graphs where vertices and edges tend to survive for longer duration and hence are copied over and over again in several snapshots. To overcome this limitation, we proposed the 𝛿-Copy+Log storage approach, then developed Clock-G [5], a graph management system that adopts this method. Our solution mainly differentiates from the Copy+Log method by storing the differences between successive snapshots instead of full snapshots. A crucial concept here is that we store a snapshot after a number of time windows in order to serve as a starting point for query evaluation. Having this, we store graph operations in consecutive time buckets containing each a number 𝑀 of time windows such that the first 𝑀 -1 time windows ends with a delta, whereas the final time window end with a snapshot. A critical optimization is the forward and backward data representation. That is, half of the deltas and time windows in a bucket is constructed in a forward fashion whereas the other half is constructed in a backward fashion. The rationale behind this choice is the acceleration of the query's execution time. That is, we choose the closest snapshot from which to start the search then compute the result in a forward or backward fashion whether the time instant of that snapshot is lower or greater than the requested one. Knowing that storing deltas adds a querying time overhead, Clock-G offers optimization techniques to mitigate this additional cost. To validate the efficiency of the proposed methods, we evaluated the performance of Clock-G with the use of real and synthetic datasets. Our experimental results demonstrated that the 𝛿-Copy+Log method can significantly reduce the space usage while adding only a negligible overhead to the query execution time as compared to the Copy+Log technique.

T-CYPHER

Another essential consideration in the design of a temporal graph management system is the querying language. Indeed, we need to couple Clock-G with a querying language that supports the additional temporal dimension. In this context, we proposed T-Cypher [6]: a time-extended version of OpenCypher [2]. We resume our main contributions as follows: Formalizing the definition of a temporal property graph pattern, extending the syntax of Cypher queries with temporal constructs and formalizing the semantics of the proposed language. That is, we defined a temporal property graph pattern (TPGP) as a graph pattern augmented with temporal variables and temporal constraints. For instance, conventional graph patterns include variables referring to vertices, edges or property values. We extended these patterns with temporal variables on top of which we defined temporal constraints that can be useful for a wide variety of temporal queries. To express TPGP queries, we extended the syntax of Cypher with temporal constructs such as temporal clauses, operators and functions. The extended syntax is non-intrusive in the sense that it offers a straightforward transition for practitioners who are already familiar with the Cypher language. Finally, we followed an approach that is similar to the one used in [1] to provide the formal semantics of the extended language. We present in Figure 1.1 how to express queries 𝑄 1 , 𝑄 2 , 𝑄 3 and 𝑄 4 with the T-Cypher language.

SUMMARY AND PERSPECTIVE

To summarize, we proposed a space-efficient technique to store temporal graphs that we have adopted in the design of the temporal graph management system Clock-G. Besides, we proposed and formalized a querying language for temporal property graphs. Our perspective is to couple this querying language with Clock-G by designing a query planner that is optimized for the evaluation of T-Cypher queries.

Privacy over RDF datasets

CONTEXT AND MOTIVATION

Nowadays, data is often organized as graphs with an underlying semantic to allow efficient querying, while supporting inference engines. Such is the case for linked data and the semantic web, which are built using the RDF standard [7]. An RDF data set is a set of triples (subject-predicate-object) which form a labeled directed graph. With the increased use of this representation, privacy in such data sources is becoming an issue [3]. A massive amount of work has focused on privacy in data presented as tables, resulting in multiple well-established models, such as k-anonymity [11], ldiversity [8], and differential privacy [4]. On the contrary, privacy in the context of semantic graph databases has been mildly studied.

In the context of this Ph.D., we study privacy over RDF datasets. In particular, we are interested in adapting differential privacy (DP) to edge-labeled directed graphs with an underlying semantic.

BACKGROUND

Differential Privacy. DP [4] is a model that provides a robust statistical definition of privacy tailored to the problem of privacypreserving data analysis. The goal is to ensure that an attacker is not able to infer (beyond a certain probabilistic threshold) whether an individual contributed to the result of a query over a database. The exact protection and the notion of individuals' contributions are defined based on the concept of neighboring (or adjacent) databases. Definition 2.1 (𝜖, 𝛿-differential Privacy [4]). A randomized mechanism K: 𝐷 𝑛 → R 𝑑 preserves (𝜖, 𝛿)-differential privacy if for any pair of adjacent databases (x, y) ∈ (𝐷 𝑛 ) 2 and for all sets S of possible outputs:

Pr[ K(x) ∈ S ] ≤ 𝑒 𝜖 Pr[ K(y) ∈ S ] + 𝛿 where the probability is taken over the randomness of K.

In traditional relational databases, two databases are neighbors if they differ by at most one individual. Hence, in that context, one should not be able to infer beyond a certain probability whether an individual is present in the database by observing the result of a DP-mechanism.

Adapting DP to graphs. Building DP algorithms on graph data means defining adjacency between graphs. The two most prevalent definitions proposed in the litterature are edge-DP and node-DP [5].

In node-DP,two graphs are neighbours if they differ by at most one node and all of its incident edges. In edge-DP, neighboring graphs are defined as graphs that differ by at most one edge. Previous studies [1,6,9,12] show different approaches to work with DP in graphs. In [12], a new definition of adjacency is presented in the context of social graphs, called Out-link. In out-link-DP, neighboring graphs are defined as graphs that differ by the outlinks (outedges) of a chosen node. However, none of these approaches tackles edge-labelled graphs and their semantic. QL-out-edge-DP is a recent refinement of out-link-DP integrating semantic [10]. QL-out-edge-DP relies on the definition of the set QL of edge types (labels) that are considered sensitive. Two neighbouring graphs differ by the outedges whose labels are within QL of one node. Edges whose labels are not contained in QL are preserved.

Building graph-DP algorithms. There exists various way of making a mechanism DP. One particular general approach to achieve differential privacy is to add an appropriate amount of noise to the query results. This obviously depends on the query and the adjacency model. Sensitivity is the parameter that determines the magnitude of noise to be added. It represents how much the query result can change over neighbouring datasets. The prevalent approach is to add noise that depends on the global sensitivity (GS) of the query, which measures the maximum variation of the query result when evaluated upon any pair of neighboring databases. The main drawback with GS is that it can be very large, and sometimes unbounded (e.g. when computing the MAX degree w.r.t. node-DP). One technique to reduce the GS of a query is to first project the dataset from the initial space noted ginto a bounded space noted 𝑅, then run the query on the projected result. The sensitivity of the composition is bounded by the sensitivity of the projection times the sensitivity of the query on the projected space [6], where the sensitivity of the projection is the maximal distance between the projections of two neighboring graphs. Theorem 2.2 (Sensitivity of the composed mechanism [6]). Given a projection 𝑇 : g → 𝑅 ⊆ g, a function 𝑓 : 𝑅 → R 𝑑 , and a distance 𝑑 over g, noting Δ 𝑑 (𝑓 •𝑇 ) the global sensitivity of 𝑓 •𝑇 w.r.t.

𝑑, we have:

Δ 𝑑 (𝑓 • 𝑇 ) ≤ Δ 𝑅 𝑑 𝑓 × Δ 𝑑 𝑇 Using this theorem, [2] have proposed to use projection by edge addition in order to achieve DP on undirected, unlabeled graphs.

OUR APPROACH : USING PROJECTION TO ACHIEVE DP FOR RDF GRAPHS 3.1 Objective of the work

The objective of this Ph.D. is thus to propose methods to query RDF graphs while respecting DP constraints. Our approach is to project RDF graphs into a bounded subspace in order to reduce the sensitivity of the queries, and thus 1) make it possible to add a finite amount of noise when the sensitivity on the original space is infinite and 2) potentially improve the utility by reducing the amplitude of said noise. Our objective is to study several projection methods, propose theoretical bounds on noise to be added, and build a prototype implementing our system in order to check the utility of the results.

Current results

In our current work, we proposed and studied three edge-addition based graph projection methods named 𝑇 1 , 𝑇 2 and 𝑇 3 which are appropriate w.r.t. node-DP, out-link-DP, and QL-out-link-DP, respectively. These projections bound the maximal degree (𝑇 1 ), out-degree (𝑇 2 ), and out-degree of specific labeled edges (𝑇 3 ) of a input graph, the bound being noted 𝐷. Although the concept of projection by edge-addition is not new, since it was introduced by [2], previous work only considers undirected graphs with no labels on edges. On the contrary, we consider RDF graphs, i.e. edge-labeled graphs, and study the behaviour of our projections w.r.t. several privacy models.

Proposed projection algorithms. The algorithm 1 formalizes 𝑇 3 which is well adapted to RDF and serves as example. In general, our projections take as input a graph 𝐺 and build a new graph with the same nodes as 𝐺 but without any edges. They then try to insert each edge following an edge-ordering function (see below) 𝐴. An edge 𝑒 from 𝑣 1 to 𝑣 2 labeled 𝑙 is successfully inserted whenever its insertion preserves the constraint, i.e. (𝑇 1 ) the degrees of both 𝑣 1 and 𝑣 2 are less than 𝐷; (𝑇 2 ) the out-degree of 𝑣 1 is less than 𝐷; (𝑇 3 ) 𝑙 ∉ 𝑄𝐿 or 𝑣 1 has less than 𝐷 out-edges with a label in 𝑄𝐿. Projection sensitivity. We studied the sensitivity of each of the proposed projection in the context of node-, out-edge-, and QL-outedge-DP. In particular, we demonstrated that the GS of 𝑇 2 in the out-edge-DP model and the GS of 𝑇 3 in the QL-ou-edge-DP model is 1. Using theorem 2.2, this shows that the GS of the composition is at most the GS of the query in the restricted space.

Edge ordering. Projection by edge-addition requires the definition of an order over the space of edges. This edge ordering must be stable in the sense that given two neighboring graphs 𝐺 1 and 𝐺 2 , if two edges appear in 𝐺 1 and 𝐺 2 then their relative order must be the same in A(𝐺 1 ) and A(𝐺 2 ). Here, the order can be determined by combining three sub-orders on the sources (subjects), labels (predicates), and objects (destinations) which can simply be lexicographical.

Testing on queries. We have studied several RDF queries and have shown that unbounded GS can be bounded using our projection approach, but also that an original bounded GS can be very much reduced.

FUTURE WORK

In future work we mainly plan on implementing the system, performing large scale experiments, and investigating the utility of the resulting mechanisms in particular. More specifically, when the GS of the projection is 1, we plan on investigating the trade-off between the data-degradation due to the projection and the reduction of the GS of the query (and thus of the amplitude of the noise). Interestingly, even though edge ordering has no impact on the GS of the projection, we have found that it does impact utility. Another outlook is therefore to study this impact and propose optimal edge orderings.

INTRODUCTION

The Open Data Initiative has led to an increasing number of publiclyspread datasets. Such datasets are often quite large and heterogeneous (depending on the provider, the kind of data, etc). Many such datasets are large; further, they are extremely heterogeneous, in particular for what concerns their data model (RDF, JSON, XML, CSV, property graphs, relational databases, etc.), their schema (if a schema exists), etc. The scale and heterogeneity make it challenging for human users to identify, among the many available datasets, those that could be used for a given application they have in mind.

This thesis is part of the ConnectionLens project [1], which aims at integrating heterogeneous data into a graph. Our goal is to create small expressive descriptions of what a dataset is about, using the power of integration of ConnectionLens. In this paper, we present the challenges (Section 2), then the approach (Section 3) and finally some preliminary results (Section 4) before concluding (Section 5).

CHALLENGES

Finding the right dataset is complicated, especially because they are often not well-documented and it can be difficult to appreciate how it can be useful. Our approach, which aims at helping users to choose a dataset, should satisfy the following requirements:

• R1: The approach should be applicable to any kind of data. There are various data formats, such as RDF (as in the Open Data Cloud), but also XML (as in the PubMed database), JSON (most of French open data), relational databases, and so on. This requirement is handled by Section 3.1.

• R2: The data descriptions we build for users should be sufficiently expressive, but also compact. Users need to understand what is inside a dataset, but when a full description is complex, we need to bring them only the most important facts about it. We discuss how to fulfil this requirement in Sections 3.2 and 3.3.

APPROACH

ConnectionLens is a system capable to produce a graph 𝐺 from any dataset of any format, where each node is a piece of data and edges link these nodes to reflect the content of the original source. Moreover, an entity extraction process is applied on text nodes, to extract from them named entities, such as Person, Location, Organization, Date, etc. In my thesis, to be able to produce compact descriptions of any data format, we leverage ConnectionLens to start our summarization method from the graph 𝐺. Our approach is the following:

(1) Build a structural summary of 𝐺.

Summarization

We explain now how we compute the summary 𝐺 ′ of 𝐺. For efficiency, we distinguish two cases: rooted, acyclic data source graphs, vs. the general case where graphs may have cycles and/or may not have a root. Rooted acyclic graphs. These graphs are obtained for instance from XML or JSON datasets. On such graphs, we apply the strong DataGuide summarization method [4] to create 𝐺 ′ from 𝐺. A Dataguide is a concise summary of the structure of a database. This method builds a set of paths, such that each path of the DAG appears exactly once in the summary. Such summarization method works only on acyclic graphs because the recursion should not encounter a cycle.

General graphs. Such graphs can originate in RDF, property graphs, or relational database datasets (where primary-foreign keys can lead to cyclic connections between the tuples). For such graphs, we need a graph summarization method that (𝑖) reflects all the graph, (𝑖𝑖) groups nodes into equivalence classes and (𝑖𝑖𝑖) can be computed efficiently even from large graphs. RDFQuotient [3], originally introduced for RDF but easy to adapt to arbitrary graphs, meets these criteria, thus we rely on it to compute the summary 𝐺 ′ of 𝐺 for non-acyclic graphs. RDFQuotient gives a set of equivalence classes between nodes based on their types and their properties.

Records and Collections

We seek to understand 𝐺 ′ based on two key concepts:

• A Record is basically a thing; in data modelling terms, it describes either an entity or a relationship. It has some properties (e.g. a title and a DOI for a paper) and can handle nested collections (e.g. the authors list of a paper).

• A Collection is a set of similar records (e.g. a bibliography is a collection of books). They are explicit when a node handles similar records; or implicit when some records refer to the same purpose without being handled by a node. Other nodes in 𝐺 ′ are called Sub-Records and are mainly the properties of the records (i.e. the set of outgoing properties of a record 𝑟 , referred as 𝑟 .P). Furthermore, we compute the signature of each sub-record 𝑠, where the signature is compound of a domain ("to which categories 𝑠 belongs to?") and a range ("to which categories 𝑠 points to?"). For example, the sub-record settledDownIn has for domain {Person, Organization} and for range {Location}.

To find them, we first determine collections and then, in a topdown fashion, the direct children of collections are identified as records. To compute collections, we rely on a clustering algorithm we devised, based on the support of a set of properties among a set of potential records (how many of these records have this set of properties). Our clustering algorithm identifies both explicit collections, where a 𝐺 ′ node is actually the parent of all the nodes representing the records in the collection, and implicit collections, where such a common parent/collection node does not exist in 𝐺 ′ .

Analysis and Categorization of Collections

Given a set of hints H and a set of user-defined categories K, we aim at categorizing a collection 𝑐 among K, i.e. give a category 𝑘 ∈ K to 𝑐 using H , as illustrated by Algorithm 1. A hint ℎ is a triple ⟨𝐴, 𝑙, 𝐵⟩ where A is the domain ⊆ K, 𝑙 is the label and 𝐵 is the range ⊆ K. For instance, the hint ⟨Organization, hasCEO, Person⟩ states that a collection having a record holding the property hasCEO, whose signature's range matches Person, should be categorized as an Organization.

For each record 𝑟 ∈ 𝑐, we initialize K 𝑟 (set of candidate categories in which 𝑟 may belong) and scores (score of 𝑛𝑐 for each hint in H ). Then, if 𝑟 has a label semantically close to one of the category in K, this category is stored as a candidate category in K 𝑟 . For each child 𝑛𝑐 ∈ 𝑟 , we create a pair 𝜋 containing the label and the signature of 𝑛𝑐. Then, we compute the similarity of 𝜋 with each hint ℎ in H , where the similarity is based on the label and the signature of both elements. We choose the hint ℎ leading to the highest similarity score for each 𝜋. Each category indicated by the domain of ℎ gets a vote. Then, we classify 𝑟 in the category that gets the highest number of votes or Other if no category is frequent enough. Finally, we classify 𝑐 in the most represented category in its records. We also determine if a collection describes entities or relationships, by looking at the connections between the collections.

STATUS

We have fully implemented our approach in a prototype, which leverages the graph creation and storage of ConnectionLens [1], and includes the novel algorithms described in Section 3. More details can be found in a short paper [2]. Figure 1 shows an example of our approach applied on a set of PubMed articles. The set of articles is considered as a collection of

CONCLUSION AND PERSPECTIVES

My PhD thesis aims to create expressive descriptions of big heterogeneous datasets by using summarization methods and categorization of expressive structures (records and collections). Beyond finalizing the implementation of our platform for all the data models we consider, we will experiment to analyse its scalability as well as the expressiveness and precision of the record categorization. Next, we will investigate the adoption of sampling-based approaches, to try to construct such dataset descriptions without traversing the dataset entirely to further improve performance. Thesis context My PhD is funded by DIM RFSI and is a collaboration between Inria and WeDoData, a SME specialized in data visualization and interactive data-driven Web content. My PhD advisers are Ioana Manolescu (Inria) and Karen Bastien (WeDoData).

Towards a Logistical View for Data Lake Optimization

Marzieh Derakhshannia * Anne Laurent * Marzieh.derakhshannia@etu.umontpellier.fr Anne.laurent@umontpellier.fr LIRMM, Univ Montpellier, CNRS Montpellier, France

ABSTRACT

Data life cycle management is a challenging issue in the big data arena. Data lakes are the new generation data repositories that provide the platform to respond to the management of huge amounts of raw data. In terms of structure, data lake architecture could have a significant role in improving the data quality and service levels. For this reason, suitable data lake design and appropriate management strategies play the important role in implementing of fruitful data lake. Logistical view is a proper solution to manage an optimal data lake that will be favorable for organisations.

CCS CONCEPTS

• Information systems → Storage architectures; Data management systems.

KEYWORDS

Data Lake, Data Lake Architecture, Logistic Systems, Supply Chain, Supply Chain Management

CONTEXT

In the last decades, the data has become a valuable property for organizations and is considered as digital oil in the big data environment.

To make capital from this precious product, proper equipment is required [6]. Traditional data management tools have inadequacies in gathering, storing, processing, and visualizing all types of data in an integrated manner in the big data arena. Therefore, the term " Data lake " has been emerged to address the shortcomings flaws and meet all the challenges related to the data lifecycle [10]. Data lakes are the developed, affordable, and agile generation of centralized data management systems that provide plenty of faculties to conduct the procedures of storage and knowledge mining from a huge amount of heterogeneous data [4,9,12]. However, welcoming all kinds of data in their native formats increases the risk of saturation with unmanageable or useless data; a phenomenon is known as "data swamp"; and threatens the security of sensitive data. For this reason, data management strategies and architecture design are more highlighted in data lake productivity. The architecture of the data lake and the administration regulations could have significant impacts on the efficiency of data lake performance. Thus, an optimized architecture under proper managerial disciplines enhances the data lake credibility and reinforces its reliability as a new component of the information systems to support decision-making processes in the organizations.

CHALLENGES

Data lake architecture design and data management are problematic issues for the implementation of an efficient data lake infrastructure. Based on these requirements, many studies in the field of the data lake architecture design have been conducted in parallel with the technical implementation [5, 7-9, 11, 12]. Despite many types of researches on the data lake architecture and with regard to their cons and pros, optimization of the data lake structure and performance based on managerial and mathematical viewpoints has been less considered. For this reason, we suggest logistical approaches like product lifecycle management and hybrid decisionmaking strategies (like facility location-allocation problems) based on supply chain management principles to design and optimize the data lake architecture. The significant principle of supply chain management is to minimize the total costs related to the flow of products in such a way that profitability of the chain and quality of the service requirement, will be maximized. We intend to implement this principle for data lake management due to the new proposed architecture and imitated strategies.

METHODS

Since the data could be considered as a valuable product, we can imagine that a data lake performs like a logistic system that manages the data throughout its life cycle. This viewpoint brings about a great deal of systematic and managerial strategies to develop data lake architecture and gain the integrated manner to manage and govern the data in a cost-effective platform. Based on this requirement, the supply chain is one of the well-known logistic systems that present a systematic view of logistic parties who are integrated into a unified network to produce a commodity or provide a service [1,2]. To design the profitable supply chain network, each level of this chain is managed by tactical and strategic strategies. Thus, the supply chain management strategies prepare the suitable guidelines to design and manage the data lake architecture in general or in detail scales.

The processes of designing a data lake architecture are related to positioning the different components like data ingestion, data storage, data process, and data access stages and defining the proper strategies and protocols to govern the data like metadata management or data democracy. For this reason, the data lake platform based on systematic definitions and network design concepts could 37ème Conférence sur la Gestion de Données -Principes, Technologies et Applications, BDA 2021, Derakhshannia and Laurent be an effective step in the evolution of data lake architecture. Regarding the analogy of data lake and supply chain, we consider the data like a product or service that should be monitored through several stages in the data lake architecture from data entering until data consumption. With respect to this point of view, we can benefit from some management tools to improve data lake functionality. For example, we can use the policies of product lifecycle assessment that is employed in logistic systems, for data governance in data lake or hybrid decision-making problems that are essential in supply chain network design, for implementation and optimization of the data lake platform.

As figure 1 shows the simple analogy of supply chain structure and data lake architecture, data are supplied, stored, manipulated, monitored, and delivered in data lake as a product that is managed throughout the supply chain. In this architecture, data are produced and supplied from different sources and are entered in the data lake by the ingestion stage, then they are stored in their raw formats at the storage level, and finally, they are sent to the processing stage for further procedures based on users requirements. In this architecture, each level of data life cycle could be managed by mimetic logistical patterns. For example, the ingestion strategies are related to the optimal decisions about metadata management and data modeling, like supply and product design management in the supply chain. The storage strategies concentrate on selecting cost-effective storage strategies (single-store systems or multi-store systems) and data integration, just like decision-making about the number, the location, and the type of the warehouses and inventory management in the supply chain. The process strategies are the vital decisions that impact on quality of data and veracity of extracted knowledge. Therefore, the main goal of process strategies is related to choose the data processing methods that prepare the data with the fastest time and the least cost possible for data queries. Based on this requirement, the hybrid decision-making models like location-allocation problems; that bring about the best solution to optimize the supply chain networks [3]; could be a logical solution to design the affordable data lake architecture. For instance, we can use the techniques of supply chain network design (like optimization mathematical models) to determine the structure of data lake with a variety of strategic decisions such as determining the number of proper processing jobs, tactical decisions like data governance all over the data lake just like product quality assessment in the supply chain, and operational decisions like fulfilling user demands. The main objective of designing the logistical data lake architecture is to minimize further costs related to the data ingestion, storage, and processing and maximize the level of data lake performance.

CONCLUSION

In the direction of mentioned goals, we focus on data lake architecture design due to the mathematical optimization models that are inspired by hybrid problems in supply chain network design. The accomplished studies showed that these interdisciplinary methods smooth the path of presenting data lake optimization models and guarantee to obtain the affordable data lake architecture as a logistic system. In both examples, the explanations benefit the user and/or the system developer. In this thesis, we aim to explore explanations for missing recommendations from the user and the system designer viewpoint, for various types of recommenders. Typically the search space of explanations on missing items is big, thus we aim to design efficient algorithms to compute the most pertinent explanations.

RELATED WORK

Recommenders. Content-based recommenders [5] exploit similarities among the characteristics of the item and user profiles. Score-based (or collaborative filtering) recommenders [8] exploit ratings and other quantifiable user-system interactions given to the items by the users. Context-based recommenders exploit information related to the situation that the items and/or the users are in, their spatio-temporal configuration, etc. [11].

Explainable Recommenders. So far, the research in explainable recommendations is focused on the Why question: "Why is an item recommended?". The approach to explain a system depends on whether the system is white, i.e., exposing the information about its internals, or black, i.e., only the input and the output are known [12]. In the case of black-box recommenders, the explanations consist in interpreting the results by revealing relationships in the input data [4], or by pinpointing the importance of the different features concerning the predicted value [6]. Another line of work proposes to locally explain a system, with a simpler machine learning model [7]. In the case of a white box system, the explanations consist in dwelling into the intrinsic characteristics of the recommendation system to truly explain the system [2].

Why-Not questions. Explaining and debugging queries in the absence of expected query results has been studied in traditional databases [3,10], top-k spatial queries [4], or workflow analysis [1]. Recently, [9] has introduced Why-Not questions in recommenders, providing a method to answer them in Nearest Neighbours collaborative filtering. Still, a lot of space is left to be explored.

RESEARCH PROBLEM

A Why-Not question is either a question of set containment, both for individual set items and subsets, or a question of ranking (why something is ranked above or below something else)

For example, a user may ask Why-Not one missing item, a category of missing items, or ask Why-Not a certain item (or category) instead of another one already appearing in the recommendations. Additionally, he/she may ask why a recommended item does not appear higher in the recommendation list, or higher than another recommended item [9]. From another aspect, a Why-Not question can be defined in the scope of one user or for the whole system, depending also on who is the user asking the question, i.e., the final user of the recommendation system or the system developer. In this thesis, we are going to investigate the various views of a Why-Not question.

An explanation is generally defined as a piece of information displayed to users, providing the reasons why a particular item is recommended [12]. In the same spirit, a Why-Not explanation is information that helps users understand the reasons behind the absence of interesting items.

Consider again the example of the e-recruitment website in Section 1. An explanation of "Why do I get recommended to apply to an entry-level job?" could be a sample of the input data (line of the CV or extract of a job offer), or a sample of the training data (job offer to a user with a similar curriculum). A similar question, but with a different scope, would be to ask "Why don't I get any senior level job offers?". A possible explanation to this question could coincide with the aforementioned explanations for the why question. However, the why explanations do not exactly answer the Why-Not question; the user expects an answer in connection to what he/she is missing. A better type of explanation could be to exploit explicit or implicit negative user feedback for the items or categories in question, for instance "You have rarely viewed a senior-level position offer". Alternatively, to provide the users with more concrete, actionable information, the explanations could take the form of actions that if were performed by the user, then the expected items would appear as recommendations. For instance, "If you had followed more management courses, you would have been proposed 'Senior Data Architect @B' position instead of 'Junior Java Developer @A'".

The challenges that exist in explaining a recommendation system via Why-Not questions are the following. First, as in any big-data system, it is hard to know what could be missing from a result, so as to formulate a Why-Not question. Second, the search space of an explanation for a missing recommendation is much bigger than for explanations for existing recommendation (multiple possible lineages of non-results). Third, there exist various recommendation system models, calling for different solutions for each model when considered as white boxes.

An approach towards addressing the first challenge could be an interactive framework that proposes candidate missing items to the users, employing machine learning for prediction or more traditional item-scoring methods. Clustering and pruning methods of the possible explanations can be used to address the second challenge. For the third challenge, we should study explainable models with different levels of detail, from fine-grained to coarsegrained, depending on the final consumer of the explanation. Such explanations could combine relevant points of the (training) data and their features, hyper-parameters of the algorithms, the model complexity, etc. In the same context, visualization and analysis of explanations must be considered for easier consumption and understanding of explanations by the final receiver. detecting errors that might rarely occur in a real world environment. Other than verification and testing purposes, another motive of this generator would be the generation of synthetic data that mimics real world data [8]. This JSON object has two key-value pairs, where the key "x" is of type number, and the key "y" is of type boolean.

PRELIMINARIES 2.1 JSON data model

JSON Schema

JSON Schema is a language for defining the structure of JSON documents. It is maintained by the Internet Engineering Task Force IETF [3]. Its latest version has been produced on 2019-09 [9]. Example 2. Consider the following schema { "type":"object", "properties": {"x": { "type": "number" }}, "minProperties": 1 "required": ["x"] } JSON Schema uses the JSON syntax. A schema is a JSON object whose fields are assertions keywords, here we have four of them at the outermost level: type, properties, minProperties and required. The keyword type specifies the data type for a schema (e.g. the property "x" is of type number). Considering the other assertions cited previously, they are specific to the type object (i.e. can only be applied to a value of type object), in the example above minProperties constrains the JSON value to have at least one property. Such constraints exist for the other types (e.g. minLength and maxLength are used to constrain the length of a string value, minimum and maximum can only be applied to numeric values, etc.).

JSON Schema allows combining assertions using standard boolean connectives: not for negation, allOf for conjunction, anyOf for disjunction, and oneOf for exclusive disjunction. Moreover, indicating the set of accepted values can be done using the enum constraint. This work relies on some prior works on not-elimination and witness generation for JSON Schema [6], which respectively deal with the problem of removing the negation operators from a JSON Schema and generating a valid document w.r.t a JSON Schema (when the schema is non-empty).

More in detail, the structure of the witness generation algorithm is as follow : first the input Schema is translated to an algebraic representation that makes not-elimination possible. Afterwards, the algebraic representation undergoes a series of transformations until it reaches the last step of the process which is the generation step, which input is an environment composed of a set of variables along with their definitions. Finally, we recursively generate a JSON value for each variable, and these values will compose the witness of the schema.

Approach. The two problems of witness and examples generation have clearly the same nature, thus the algorithms and procedures for achieving example generation will rely on the ones introduced in witness generation, and the experimental analysis of the witness generation tool can help instigating either optimizations or new approaches.

Given the eventual existence of schemas with infinite number of valid instances, and since this set of instances is countably infinite the example generation process may be parametric by relying on user-defined constraints in order to retrieve a finite number of JSON documents.

The approach for generating values for the null and boolean types is trivial given that they have a finite number of possible values. For the number type, the idea is to find a valid value w.r.t the corresponding requirements to start with, then increment/decrement with a step which value gives the next/previous valid value, a userdefined constraint here could be a probabilistic distribution (e.g. Poisson distribution). Regarding the generation of string type values, the technique would be to update the pattern given in the constraints by excluding the word generated at each iteration until the desired number of JSON values is reached. The approach for generating multiple JSON values for the JSON types array and object is not yet well defined, but as stated before it will rely on the witness generation works with the possibility of introducing optimizations and new ideas.

USE CASES 4.1 Black box testing

Black box testing of an API is testing this API with no prior knowledge of its internal workings, it only focuses on its input and output.

Adopting JSON Schema as a way for representing the structure of the data in the JSON-based web APIs may not be a difficult task, given that these APIs provide data that is encoded using JSON.

Let us consider the two JSON Schemas that represent the input and output data consumed and produced by a web API, and then we proceed in streaming as follow : we generate data from the input JSON Schema and then we validate the data produced against the output schema. With this process we can easily check the behavior of the program, and also conduct performance measurements.

Synthetic data generation

Designing robust and reliable machine learning models require a lot of data, however acquiring huge amount of data is sometimes challenging, either for privacy and confidentiality concerns or simply for the scarcity of real world datasets.

To address this problem, companies and researchers tend to use synthetic data. Synthetic data is data that is artificially created, it can be fully synthetic or generated according to real world data, thus having the same structure and statistical properties [7].

Generating JSON synthetic data by applying similar techniques could be interesting, an approach here is inferring a JSON Schema from JSON data as well as structural and quantitative information [5], then we generate the synthetic data from the JSON Schema inferred by considering the information retrieved as constraints.

RELATED WORK

There exist few implementations of JSON data generators, and only a couple of them generate data from JSON Schema [1,2]. These generators do not possess a solid theoretical background, hence they are not complete and they sometimes produce wrong outputs. The inability of eliminating negative operators is one of the struggles encountered by these generators, indeed when testing schemas containing negation the generated JSON documents are most of the time incorrect.

CONCLUSION

We have defined in this paper the problem of generating JSON data from JSON Schema and given an approach to achieve this. We have shown that although JSON Schema is not widely used for describing and validating JSON documents, there still exist use cases that could benefit from a JSON data generator. Generating mock data could be used for testing, by simulating the behavior of JSON-based web APIs in order to detect errors that could not be detected using real world data and to measure the performance of the programs. In addition to this, the generation of JSON data in the fields of artificial intelligence and machine learning could help overcome the problem of real world data scarcity by building synthetic datasets, and could also help in building solid AI automation tools.

- 1 - 1 - 1 - 1 - 1 -- 1 -2. 5

 1111115 Rennes, et INSA Valor. Enfin, nos remerciements vont aux nombreux participants qui ont fait vivre cette belle édition 2021. Philipp Rigaux, Président des journées Zoltan Miklos, Président du Comité d'Organisation Esther Pacitti, Président du Comité de Programme Zoltan Miklos, IRISA, Université de Rennes 1 (président) -Hélène Jaudoin, IRISA, Université de Rennes 1 -François Goasdoué, IRISA, Université de Rennes Virginie Thion, IRISA, Université de Rennes Laurent d'Orazio, IRISA, Université de Rennes Mickaël Foursov, IRISA, Université de Rennes Annie Foret, IRISA, Université de Rennes Sébastien Ferré, IRISA, Université de Rennes 1 -Michael Thomazo, INRIA, ENS PSL -Camille Bourgaux, CNRS, ENS PSL -Bernd Amann, LIP6, Sorbonne Université2.3 Comité de programme -Esther Pacitti, LIRMM, Université de Montpellier (présidente) -Bernd Amann, LIP6, Sorbonne Université -Omar Boucelma, LSIS, Université Aix-Marseille -Amel Bouzeghoub, Télécom SudParis -Sylvie Cazalens, LIRIS, INSA de Lyon -Sarah Cohen-Boulakia, LRI, Université Paris-Sud -Alexandru Constan, INRIA -Helena Galhardas, Université de Lisbonne -François Goasdoué, IRISA, Université de Rennes 1 -Daniela Grigory, LAMSADE, Université Paris-Dauphine -David Gross-Amblard, IRISA, Université Rennes 1 Mirian Halfeld Ferrari, LIFO, Université d'Orléans -Zoubida Kedad, DAVID, Université de Versailles-Saint-Quentin -Anne Laurent, LIRMM, Université de Montpellier -Ioana Manolescu, INRIA, Institut Polytechnique de Paris -Riad Mokadem, IRIT, Université Paul Sabatier -Pascal Molli, LS2N, Université de Nantes -Cedric Mouza, CNAM -Hubert Naake LIP6, Sorbonne Université -Paolo Papotti, EUROCOM -Jorge-Arnulfo Quiané-Ruiz, TU Berlin -Claudia Ronconcio, LIG, Université de Grenoble -Marie-Christine Rousset, LIG, Université de Grenoble Alpes -Patricia Serrano, LS2N, Université de Nantes -Maximilien Servajean, LIRMM, Université de Montpellier -Dennis Shasha, New York University -Hala Skaf-Molli, LS2N, University of Nantes -Farouk Toumani, LIMOS, Université Clermont Auvergne -Patrick Valduriez, INRIA, Université de Montpellier -Genoveva Vargas, LIRIS, INSA de Lyon -Dan Vodislav, ETIS, University of Cergy-Pontoise -Karine Zeitouni, DAVID, Université de Versailles-Saint-Quentin 2.4 Comité de démonstration -Reza Akbarinia, INRIA (président) -Tristan Allard, IRISA, Université de Rennes -Oana Balalau, Inria and École Polytechnique -Laure Berti-Equille, IRD -Dario Colazzo, LAMSADE, Université Paris-Dauphine -Camélia Constantin, LIP6, Sorbonne Université -Amelie Gheerbrant, IRIF, CNRS, Université de Paris -Hélène Jaudoin, IRISA, Université de Rennes Florent Masseglia, INRIA -Nada Mimouni, Le CNAM -Tanmoy Mondal, IMT Atlantique -Marian Scuturici, LIRIS, INSA de Lyon -Nicolas Travers, Léonard de Vinci Pôle Universitaire -Katerina Tzompanaki, ETIS, Université de Cergy-Pontoise -Chao Zhang, LIRIS, Université Lyon 1 Comité du prix de thèse -Jean-Marc Petit, LIRIS, INSA de Lyon (président) -Laure Berti-Equille, IRD, Montpellier -Pierre Bourhis, Cristal, CNRS, Lille -Daniela Grigori, Lamsade, Paris Dauphine -Nabil Layaïda, Tyrex, INRIA, Grenoble -Ioana Manolescu, Cedar, INRIA, Paris Saclay -Sofian Maabout, Labri, Bordeaux -Florent Masseglia, Zenith, INRIA, Montpellier

  Nguyen graduated from ENS Cachan in 2000. He obtained his Ph.D from University of Paris Sud in 2003 on data warehousing, and his HDR from University of Versailles in 2013 on privacy preserving data mangement. Since 2014, he holds a professor position in the Systems and Data Security team of the Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), at INSA Centre Val de Loire and is an external collaborator of the Inria Private and Trusted Cloud (PETRUS) team. His current research topics cover anonymization techniques, models and methods to represent, quantify and enforce privacy models (such as logics, secure hardware and cryptography), and the design and implementation of large scale privacy-by-design information management systems. Pr. Nguyen is head of LIFO since 2016, and co-chair of the Privacy Working group of the CNRS research group on Computer Security since 2016.

Figure 1 :

 1 Figure 1: Predictive Anomaly Explanation Pipeline

Conference' 17 ,

 17 July 2017, Washington, DC, USA Chao Zhang, Reza Akbarinia, and Farouk Toumani

Figure 1 :

 1 Figure 1: Example of computing sum over a count-based sliding window with a range of 10 values and a slide of 2 values. SWAG computation consists of two phases: (1) computing the partial aggregations sum over 2 values; (2) merging 5 partial aggregations.

BDA' 21 ,

 21 October 2021, Paris, France R.Bouhamoum, et al.

Figure 1 :

 1 Figure 1: Overview of the Incremental Schema Discovery Approach

Figure 2 :

 2 Figure 2: Incremental vs. Sequential Scalable Algorithm

Figure 1 :

 1 Figure 1: Une relation r avec les 3 treillis de vérité associés

Figure 2 :

 2 Figure 2: L'égalité de deux tuples avec un contexte de schéma

Figure 3 :

 3 Figure 3: Le treillis abstrait L r associé à r

Figure 1 :

 1 Figure 1: goldMEDAL concepts (UML class diagram)

BDA 2021, 25 -

 25 28 octobre 2021, En ligne, France Scholly, et al. goldMEDAL: A Data Lake Generic Metadata Model 3 GOLDMEDAL LOGICAL MODEL At the logical level, goldMEDAL concepts are represented by a graph. Data entities translate into nodes, links translate into edges and groups and processes translate into hyperedges. For example, in Figure 2, four data entities (say, textual documents) are represented by nodes 𝑛 1 , 𝑛 2 , 𝑛 3 and 𝑛 4 . The set of hyperedges 𝐻 1 = {𝜃 11 , 𝜃 12 } represents a zone grouping, where 𝜃 11 and 𝜃 12 are hyperedges representing the groups Raw data zone and Processed data zone, respectively. Similarly, 𝐻 2 = {𝜃 21 , 𝜃 22 } represents a language grouping, where 𝜃 21 and 𝜃 22 represent the groups French and English, respectively.

Figure 2 :

 2 Figure 2: Sample grouping graph logical model Figure 3 represents the logical model of a process that merges two data entities (say, two relational tables) represented by nodes 𝑛 7 and 𝑛 8 into a new node 𝑛 9 . Process Π 1 = {Υ 1 , Ω 1 } is an oriented hyperedge, with Υ 1 = {𝑛 7 , 𝑛 8 } and Ω 1 = {𝑛 9 } being the sets of input and output nodes of Π 1 , respectively.

Figure 3 :

 3 Figure 3: Sample process graph logical model

  yang@lri.fr LISN, Univ. Paris-Sud, CNRS, Université Paris-Saclay Orsay, France Yue Ma ma@lri.fr LISN, Univ. Paris-Sud, CNRS, Université Paris-Saclay Orsay, France Nicole Bidoit nicole.bidoit@lri.fr LISN, Univ. Paris-Sud, CNRS, Université Paris-Saclay Orsay, France

  For a given EL + ontology O, the associated hyper-graph G O = (V O , E O ) is illustrated as Figure 1.

Figure 1 :

 1 Figure 1: Illustration of hyper-edges.

Figure 2 :

 2 Figure 2: Structure of H-paths ( and ℎ for the existence of simple and H-paths respectively).

Figure 3 :

 3 Figure 3: The y-axis is the log value of time(s). The red (resp. black) curve presents the increasingly ordered (log value of) time cost of PULi (resp. minH). For a green point (𝑥, 𝑦), 𝑒 𝑦 is the time cost of minH for the query corresponding to the red point (𝑥, 𝑦 ′ ) in the red line.

Figure 1 :Figure 2 :

 12 Figure 1: Coverage and p-values as a function of 𝑛

© 2021 ,

 2021 Copyright is with the authors. Published in the Proceedings of the BDA 2021 Conference (October 25-28, 2021, En ligne, France). Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0. © 2021, Droits restant aux auteurs. Publié dans les actes de la conférence BDA 2021 (25-28 octobre 2021, En ligne, France). Redistribution de cet article autorisée selon les termes de la licence Creative Commons CC-by-nc-nd 4.0.

Figure 1 :

 1 Figure 1: Creation of a slice set for a pool of queries.

Figure 2 :

 2 Figure 2: Three slice sets feeding each other. Each slice set is built from its own query step, and it is filled either by the data stream (Γ a ) or by another slice set (Γ b and Γ c ).

Figure 3 :

 3 Figure 3: A pooled slice set Γ bc built from queries {b, c} and subscribing to another slice set Γ a .

Figure 4 :

 4 Figure 4: Cost of the query plan following, from left to right, no sharing, pool, feed and hybrid schemes.

  KEYWORDS contre-exemple, fonction, dépendance fonctionnelle, g3, indicateur, non-stricte, np-hard, données massives, fastg3 1 INTRODUCTION Lorsqu'elle collabore avec des experts métiers dans le but de confronter leurs connaissances à des données réelles, la spécialiste en science des données a besoin d'un moyen efficace pour exprimer et évaluer leur modèle sur un jeu de données. Souvent, le modèle peut s'exprimer à travers une fonction. Par exemple, la fonction reliant la puissance d'une turbine au débit et à l'élévation du fleuve (et deux constantes 𝜌 et 𝜂) comme présenté en Formule 1 nous sert de fil rouge dans la version complète du papier. power = 𝑓 𝜂,𝜌 (flow, elevation) = 𝜂 • 𝜌 • flow • elevation (1) Par conséquent, pour évaluer le bon fonctionnement de leurs turbines et avoir un aperçu des optimisations techniques possibles, il est intéressant d'évaluer la véracité de la fonction 1 par rapport aux données enregistrées sur place. Pour exprimer une telle fonction, les dépendances fonctionnelles (DFs) ont prouvé leur efficacité en offrant un cadre complet pour exprimer des contraintes entre des ensembles d'attributs dans une relation. Par exemple, la fonction 1 peut s'exprimer par la DF suivante :

BDA ' 21 ,

 21 October 25-28, 2021, Paris, France Faure--Giovagnoli, et al.

  BDA 2021, 25-28 octobre, 2021, Paris, France A.Gillet et al.

Figure 1 :

 1 Figure 1: Overview of the Lambda+ Architecture

1

 1 Paul r 5 Apple A 4 Samsung r 4 Rick A 3 Paul ... r 5 Paul r 1 iPad_4th A 2 Galaxy r 3 Steve r 3 Galaxy ...

3Figure 1 :

 1 Figure 1: A vector space learned from text (prior methods) and from data (EmbDI).

2. 1 . 1

 11 Transformation du Problème (PT). La transformation du problème consiste à 'transformer' le jeu de données pour changer le problème en une classification multiclasses à label unique. Une de ces méthodes consiste à considérer toutes les combinaisons uniques de labels possibles du jeu de données, label powerset[Tsoumakas et al. 2010], et à entraîner un classifieur multiclasses 𝑀 : 𝑋 → 𝑃 (𝑌 ), où Architectures Transformeurs pour la classification multilabels de textes BDA 2021, 25-28 octobre, 2021, ENS, Paris 𝑃 (𝑌 ) est le powerset de Y, l'ensemble des sous-ensembles uniques et distincts de labels. En plus du nombre élevé de classes possibles qui peut atteindre 2 |𝑌 | , le challenge réside dans la capacité à trouver suffisamment d'exemples pour chaque combinaison de labels pour éviter la sousreprésentation des classes. La pertinence binaire [Boutell et al. 2004], est une autre méthode de transformation de problème où sont entraînés |Y| classifieurs binaires qui détectent la présence ou la non-présence d'un label pour une instance. |Y| jeux de données sont construits à partir du jeu original. Chaque jeu de données 𝐷 𝑦 , 𝑦 ∈ Y, contient les instances où 𝑦 est un label qui les caractérise. Pour une instance 𝑥 du jeu de données, le résultat de la classification est l'union des labels détectés par chaque classifieur. Pour un |Y| grand, le temps d'entraînement et d'inférence des modèles est élevé. Il est important de noter, qu'en transformant le problème en une classification multiclasses, les dépendances qui peuvent exister entre les différents labels ne sont plus considérées [Luaces et al. 2012].2.1.2 Méthodes d'ensembles. Un ensemble de classifieurs multiclasses peut être combiné pour créer un classifieur multilabels. Pour une instance donnée, chaque classifieur va prédire une seule classe et toutes les sorties de ces classifieurs sont alors combinées via une méthode d'ensemble. Une de ces méthodes consiste à considérer une classe comme présente si un pourcentage de classifieurs ayant prédit cette classe est atteint, aussi appelé seuil discriminatif 1 . L'algorithme 𝑅𝐴𝐾𝐸𝐿 [Tsoumakas and Vlahavas 2007] est une autre variation de cette méthode. Des classifieurs entraînés sur des sous-ensembles aléatoires des labels powersets sont utilisés pour la création d'un classifieur multilabels, les prédictions de ces classifieurs passent par un système de vote pour la prédiction finale.L'utilisation de plusieurs classifieurs impose des contraintes fortes en termes d'espace mémoire, ainsi que la nécessité d'optimiser un nombre de modèles qui augmente linéairement avec le nombre de classes du jeu de données.2.1.3 Adaptation du Problème (PA).Les méthodes d'adaptation du problème ne nécessitent pas une transformation du jeu de données mais une adaptation des algorithmes de classification, tels que ML-kNN[START_REF] Zhang | ML-KNN: A lazy learning approach to multi-label learning[END_REF] qui étend l'algorithme kNN pour les données multilabels, ou BP-MLL [Min-Ling Zhang and Zhi-Hua Zhou 2006] une adaptation de l'algorithme de rétro-propagation pour les réseaux de neurones.

Figure 1 :

 1 Figure 1: Architecture BERT avec une couche dense de classification au-dessus des couches transformeurs et les valeurs d'activation des sorties.

  [CLS] comme entrée, et 𝑛 𝑦 sorties (approche similaire à [Adhikari et al. 2019]. La figure 1 présente l'architecture du modèle. Architectures Transformeurs pour la classification multilabels de textes BDA 2021, 25-28 octobre, 2021, ENS, Paris

Figure 2 :

 2 Figure 2: Architecture couche de classification dense avec un paramètre pour le calcul du nombre de classes présentes.

Figure 3 :

 3 Figure 3: Architecture couche de classification dense de seuillage rajoutée à la fin du classifieur.

BDA 2021, 25 -

 25 28 octobre, 2021, ENS, Paris Fallah et al.

Figure 4 :

 4 Figure 4: Compte des instances en fonction du nombre de labels pour l'ensemble des corpus.

© 2021 ,Figure 1 :

 20211 Figure 1: Overview of IOPE workflow

© 2021 ,

 2021 Copyright is with the authors. Published in the Proceedings of the BDA 2021 Conference (October 25-28, 2021, En ligne, France). Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0. © 2021, Droits restant aux auteurs. Publié dans les actes de la conférence BDA 2021 (25-28 octobre 2021, En ligne, France). Redistribution de cet article autorisée selon les termes de la licence Creative Commons CC-by-nc-nd 4.0.

BDA' 21 ,Figure 1 :

 211 Figure 1: DNA Storage Pipeline

__________________________________________________________________________________________ 2021 ,

 2021 Copyright is with the authors. Published in the Proceedings of the BDA 2021 Conference (October 25-28, 2021, En ligne, France). Distribution of this paper is permitted under the terms of the Creative Commons license CC-bync-nd 4.0. 2021, Droits restant aux auteurs. Publié dans les actes de la conférence BDA 2021 (25-28 octobre 2021, En ligne, France). Redistribution de cet article autorisée selon les termes de la licence Creative Commons CC-by-nc-nd 4.0. Post-actes BDA 2021 5 RÉSUMÉS DES ARTICLES COURTS BDA 2021, Octobre, 2021, Paris, France A. Saulnier.

Figure 1 :

 1 Figure 1 : Schéma général du modèle conceptuel Le modèle proposé est représenté sur la Figure 1. Les concepts principaux (en noir), que l'on retrouve aussi sous le nom de classes, correspondent tout d'abord aux éléments de la chaine de production médiatique: Producteur de contenu, Editeur, Participant, Maison mère et Propriétaire. Ensuite, nous nous sommes inspirés des ontologies documentaires, BibFrame et FRBR, pour distinguer le Produit médiatique (oeuvre) de ses Publications, ce qui permet de relier plusieurs publications (presse papier, web, ou réseaux sociaux…) à un même produit. Les identifiants externes (en vert) font référence à des éléments de base du Web sémantique. Il s'agit aussi bien de classe pour le modèle que d'URIs pour identifier des ressources particulières dans les instances. Il existe

Figure 1 :

 1 Figure 1: Analogy of supply chain structure and data lake architecture

Figure 1 :

 1 Figure 1: Screenshot: from JSON Schema to our algebra.

BDA ' 21 ,

 21 October 25-28, 2021, Paris, France Faure--Giovagnoli, et al. dans ses attributs ou sa sélection des données. Nous proposons plusieurs statistiques sur le jeu de données jusqu'à des granularités au niveau du tuple ainsi qu'une représentation interactive des données et des contre-exemples trouvés. Juste avant la création du modèle, ADESIT propose à l'utilisateur de comprendre les limites de son jeu de données, participant ainsi à tout le processus de l'acquisition au prétraitement. Pour un nouveau problème d'AS, nous voulons que l'utilisateur soit rapidement en mesure d'évaluer les performances qu'il ne peut dépasser et les mesures à prendre avant d'aborder le processus d'apprentissage. 2 VUE GÉNÉRALE DU SYSTÈME 2.1 Analyse des contre-exemples On considère une relation 𝑟 [𝑈 ] avec 𝑈 un ensemble d'attributs et une cible 𝐶 à prédire à partir d'un ensemble d'attributs 𝑋 tel que 𝑋 ∪ {𝐶} ⊆ 𝑈 . Ainsi, la fonction sous-jacente 𝑓 (𝑋 ) ≃ 𝐶 peut être représentée par une DF sous la forme 𝜑 : 𝑋 → 𝐶. Dans notre cas d'étude par exemple, on peut utiliser le débit et l'élévation d'un fleuve pour prédire la puissance d'une turbine tel que 𝑓 (𝑑𝑒𝑏𝑖𝑡, 𝑒𝑙𝑒𝑣𝑎𝑡𝑖𝑜𝑛) ≃ 𝑝𝑢𝑖𝑠𝑠𝑎𝑛𝑐𝑒 devient 𝑑𝑒𝑏𝑖𝑡, 𝑒𝑙𝑒𝑣𝑎𝑡𝑖𝑜𝑛 → 𝑝𝑢𝑖𝑠𝑠𝑎𝑛𝑐𝑒. Mesurer la véracité de 𝜑 dans 𝑟 et donc la présence de la fonction 𝑓 associée permet alors d'évaluer le potentiel d'apprentissage d'un jeu de données. Notamment, ADESIT propose l'étude des contreexemples : un contre-exemple est une paire de tuples avec des valeurs d'attributs X égales et des cibles 𝐶 différentes. Dans cette étude, le calcul des contre-exemples est étendu à une classe de DFs non-strictes où l'égalité stricte est remplacée par prédicats permettant de prendre en compte des notions d'incertitudes et de généralisation. Dans ce cas, la paire de tuples (𝑢, 𝑣) forme un contreexemple ssi pour tout 𝐴 ∈ 𝑋 , 𝑢 [𝐴] ≃ 𝑣 [𝐴] et 𝑢 [𝐶] 𝑣 [𝐶] avec ≃ un prédicat lié à une mesure de similarité.

Figure 1 :

 1 Figure 1: Interface labellée d'ADESIT. A : Paramètre du problème d'apprentissage supervisé. B : Indicateurs de contreexemples. C : Exploration des contre-exemples.

BDA ' 21 ,

 21 October 25-28, 2021, Paris, France Rosendo, et al.

Figure 1 :

 1 Figure 1: Processing DL workloads on the Computing Continuum. main factors leading to stragglers slowing down the whole training process. The architectural differences of DNNs should be compared.The outcomes will drive the design of a framework mitigating the identified infrastructure bottlenecks in DL scenarios. By explicitly considering heterogeneity, various policies should improve the following objectives:

Figure 1 :

 1 Figure 1: Graph modeling the use case of smart transportation networks

Conference' 17 ,

 17 July 2017, Washington, DC, USA Maria Massri

Figure 2 :

 2 Figure 2: Queries 𝑄 1 , 𝑄 2 , 𝑄 3 and 𝑄 4 of Example 1.1 expressed with the T-Cypher syntax

Algorithm 1 :

 1 𝑇 3 : projection by edge-addition, Bound QLout-degree Input: A graph G = (V, E) ∈ gwhose edges are label within the set 𝐿, a degree bound D, a stable edge ordering A, a set of labels QL ⊆ L Output: An output D-Ql-out-degree bounded graph 𝑇 3 (G)

Conference' 17 ,

 17 July 2017, Washington, DC, USA Nelly Barret

Algorithm 1 : 5 if

 15 Classifying a collection 𝑐Input: a collection 𝑐, hints H, categories K Output: a category 𝑘 ∈ K or Other 1 foreach 𝑟 ∈ C do 2 the similarity between 𝑘 and the label of 𝑟 is higher than a threshold then 6 K𝑟 ← K𝑟 ∪ {𝑘 } 7 foreach 𝑛𝑐 ∈ 𝑟 .children do 8 𝜋 ← (𝑛𝑐.𝑙𝑎𝑏𝑒𝑙, 𝑛𝑐.𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒) 9 foreach ℎ ∈ H do 10 scores ← scores (ℎ, 𝑠𝑖𝑚 (𝜋, ℎ)) 11 bestHint ← argmax(scores) 12 K𝑟 ← K𝑟 ∪ { bestHint.domain } 13 Classify 𝑟 in the most frequent 𝑘 ∈ K𝑟 , or Other 14 Classify 𝑐 with the most frequent category of its records Creative Work. Moreover, the authors are identified as a collection of Persons.

Figure 1 :

 1 Figure 1: Example of 𝐺 ′ , an abstract graph with collections and categorized records.

Figure 1 :

 1 Figure 1: Analogy of supply chain structure and data lake architecture

Figure 1 :

 1 Figure 1: User likes (solid arrow), recommendations (dashed arrow) and missing recommendation (dotted arrow)

  JSON values are either basic values, objects, or arrays. Basic values include the null value, booleans, numbers and strings. Objects represent sets of members, each member being a name-value pair, and arrays are ordered lists of values. Example 1. Consider the following JSON object { "x" : 0, "y" : true }

BDA ' 21 ,

 21 October 2021, Paris Attouche3 EXAMPLE GENERATIONExample generation for JSON Schema is the procedure of generating valid JSON documents w.r.t a JSON schema given as an input.

  Esther Pacitti 1 and Zoltan Miklos 2 1 LIRMM, Université de Montpellier. esther.pacitti@lirmm.fr 2 IRISA, Université de Rennes 1. zoltan.miklos@irisa.fr A Demonstration of the Exathlon Benchmarking Platform for Explainable Anomaly Detection Vincent Jacob, Fei Song, Arnaud Stiegler, Bijan Rad, Yanlei Diao and Nesime Tatbul SaGe-Path : Pay-as-you-go SPARQL Property Path Queries processing using Web Preemption Julien Aimonier-Davat, Hala Skaf-Molli, Pascal Molli . . . . . . . . . . . . . . . . . . Tell Me What Air You Breath, I Tell You Where You Are Hafsa El Hafyani, Mohammad Abboud, Jingwei Zuo, Katerine Zeitouni, Yehia Taher .

	BDA 2021
	-
	37ème Conférence sur la Gestion de Données
	Principes Technologies et Applications

  Une approche déclarative des comparabilités : application aux dépendences fonctionnelles. *

	Lhouari Nourine lhouari.nourine@uca.fr LIMOS, Université Clermont Auvergne Aubière, France	Jean-Marc Petit jean-marc.petit@insa-lyon.fr LIRIS, Université de Lyon Lyon, France	Simon Vilmin † simon.vilmin@ext.uca.fr LIMOS, Université Clermont Auvergne Aubière, France

  représente donc le contexte du schéma R. Dans la Figure 2 nous illustrons le fonctionnement de notre cadre formel avec les tuples t 2 et t 4 . D'abord nous comparons t 2 et t 4 avec f R et obtenons le tuple abstrait ⟨u, t, u⟩. En effet, nous avons f A (1.5, 3.5) = дb, f B (F, F ) = t et f C (null, 76) = u. Ensuite, nous considérons deux interprétations possibles : д 1 et д 2 . Dans la figure, les éléments en blancs (au dessus des pointillés) sont interprétés à 1. Les noirs (en dessous des pointillés) sont interprétés à 0. Il s'en suit que par д 1 , les tuples t 2 et t 4 diffèrent sur A et C, tandis ce qu'ils sont égaux pour д 2 . Observons que д 1 et д 2 sont des réalités.

Table 1 :

 1 Summary of size of elk, U.

			go-plus galen7 snt2015 snt2021
		average	166.9	3602.0	114.7	67.3
	elk	median	43.0	3648.0	10.0	31.0
		max	7919.0	81501.0	2357	2226
		average	34.2	74.6	29.4	19.4
	U	median max	4.0 7772	5.0 24103	1.0 2002	3.0 6452
	#non-trivial query	50272	62470	195082	304321

  Greedy coverage algorithm (COVER_G)illustrated with Benjamini-Yekutieli correction Input: a Request 𝑅, a dataset 𝐷, a significance level 𝛼, number of desired results 𝑛 Output: 𝐶 1 Candidates ← GenerateCandidates(𝑅, 𝐷) 2 Candidates ← ComputePvalues(Candidates, 𝛼)

	BDA '21, October 25-28, 2021, Paris, France	Bouarour, Benouaret, Amer-Yahia
	Algorithm 1:

  = argmax 𝑐∈Candidates 𝑐𝑜𝑣𝑒𝑟 (𝐶 ∪ {𝑐 }, 𝐷)Input: a request 𝑅, a dataset 𝐷, a significance level 𝛼, number of results 𝑛,

		1/𝑖	-1
	7 while |𝐶 | ≤ 𝑛 do
	9 10 11	Candidates ← Candidates \{𝑐 * } if 𝑐 * .𝑝𝑣𝑎𝑙 ≤ 𝐿 [𝑘 ] then 𝐶 ← 𝐶 ∪ {𝑐 * }
	12 return 𝐶
	Algorithm 2: 𝛼-investing coverage algorithm (COVER_𝛼)

8

𝑐 * parameters 𝜆

  Attaque par inférence d'appartenance sur des séries temporelles agrégées en utilisant la programmation par contraintes

	Efficient Exploration of Interesting Aggregates in RDF Graphs
	Yanlei Diao yanlei.diao@polytechnique.edu Ecole Polytechnique, Institut Polytechnique de Paris Palaiseau, France Inria Palaiseau, France	Paweł Guzewicz pawel.guzewicz@inria.fr Ecole Polytechnique, Institut Polytechnique de Paris Palaiseau, France Inria Palaiseau, France
	Dans cet article, nous étu-dions la vulnérabilé de séries temporelles agrégées -où chaque point est un agrégat horodaté -face à des attaques par inférence d'appartenance. L'attaquant que nous considérons dispose de con-naissances auxiliaires sur un sur-ensemble des données agrégées multiples points formant la série temporelle agrégat. Notre attaque attaque tirant parti de ce type de connaissances auxiliaires et des (e.g., issu d'une fuite de données). Nous proposons une nouvelle Ioana Manolescu ioana.manolescu@inria.fr Inria Palaiseau, France Ecole Polytechnique, Institut Polytechnique de Paris Palaiseau, France ABSTRACT Large (Linked) Open Data are increasingly published as RDF graphs today. However, such data has not yet reached its full potential in terms of sharing and reuse. The main bottleneck here lies in the capacity of human users to explore, discover, and grasp the content and insights of RDF graphs, which are inherently heterogeneous and can be both large and complex. To help democratize the access to such intricate data collections, we need new automatic tools.	est modélisée comme un problème d'optimisation linéraire en nom-Mirjana Mazuran mirjana.mazuran@inria.fr Inria Palaiseau, France Ecole Polytechnique, Institut Polytechnique de Paris Palaiseau, France bres entiers, permettant à l'attaquant de bénéficier de la puissance des solveurs dédiés (e.g., Gurobi). Cette attaque, testée sur des jeux de données publics, montre la vulnérabilité d'une publication de série temporelle agrégat si le nombre de séries agrégées est trop faible face au nombre de points constituant la série.

ABSTRACT

L'agrégation est largement utilisée comme méthode de protection de la vie privée. Les attaques par inférence d'appartenance sur agrégat ont pour but de déterminer si une cible donnée a participé ou non au calcul de l'agrégat attaqué.

Table 1

 1

	: Data complexity of cardinality queries based upon concept / role atoms for various DL-Lite dialects. † : holds for all DL-Lite H 𝑐𝑜𝑟𝑒 ontologies without negative role inclusions.

  Demian Hespe, Sebastian Lamm, Christian Schulz, and Darren Strash. 2020. We-GotYouCovered : The Winning Solver from the PACE 2019 Challenge, Vertex Cover Track. In 2020 Proceedings of the SIAM Workshop on Combinatorial Scientific Computing. SIAM, 1-11. [3] Jyrki Kivinen and Heikki Mannila. 1995. Approximate inference of functional dependencies from relations. Theoretical Computer Science 149, 1 (1995), 129-149. [4] Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld. 2012. A nearoptimal sublinear-time algorithm for approximating the minimum vertex cover size. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1123-1131. [5] Shaoxu Song. 2010. Data dependencies in the presence of difference. Ph. D. Dissertation. Hong Kong University of Science and Technology. [6] Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. 2009. An improved constant-time approximation algorithm for maximum˜matchings. In Proceedings of the forty-first annual ACM symposium on Theory of computing. 225-234.Lambda+, the renewal of the Lambda Architecture: Category Theory to the rescue

	Annabelle Gillet LIB Univ. Bourgogne Franche Comté Dijon, France annabelle.gillet@depinfo.u-bourgogne.fr	Éric Leclercq LIB Univ. Bourgogne Franche Comté Dijon, France eric.leclercq@u-bourgogne.fr	Nadine Cullot LIB Univ. Bourgogne Franche Comté Dijon, France nadine.cullot@u-bourgogne.fr

[1]

Graham Cormode, Lukasz Golab, Korn Flip, Andrew McGregor, Divesh Srivastava, and Xi Zhang. 2009. Estimating the Confidence of Conditional Functional Dependencies. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data (Providence, Rhode Island, USA) (SIGMOD '09). Association for Computing Machinery, New York, NY, USA, 469-482. https: //doi.org/10.1145/1559845.1559895 [2]

•

  𝐺𝑃 is a temporal graph pattern, • 𝐹 𝐼𝐿𝑇 𝐸𝑅 is a boolean combination of atomic comparisons of the form 𝑡 > 𝑡 ′ or 𝑡 ≥ 𝑡 ′ where 𝑡 and 𝑡 ′ are variables of

	Definition 2 (Utility policy). A utility policy is defined by a set of TACQ queries, called utility queries. A utility policy (issued by a service provider) is satisfied by a data producer if s/he accepts to provide the set of answers of all of the utility queries for any RDF graph storing her/his data.
	Definition 1 (Temporal aggregated conjunctive query). A 𝑇 𝐴𝐶𝑄 is defined as SELECT x, 𝑎𝑔𝑔(𝑦) WHERE {𝐺𝑃 . 𝐹 𝐼𝐿𝑇 𝐸𝑅} GROUP BY x TIMEWINDOW (𝑆𝑖𝑧𝑒, 𝑆𝑡𝑒𝑝) where
	𝑉 𝑎𝑟 (𝐺𝑃) or literals (numbers, strings or dates), • x is a tuple of variables called the output (or grouping) vari-ables,

• when the aggregate term 𝑎𝑔𝑔(𝑦) is present, 𝑦 (called the aggregate variable) is not in x and 𝑎𝑔𝑔 is an aggregate function that produces a single value when applied to a set of values assigned to 𝑦.

, Hira Asghar, Christophe Bobineau, and Marie-Christine Rousset

• 𝑆𝑖𝑧𝑒 and 𝑆𝑡𝑒𝑝 are time durations (i.e. differences between timestamps),

  Les requêtes SPARQL property path représentent un outil indispensable pour chercher des motifs complexes dans un graphe de connaissance. Cependant, évaluer ces requêtes sur des données en ligne, et obtenir des résultats complets, est difficile. Du fait de leur complexité, les requêtes property path sont souvent intérrompues par les politiques d'usage équitable en place sur les SPARQL endpoints. Pour garantir des résultats complets, le client Web décompose les requêtes property path en un ensemble de sous-requêtes, dont la terminaison est garantie par le serveur. La granularité de la décomposition dépend de l'expressivité du serveur. Quand bien même, décomposer une requête property path peut générer un important traffic entre le client et le serveur, si bien que le temps d'exécution d'une requête se retrouve dominé par les coûts réseaux. Dans ce papier, nous étendons le modèle de la préemption Web avec un nouvel opérateur, capable d'évaluer des fermetures transitives partielles (PTC). Cet opérateur repose sur l'utilisation d'un algorithme de recherche en profondeur, dont l'exploration est limitée à une profondeur 𝑘, définie à l'avance. Nous montrons ensuite qu'un client Web, s'il dispose d'un serveur SPARQL préemptif sur lequel est implémenté l'opérateur PTC, est capable d'exécuter efficacement n'importe quelle requête property path, avec la garantie d'obtenir des résultats complets. Une étude expérimentale confirme que, par rapport aux approches par décomposition, notre approche réduit drastisquement la quantité de données et le nombre d'appels échangés entre le client et le serveur, et ainsi, le temps d'exécution des réquêtes SPARQL property path.

	Université de Nantes, LS2N Nantes, France julien.aimonier-davat@univ-nantes.fr Reasoning in EL-Description Logic with Refreshing Variables Hala Skaf-Molli Université de Nantes, LS2N Nantes, France hala.skaf@univ-nantes.fr Pascal Molli Université de Nantes, LS2N pascal.molli@univ-nantes.fr Nantes, France Théo Ducros LIMOS Aubière, France theo.ducros@limos.fr Marinette Bouet LIMOS Aubière, France marinette.bouet@uca.fr Farouk Toumani LIMOS Aubière, France farouk.toumani@limos.fr
	RÉSUMÉ

Table 1 :

 1 Table 1 for unsupervised settings show that EmbDI-O embeddings obtain the best quality results in three scenarios and

	BB WA AG FZ IA DA DS IM	Pretrain fTxt 0.59 0.58 0.18 0.99 0.10 0.72 0.80 0.31	Local EmbDI-S EmbDI-F EmbDI-O N2V Harp 0.50 0.82 0.86 0.86 0.86 0.59 0.75 0.81 mem 0.78 0.14 0.57 0.59 0.70 0.71 0.98 0.99 0.99 1.00 1.00 0.09 0.09 0.11 mem 0.14 0.95 0.94 0.95 0.87 0.97 0.85 0.75 0.92 mem 0.81 0.90 0.64 0.94 mem 0.95

F-Measure results for Entity Resolution (ER).

second to the best in four cases. In every case, local embeddings obtained from our graph outperform pre-trained ones. L'analyse de sentiment est le processus d'extraction de la polarité d'un texte afin de déterminer son orientation sémantique : positive, négative, ou neutre. Grâce à sa présence dans plusieurs domaines de recherche

[7, 14]

, beaucoup travaux

[2, 4, 5, 13, 15, 17]

se sont penchés sur l'analyse de sentiment et des outils performants pour l'extraction automatique de la polarité du texte. Néanmoins, malgré les avancées de la recherche réalisées dans ce domaine, cette tâche reste difficile à cause de la richesse du langage naturel et la dépendance de la polarité au contexte. Pour illustrer cette complexité, considérons les deux phrases : (a) Donald Trump softens tone on

  BDA'21, Octobre 2021, En ligne, France Mammar kouadri, et al.Notre évaluation porte sur deux types d'incohérences : des incohérences intra-algorithme qui se produisent dans le cas ou un algorithmes extrait des polarités différentes de deux phrases sémantiquement équivalentes, et des incohérences inter-algorithme qui se produisent lorsque deux algorithmes attribuent des polarités différentes à la même phrase. Nous avons évalué six algorithmes d'analyse de sentiment qui appartiennent à des catégories différentes pour définir les causes d'anomalies trouvées. Notre évaluation est effectuée sur quatre axes:2.2.1 Étude Statistique. Le but de cette étude est de (1) vérifier si les incohérences sont fréquentes ou s'il s'agit d'anomalies rares, (2) trouver les différents types d'incohérences (3) déterminer les algorithmes et le type de données qui sont plus vulnérables à l'incohérence. Les résultats ont montré que les incohérences sont très fréquentes sur toutes les catégories d'algorithmes et dans tous les ensembles de données avec plus de présence dans les algorithmes basés sur l'apprentissage profond et sur les données factuelles. 2.2.2 Étude structurelle. Dans cette étude nous nous intéressons à la relation entre les incohérences et la structure des paraphrases évaluées. Nous nous sommes focalisés sur la relation entre les incohérences, la similarité sémantique et syntaxique entre les phrases sémantiquement équivalentes. Cela a permis de vérifier si les algorithmes sont vulnérables aux paraphrases avec une grande distance syntaxique. Les résultats ont montré que les algorithmes sont très sensibles à la différence syntaxique entre les textes sémantiquement équivalents. Les résultats ont montré que les incohérences sont présentes sur toutes les configurations. En se basant sur leurs résultats, nous avons proposé des configurations qui permettent de minimiser les incohérences et maximiser la précision.

2.2.3 Étude sémantique. Le but de cette étude est de vérifier si les incohérences dépendent de la subjectivité des paraphrases et si les incohérences dépendent de la précision des algorithmes. Autrement dit, nous vérifions si les algorithmes les plus précis présentent moins d'incohérences. Les résultats ont montré plus d'incohérences entre les données factuelles ainsi qu'une corrélation inverse entre les incohérences inter-algorithmes et la précision, i.e, plus l'algorithme est cohérent, plus il est plus précis.

2.2.4

Étude de l'effet des hyperparamètres sur la précision et les incohérences. Etant donné le constat effectué sur les outils basés sur l'apprentissage profond, nous avons étudié l'impact des hyperparamètres sur la précision et l'incohérence des algorithmes.

  Nous évaluons ces approches sur des corpus d'articles de journaux et d'articles scientifiques. Nous avons aussi constitué et mis à disposition un jeu de données de résumés d'articles scientifiques en français que nous avons conçu à partir du dépôt d'archives ouvertes 'HAL'. Ces évaluations montrent que la performance de nos propositions dépasse celles des méthodes de l'état de l'art de classification multilabels de texte pour les jeux de données étudiés, et sont transposables à tout problème de classification multilabels utilisant les réseaux de neurones.

modèles de langue pré-entraînés ont prouvé leur efficacité dans la classification de texte multiclasses. Notre objectif est d'étudier et d'améliorer ce type d'approches pour la classification multilabels de texte, une tâche étonnamment peu explorée au cours de ces toutes dernières années. Cette tâche a pourtant des applications industrielles importantes telles que la recommandation de contenu, l'extraction de méta-données pour l'enrichissement des bases de données ou le routage automatique multicritères des emails. Dans cet article, notre originalité est de proposer des méthodes d'exploitation des activations des couches de sortie des transformeurs pour améliorer la performance de ces modèles pour la classification multilabels. Notre contribution concerne l'évaluation de l'utilité des méthodes de seuillage sur plusieurs modèles d'apprentissage profond, en calculant un seuil de classification global pour optimiser l'ensemble des classes (SGO), ou un seuil individuel propre à chaque classe étudiée (SI). Elle concerne aussi la proposition de deux approches pour la classification multilabels de texte. La première approche (NPA) consiste à ajouter un paramètre pour l'apprentissage du nombre de classes et/ou labels N présentes pour un exemple donné, pour considérer les classes qui correspondent aux N activations les plus élevées comme étant des labels valides. La deuxième approche (TL) consiste à ajouter une couche au transformeur pour l'apprentissage des critères utiles pour la sélection des labels pertinents.

  1 https://www.scikit-yb.org/en/latest/api/classifier/threshold.html directement le choix d'une classe pour le problème multilabels. Le seuil peut être ajusté de plusieurs façons, soit pour optimiser toutes les classes (un seuil global), ou pour optimiser individuellement chaque classe (nombre de seuils égal au nombre de classes). Soit 𝑚 le nombre d'exemples dans le jeu de données de test (ou la validation) et 𝑛 𝑦 le nombre de classes (labels). Les quatre stratégies les plus utilisées pour le choix du(des) seuil(s) sont : • SCut: Les classes sont optimisées de façon individuelle, les seuils sont choisis en fonction des performances sur le jeu de données de validation, mesurés soit par la maximisation d'un score ou la minimisation d'une fonction de coût, et sans garantir l'obtention d'un optimum global. Cette méthode peut aussi être utilisée pour obtenir un seuil global pour toutes les classes [Yang 2001]; • RCut (Rank Cut) : pour chaque instance, les classes sont ordonnées selon le score obtenu, les 𝑡 premières classes sont choisies comme labels pertinents. Le paramètre 𝑡 peut être fixé ou réglé à partir du jeu de données de validation [Yang 2001]; • PCut (Proportion Cut) : pour chaque classe 𝑦 𝑖 , les instances du jeu de données de test sont ordonnées selon le score obtenu pour cette classe. Les 𝑘 𝑖 premières instances sont choisies pour la classe 𝑦 𝑖 où 𝑘

𝑖 = 𝑃 (𝑦 𝑖 ) × 𝑥 × 𝑛 𝑦 est le nombre d'instances attribuées à cette classe. 𝑃 (𝑦 𝑖 ) est la probabilité qu'une instance fasse partie de la catégorie 𝑦 𝑖 (calculée préalablement à partir du jeu d'entraînement), et 𝑥 le nombre moyen d'instance à attribuer pour une classe quelconque fixé au préalable. Si 𝑥 = 𝑛 toutes les instances sont prises pour une catégorie, pour 𝑥 = 0 aucun exemple n'est considéré comme faisant partie de la classe étudiée

[START_REF] Lewis | A Comparison of Two Learning Algorithms for Text Categorization[END_REF][START_REF] Yang | An evaluation of statistical approach to text categorization[END_REF]

];

• MCut (Maximum Cut) : les labels sont ordonnés à partir des scores obtenus pour une instance du jeu de données, le seuil est égal à la moyenne des deux labels contigus pour lesquels l'écart de score est le plus important [?].

Table 1 :

 1 Les jeux de données avec W le nombre moyen de mots par document.

		#Train	#Valid	#Test	labels	W	#Train Epochs
	Reuter-21578 AAPD HAL-Dataset	5827 53840 9944	1943 1000 1243	3019 1000 1243	90 54 194	127,76 163,16 112,72	120 40 50

Table 2 :

 2 Scores pour les données de test issues des corpus en anglais Reuters et AAPD (les meilleurs scores sont en bleu gras).

	Modèles	Pr.	R	Reuters F1	Acc	Pr.	R	AAPD	F1	Acc
	Decision Tree Bagging Random Forest GradientBoost SVM	78,36 88,12 97,18 88,06 94,19	75,05 79,65 57,13 80,56 79,62	76,67 83,67 71,96 84,14 86,29	74,23 73,34 64,06 74,23 80,64	49,67 77,27 94,2 79,73 80,85	46,8 48,16 25,49 46,8 59,98	48,19 59,34 40,12 58,98 68,86	26,6 26,9 20 27,1 36,2
	CNN CNN-RNN SGM MAGNET DocBERT 𝑏𝑎𝑠𝑒 DocBERT 𝑙𝑎𝑟𝑔𝑒	------	------		86,3 85,5 -89,9 89,0 90,7	------	------	------		66,4 66,9 71,0 69,6 73,4 75,2	------
	Méthodes de seuillage, sans architecture spécifique (SGO et SI)
	BERT+𝑆𝐺𝑂 BERT+𝑆𝐼 DistilBERT+𝑆𝐺𝑂 DistilBERT+𝑆𝐼 RoBERTa+𝑆𝐺𝑂 RoBERTa+𝑆𝐼 DeBERTa+𝑆𝐺𝑂 DeBERTa+𝑆𝐼	90,0 88,89 90,83 88,40 90,73 89,77 91,63 90,67	91,74 92,30 90,78 91,66 89,90 90,49 90,41 90,92	90,86 90,56 90,80 90,0 90,31 90,13 91,02 86,78 74,46 86,45 75,56 72,65 74,08 85,72 75,51 72,61 74,04 86,29 75,73 72,08 73,86 85,29 79,06 68,31 73,3 86,28 74,49 72,49 73,47 85,92 75,35 71,09 73,15 73,56 74,01 90,79 86,61 75,87 72,08 73,92	41,7 41,3 39,8 41,01 40,3 40,2 39,4 40,7
	Adaptation architecture Transformeurs (NPA et TL)
	BERT+𝑁 𝑃𝐴 BERT+𝑇 𝐿 DistilBERT+𝑁 𝑃𝐴 DistilBERT+𝑇 𝐿 RoBERTa+𝑁 𝑃𝐴 RoBERTa+𝑇 𝐿 DeBERTa+𝑁 𝑃𝐴 DeBERTa+𝑇 𝐿	92,33 90,60 92,08 90,0 89,43 91,17 92,22 90,97	85,87 90,41 86,03 89,66 83,20 89,05 86,41 90,43	88,98 90,50 88,95 89,83 86,20 90,09 89,21 90,70	85,92 86,12 86,15 85,89 83,40 86,02 86,35 86,12	73,48 73,48 73,93 73,63 75,04 76,48 75,32 75,97	66,38 72,20 66,29 72,32 66,58 71,58 65,67 71,70	69,75 72,83 69,90 72,97 70,56 73,94 70,16 73,78	40,3 39,5 41,8 40,2 42,0 42,5 41,9 41,8

Table 3 :

 3 Scores des approches oracles pour les données de test des corpus en anglais Reuters et AAPD (les meilleurs scores sont en bleu gras).

	Modèles	Pr.	R	Reuters F1	Acc	Pr.	R	AAPD	F1	Acc
	BERT+𝑆𝐺𝑂 𝑜𝑟𝑎𝑐𝑙𝑒 BERT+𝑆𝐼 𝑜𝑟𝑎𝑐𝑙𝑒 DistilBERT+𝑆𝐺𝑂 𝑜𝑟𝑎𝑐𝑙𝑒 DistilBERT+𝑆𝐼 𝑜𝑟𝑎𝑐𝑙𝑒 RoBERTa+𝑆𝐺𝑂 𝑜𝑟𝑎𝑐𝑙𝑒 RoBERTa+𝑆𝐼 𝑜𝑟𝑎𝑐𝑙𝑒 DeBERTa+𝑆𝐺𝑂 𝑜𝑟𝑎𝑐𝑙𝑒 DeBERTa+𝑆𝐼 𝑜𝑟𝑎𝑐𝑙𝑒	91,46 93,61 91,61 92,48 91,21 93,18 92,74 93,74	90,70 91,24 90,17 92,04 89,56 90,57 90,73 91,56	91,08 92,41 90,88 92,26 90,38 91,86 91,72 92,64	87,01 87,94 86,52 87,45 86,32 87,78 87,41 88,27	80,41 83,0 74,50 82,59 74,12 81,95 75,21 82,82	68,85 70,59 73,27 70,34 71,83 70,14 71,95 70,26	74,18 76,29 73,88 75,97 72,96 75,58 73,55 76,02	43,1 44,9 40,0 44,0 39,9 44,2 40,4 44,0
	BERT+𝑁 𝑃𝐴 𝑜𝑟𝑎𝑐𝑙𝑒 DistilBERT+𝑁 𝑃𝐴 𝑜𝑟𝑎𝑐𝑙𝑒 RoBERTa +𝑁 𝑃𝐴 𝑜𝑟𝑎𝑐𝑙𝑒 DeBERTa +𝑁 𝑃𝐴 𝑜𝑟𝑎𝑐𝑙𝑒	92,55 91,99 91,69 92,31	92,55 91,99 91,69 92,31	92,55 91,99 91,69 92,31	92,45 74,06 91,95 75,09 75,09 74,06 91,45 73,36 73,36 92,41 73,48 73,48	74,06 75,09 73,36 73,48	51,8 54,7 51,5 52,7

Table 4 :

 4 Scores pour les données de test issues du corpus en français HAL-Dataset (les meilleurs scores sont en bleu gras).

	Modèles	Pr.	HAL-Dataset R F1	Acc
	Decision Tree Bagging Random Forest GradientBoost SVM	56,96 86,24 90,72 64,14 95,23	52,42 52,66 50,85 57,32 55,56	54,60 65,39 65,17 60,54 70,18	62,27 62,35 64,60 60,58 66,37
	Seuillage sans architecture spécifique (SGO et SI)
	CamemBERT+𝑆𝐺𝑂 CamemBERT+𝑆𝐼 FlauBERT+𝑆𝐺𝑂 FlauBERT+𝑆𝐼	79,17 77,12 80,09 78,61	67,11 67,65 69,58 70,01	72,64 72,08 74,47 74,06	71,84 71,35 73,12 73,45
	Adaptation architecture Transformeurs (NPA et TL)
	CamemBERT+𝑁 𝑃𝐴 CamemBERT+𝑇 𝐿 FlauBERT+𝑁 𝑃𝐴 FlauBERT+𝑇 𝐿	66,45 88,38 65,70 82,49	49,93 59,31 60,58 66,08	57,02 70,98 63,04 73,38	64,36 68,78 67,42 71,6

Table 5 :

 5 Scores des approches oracles pour les données de test du corpus en français HAL-Dataset(les meilleurs scores sont en bleu gras). Les modèles BERT et dérivés surpassent toutes les autres méthodes, que ce soient les méthodes classiques comme les SVM ou le GradientBoost, ou les autres méthodes d'apprentissage profond. Les méthodes de seuillage (SGO et SI ) ainsi que les architectures proposées (NPA et TL) dépassent la version base de DocBERT (état de l'art actuel de la classification multilabels de textes pour les corpus AAPD et Reuters), et dans certains cas sa version large. L'implantation des méthodes SGO et SI sont les plus performantes parmi toutes les approches étudiées, avec un score micro-F1 de 91,02 et 90.79 respectivement, comparés au score de 90,7 de la version large de DocBERT pour le corpus Reuters (cf. tableau 2).

	Modèles	Pr.	HAL-Dataset R F1	Acc
	CamemBERT+𝑆𝐺𝑂 𝑜𝑟𝑎𝑐𝑙𝑒 CamemBERT+𝑆𝐼 𝑜𝑟𝑎𝑐𝑙𝑒 FlauBERT+𝑆𝐺𝑂 𝑜𝑟𝑎𝑐𝑙𝑒 FlauBERT+𝑆𝐼 𝑜𝑟𝑎𝑐𝑙𝑒	83,20 90,33 83,16 89,21	65,59 67,83 68,38 70,49	73,36 77,48 75,05 78,75	71,92 72,96 73,61 75,30
	CamemBERT+𝑁 𝑃𝐴 𝑜𝑟𝑎𝑐𝑙𝑒 FlauBERT+𝑁 𝑃𝐴 𝑜𝑟𝑎𝑐𝑙𝑒	70,80 72,85	70,80 72,85	70,80 72,85	75,46 76,75
	la version base contre 24 pour la version large), ainsi que la taille du vecteur d'embedding (768 pour la version base contre 1024 pour la version large). L'entraînement des modèles a été réalisé à l'aide d'une Nvidia RTX 2080 Ti (11 Go de mémoire vidéo), le tableau 6 présente les différentes durées des phases d'entraînement et de validation pour les jeux de données étudiés.

Table 6 :

 6 Durée (en secondes) d'une itération dans la phase d'entraînement et de l'inférence pour la phase de validation des modèle BERT et FlauBERT sur les jeux de donnés AAPD, Reuters et HAL avec un batch size de 8 DocBERT ainsi que le modèle MAGNET, et se rapproche de la version large du premier avec un score de 90,60 pour le modèle DeBERTa. L'approche NPA quant à elle ne réussit pas à atteindre son optimal théorique, en obtenant un score quand bien même dépassant la version base de DocBERT (cf. partie Adaptation architecture Transformeur du tableau 2). Ces deux architectures nécessitent un temps d'entraînement moins important que les deux méthodes de seuillage (une différence de 1000 secondes dans la configuration de nos tests pour le modèle BERT) , mais possèdent un coût d'inférence plus élevé, notamment pour l'architecture TL où le temps d'inférence, 25 et 29.6 secondes pour BERT et FlauBERT respectivement, est presque deux fois celui des autres méthodes (cf. tableau 6). Cela peut être expliqué par la présence de la couche supplémentaire que possède cet architecture, augmentant ainsi le temps d'inférence des modèles, chose qui n'impacte pas de façon considérable la phase d'entraînement de par sa nature parallèle (l'inférence étant exécutée d'une manière séquentielle couche après couche).

	Modèles	AAPD Train Valid	Reuters Train Valid
	BERT+𝑆𝐺𝑂 BERT+𝑆𝐼 BERT+𝑁 𝑃𝐴 BERT+𝑇 𝐿	2822 3202 2031 2015	13,5 13,5 13,7 25	315 420 223 213	26,4 26,5 27 50,8
			HAL Train Valid
	FlauBERT+𝑆𝐺𝑂 FlauBERT+𝑆𝐼 FlauBERT+𝑁 𝑃𝐴 FlauBERT+𝑇 𝐿		539 836 369 379	15.6 15.7 16.1 29.6

Ces deux méthodes améliorent de façon notable le score micro F1 et l'exactitude (Accuracy) des modèles, mais sont celles qui ont les coûts d'entraînement les plus élevés. Ceci est dû au fait que le calcul des seuils dans la phase d'entraînement requiert un temps de traitement considérable (cf. tableau 6). Le(s) seuil(s) de détection baisse parfois, ce qui a pour effet d'augmenter le nombre de vrais positifs; dans d'autre cas, ce(s) seuil(s) augmente, ce qui diminue le nombre de faux positifs. La précision du modèle augmente ainsi que la micro-F1 et l'exactitude.

Pour ce même corpus, l'architecture TL dépasse la version base du modèle

  Définir, observer et modéliser les médias d'information

	Agnès Saulnier
	Institut National de l'Audiovisuel
	Bry Sur Marne, France
	asaulnier@ina.fr
	RESUME Internet a bousculé l'univers médiatique et pour s'y retrouver l'enjeu est de fournir un nouvel ensemble de critères de description des entités médiatiques. 1 Introduction	lié à l'évolution des médias. Une liste de 3000 sites web d'information a été recensée afin d'aider à la normalisation du vocabulaire et aux tests du modèle. Cette modélisation est destinée à déboucher plus tard sur la réalisation d'une base de connaissance médiatique.
	L'enjeu de ce travail est de modéliser conjointement les
	médias de masse traditionnels et les nouveaux médias très
	divers que permet Internet, afin d'aider les utilisateurs à
	s'orienter dans le nouveau paysage médiatique. En effet, de
	nos jours, Internet véhicule un grand nombre d'informations
	qu'il est important de pouvoir distinguer car le terme
	information tend à se confondre avec celui de contenu, faisant
	disparaitre la valeur ajoutée journalistique. Notre démarche
	repose sur la définition du périmètre, la constitution d'une
	grille d'observation et la modélisation conceptuelle du
	domaine médiatique. Cette modélisation nécessite une plus
	grande finesse de description que celle des systèmes déjà
	existants ainsi que la prise en compte de l'aspect diachronique

D'où vient l'information ? Comment est-elle financée ? Comment a-t-elle été produite ? Dans quel but ? Par qui est-elle diffusée ? Pour quel public ? Autant de questions essentielles à se poser pour mieux se diriger dans l'écosystème des médias. Notre objet d'étude porte ainsi sur la définition, l'observation et la modélisation des médias d'informations. Ce papier se concentre plus particulièrement sur la démarche de modélisation reposant sur une grille d'observation des entités médiatiques. Modéliser le domaine médiatique est en effet une tâche complexe et délicate car elle doit prendre en compte un niveau très fin de description des médias ainsi que l'aspect diachronique lié à l'évolution de la structure juridique des entités médias, de la structure de production et de la ligne éditoriale. Le modèle est testé et affiné à l'aide d'une liste de 3000 sites web d'information.

  Data Management Systems (PDMS) are flourishing, boosted by legal and technical means like smart disclosure, data portability and data altruism. A PDMS allows its owner to easily collect, store and manage data, directly generated by her devices, or resulting from her interactions with companies or administrations. PDMSs unlock innovative usages by crossing multiple data sources from one or many users, thus requiring aggregation primitives. Indeed, aggregation primitives are essential to compute statistics on user data, but are also a fundamental building block for machine learning algorithms. This paper proposes a protocol allowing for secure aggregation in a massively distributed PDMS environment, which adapts to selective participation and PDMSs characteristics, and is reliable with respect to failures, with no compromise on accuracy. Preliminary experiments show the effectiveness of our protocol which can adapt to several contexts with varying PDMSs characteristics in terms of communication speed or CPU resources and can adjust the aggregation strategy to the estimated selective participation.

	Practical Fully-Decentralized Secure Aggregation for Personal Data Management Systems
	Julien Mirval julien.mirval@cozycloud.cc Cozy Cloud Inria-Saclay UVSQ, Université Paris-Saclay France	Luc Bouganim luc.bouganim@inria.fr Inria-Saclay UVSQ, Université Paris-Saclay France	Iulian Sandu-Popa iulian.sandu-popa@uvsq.fr UVSQ, Université Paris-Saclay Inria-Saclay France

Personal

  de quotient de la théorie des graphes offre un cadre élégant pour le résumé de grands graphes; cette opération consiste à fusionner des noeuds équivalents au sens d'une relation d'équivalence. Le résumé de graphes fondé sur cette opération a été largement étudié dans la littérature, notamment pour l'exploration et la gestion efficace de grands graphes. Nous étudions si une opération similaire peut être utilisée pour résumer des bases de données en logiques de description (LD), c'està-dire des ABoxes. Dans ce but, nous définissons et examinons l'opération de quotient sur une ABox: nous établissons qu'une ABox quotient est plus spécifique que la ABox qu'elle résume et nous caractérisons dans quelle mesure elle est plus spécifique. Ces investigations préliminaires valident l'intérêt d'un cadre de résumé de ABoxes fondé sur l'opération de quotient de graphe, et ouvrent la voie à de futurs travaux en LD, par exemple pour concevoir des relations d'équivalence adaptées à l'optimisation des tâches typiques de gestion et de raisonnement sur de grandes ABoxes ou encore à la visualisation de grandes ABoxes, ainsi qu'à l'application de ces travaux dans des domaines connexes comme le Web Sémantique.Toward Generic Abstractions for Data of Any Model

	Cheikh-Brahim El Vaigh Univ. Rennes Lannion, France cheikh-brahim.el-vaigh@irisa.fr Inria & Institut Polytechnique de Paris ABSTRACT nelly.barret@inria.fr Inria & Institut Polytechnique de Paris Ioana Manolescu ioana.manolescu@inria.fr ABSTRACT L'opération Nelly Barret Digital data sharing leads to unprecedented opportunities to de-velop data-driven systems for supporting economic activities, the social and political life, and science. Many open-access datasets are RDF graphs, but others are CSV files, Neo4J property graphs, JSON or XML documents, etc.	François Goasdoué Univ. Rennes Lannion, France fg@irisa.fr Prajna Upadhyay Inria & Institut Polytechnique de Paris prajna-devi.upadhyay@inria.fr

  A Demonstration of the Exathlon Benchmarking Platformfor Explainable Anomaly Detection * to high-quality data repositories and benchmarks have been instrumental in advancing the state of the art in many experimental research domains. While advanced analytics tasks over time series data have been gaining lots of attention, lack of such community resources severely limits scientific progress. In this demonstration, we showcase Exathlon, the first comprehensive public benchmark for explainable anomaly detection over high-dimensional time series data. Exathlon has been systematically constructed based on real data traces from repeated executions of large-scale stream processing jobs on an Apache Spark cluster. Some of these executions were intentionally disturbed by introducing instances of six different types of anomalous events (e.g., misbehaving inputs, resource contention, process failures). For each of the anomaly instances, ground truth labels for the root cause interval as well as those for the extended effect interval are provided, supporting the development and evaluation of a wide range of anomaly detection (AD) and explanation discovery (ED) tasks. This demonstration presents Exathlon's curated anomaly dataset, novel benchmarking methodology, and end-to-end data science pipeline in action via example usage scenarios. The dataset, code, and documentation for Exathlon are publicly available at https://github.com/exathlonbenchmark/exathlon.Les requêtes SPARQL property path représentent un outil indispensable pour chercher des motifs complexes dans un graphe de connaissance. Cependant, évaluer ces requêtes sur des données en ligne, et obtenir des résultats complets, est difficile. Du fait de leur complexité, les requêtes property path sont souvent intérrompues par les politiques d'usage équitable en place sur les SPARQL endpoints. Afin de garantir des résultats complets, SaGe-Path repose sur la préemption Web et le concept de fermetures transitives partielles (PTC). Lors de l'évaluation d'une expression property path, le serveur PTC limite l'exploration du graphe à une profondeur 𝑘, définie à l'avance. Les noeuds visités à une profondeur 𝑘 sont appelés noeuds frontières et sont envoyés au client. En utilisant ces noeuds frontières, le client PTC est alors capable de générer de nouvelles requêtes, afin de continuer l'exploration du graphe.

	SaGe-Path : Pay-as-you-go SPARQL Property Path Queries Processing using Web Preemption
	Vincent Jacob vincent.jacob@polytechnique.edu Ecole Polytechnique France Bijan Rad bijan.rad@polytechnique.edu Ecole Polytechnique France Julien Aimonier-Davat Université de Nantes, LS2N Nantes, France julien.aimonier-davat@univ-nantes.fr RÉSUMÉ	Fei Song fei.song@polytechnique.edu Ecole Polytechnique France Yanlei Diao yanlei.diao@polytechnique.edu Ecole Polytechnique France Hala Skaf-Molli Université de Nantes, LS2N Nantes, France hala.skaf@univ-nantes.fr	Arnaud Stiegler arnaud.stiegler@polytechnique.edu Ecole Polytechnique France Pascal Molli Université de Nantes, LS2N Nantes, France pascal.molli@univ-nantes.fr Nesime Tatbul tatbul@csail.mit.edu USA Intel Labs and MIT

Access

1

  𝐸 𝐷 ← ∅; QLOutd(v)←0 for each v ∈V; 2 foreach e=(𝑣 1 ,𝑙,𝑣 2 ) ∈ A, in A's order do 𝐸 𝐷 ← 𝐸 𝐷 ∪{e};

	5 6 7	QLOutd(𝑣 1 )=QLOutd(𝑣 1 )+ 1; end if if 𝑙 ∉ QL then
	8
	9 10 end foreach end if 11 return 𝐺 𝐷 𝑄𝐿 = ( V, 𝐸 𝐷 )

3 if 𝑙 ∈ QL ∧ QlOutd(𝑣 1 ) < D then 4 𝐸 𝐷 ← 𝐸 𝐷 ∪{e};

  The structural summary 𝐺 ′ is a graph computed out of 𝐺, potentially much smaller than 𝐺, and which gives us a first idea of groups of nodes that may contain similar information: each such group of 𝐺 nodes is represented by a single node in 𝐺 ′ .(2) Find collections and records. Starting from the summary, we seek to identify the nodes that represent records, that is, objects of a certain "kind" with some internal structure, and collections, that is, containers of potentially many records of the same "kind". (3) Categorize collections. Finally, we aim at classifying collec-

tions among a set of categories K, containing (𝑖) the kind(s) of data that the user is looking for, if the user can formulate such a request, e.g., "Books", or "Places to visit", and/or (𝑖𝑖) a set of generic categories we pre-define, such as Person, Organization, Location, Event and Creative work. The categorization adds a limited form of semantics (we keep things simple on purpose since we assume non-technical users), and enable adapting to the users' interest.

https://neo4j.com/

https://atlas.apache.org/

https://www.mongodb.com/

https://www.elastic.co/

a (10, 10, 10) b (120, 20, 20) c (90, 30, 30) a,b,c c a b, c c

© 2021, Copyright is with the authors. Published in the Proceedings of the BDA 2021 Conference (October 25-28, 2021, En ligne, France). Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0. © 2021, Droits restant aux auteurs. Publié dans les actes de la conférence BDA 2021 (25-28 octobre 2021, En ligne, France). Redistribution de cet article autorisée selon les termes de la licence Creative Commons CC-by-nc-nd 4.0.

https://gluebenchmark.com/tasks

Tous les jeux de données sont téléchargeables ici : https://github.com/hf-lis/Multi-Label-Datasets

API HAL : https://api.archives-ouvertes.fr/docs/search

https://archive.ics.uci.edu/ml/datasets/reuters-21578+text+categorization+ collection

BDA 2021, 25-28 octobre, 2021, ENS, Paris Fallah et al.

https://www.w3.org/TR/turtle/

Une liste d'autorité de 3000 sites web d'information a été constituée en croisant des sources de données de différents types (CPPAP, BNF, SPIIL, Upreg, ACPM, annuaires…). Cette liste d'autorité, destinée à fournir des instances dans la future base de connaissance, a servi à deux types de test. Tout d'abord, une sélection d'une vingtaine de sites représentatifs de la liste a permis d'évaluer la structure générale et la souplesse du modèle conceptuel. Ensuite, 2/3 de la liste a été analysé à la main pour tester, affiner et compléter les attributs. Ainsi des critères de la presse écrite ont pu être étendus à d'autres supports. Des typologies ont pu être affinées à partir de l'observation de la liste. Les tests ont aussi démontré le besoin d'ajouter des descripteurs particuliers.

http://polluscope.uvsq.fr ©

2021, Copyright is with the authors. Published in the Proceedings of the BDA 2021 Conference (October 25-28, 2021, En ligne, France). Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0. © 2021, Droits restant aux auteurs. Publié dans les actes de la conférence BDA 2021 (25-28 octobre 2021, En ligne, France). Redistribution de cet article autorisée selon les termes de la licence Creative Commons CC-by-nc-nd 4.0.

https://www.thinginthefuture.com/ ©

2021, Copyright is with the authors. Published in the Proceedings of the BDA 2021 Conference (October 25-28, 2021, En ligne, France). Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0. © 2021, Droits restant aux auteurs. Publié dans les actes de la conférence BDA 2021 (25-28 octobre 2021, En ligne, France). Redistribution de cet article autorisée selon les termes de la licence Creative Commons CC-by-nc-nd 4.0.

ACKNOWLEDGEMENTS

Étienne Scholly (PhD), Pegdwendé Nicolas Sawadogo (PhD) and Pengfei Liu's (postdoc) are funded by the BIAL-X company, the AURA Region and the IMU LabEx, respectively.

ACKNOWLEDGMENTS

Yanlei Diao and Paweł Guzewicz are supported by the European Research Council, H2020 research program under GrantNo.: 725561, and by the Agence Nationale de la Recherche under GrantNo.: ANR-16-CE23-0010-01. Mirjana Mazuran is supported by the European Research Council, H2020 research program under GrantNo.: 800192.

ACKNOWLEDGMENTS

This work is supported by a graduate fellowship from KACST.

ACKNOWLEDGMENTS

Partially supported by ANR project CQFD (ANR-18-CE23-0003)

ACKNOWLEDGMENTS

This work is supported by ISITE-BFC (ANR-15-IDEX-0003) coordinated by G. Brachotte, CIMEOS Laboratory (EA 4177), University of Burgundy.

ACKNOWLEDGMENTS

This work has been partially supported by MIAI@Grenoble Alpes (ANR-19-P3IA-0003), PERSYVAL-Lab (ANR-11-LABX-0025-01) and TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215. Acknowledgement. This work has been partially supported by the ANR JCJC grant ANR-18-CE23-0019 and by the IMT Futur & Ruptures program "AutoClean". ACKNOWLEDGMENTS This work was supported by the ANR AI Chair project SourcesSay Grant no ANR-20-CHIA-0015-01. ACKNOWLEDGMENTS Giorgio Ghelli's contribution has been funded by MIUR project PRIN 2017FTXR7S "IT-MaTTerS" (Methods and Tools for Trustworthy Smart Systems). Stefanie Scherzinger's contribution has been funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) -385808805. Acknowledgments. The authors thank M. Ferrer and the Décodeurs team (Le Monde) for introducing us, and for many insightful discussions. We also thank Jérémie Feitz and Emmanuel Pietriga for their work on the GUI of ConnectionLens. This work was supported by the ANR AI Chair project SourcesSay Grant no ANR-20-CHIA-0015-01. ACKNOWLEDGMENTS This work has supported by the French National Research Agency (ANR) project Polluscope, funded under the grant agreement ANR-15-CE22-0018, by the H2020 EU GO GREEN ROUTES funded under the research and innovation programme H2020-EU.3.5.2 grant agreement No 869764, and by the DATAIA convergence institute project StreamOps, as part of the Programme d' Investissement d'Avenir, ANR-17-CONV-0003. Part of the equipment was funded by iDEX Paris-Saclay, in the framework of the IRS project ACE-ICSEN, and by the Communauté d'agglomération Versailles Grand Parc.

We are thankful to all the members of the Polluscope consortia who contributed in one way or another to this work: Salim Srairi and Jean-Marc Naude (CEREMA) who conducted the campaign; Boris Dessimond and Isabella Annesi-Maesano (Sorbonne University) for their contribution to the campaign; Valerie Gros, Baptiste Languille and Nicolas Bonnaire (LSCE), and Anne Kauffmann and Christophe Debert (Airparif) for their contribution in the periodic qualification of the sensors and their feedback. Finally, we would like to thank the participants for their involvement.

ACKNOWLEDGMENT

Work supported by the French National Research Agency, under grant ANR-18-CE23-0010 Acknowledgments. This work is funded by DIM RFSI PHD 2020-01 and AI Chair SourcesSay project (ANR-20-CHIA-0015-01) grants.

OUTLOOK

Big data and artificial intelligence comes with the promise to improve people's lives, also by enhancing the discovery of interesting information and providing results tailored to users' profiles. However, the same technology, if not used responsibly, may lead to discrimination, amplify biases in the original data, restrict decision transparency and strengthen unfairness. With this project, we aim to promote research towards explainable, transparent, and fair systems by explaining the absence of certain options from a user's recommendation list.

She received the 2019 ACM SIGMOD Edgar FAward. She is also the recipient of an ERC Consolidator Award (2013), the Finmeccanica endowed chair from the Computer Science Department at Carnegie Mellon (2007), a European Young Investigator Award from the European Science Foundation (2007), an Alfred P. Sloan Research Fellowship (2005), an NSF CAREER award (2002), and ten best-paper awards in database, storage, and computer architecture conferences. She is an ACM fellow, an IEEE fellow, the Laureate for the 2018 Nemitsas Prize in Computer Science, and an elected member of the Swiss, the Belgian, the Greek, and the Cypriot National Research Councils. She is a member of the Academia Europaea and of the World Economic Forum Expert Network.

ADESIT : Visualisez les Limites de vos Données dans un Processus d'Apprentissage Machine

ABSTRACT Wide spread use of sensors and mobile devices along with the new paradigm of Mobile Crowd-Sensing (MCS), allows monitoring air pollution in urban areas. Several measurements are collected, such as Particulate Matters, Nitrogen dioxide, and others. Mining the context of MCS data in such domains is a key factor for identifying the individuals' exposure to air pollution, but it is challenging due to the lack or the weakness of predictors. We have previously developed a multi-view learning approach which learns the context solely from the sensor measurements. In this demonstration, we propose a visualization tool (COMIC) showing the different recognized contexts using an improved version of our algorithm. We also demonstrate the change points detected by a multi-dimensional CPD model. We leverage real data from a MCS campaign, and compare different methods.

KEYWORDS

Activity Recognition, Multivariate Time Series Classification, Multiview Learning, Mobile Crowd Sensing, Air Quality Monitoring

COMIC OVERVIEW

Air quality and exposure to pollution is a central concern for people living in urban areas. As the harmful effects of air pollutants on their health is alarming. The key concern to reduce the risk of these pollutants on individual's health is by understanding the totality of exposure. Air pollution monitoring is getting more interest nowadays, due to the rapid advances of the Internet of things (IoT) along with the emergence of the Mobile Crowd Sensing (MCS) paradigm.

The mentioned technologies coupled with the widespread use of GPS, allows volunteers to contribute their collected data in order to get personalized insights about their exposures to pollution. Polluscope 1 is a French project deployed in Île-de-France (i.e., Paris region), and is a typical use case study based on MCS. In Polluscope, participants are equipped with a sensor kit which can measure Deploying Heterogeneity-aware Deep Learning Workloads on the Computing Continuum

ABSTRACT

The increasing need for real-time analytics motivated the emergence of new incremental methods to learn representations from continuous flows of data, especially in the context of the Internet of Things. This trend led to the evolution of centralized computing infrastructures towards interconnected processing units spanning from edge devices to cloud data centers. This new paradigm is referred to as the Computing or Edge-to-Cloud Continuum. However, the network and compute heterogeneity across and within clusters may negatively impact Deep Learning (DL) training. We introduce a roadmap for understanding the end-to-end performance of DL workloads in such heterogeneous settings. The goal is to identify key parameters leading to stragglers and devise novel intra-and inter-cluster strategies to address them. We will explore various policies aiming to improve makespan, cost and fairness objectives while ensuring system scalability.

CCS CONCEPTS

• Computer systems organization → Grid computing; • Computing methodologies → Distributed computing methodologies; Machine learning.

KEYWORDS

Deep Learning, incremental learning, heterogeneous systems, Computing Continuum.

Why-Not explanations for recommenders

Hervé-Madelein Attolou herve-madelein.attolou@cyu.fr ETIS, CY Cergy Paris University, ENSEA, CNRS UMR8051 Cergy-Pontoise, France Supervisors: Dimitris Kotzinos & Katerina Tzompanaki

ABSTRACT

Recommenders suggest pertinent items to users from a vast variety of possibilities. However, it is crucial for the user and the system developer to understand why the system recommends certain items (why), and why it does not recommend others that he/she might expect (why not). In this thesis, we aim to explore explanations to the why not problem, which is less explored, but equally important.

KEYWORDS

Explanations; Why-Not questions; Explainable AI; Recommenders

INTRODUCTION

Recommenders are automatic tools that aid users in their data exploration tasks, usually in scenarios where the possibilities are vast, e.g., on e-commerce and other online platforms. Recommenders provide suggestions for data items based on explicit or implicit user feedback, like their preferences expressed as likes or ratings, previous views and purchases, their social network, or other context variables, e.g., spatiotemporal features, user characteristics, e.t.c.

Unexpected (either existing or missing) and not-explained recommendations may frustrate the user and can be detrimental to his/her trust and loyalty to the system. Explaining existing recommendations (and in general machine learning results) is an active scientific problem for at least the last decade (see Section 2). In this thesis, we focus on the problem of explaining missing recommendations, which we argue can be as important as explaining recommendations.

In our context a missing recommendation would be any item that the user or the system designer expect to be part of the recommendation and is not. It could be missing for "good" reasons, which would be justified by the provided explanation.

Consider for instance an e-recruitment site, which does not propose managerial positions to Alice. For Alice to trust the system, and continue using it, she needs to understand why this kind of positions is not proposed. Are there some points in her CV that count a lot for the system and thus need improvement? Or is the system gender biased? Furthermore, explanations of missing recommendations can reveal why certain (categories of) items are neglected by the system. For example, consider a movie streaming service that suggests only romantic movies to Alice (Figure 1). Explaining why no action movies are suggested, can be a useful tool for the system designers, who may want to debug their system or improve its diversity.

Example Generation for JSON Schema

Lyes Attouche * † Université Paris-Dauphine, PSL Research University lyes.attouche@dauphine.fr

ABSTRACT

JSON is one of the most popular format used for exchanging data on the web, its schema-less representation of data is one of its advantages but also one of its drawbacks, since it can induce the creation of malformed data, but with the creation of JSON Schema it has become possible to describe and control the content of the JSON documents, which ensures the quality of the exchanged data. JSON Schema is a logical language, and as any other logical language it is subject to some challenging problems like schema consistency and schema equivalence. A tool for generating documents from a JSON Schema can be useful when answering these theoretical problems, it also has a practical interest since it can serve for testing the behavior of JSON-based web APIs.

We present in this paper an approach for achieving documents generation from JSON Schema and provide some potential use cases.

KEYWORDS

JSON, JSON Schema, Data Generation

INTRODUCTION

In recent years many web APIs have adopted JSON as a data format for transmitting and receiving data to and from web servers.

The rise of its popularity is mainly due to its adoption of a schema-less representation of the data which ensures several advantages, but these advantages go along with many disadvantages, indeed the absence of a schema imply not having a control over the data, hence web APIs may receive corrupt and malformed data.

The growing popularity of JSON and the need for overcoming some of its disadvantages has led to the creation of JSON Schema [4]. As for any other data format endowed with a schema language, JSON Schema offers a way for interpreting and validating JSON documents. On the one hand JSON Schema is not widely adopted, one reason for this is that JSON Schema is considered to be hard to work with, on the other hand new web APIs tend to use it since it can improve their designs by offering means for defining validation rules and for contract testing.

Having a JSON data generator can serve for simulating the behavior of programs, either for performance measurements or for