Bases de Données / Databases

Site Web de l'équipe BD du LIP6 / LIP6 DB Web Site

Outils pour utilisateurs

Outils du site


site:recherche:axes_de_recherche

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision
Révision précédente
site:recherche:axes_de_recherche [05/01/2017 09:49]
amann
site:recherche:axes_de_recherche [15/12/2017 22:09] (Version actuelle)
amann
Ligne 1: Ligne 1:
 {{indexmenu_n>​1}} {{indexmenu_n>​1}}
-~~NOTOC~~ 
  
-====== ​Thèmes ​de recherche ======+====== ​Axes de recherche ======
  
-<WRAP clear/> 
  
 +===== Data streams and continuous queries =====
 +The web produces continuous streams of text items published as RSS news, tweets, blog messages etc. Users can subscribe to these streams be defining queries which continuously filter and rank the most recent information items. A major challenge is then to efficiently process millions of such subscription queries over high rate input streams. In the context of the ROSES ANR project ROSES (2008-2012) on RSS feed aggregation and filtering we worked in on multi-query optimisation (PhD J. Creus), on efficient refresh strategies for dynamic RSS feeds (PhD of R. Horincar in collaboration with the MLIA team), and on continuous top-k query processing (PhD of N. Vouzoukidou in collaboration with ICS-Forth, Crete).
  
