Programme détaillé

Accueil

Ouverture BDA 2013

Tutoriel : Parallel Techniques for Big Data

Patrick Valduriez is a senior researcher at INRIA, heading the Zenith team in Montpellier. He has also been a professor of Computer Science at University Paris 6 (1999-2002) and a researcher at Microelectronics and Computer Technology Corp. in Austin, Texas (1985-1989). He received his Ph. D. degree and Doctorat d'Etat in CS from University Paris 6 in 1981 and 1985, respectively. His research focuses on data management in large-scale distributed and parallel systems (P2P, cluster, grid, cloud), in particular, scientific data management. He has authored and co-authored over 250 technical papers and several textbooks, among which “Principles of Distributed Database Systems”. He has been a member of the SIGMOD board, a trustee of the VLDB endowment and an associate editor of several journals, including ACM TODS, the VLDB Journal, Distributed and Parallel Databases, and Internet and Databases. He has served as PC chair of major conferences such as PDIS93, SIGMOD97, VLDB98 (industrial chair), VLDB99 (European chair). He was the general chair of SIGMOD04, EDBT08 and VLDB09. He was the recipient of the 1993 IBM scientific prize in CS in France. He obtained the best paper award at VLDB00. He is a Fellow of the ACM.

Abstract

Big data has become a buzzword, referring to massive amounts of data that are very hard to deal with traditional data management tools. In particular, the ability to produce high- value information and knowledge from big data makes it critical for many applications such as decision support, forecasting, business intelligence, research, and (data-intensive) science. Processing and analyzing massive, possibly complex data is a major challenge since solutions must combine new data management techniques (to deal with new kinds of data) with large-scale parallelism in cluster, grid or cloud environments. Parallel data processing has long been exploited in the context of distributed and parallel database systems for highly structured data. But big data encompasses different data formats (doc- uments, sequences, graphs, arrays, ) that require significant extensions to traditional par- allel techniques. In this talk, I will discuss such extensions, from the basic techniques and architectures to NoSQL systems and MapReduce.

Vidéo

[Slides]

Pause

Tutoriel : Les flux de données personnelles, enjeux technologiques, économiques et stratégiques

Stéphane Frénot est professeur à l’INSA de Lyon. Stéphane Grumbach est directeur de recherche à l’Inria Rhône-Alpes. Ils sont à l’initiative de l'équipe Inria Dice, Données de l’Internet au Coeur de l’Economie, spécialisée sur les enjeux sociétaux, économiques et politiques de l’exploitation des données personnelles, ainsi que sur les systèmes distribués de gestion des flux de données qui sont à la base de Facebook, Twitter, etc. Ils interviennent régulièrement dans des forums politiques (Assemblée nationale, Conseil de l’Union européenne, etc.) ou grand public, sur ces questions, ainsi que des forums scientifiques, parmi lesquels

• Congrès Big Data, Turning the Data Deluge into Decisions, CNIT, Paris, avril 2013
• Panel on Big Data, 6th International Conference on Computers, Privacy and Data Protection, CPDP, Reloading Data Protection, Brussels, january 2013
• ”International overview & analysis of the digital native revolution”, Invited talk at fOSSa, Free Open Source Software Academia Conference, Lille, december 2012
• ”Web 2.0, where are the data ?” Invited talk Global Forum 2012 : ”SHAPING A CONNECTED DIGITAL FUTURE”, New usages : for privacy and security? Stock- holm, november 2012
• ”Big Data ? Global Imbalance !”, invited speaker at conference Lift France 12 : ”Digital Promises & Compromises”, Marseille, septembre 2012

 

Abstract

Les données personnelles sont devenues une ressource essentielle de l’économie numérique, comparable au pétrole pour l’économie traditionnelle. L’objectif de ce tutoriel est d’aborder d’une part les enjeux économiques et stratégiques de la révolution induite par la disponibilité de masses considérables de données personnelles, dont l’impact commence à se faire sentir sur nos sociétés, et d’autre part les technologies des systèmes en émergence pour le traitement en continu et en temps réel des flux de données personnelles.

Vidéo

[Slides]

Démonstrations

