News
You are here : English versionNewsNews

PhD Defense Mahfoud Djedaini

Dates

on the December 6, 2017

14h00
Location
Amphi 1, IUT de Blois, 3 place Jean Jaurès, 41000 Blois

Automatic assessment of Databases explorations: The OLAP use case

Résumé :

Avant l’arrivée du Big Data, la quantité de données contenues dans les bases de données était relativement faible et donc plutôt simple à analyser. Dans ce contexte, le principal défi dans ce domaine était d’optimiser le stockage des données, mais aussi et surtout le temps de réponse des Systèmes de Gestion de Bases de Données (SGBD). De nombreux benchmarks, notamment ceux du consortium TPC, ont été mis en place pour permettre l’évaluation des différents systèmes existants dans des conditions similaires. Cependant, l’arrivée de Big Data a complètement changé la situation, avec de plus en plus de données générées de jour en jour. Parallèlement à l’augmentation de la mémoire disponible, nous avons assisté à l’émergence de nouvelles méthodes de stockage basées sur des systèmes distribués tels que le système de fichiers HDFS utilisé notamment dans Hadoop pour couvrir les besoins de stockage technique et le traitement Big Data. L’augmentation du volume de données rend donc leur analyse beaucoup plus difficile. Dans ce contexte, il ne s’agit pas tant de mesurer la vitesse de récupération des données, mais plutôt de produire des séquences de requêtes cohérentes pour identifier rapidement les zones d’intérêt dans les données, ce qui permet d’analyser ces zones plus en profondeur, et d’extraire des informations permettant une prise de décision éclairée.

Comme nous le verrons plus en détail dans le chapitre 3, beaucoup de chercheurs de différentes communautés ont commencé à considérer ces défis et ont proposé des approches inspirées de leurs propres domaines de recherche pour les gérer. Dans le domaine de l’Exploration Interactive des Données, les chercheurs ont lutté et luttent toujours pour construire des systèmes de support utilisateur de plus en plus efficaces. Quelle que soit la communauté, les systèmes de support utilisateur ont le même objectif et globalement le même mode de fonctionnement. En fonction de l’utilisateur actuel et du système actuel sur lequel travaille l’utilisateur, ces systèmes peuvent suggérer certaines requêtes ou données à l’utilisateur. Ils essayent de le guider aussi bien que possible vers les données qui lui permettront de répondre à son besoin en information. Avec la multiplication de ces systèmes, les chercheurs de la communauté benchmarking ont récemment commencé à proposer différentes stratégies afin de construire des benchmarks qui prennent en considération
l’aspect qualité des explorations de données que permettent d’atteindre ces systèmes. En effet, comme indiqué ci-dessus, il ne suffit plus d’évaluer la rapidité d’un système, mais un système doit être évalué en fonction de l’aide qu’il apporte aux utilisateurs. En même temps, beaucoup d’efforts ont été faits autour de l’Analyse Utilisateur. De la Recherche Exploratoire [White et Roth, 2009] à la mesure de l’évolution des connaissances des utilisateurs, nous avons assisté ces dernières années à plusieurs approches qui considèrent la satisfaction utilisateur comme leur principale préoccupation.

Dans ce travail, nous présentons plusieurs contributions dont l’objectif est de combler certaines des lacunes actuelles identifiées ci-dessus. La première contribution que nous proposons est d’évaluer une exploration de données en termes de qualité puis d’utiliser ce cadre d’évaluation pour estimer le niveau d’expertise des analystes sur la base des explorations qu’ils produisent. Notre deuxième contribution importante consiste à évaluer qualitativement les systèmes de support à l’Exploration Interactive des Données. D’une manière générale, notre contribution consiste à proposer un benchmark permettant à un système de générer des explorations de données, puis d’évaluer ce système à travers les explorations qu’il permet de produire, en s’appuyant notamment sur le cadre d’évaluation proposé dans la précédente contribution.