-<​tabs>​ +===== Web archive indexing and maintenance ​===== 
-  * [[#​tab-positionnement|Positionnement]] + The Web is continuously changing and building representative archives for the future generates many challenging data processing problems including efficient harvesting, storage and indexing of Web resources. Our work on these 
-  * [[#​tab-theme1|Flux de données]] +challenges has started within the ANR Cartec project (before 2012) and pursued in the context of the European 
-  * [[#​tab-theme2|Archivage du web]] +research project SCAPE (2011-2014) and an ongoing collaboration with the Central University of Venezuela 
-  * [[#​tab-theme3|Données distribués]] +(UCV)Caracas. The originality of our contributions is based on a Web page segmentation and ranking model 
-  * [[#​tab-theme4|Qualité de données]] +which identifies and ranks semantically coherent blocks within a web pageBased on this model, highly-ranked 
-  +blocks can be considered as more important by a page refresh strategy or more relevant within an information 
-<pane id="​tab-positionnement">​ +retrieval task. Three PhD thesis took place in this context on (1) semantic web page refresh strategies for web 
-====== Positionnement scientifique ​ ====== +archives(2) Web archive querying and text indexing (pruning)and (3) Web page segmentation and migration 
-Les problèmes actuels de gestion de données se caractérisent par un accroissement constant et considérable +to HTML5 format (collaboration with UCV)A collaboration with the MLIA team (PhD thesis of M. Law) 
-des données à traiter et par l’émergence de nouveaux usages de ces donnéesprincipalement induits par le +allowed us to explore advanced machine learning and image analysis techniques to improve the accuracy of our 
-développement du web social et du web sémantiqueLes systèmes et les technologies classiques de la gestion de +page change estimation model.
-données ne sont plus à même de gérerde traiteret d’analyser efficacement ces gigantesques masses de données+
-Les recherches menées dans l’équipe Bases de Données visent à offrir des solutions efficaces et originales pour +
-la gestion de données à large échelle et ses nouveaux usages. Elles se concentrent plus précisément sur l’accès +
-aux données, la qualité et la cohérence des données et la gestion de transactions à large échelle+
  
-</​pane>​ +===== Workload-aware data replication ​===== 
-<pane id="​tab-theme1">​ +Distributed transactions in large data clusters 
-===== Filtrage et Agrégation de Flux d’Informations ​=====+generate a high control and synchronization overhead which is a major obstacle for achieving scalability. To 
 +reduce this overhead, we focus on user-centric applications where (1) the data fragment attached to each user 
 +defines the basic access unit, (2) transactions mostly access the data of two users (message exchange) and (3) the 
 +access frequency (popularity) is biased and fluctuates over time. To achieve optimal performance,​ we propose 
 +to move user data to a single node where the transaction can be executed locally. Then, under the assumption 
 +that users interact within social circles, we detect data groups (or bundles) and adapt data placement and cluster 
 +resources gradually according to their interactions. We have studied a related problem in the context of the 
 +GBIF (Global Biodiversity Information Facility) community and designed advanced querying facilities for 
 +world-wide federations of autonomous databases storing descriptions of observed natural species. To overcome 
 +the limited query capacities of GBIF database interfaces, we proposed a distributed middle-ware providing 
 +a higher-level structured access to the GBIF data. Our main contributions are a decentralized algorithm for 
 +parallel query processing and a cost-based placement and replication strategy keeping node usage (storage and 
 +query processing) below a given upper bound. This work is part of two PhD thesis (I. Gueye and N. Bame) in 
 +collaboration with the University Cheikh Anta Diop (UCAD) in Senegal.
  
-==== Positionnement scientifique ​==== +===== SPARQL query optimization ​===== 
- Les utilisateurs du Web 2.0 sont de plus en plus confrontés à une surcharge +RDF has become a standard format 
-d’information provoquée par l’apparition de ressources d’informations de plus en plus dynamiques comme +for publishing and integrating data and knowledge on the webThe resulting Linked-Open-Data cloud is conti- 
-les sites d’actualités et les médias sociauxL’enjeu du thème “Agrégation de flux RSS” est de fournir à ces +nuously growing and implementing efficient SPARQL query processors is a challenging problemTo achieve 
-utilisateurs des outils de personnalisation de flux d’informations sur le WebL’approche choisie consiste à +scalability,​ we propose to exploit MapReduce data parallelism implemented in the Apache Spark platformFor 
-combiner le standard ​RSS largement utilisé par les applicationsWeb 2.0 avec des techniques d’interrogation de +this, we defined a cost-model which allows to choose among two standard ​distributed join operators (partitioned 
-flux de donnéesNous avons en particulier étudié des problèmes posés par le passage à l’échelle en terme de +and broadcast join) implemented on top of the different Spark data layersOur experimental results show that 
-nombre de flux et de requêtes à traiter.+hybrid join plans combining these two operators allow to improve the performance significantly.
  
-==== Principaux résultats ​==== +===== Social Recommendation Models and Algorithms ===== 
-Le projet ANR RoSeS (2008-2011) se trouve au coeur de ce thème de recherche+Recommendation methods aim to predict, for a given user, the rating or preference she would give to an “item” which can 
-L’objectif de ce projet ​(coordonné par Bernd Amannétait de réaliser un agrégateur de flux d’informations qui +be an action, a document, a product or even another user etcThese predictions can be derived from different 
-intègre un crawler RSS et un moteur de requêtes continues pour l’interrogation de flux RSS+kinds of input data like the past activities, social links and preferences of the user and of other “similar” users 
-Le moteur de requêtes RSS développé par Jordi Creus dans le cadre de sa thèse intègre une nouvelle technique +(collaborative filteringand/or the explicit description of the items and the preferences of the users (content- 
-d’optimisation multi-requêtes pour des grandes collections de requêtes continues RSS. Cette technique +based filtering)
-est fondée sur une algèbre d’opérateurs continues (filtrageunion, jointure, transformation) et des règles de +==== User similarity and recommendation in social networks ==== 
-normalisation et de factorisation de prédicatsUne contribution importante est la définition d’un algorithme de +We consider the problem of discovering valuable 
-recherche approximative d’un arbre de Steiner minimal dans un treillis d’inclusion de prédicats logiques exploitant +content publishers in micro-blogging systems by providing efficienttopological and contextual user recom- 
-les propriétés particuliers de la distribution des coûts dans le grapheCes travaux ont été publiés dans +mendationsBuilding on the idea that topology-based measures are good indicators for estimating user simi- 
-deux conférences internationales[26,​ 15] et un journal national [39]+larity, we propose personalized user recommendation scores which capture both the topological proximity and 
-La thèse de Roxana Horincar présente une nouvelle stratégie de rafraîchissement de documents RSS qui +connectivity of publishers along with their topic authoritiesThe size of the underlying social graphs strongly 
-prend en compte le problème de perte d’information [16] et intègre un modèle d’estimation de divergence +influences score computation costs especially with graph exploration operatorsIn order to speed up the re- 
-dynamique adapté aux flux RSS [23]Ce travail ​adapté des travaux existants sur les stratégies “best-effort” +commendation process we propose approximate algorithms based on landmarks that are selected according to 
-pour le crawling de pages web et inclut des nouvelles techniques d’estimation en-ligne des fréquences de +several strategiesWithin this context, we also develop ​novel block-based, workload-aware edge partitioning 
-publication de flux RSS+strategy for distributed user similarity computation. Our method relies on a block approach for capturing local 
-Par ailleursnous avons étudié des algorithmes d’estimation de scores dans les réseaux d’annotation collaboratifs +communities and takes advantage of the topological real-world large graph properties to provide a balanced 
-(social tagging systems). Nous nous sommes particulièrement intéressés à des problèmes d’optimisation +edge distribution and reduce the communication costs for random walk-based computationsThis work was 
-des calculs de scores sociaux en partant des travaux de thèse de Camelia Constantin et des travaux d’Hubert +done in collaboration with the Cédric-CNAM laboratory (PhD of R. DahimeneQ. Grossetti and Y. Li) and was 
-naacke sur la cohérence de données répliquées.+partially supported by the PEPS INS2I/INSMI 2015 FaSciDo “FAIT” ​(Finding Account of Interest on Twitter).
  
-</​pane>​ +==== Online matrix factorization and tag recommendation ​==== 
-<pane id="​tab-theme2">​ +In this work, we consider matrix factorization algorithms in highly dynamic contexts with continuous rating streams where it is difficult to have an up-to-date 
-===== Archivage du Web =====+recommendation model even with powerful parallelization techniques. Our solution reduces the lag-based re- 
 +commendation quality loss by introducing biases tracking the user behavior deviation. These biases are conti- 
 +nuously updated with the new ratings, in order to maintain the quality of recommendations at a high level for a 
 +longer time. We also propose an algorithm that takes into account the popularity of the tags and the opinions of 
 +the user’s neighborhood. Unlike the common Nearest-Neighbors approaches, which relies on a fixed number 
 +of neighbors, we propose a heuristic network traversal bound that enables on-the-fly recommendation com- 
 +putation with limited computation cost. We also propose a new method for improving the accuracy of top-k 
 +recommendation algorithms which dynamically estimates and adjusts candidate item lists to optimize the glo- 
 +bal recommendation accuracy. Finally, we propose a new Geographical POI (Point of Interest) recommendation 
 +method which takes into account the delay and distance between POIs to better capture the set of POIs which 
 +might be worth to be visited together than other existing methods based on matrix factorization. This work is 
 +done in collaboration with the LTCI-Télécom ParisTech (PhD M. Gueye, PhD J.-B. Griesner).
  
-==== Positionnement scientifique ​==== +===== Large-Scale text mining workflows ===== 
- L’archivage duWeb est en pleine expansion depuis une dizaine d’annéesdans +In the context of the ARESOS CNRS Mastodons projectwe have started to explore the usage of MapReduce based algo- 
-un nombre grandissant de paysL’un ​des enjeux du thème est d’améliorer la qualité ​(complétude et cohérence +rithms and platforms (Hadoop and Spark) for complex text and graph mining workflowsIn collaboration with 
-temporellesdes archives Web malgré la limitation des ressources (bande passantepolitesse, stockage. . .). La +the Institut ​des Systèmes Complexes and IRISA (Université de Rennes), the goal is to design and implement 
-complétude reflète la quantité de versions de pages importantes archivées par rapport aux versions générées +scalable algorithms for building phylomemetic networks describing the evolution of science in form of tempo- 
-sur les sites. La cohérence reflète le fait que les versions archivées sont apparues en même temps sur le Web+ral topic graphsScalability is achieved by combining data parallelism and incremental computation for topic 
-Pour cela, il faut estimer le comportement des sites pour crawler au bon momentUne fois l’archive constituée+extraction and topic alignmentAfter some preliminary resultsthis work is perpetuated in the ANR project 
-il est nécessaire de disposer d’outils de recherche d’information (RI) adaptés aux caractéristiques des archives +EPIQUE which started in January 2017 under our coordination.
-(incomplétude et dimension temporelle)+
  
-==== Principaux résultats ​==== +===== Representation learning and information access ===== 
- Notre approchedéveloppée dans le cadre du projet ANR Cartec (2008-2011) consiste +The topic machine learning and information access is mainly represented by B. Piwowarski who enriched the team competencies for better understanding data science related problems and applicationsand fosters the collaboration with the MLIA team 
-à fournir un outil très précis de comparaison entre versions successives,​ afin de mieux quantifier les changements +around the theme of learning to project complex objects ​(e.gtext or graphsinto continuous latent space for 
-intervenus. Afin de tenir compte de l’aspect visuel des pages (primordial dans le contexte du dépôt légal), +information access tasks : node classificationinformation retrievalor word evolutionThe quantum probability 
-nous procédons au préalable à une segmentation de la page en blocs, puis affectons des poids d’importance aux +formalism,whichisawaytorepresentobjectsinacontinuousspace,hasbeenalsoexploitedforsummarization.
-blocs, ce qui permet de quantifier un changement intervenu dans un blocCeci permet, dans une phase d’apprentissage,​ +
-de définir un pattern de changement quotidien pour chaque pageCes patterns permettent de mettre +
-en oeuvre des algorithmes optimisant la complétude temporelle, la cohérence temporelle, ou bien les deux à la +
-fois (Thèse de Myriam Ben Saad). Les résultats obtenus sont d’une part un prototype qui inclus la segmentation +
-de versions de page, leur comparaison et le calcul de l’ordonnancement ou de la fréquence optimale, et d’autre +
-part un grand nombre de publications [32, 29, 30, 12, 13, 4]. Il est à noter que l’originalité de notre approche, +
-par rapport aux approches précédentes, ​été unanimement reconnue. Elle a valu deux récompenses best student +
-paper à Myriam Ben Saad [2912]. +
-Par ailleursdans le cadre de la thèse de Zeynep Pehlivan, nous developpons des outils de RI pour les +
-archivesLes travaux portent sur la définition d’un modèle de données [27], d’algorithmes de ranking temporel +
-incluant les blocs des pages segmentés et leur importanceainsi queplus récemment, des techniques de +
-compression d’index par élagage (pruning). +
-Enfin, les techniques développées dans le cadre du projet Cartec sont reprises et étendues dans le cadre du +
-projet européen Scape (collaboration avec M. Cord, équipe Malire). La contribution de l’équipe BD est principalement +
-de développer un nouvel outil de segmentation plus précis que les outils actuels [24, 10]. Cet outil +
-se base sur une approche hybride (structurelle et par traitement d’image) développée dans le cadre notamment +
-des thèses de Marc Law et Andrès Sanoja.+
  
-</​pane>​ +===== Semantic IoT data integration ​=====
-<pane id="​tab-theme3">​ +
-===== Gestion des données et des transactions à large échelle ​====+
- +
-==== Positionnement scientifique ==== +
- Nous étudions les problèmes de gestion de données dans les applications web +
-transactionnelles. Une caractéristique principale de ce type d’application est le nombre important d’utilisateurs +
-qui accèdent concurremment à des données pour les modifier, ce qui génère des lectures/​écritures intensives. +
-En présence de millions d’utilisateurs,​ il s’avère complexe de maintenir la cohérence des données lues ou +
-modifiées simultanément (e.g., enchères en ligne). D’une part, les données doivent être répliquées afin de traiter +
-en parallèle les nombreuses demandes de lecture. D’autre part, la modification d’une donnée répliquée nécessite +
-de synchroniser les répliques pour garantir leur cohérence, ce qui ralentit l’accès aux données. Les travaux +
-effectués par l’équipe BD visent à offrir un compromis cohérence/​performance le mieux adapté à la gestion des +
-transactions en fonction du contexte applicatif. +
- +
-==== Principaux résultats ==== +
- Dans le cas où les transactions sont courtes, mais trop nombreuses pour être traitées +
-de manière centralisée,​ nous avons proposé une solution intergicielle décentralisée pour acheminer (ou router) +
-chaque transaction vers une réplique optimale, de telle sorte que la réplique choisie soit suffisamment cohérente +
-et que le temps de réponse des transactions reste inférieur au plafond toléré par les utilisateurs finaux [35, 50, +
-40]. La solution repose sur une infrastructure pair-à-pair qui découple les serveurs de données, et les tiers +
-chargés de maintenir la cohérence des répliques et d’équilibrer la charge. Un prototype (TransPeer [17]) a +
-été expérimenté à grande échelle. De plus, une stratégie de routage optimiste permet de paralléliser encore +
-plus largement les transactions. Pour cela, l’indépendance entre les transactions est déterminée dynamiquement +
-pendant leur exécution [31, 40]. Ces travaux se sont déroulés dans le cadre du projet ANR Respire porté par S. +
-Gançarski. +
-Lorsque la charge transactionnelle présente des pics importants (augmentation brusque du nombre d’utilisateurs +
-simultanés voulant modifier la même donnée), nous avons proposé, au sein du projet SyncDB (projet +
-interne au LIP6, en collaboration avec l’équipe Regal), une solution répartie, basée sur un anneau à jeton. La +
-solution est robuste aux pics de transactions,​ et de plus, tolère les pannes de plusieurs membres consécutifs de +
-l’anneau [25]. +
-Lorsque l’infrastructure sous-jacente doit être louée en fonction de l’usage (modèle dit pay per use), nous +
-avons proposé une solution pour ajuster le nombre de machines qui forment l’intergiciel,​ au plus près des +
-besoins provenant de la charge applicative qui peut croitre et décroitre [21]. +
-Nous nous sommes également intéressées à des transactions portant sur des données semi-structurées +
-(XML). Sur chaque serveur, nous avons proposé un algorithme de gestion de concurrence optimiste qui autorise +
-les transactions à s’effectuer en parallèle lorsque les données touchées ne sont pas conflictuelles a priori [37, 34]. +
- +
-</​pane>​ +
-<pane id="​tab-theme4">​ +
-===== Qualité de Workflows de Données ===== +
- +
-==== Positionnement scientifique ==== +
- Des nombreuses applications modernes sont définies par des compositions +
-de services web spécialisées pour traiter et pour produire des données complexes. Dans certains domaines +
-comme les chaînes de traitement de données scientifiques ou de données du web, le choix des services (et des +
-paramètres utilisés) peuvent fortement influencer la qualité des resultats obtenus. Dans cette thématique nous +
-nous adressons au problème de l’estimation et l’amélioration de workflows en prenant en compte la provenance +
-et la qualité des données produits par les appels de service. Nous étudions à la fois l’interaction entre les modèles +
-de qualité de services et de qualité de données, leurs mise-en-oeuvre et leur application dans le contexte de la +
-génération d’entrepôts de données web. +
-</​pane>​ +
- +
-</​tabs>​+
  
 +In January 2014, we have started a new activity on Smart IoT applications as part of the two year exploratory project EBITA. The goal of EBITA was to
 +explore business and research opportunities between Fraunhofer (Germany) and UPMC concerning semantic
 +data technologies developed in the DAPA department and the IOSB Fraunhofer Institute in Karlsruhe. During
 +the project (01/2015- 12/2016), the team temporarily hosted the project leader (V. Tippmann) and two research
 +engineers. EBITA also allowed us to finance an ongoing PhD on semantic IoT data enrichment and integration
 +(F. Hannou). Taking the data generated by thousands of sensors at the Jussieu Campus as starting point, the
 +goal is to develop new data preparation and integration methods for combining raw sensor data with contex-
 +tual information (room occupation, energy consuming devices, outside temperature,​ ...) to enable higher-level
 +semantic data exploration and analysis.
  
 +===== Schema inference for NoSQL applications =====
 +Data formats like XML or JSON are more and
 +more adopted because of their flexibility to encode semi-structured documents data. Compared to the relational
 +model where data must strictly conform to a predefined prescriptive schema, JSON imposes no a priori schema
 +simply because the structure of the data is unknown in advance or might change later. However, the absence
 +of a schemas also complicates the interaction with the data. First, formulating sound queries without a concise
 +description of the underlying data is more difficult. The lack of a schema prevents query processors from perfor-
 +ming a static analysis to check, for example, if a query uses nonexistent attributes. Finally, the lack of schema
 +prevents from accelerating query processing by using well-known optimization techniques like wildcard ex-
 +pansion and data projection. We introduce an MapReduce based inference algorithm for extracting descriptive
 +schemas from large JSON data-sets. The extracted schemas concisely and precisely capture the structure of the
 +input data set. This work is done in collaboration with researchers from Paris-Dauphine University, University
 +of Pisa and University della Basilicata, Italy.
  
site/recherche/axes_de_recherche.1483606197.txt.gz · Dernière modification: 05/01/2017 09:49 par amann