• Fact Checking and Analyzing the Web, François Goasdoué, Konstantinos Karanasos, Yannis Katsis, Julien Leblay, Ioana Manolescu and Stamatis Zampetakis
• MicroFilter: Scalable Real-Time Filtering Of Micro-blogging Content, Ryadh Dahimene and Cedric Du Mouza
• Processing XML Queries and Updates on Map/Reduce Clusters, Nicole Bidoit-Tollu, Dario Colazzo, Noor Malla, Maurizio Nolé, Carlo Sartiani and Federico Ulliana
• MEoWS Reader: Top-k News Recommendation, Filtering and Personalization, Nelly Vouzoukidou, Bernd Amann and Vassilis Christophides
• SQuIF: Subtile Quête d'Informations personnelles issues de Fichiers, Sabina Surdu, Vincent Primault and Yann Gripay
• WaRG: Warehousing RDF Graphs, Dario Colazzo, Tushar I. Ghosh, François Goasdoué, Ioana Manolescu and Alexandra Roatiş
• Rule-Based Application Development using Webdamlog, Serge Abiteboul, Émilien Antoine, Gerome Miklau, Julia Stoyanovich and Jules Testard
• Une démonstration d’un crawler intelligent pour les applications Web, Muhammad Faheem and Pierre Senellart
• Block-o-Matic: a Web Page Segmentation Tool and its Evaluation, Andres Sanoja and Stephane Gancarski
• CoBRa for optimizing global queries, Lourdes Martinez, Christine Collet, Christophe Bobineau and Etienne Dublé
• Evaluating Cooperation in coauthorship graphs with degeneracy, Christos Giatis, Klaus Berberich, Dimitrios Thilikos and Michalis Vazirgiannis
• DataTour: Location-based Datastore over a Community Cloud, Kun Mi, Bo Zhang, Hubert Naacke, Daniel Stern and Stéphane Gançarski
• An Intelligent PubSub Filtering System, Zeinab Hmedeh, Cedric Du Mouza and Nicolas Travers

Apéritif

Accueil

Keynote : Database Architectures for Big Data Exploration - Stratos Idreos

Stratos Idreos is currently a senior researcher with the Dutch National Research Center for Mathematics and Computer Science in the Netherlands and a visiting scholar at EPFL, Switzerland. As of January 2014 he will be an assistant professor of Computer Science in the School of Engineering and Applied Sciences in Harvard University. Stratos obtained his Ph.D. from University of Amsterdam in the Netherlands. For his doctoral work on Database Cracking, Stratos won the 2011 ACM SIGMOD Jim Gray Doctoral Dissertation as well as the 2011 ERCIM Cor Baayen award as "most promising European young researcher in computer science and applied mathematics" from the European Research Council on Informatics and Mathematics. In 2010 he was awarded the IBM zEnterpise System Recognition Award by IBM Research, while in 2011 he also won the Challenges and Visions best paper award in the 2011 International Conference on Very Large Databases.

Abstract

We are now entering the era of data deluge, where the amount of data outgrows the capabilities of query processing technology. Many emerging applications, from social networks to scientific experiments, are representative examples of this deluge, where the rate at which data is produced exceeds any past experience. For example, scientific analysis such as astronomy is soon expected to collect multiple Terabytes of data on a daily basis, while already web-based businesses such as social networks or web log analysis are confronted with a growing stream of large data inputs. State-of-the-art database systems cannot cope with the data deluge requirements as they are designed for much more static environments. A modern database system requires heavy preparation steps and tuning which implies plenty of idle time to prepare the system and quite complete workload knowledge such as we know what to tune the system for. Today though, idle time and workload knowledge are scarce resources as application scenarios are much more dynamic and ad hoc. For example scientists might not always know what they are looking for and with Terabytes arriving daily they might also not have the time (and resources) to invest in any set-up actions; they just want to explore the data to see if there are any interesting patterns. In this talk, we focus on a new direction of query processing for big data where data exploration becomes a first class citizen. We will talk about database architectures which are tailored for scenarios where new big chunks of data arrive rapidly and we want to react quickly, i.e., with little time to spare for tuning and set-up. Such systems automatically and adaptively perform all core database actions such as data loading, indexing and tuning based on the running workload and with zero human input.

Vidéo

Pause

Session 1 - Fondements de la gestion de données