Dans notre approche, nous limitons d’abord intentionnellement la portée aux bases de données multidimensionnelles et à la navigation OLAP. Nous nous limitons d’abord à OLAP en raison de son caractère exploratoire, mais aussi parce que sa topologie favorise un support utilisateur plus simple au départ. De manière plus pragmatique, la littérature OLAP fournit presque tous les logiciels et algorithmes pertinents pour implémenter nos propositions. Avoir des preuves de concept fonctionnant sur OLAP prouverait alors la faisabilité de nos propositions. Il conduirait alors intuitivement à l’extension de l’idée, à appliquer dans d’autres domaines, pour lesquels les bases de données relationnelles semblent être un bon candidat à étudier.

Evaluer les compétences des analystes OLAP Une contribution importante de notre travail est la conception d’un modèle automatique pour évaluer dans quelle mesure un analyste OLAP maîtrise l’exploration de données. Notre méthode est basée sur un modèle descriptif de requêtes OLAP développé par nos soins, qui est en soi une contribution, présenté en détail dans le chapitre 4. Dans ce modèle, une requête OLAP est représentée comme un ensemble de 25 scores calculés par 25 descripteurs, permettant de capturer un maximum d’aspects de la requête. Nous utilisons ensuite un SVM (un algorithme d’apprentissage automatique supervisé) pour apprendre, sur la base d’étiquettes faites par des experts, comment une requête permet de satisfaire le besoin d’information pour lequel l’utilisateur a décidé d’entreprendre une exploration. En utilisant ce modèle, afin d’évaluer la compétence d’un utilisateur donné à un moment donné, nous considérons une exploration de cet utilisateur au moment voulu et prédisons, grâce à notre modèle, la contribution de chaque requête constituant l’exploration. Ensuite, afin de déduire le niveau de compétences de l’utilisateur à partir de cette séquence de scores de contribution de chaque requête, nous appliquons le Knowledge Tracing, un algorithme qui, à partir d’une séquence de résultats à des exercices donnés, permet de mesurer la probabilité que l’utilisateur maîtrise la compétence requise pour résoudre ces exercices. Dans notre cas, le Knowledge Tracing évalue donc la probabilité que l’utilisateur maîtrise la compétence d’exploration de données.

Evaluer l’efficacité des systèmes de support à l’exploration Une autre contribution importante découlant de notre travail est le développement d’un benchmark pour évaluer l’efficacité des systèmes qui aident les utilisateurs dans leur exploration de données. Nous distinguons l’efficience d’un système qui correspond à sa rapidité et son efficacité qui correspond à la qualité de son support. Le benchmark que nous proposons est complet, en ce sens qu’il offre les quatre composants qui constituent usuellement un benchmark, à savoir les données, le workload (ou la charge de travail), le protocole et les métriques. L’idée du benchmark est de simuler, en utilisant harmonieusement différentes techniques de pointe, un environnement OLAP complet avec un schéma, une instance, un log et des utilisateurs. Ensuite, le protocole d’évaluation consiste à brancher un système que nous voulons évaluer, appelé System Under Test (SUT). A partir de ce moment, le benchmark génère ce que l’on appelle des tâches, qui sont des exercices soumis au SUT, et que ce dernier doit résoudre. Plus commodément, une tâche consiste en un petit nombre de requêtes, appelées requêtes de base, qui forment le début d’une exploration. L’exercice implicite soumis au SUT consiste à analyser cet ensemble de requêtes. L’hypothèse sous-jacente est la suivante: pour être complète, l’analyse doit renvoyer toutes les cellules du cube situées à une distance de 1, en termes d’opérations OLAP, à partir d’au moins une cellule appartenant aux résultats des requêtes à analyser. Pour obtenir une exploration, le benchmark appelle successivement le SUT et l’utilisateur, dont le comportement est simulé selon un modèle basé sur le modèle de Markov, et appris sur la base des explorations passées de l’utilisateur en question. L’opération est répétée autant de fois que l’on souhaite produire d’explorations. Chaque exploration ainsi obtenue est notée selon un ensemble de métriques centrées sur l’utilisateur, classées selon le cadre proposé dans Exploratory Search. En particulier, l’évaluation des compétences présentée dans la contribution précédente est l’une
des mesures utilisées. Cette dernière reflète dans quelle mesure SUT utilisé pour produire l’exploration conduit à des explorations de meilleure qualité.

Mots clés : Interactive Data Exploration, OLAP, Business Intelligence, Benchmarking, Big Data