1. On the Expressive Power of Update Primitives Tom Ameloot, Jan Van Den Bussche and Emmanuel Waller Le standard SQL propose trois opérations primitives (insert : insertion, delete : suppression, et update, qui est appelée ici modification) pour mettre à jour une relation à partir d'une requête générique. Cet article compare l'expressivité des programmes composés de ces trois opérations avec la notion générale de mise à jour qui remplace simplement le contenu d'une relation par le résultat d'une requête. Il s'avère que le remplacement ne peut pas être exprimé en termes d'insertions, suppressions et modifications, et que la modification ne peut pas être exprimée en termes d'insertions et de suppressions. La puissance d'expression apportée par la structure de contrôle if-then-else dans les programmes est étudiée aussi. Différentes manières d'effectuer le remplacement sont discutées : en utilisant une variable temporaire, en utilisant la nouvelle opération SQL de fusion (merge), en utilisant les "tables incrémentales de changement de données" (data change delta tables) de SQL, ou en utilisant des requêtes avec création d'objet ou arithmétique. Pour finir, l'article étudie la puissance d'expression résultant de l'alternance des différentes primitives. Par exemple, une insertion suivie d'une modification ne peut pas toujours être exprimée par une modification suivie d'une insertion.
2. Probabilistic simulation for probabilistic data-aware business processes Haizhou Li, Francois Pinet and Farouk Toumani There is a wide range of new applications that stress the need for business process models that are able to handle imprecise data. This paper studies the underlying modelling and analysis issues. It uses as formal model to describe process behaviors a labelled transitions system in which transitions are guarded by conditions defined over a probabilistic database and presents an approach for testing probabilistic simulation preorder in this context. A complexity analysis reveals that the problem is in 2-EXPTIME, and is EXPTIME-hard, w.r.t. expression complexity while it matches probabilistic query evaluation w.r.t. data-complexity.
3. Preferences Chain Guided Search and Ranking Refinement Isma Sadoun, Yann Loyer and Karine Zeitouni Preference queries aim at increasing personalized pertinence of a selection. The most famous ones are the skyline queries based on the concept of dominance introduced by Pareto. Many other dominances have been proposed. In particular, many weaker forms of dominance aim at reducing the size of the answer of the skyline query. In most cases, applying just one dominance is not satisfying as it is hard to conciliate high pertinence, i.e. a strong dominance, and reasonable size of the selection. We propose to allow the user to decide what dominances are reliable, and what priorities between those dominances should be respected. This can be done by defining a sequence, eventually transfinite, of dominances. According to that sequence, we propose operators that compute progressively the ranking of a dataset by successive application of the dominances without introducing inconsistencies. The principle of progressive refinement provides a great flexibility to the user that can not only dynamically decide to stop the process whenever the results satisfies his/her wishes, but can also navigates in the different levels of ranking and be aware of the level of reliability of each successive refinement. We also define maximal selection and top-k methods, and discuss some experimentations of those operators.

Vidéo

Déjeuner

Session 2 - Web des données

1. Warehousing RDF Graphs Dario Colazzo, François Goasdoué, Ioana Manolescu and Alexandra Roatis Data warehousing (DW) research has lead to efficient techniques and tools for the multidimensional analysis of large amounts of data. As more data gets produced and shared in RDF, analytic concepts and tools for analyzing such irregular, graph-shaped, semantic-rich data need to be revisited. We introduce the first all-RDF model for warehousing RDF graphs. Notably, we define analytical schemas and analytical queries for RDF, corresponding to the relational DW star/snowflake schemas and cubes. We also show how typical OLAP operations can be performed on our RDF cubes, and we present some experiments validating the practical interest of our approach.
2. Collecte intelligente et adaptative d'applications Web pour l'archivage du Web Muhammad Faheem and Pierre Senellart Les sites Web sont par nature dynamiques, leur contenu et leur structure changeant au fil du temps. De nombreuses pages sur le Web sont produites par des systèmes de gestion de contenu (Content Management System ou CMS) tels que WordPress, vBulletin ou phpBB. Les outils actuellement utilisés par les archivistes du Web pour préserver le contenu du Web collectent et stockent de manière aveugle les pages Web, en ne tenant pas compte du CMS sur lequel le site est construit (ce qui conduit à des stratégies de collectes sub-optimales) et du contenu structuré de ces pages Web (ce qui résulte en des archives au niveau des pages dont le contenu est difficile à exploiter). Nous présentons dans cet article un application-aware helper (AAH) qui s'intègre à une chaine d'archivage classique pour accomplir une collecte intelligente et adaptative des applications Web (p. ex., les pages servies par un CMS). Parce que l'AAH est conscient des applications Web actuellement collectées, il est capable de raffiner la liste des URL à traiter et d'ajouter à l'archive de l'information sémantique sur le contenu extrait. Afin de traiter les changements possible de structure des applications Web, notre AAH inclut un module d'adaptation qui rend la collecte résistante aux petits changements de structure du site Web. Nous démontrons la valeur de notre approche en comparant la sortie et l'efficacité du AAH par rapport à des robots Web traditionnels, également en présence de changement.
3. Nearest-neighbor algorithms for diverse news retrieval Sofiane Abbar, Sihem Amer-Yahia, Piotr Indyk and Sepideh Mahabadi Les sites web d'information attirent de plus en plus d'utilisateurs qui sont plus que jamais enclins à exprimer leur opinion par rapport aux sujets qui les intéressent. Cette expression d'opinion se manifeste le plus souvent sous la forme de commentaires, impliquant à la fois des entités nommées et des sentiments. Les mécanismes de recommandation d'articles proposés aujourd'hui aux lecteurs ne prennent en considération que la popularité (ex. articles les plus lus, les plus partagés ou encore les plus commentés), la nouveauté (ex. articles les plus récents), et parfois les choix des éditeurs (ex. sujets les plus importants). Nous formalisons dans ce travail un nouveau problème de recommandation dont l'objectif est de trouver "le plus proche ensemble d'articles divers" par rapport à l'article courant que lit un utilisateur. La mesure de diversité proposée prend en considération les entités nommées extraites depuis les commentaires ainsi que les sentiments qui y sont exprimés. Étant donnée la contrainte temps-réel que doit satisfaire notre système de recommandation, nous avons exploré l’applicabilité des algorithmes approximatifs des plus proches voisins à notre problème. Nous avons montré à travers des expérimentations approfondies sur de vrais jeux de données de Aljazeera.com et de reuters.com la validité des différentes définitions de diversité que nous proposons en termes de qualité des recommandations retournées (en combinant la diversité et la pertinence) et de temps d’exécution.

Vidéo

Pause

Session 3 - Applications innovantes

1. Contrôle de version incertain dans l'édition collaborative ouverte de documents arborescents Mouhamadou Lamine Ba, Talel Abdessalem and Pierre Senellart En vue de faciliter l’enrichissement, l’échange et le partage de contenu, les plates-formes collaboratives Web telles que Wikipedia ou Google Docs permettent des interactions à large échelle entre un grand nombre de contributeurs. Cette collaboration ne requiert pas une connaissance préalable du niveau d’expertise et de fiabilité des participants. La gestion de version est donc essentielle pour garder une trace de l’évolution du contenu partagé et de la provenance des contributions. Dans de tels environnements, l’incertitude est malheureusement omniprésente à cause des sources non fiables, des contributions incomplètes et imprécises, des éditions malveillantes et des actes de vandalisme possible, etc. Pour gérer cette incertitude, nous utilisons un modèle XML probabiliste comme élément de base de notre système de contrôle de version. Chaque version d’un document partagé est représenté par un arbre XML et le document tout en entier, incluant toutes ses différentes versions, est modélisé en un document XML probabiliste. L’incertitude est évaluée via le modèle probabiliste et la mesure de fiabilité associée à chaque source, chaque contributeur, ou chaque événement d’édition. Ceci résulte en une mesure d’incertitude sur chaque version et chaque partie du document. Nous démontrons que les opérations classiques de gestion de version peuvent être implémentées directement comme opérations sur le modèle XML probabiliste ; son efficacité comparée aux systèmes de contrôle de version déterministes est démontrée sur des données réelles.
2. Large-Scale Sentiment Correlation for User Demographics Mikalai Tsytsarau, Sihem Amer-Yahia and Themis Palpanas L'agrégation de sentiments d'utilisateurs est aujourd'hui devenue une opération nécessaire sur le Web social où des millions d'internautes expriment une opinion individuelle sur une variété de sujets. Il existe un grand nombre d'approches pour l'extraction de sentiment de revues de produits ou de micro-blogs mais il y très peu de travaux qui se sont penchés sur l'agrégation et la comparaison de sentiments de différents groups d'utilisateurs tels que les étudiants en Italie ou les adolescents en Europe. Ce problème nécessite des méthodes efficaces qui doivent passer à l'échelle pour permettre la corrélation de sentiments à la demande. Dans ce travail, nous proposons une méthode d'indexation et d'agrégation de sentiments qui détecte automatiquement et de manière efficace la bonne granularité de temps pour corréler les sentiments de différents groupes d'utilisateurs. Nous décrivons également une méthode de compression des top-k corrélations qui améliore les performances sans affecter la qualité des résultats retournés. Nos multiples expériences sur des données synthétiques et réelles démontrent l'efficacité et l'efficience de notre solution.
3. Profile Diversity for Phenotyping Data Search and Recommendation Maximilien Servajean, Esther Pacitti, Sihem Amer-Yahia and Pascal Neveu Dans ce travail, nous étudions la diversité de profils. Il s'agit d'une approche nouvelle dans la recherche de documents scientifiques. De nombreux travaux ont combinés la pertinence des mots clés avec la popularité des documents au sein d'une fonction de score "sociale". Diversifier le contenu des documents retournés a également été traité de manière approfondie et la recherche, la publicité, les requêtes en base de données et la recommandation. Nous pensons que notre travail est le premier à traiter de la diversité de profils afin de traiter le problème des listes de résultats hautement populaires mais trop ciblées. Nous montrerons comment nous adaptons l'algorithme de Fagin sur les algorithmes à seuil pour retourner les documents les plus pertinents, les plus populaires mais aussi les plus divers que ce soit en terme de contenus ou de profils. Nous avons également un ensemble de simulations sur deux benchmarks afin de valider notre fonction de score.

Vidéo

Cocktail de bienvenue

O'Deck, Restaurant sur l'O

Accueil

Keynote : Collaborative Access Control in WebdamLog, Serge Abiteboul

Serge Abiteboul obtained his Ph.D. from the University of Southern California, and a Doctoral Thesis from the University of Paris-Sud. He became a researcher at the Institut National de Recherche en Informatique et Automatique in 1982. He was a Lecturer at the École Polytechnique and Visiting Professor at Stanford and Oxford University. He has been Chaire Professor at Collège de France in 2011-12 and Francqui Chair Professor at Namur University in 2012-2013. He co-founded the company Xyleme in 2000. Serge Abiteboul has received the ACM SIGMOD Innovation Award in 1998, the EADS Award from the French Academy of sciences in 2007 and the Milner Awards from the UK Royal Society. He became a member of the French Academy of Sciences in 2008, and a member the Academy of Europe in 2011. He is currently PI of the Webdam ERC (2008-2013) and a member of the LSV at the École Normale Supérieure, Cachan. His research work focuses mainly on data, information and knowledge management, particularly on the Web. He is a member of the Conseil national du numérique and Chairman of the Scientific board of the Société d'Informatique de France.

Abstract

We survey recent work on the specification of an access control mechanism in a collaborative environment. The work is presented in the context of the WebdamLog language, an extension of datalog to a distributed context. We discuss a fine-grained access control mechanism for intentional data based on provenance as well as a control mechanism for delegation, i.e., for deploying rules at remote peers.

Vidéo

Pause

Session 4 - Optimisation de requêtes

1. CliqueSquare: efficient Hadoop-based RDF query processing François Goasdoué, Zoi Kaoudi, Ioana Manolescu, Jorge Quiané-Ruiz and Stamatis Zampetakis Large volumes of RDF data collections are being created, published and used lately in various contexts, from scientific data to domain ontologies and to open government data, in particular in the context of the Linked Data movement. Managing such large volumes of RDF data is challenging due to the sheer size and the heterogeneity. To tackle the size challenge, a single isolated machine is not an efficient solution anymore. The MapReduce paradigm is a promising direction providing scalability and massively parallel processing of large-volume data. We present CliqueSquare, an efficient RDF data management platform based on Hadoop, an open source MapReduce implementation, and its file system, Hadoop Distributed File System (HDFS). CliqueSquare relies on a novel RDF data partitioning scheme enabling queries to be evaluated efficiently, by minimizing the number of MapReduce stages as well as the data transfers between nodes during query evaluation. Finally, we present preliminary experiments comparing our system against HadoopRDF, the state-of-the-art Hadoop-based RDF platform, which demonstrate the advantages of CliqueSquare in terms of query response times and network traffic.
   
   
2. MR-Part : Minimizing Data Transfers Between Mappers and Reducers in MapReduce Miguel Liroz, Reza Akbarinia, Divyakant Agrawal, Esther Pacitti and Patrick Valduriez La réduction du transfert des données dans la phase ``Shuffle'' de MapReduce est très importante, car elle augmente la localité des données, et diminue le coût total des exécutions des jobs MapReduce. Dans la littérature, plusieurs optimisations ont été proposées pour réduire le transfert de données entre les mappers et les reducers. Néanmoins, toutes ces approches sont limitées par la façon dont les clé-valeurs intermédiaires sont réparties sur les mappers. Dans cet article, nous proposons une technique qui repartitionne les tuples dans le fichier d'entrée, avec l'objectif d'optimiser la distribution des clés-valeurs sur les mappers. Notre approche détecte les relations entre les tuples d'entrée et les clé-valeurs intermédiaires en surveillant l'exécution d'un ensemble de tâches MapReduce qui est représentatif du workload. Puis, à partir des relations détectées, il affecte les tuples d'entrée aux mappers, et augmente la localité des données lors des futures exécutions. Nous avons implémenté notre approche dans Hadoop, et l'avons évaluée par expérimentation dans Grid5000. Les résultats montrent une grande réduction dans le transfert de données pendant la phase ``Shuffle'' par rapport à Hadoop.
   
   
3. Answering Why-Not questions Nicole Bidoit, Melanie Herschel and Katerina Tzompanaki With the increasing amount of available data and transformations manipulating the data, it has become essential to analyze and debug data transformations. A sub-problem of data transformation analysis is to understand why some data are not part of the result of a relational query. One possibility to explain the lack of data in a query result is to identify where in the query data pertinent to the expected, but missing output is lost during query processing. A first approach to this so called \emph{why-not provenance} has been recently proposed, but we show that this first approach has some shortcomings. To overcome these shortcomings, we propose an algorithm to explain non-existing data in a query result. This algorithm allows to compute the why-not provenance for relational queries involving selection, projection, join, and union. After providing necessary definitions, this paper contributes a detailed description of the algorithm. A comparative evaluation shows that it is both more efficient and effective than the state-of-the-art approach.
   
   

Déjeuner

Session Jeunes Chercheurs

1. Pattern mining in big datasets’ corners, Martin Kirchgessner
2. Contrôles d'accès pour l'intégration de données, Mehdi Haddad
3. Indexation d’une grande quantité de séquences ADN dans une base de données NoSQL à l’aide d’algorithmes de hachage perceptuel, Jocelyn De Goer
4. Interactive Exploration of Users and Activities, Behrooz Omidvar Tehrani
5. QTor : Une organisation basée sur les requêtes pour les systèmes distribués de gestion de flux, Sébastien Dufromentel
6. Query Processing Over Hybrid Database, Baraa Mohamad
7. A learning-based approach for optimizing global queries, Lourdes Martinez
8. An approach for social interest detection, Manel Mezghani
9. Modèles et Algorithmes pour la provenance dans le Cloud, Julien Lacroix
10. OnADIQ : Ontological Architecture for Dynamic Indexing and Querying - Application à la recherche d'information personnalisée, Vincent Martin
11. Composing, Processing and Notifying Event Flows, Orleant Epal Njamen
12. UNIMAP: Introduction to the Integration of Location-Based Services of Several Providers, Bilal Berjawi
13. Leveraging Ontology-based Methodologies for Designing Semantic Data Warehouses, Selma Bouarar

Vidéo

(présentation de Julien Lacroix non disponible sur la vidéo)

Pause

Session 5 - Sécurité et protection des données

1. Privacy-Preserving SQL Query Execution on Distributed Data Quoc-Cuong To, Benjamin Nguyen and Philippe Pucheral The de-facto monopoly of online services on the storage and management of personal data urged the scientific community to develop decentralized architectures where individuals keep full control on their data. The negative side effect is that global treatments/queries become impractical, impeding the development of services of great interest for the community. This paper promotes the idea of managing personal data on individuals' secure devices and proposes distributed querying protocols which do not reveal any sensitive information to central servers. We show that our protocols can support general SQL queries and are secure against honest-but-curious and weakly-malicious attackers. Cost models and experiments demonstrate that this approach can gracefully scale up to nationwide sized datasets.
2. Securing Materialized Views: a Rewriting-Based Approach Sarah Nait-Bahloul, Emmanuel Coquery and Mohand-Said Hacid A materialized view consists of both the definition of the view and the rows resulting from the view execution. Several techniques and models have been proposed to control access to databases. However, the problem of automatically generating from access control policies defined over base relations, the access control policies that are needed to control materialized views, is not investigated so far. We choose to express fine-grained access control through authorization views. We investigate this problem by resorting to an adaptation of query rewriting techniques. We provide a complete approach to automatically derive access control policies of materialized views from access control policies defined for base relations when views can be expressed as conjunctive queries.
3. tau-safety: a privacy model for sequential publication with arbitrary updates Adeel Anjum and Guillaume Raschia La grande majorité des travaux de recherche menés dans le cadre de la publication de données respectant la vie privée par des mécanismes d'assainissement font l'hypothèse d'une publication unique et datée, sans prise en compte des modifications ultérieures du jeu de données. Néanmoins, dans nombre de cas d'espèces de la vie courante, les données à assainir sont changeantes et ce de manière arbitraire. De ce fait, appliquer une nouvelle fois un mécanisme d'assainissement élaboré sous l'"hypothèse statique" sur un jeu de données mis à jour conduit inévitablement à introduire des failles dans la protection des données. Parmi les rares travaux qui traitent de la publication en séquence, aucun à notre connaissance ne fait l'hypothèse de mises à jour quelconques, ni même d'informations auxiliaires enregistrant les modifications de données par individu. Dans cette communication, nous commençons par invalider les mécanismes existants sous ces nouvelles hypothèses, puis nous proposons une extension de la m-invariance intitulée tau-sûreté. Nous proposons également une formalisation du problème de protection de données pour la publication en séquence avec mises à jour quelconques et informations auxiliaires de traçabilité individuelle. Pour finir, nous présentons et expérimentons un nouveau mécanisme qui produit des données tau-sûres tout en maintenant un degré d'utilité élevé pour l'interrogation et l'analyse des données assainies.

Vidéo

Banquet

Baron-Lefevre

Accueil

Session 6 - Optimisation sous contraintes

1. Exploration adaptative de graphes sous contrainte de budget Georges Gouriten, Silviu Maniu and Pierre Senellart Nous nous intéressons dans cet article à l'exploration d'un graphe tel celui du Web ou d'un réseau social dans un contexte où les nœuds (et les arêtes qui en sont issues) sont découverts un à un, et où le nombre total de nœuds que l'on peut explorer est contraint. Le but est d'optimiser un score global du sous-graphe découvert, fonction monotone de scores élémentaires sur chaque nœud. Ce problème se pose en particulier quand on souhaite collecter les pages du Web correspondant à un sujet donné ou quand on utilise l'API du site d'un réseau social tel Twitter pour constituer un jeu de données centré sur d'un thème. Nous présentons une abstraction de ce problème faisant appel à deux composants principaux : une stratégie d'exploration et un estimateur du score des nœuds de la frontière du graphe. Nous montrons qu'une stratégie gloutonne est suffisante en pratique, et qu'il est possible de s'adapter aux caractéristiques de différents graphes en utilisant des estimateurs qui apprennent automatiquement les caractéristiques prédisant le mieux les scores des nœuds. Ces techniques sont appliquées à des des graphes réels issus de Wikipedia ou de Twitter.
   
   
2. Delta: Scalable Data Dissemination under Capacity Constraints Konstantinos Karanasos, Asterios Katsifodimos and Ioana Manolescu Dans des systèmes d'abonnements basés sur le contenu, les utilisateurs expriment leurs intérêts par des requêtes sur les flux de publications. Le passage à l'échelle des systèmes d'abonnements pose de nombreux problèmes de performance: les utilisateurs sont intéressés par la fraîcheur des données, c'est à dire, obtenir les résultats de leurs abonnements le plus vite possible, tandis que les fournisseurs du système sont surtout intéressés par le passage à l'échelle, c'est à dire, être capable de répondre à de grands nombres d'utilisateurs tout en utilisant peu de ressources système. Nous décrivons une nouvelle approche de dissémination de données dans un système d'abonnements, en présence de contraintes sur les ressources CPU et réseau disponibles; cette approche est mise en oeuvre dans le cadre de notre plateforme Delta. Le passage à l'échelle est obtenu en déchargeant le fournisseur de données de l'effort de répondre à une partie des abonnements; en échange, nous tirons profit de techniques de re-écriture de requêtes à l'aide de vues afin de propager les données de ces abonnements à partir d'autres abonnements. Notre contribution principale est un nouvel algorithme qui organise les vues dans un réseau de dissémination d'information sur plusieurs niveaux, qui s'appuie sur la re-écriture à base de vues ainsi que sur des techniques puissantes de programmation linéaire afin de passer à l'échelle pour de grands nombres de vues, respecter les contraintes de capacité du système, et minimiser les délais de propagation des information. L'efficacité et la performance de notre algorithme est confirmée par notre évaluation expérimentale, qui inclut l'étude d'un déploiement réel dans un réseau WAN.
   
   

Pause

Session 7 - Dépendances de données

1. Calcul parallèle de dépendances Eve Garnaud, Nicolas Hanusse, Sofian Maabout and Noël NovelliL'extraction de dépendances fonctionnelles (DFs) est un problème classique qui continue de susciter de nouveaux travaux du fait des multiples exploitations possibles que cette information peut avoir. Dans cet article, nous présentons un algorithme parallèle paramétrable qui calcule les DFs exactes, DFs approchées, DFs conditionnelles (DFCs) ainsi que les clés minimales. Pour les cas des DFs exactes et des clés minimales, les tests de validité sont basés sur un calcul de nombre de valeurs distinctes. Nous étudions l'introduction des techniques approximatives proposées à cet effet (nombre de valeurs distinctes), précisément la méthode Hyperloglog, permettant ainsi d'économiser l'espace mémoire et ouvrant la voie à une approche parallèle orientée données. Ceci est d'autant plus important quand les données sont massives. Bien que les résultats retournés dans ce dernier cas soient approximatifs, nous donnons des bornes théoriques sur les erreurs qu'on peut avoir. Une série d'expériences montrent l'efficacité de notre approche.
   
   
2. Extending Multivalued Dependencies for Refactoring Access Control Policies Matteo Casalino and Romuald Thion Policy-based access control is a well-established paradigm for securing layered IT systems. Access control policies, however, often do not focus on dedicated architecture layers (e.g., network, web, application), but increasingly employ concepts of multiple layers. Web application servers, for instance, typically support request filtering on the basis of network addresses. The resulting flexibility comes with increased management complexity and the risk of security-relevant misconfiguration when looking at the various policies in isolation. In this paper we focus on policy refactoring, i.e., the task of finding the least permissive rewriting of a collection of policies such that the global composed policy remains identical. Some connections between access control and the relational model have been already identified in literature. Following this avenue, we argue that normalization theory can help to solve the refactoring problem. By exploiting techniques inspired from multivalued dependencies, we lay down the foundations of a theoretical framework that allows (i) to describe authorization policies from different architecture layers, (ii) to capture the relationships between layers in order to create a universal view of the global policy, and (iii) to decompose the global policy into a collection of simpler ones.
   
   
3. Maximal Set of XML Functional Dependencies over Multiple Systems Joshua Amavi and Mirian Halfeld Ferrari Nous voulons établir des contraintes d'intégrité pour une application web conçue comme une évolution conservatrice de différents systèmes locaux manipulant des données similaires, mais pas forcément identiques. Cette application doit être capable de vérifier un maximum de contraintes locales ainsi que de traiter tous les documents valides par rapport aux sources d'origine. Dans ce cadre, nous proposons un algorithme efficace pour obtenir l'ensemble maximal de dépendances fonctionnelles (XFD) locales non contradictoires. Notre méthode est fondée sur un système d'axiomes correct et complet pour des XFD relatives permettant deux types d'égalités. Ce papier aborde plusieurs aspects théoriques et pratiques des dépendances fonctionnelles en XML. Nos expérimentations montrent l'intérêt de l'approche.
   
   

Déjeuner

Session 8 - Matching

1. Resolving Terminological Heterogeneity Across Ontologies by Using Information Content Duyhoa Ngo, Zohra Bellahsene and Konstantin Todorov Terminological matchers discover correspondences across the elements of ontologies by comparing the annotations, such as labels and comments, of their concepts and relations. To this end, they often combine different similarity measures, coming from neighboring fields, such as information retrieval, bioinformatics or databases. In order to adapt these measures, the specificity of the ontology matching task needs to be considered. Addressing this challenge, we propose a novel method to compute similarity between cross-ontology concepts based on the amount of overlap of the information content of their labels. We extend Tversky's similarity measure by using the information content of each term within an ontology label both for the similarity computation and for the weight assignment to tokens. The approach is able to effectively compute similarity between complex, compound concept labels. We have carried out ontology matching experiments on two different datasets. The results show that our method outperforms state-of-the-art terminological similarity measures for the ontology matching task.
   
   
2. On Leveraging Crowdsourcing Techniques for Schema Matching Networks Quoc Viet Hung Nguyen, Thanh Tam Nguyen, Zoltan Miklos and Karl Aberer As the number of publicly-available datasets are likely to grow, the demand of establishing the links between these datasets is also getting higher and higher. For creating such links we need to match their schemas. Moreover, for using these datasets in meaningful ways, one often needs to match not only two, but several schemas. This matching process establishes a (potentially large) set of attribute correspondences between multiple schemas that constitute a schema matching network. Various commercial and academic schema matching tools have been developed to support this task. However, as the matching is inherently uncertain, the heuristic techniques adopted by these tools give rise to results that are not completely correct. Thus, in practice, a post-matching human expert effort is needed to obtain a correct set of attribute correspondences. Addressing this problem, our paper demonstrates how to leverage crowdsourcing techniques to validate the generated correspondences. We design validation questions with contextual information that can effectively guide the crowd workers. We analyze how to reduce overall human effort needed for this validation task. Through theoretical and empirical results, we show that by harnessing natural constraints defined on top of the schema matching network, one can significantly reduce the necessary human work.
   
   

Clôture