Au cours des dernières années, le volume des données qui sont capturées et générées a explosé. Les progrès des technologies informatiques, qui fournissent du stockage à bas prix et une très forte puissance de calcul, ont permis aux organisations d'exécuter des analyses complexes de leurs données et d'en extraire des connaissances précieuses. Cette tendance a été très importante non seulement pour l'industrie, mais a également pour la science, où les meilleures instruments et les simulations les plus complexes ont besoin d'une gestion efficace des quantités énormes de données.Le parallélisme est une technique fondamentale dans la gestion de données extrêmement volumineuses car il tire parti de l'utilisation simultanée de plusieurs ressources informatiques. Pour profiter du calcul parallèle, nous avons besoin de techniques de partitionnement de données efficaces, qui sont en charge de la division de l'ensemble des données en plusieurs partitions et leur attribution aux nœuds de calculs. Le partitionnement de données est un problème complexe, car il doit prendre en compte des questions différentes et souvent contradictoires telles que la localité des données, la répartition de charge et la maximisation du parallélisme.Dans cette thèse, nous étudions le problème de partitionnement de données, en particulier dans les bases de données parallèles scientifiques qui sont continuellement en croissance. Nous étudions également ces partitionnements dans le cadre MapReduce.Dans le premier cas, nous considérons le partitionnement de très grandes bases de données dans lesquelles des nouveaux éléments sont ajoutés en permanence, avec pour exemple une application aux données astronomiques. Les approches existantes sont limitées à cause de la complexité de la charge de travail et l'ajout en continu de nouvelles données limitent l'utilisation d'approches traditionnelles. Nous proposons deux algorithmes de partitionnement dynamique qui attribuent les nouvelles données aux partitions en utilisant une technique basée sur l'affinité. Nos algorithmes permettent d'obtenir de très bons partitionnements des données en un temps d'exécution réduit comparé aux approches traditionnelles.Nous étudions également comment améliorer la performance du framework MapReduce en utilisant des techniques de partitionnement de données. En particulier, nous sommes intéressés par le partitionnement efficient de données d'entrée / During the last years, the volume of data that is captured and generated has exploded. Advances in computer technologies, which provide cheap storage and increased computing capabilities, have allowed organizations to perform complex analysis on this data and to extract valuable knowledge from it. This trend has been very important not only for industry, but has also had a significant impact on science, where enhanced instruments and more complex simulations call for an efficient management of huge quantities of data.Parallel computing is a fundamental technique in the management of large quantities of data as it leverages on the concurrent utilization of multiple computing resources. To take advantage of parallel computing, we need efficient data partitioning techniques which are in charge of dividing the whole data and assigning the partitions to the processing nodes. Data partitioning is a complex problem, as it has to consider different and often contradicting issues, such as data locality, load balancing and maximizing parallelism.In this thesis, we study the problem of data partitioning, particularly in scientific parallel databases that are continuously growing and in the MapReduce framework.In the case of scientific databases, we consider data partitioning in very large databases in which new data is appended continuously to the database, e.g. astronomical applications. Existing approaches are limited since the complexity of the workload and continuous appends restrict the applicability of traditional approaches. We propose two partitioning algorithms that dynamically partition new data elements by a technique based on data affinity. Our algorithms enable us to obtain very good data partitions in a low execution time compared to traditional approaches.We also study how to improve the performance of MapReduce framework using data partitioning techniques. In particular, we are interested in efficient data partitioning of the input datasets to reduce the amount of data that has to be transferred in the shuffle phase. We design and implement a strategy which, by capturing the relationships between input tuples and intermediate keys, obtains an efficient partitioning that can be used to reduce significantly the MapReduce's communication overhead.

La problématique de recherche développée concerne la modélisation de milieux complexes sous différentes approches. Initialement centrée sur la simulation d'écoulements fluides implémentée sur des systèmes informatiques parallèles, la thématique a évoluée vers des conceptions et des domaines d'applications plus vastes et notamment la modélisation des écosystèmes aquatiques dans leur complexité naturelle. On développe des aspects méthodologiques permettant la représentation d'organisations dynamiques détectées par des techniques de clustering puis représentées globalement dans des simulations multi-échelles. Les aspects liés à l'implémentation sont développés dans le cadre de systèmes informatiques distribués dynamiques et abordent quelques problèmes liés à la migration dynamique de codes. Le travail présenté ici traduit un instantané d'une recherche qui s'inscrit dans une dynamique qui a conduit à l'émergence d'une activité de recherche significative dans le cadre de la montée en puissance d'un laboratoire, le LIH (Laboratoire d'Informatique du Havre), et d'une formation doctorale, le DEA ITA (Informatique Théorique et Applications).

Dans les machines parallèles les performances des programmes posent de manière cruciale le problème de l'efficacité des communications dans les réseaux d'interconnexion des processeurs d'une machine sans mémoire commune. Les communications point-à-point ne sont qu'un cas très particulier des schémas de communications complexes utilisés par les applications. Les communications globales, basées sur la construction correcte de protocoles à diffusion, sont une classe de ces schémas de communication. Ce problème comprend deux aspects : l'acheminement des messages pour la diffusion et la construction de protocoles de communication/synchronisation inter-processus. Nous considérons d'abord le problème de l'acheminement pour la diffusion, que nous construisons à partir d'une fonction de routage correcte pour des réseaux généraux de topologies quelconques. La famille d'algorithmes de diffusion obtenus s'adapte à la fois à la représentation de la fonction de routage, et à la topologie d'interconnexion entre processeurs. Un aspect de l'efficacité des algorithmes produits est l'espace mémoire nécessaire à une telle fonction de routage à diffusion. Nous développons des algorithmes qui requierent un espace mémoire constant et qui de plus, en utilisant une représention par intervalles de la fonction de routage, peuvent être intégrés dans un circuit routeur. Nous nous intéressons ensuite à la construction de divers types de protocoles à diffusion (synchrone et asynchrone) et proposons une machine virtuelle parallèle à diffusion (PDVM). Cette machine virtuelle s'inscrit dans l'architecture du micro-noyau pour systèmes parallèles ParX, développé par notre équipe, qui offre un support d'exécution générique pour de multiples machines virtuelles. PDVM se présente sous la forme de deux de protocoles nécessaires à l'élaboration de la plupart des schémas de communication par diffusion. L'interface d'accès à ces protocoles permet de gérer des groupes de processus à diffusion toujours cohérents. Dans sa conception cette machine virtuelle est un support minimal pour implémenter efficacement et correctement les diverses interfaces et bibliothèques de communications globales pour les standards de programmation parallèle qui émergent (PVM, MPI, etc.). L'ensemble des solutions proposées a été intégré dans le prototype de ParX; et leurs résultats d'évaluation de performances sont produits.

Au cours des dernières années, le volume des données qui sont capturées et générées a explosé. Les progrès des technologies informatiques, qui fournissent du stockage à bas prix et une très forte puissance de calcul, ont permis aux organisations d'exécuter des analyses complexes de leurs données et d'en extraire des connaissances précieuses. Cette tendance a été très importante non seulement pour l'industrie, mais a également pour la science, où les meilleures instruments et les simulations les plus complexes ont besoin d'une gestion efficace des quantités énormes de données.Le parallélisme est une technique fondamentale dans la gestion de données extrêmement volumineuses car il tire parti de l'utilisation simultanée de plusieurs ressources informatiques. Pour profiter du calcul parallèle, nous avons besoin de techniques de partitionnement de données efficaces, qui sont en charge de la division de l'ensemble des données en plusieurs partitions et leur attribution aux nœuds de calculs. Le partitionnement de données est un problème complexe, car il doit prendre en compte des questions différentes et souvent contradictoires telles que la localité des données, la répartition de charge et la maximisation du parallélisme.Dans cette thèse, nous étudions le problème de partitionnement de données, en particulier dans les bases de données parallèles scientifiques qui sont continuellement en croissance. Nous étudions également ces partitionnements dans le cadre MapReduce.Dans le premier cas, nous considérons le partitionnement de très grandes bases de données dans lesquelles des nouveaux éléments sont ajoutés en permanence, avec pour exemple une application aux données astronomiques. Les approches existantes sont limitées à cause de la complexité de la charge de travail et l'ajout en continu de nouvelles données limitent l'utilisation d'approches traditionnelles. Nous proposons deux algorithmes de partitionnement dynamique qui attribuent les nouvelles données aux partitions en utilisant une technique basée sur l'affinité. Nos algorithmes permettent d'obtenir de très bons partitionnements des données en un temps d'exécution réduit comparé aux approches traditionnelles.Nous étudions également comment améliorer la performance du framework MapReduce en utilisant des techniques de partitionnement de données. En particulier, nous sommes intéressés par le partitionnement efficient de données d'entrée

Les plateformes de calcul à grande échelle ont beaucoup évoluées dernières années. La réduction des coûts des composants simplifie la construction de machines possédant des multicœurs et des accélérateurs comme les GPU.Ceci a permis une propagation des plateformes à grande échelle,dans lesquelles les machines peuvent être éloignées les unes des autres, pouvant même être situées sur différents continents. Le problème essentiel devient alors d'utiliser ces ressources efficacement.Dans ce travail nous nous intéressons d'abord à l'allocation efficace de tâches sur plateformes hétérogènes composées CPU et de GPU. Pour ce faire, nous proposons un outil nommé SWDUAL qui implémente l'algorithme de Smith-Waterman simultanément sur CPU et GPU, en choisissant quelles tâches il est plus intéressant de placer sur chaque type de ressource. Nos expériences montrent que SWDUAL donne de meilleurs résultats que les approches similaires de l'état de l'art.Nous analysons ensuite une nouvelle méthode d'ordonnancement enligne de tâches indépendantes de différentes tailles. Nous proposons une nouvelle technique qui optimise la métrique du stretch. Elle consiste à déplacer les jobs qui retardent trop de petites tâches sur des machines dédiées. Nos résultats expérimentaux montrent que notre méthode obtient de meilleurs résultats que la politique standard et qu'elle s'approche dans de nombreux cas des résultats d'une politique préemptive, qui peut être considérée comme une borne inférieure.Nous nous intéressons ensuite à l'impact de différentes contraintes sur la politique FCFS avec backfilling. La contrainte de contiguïté essaye de compacter les jobs et de réduire la fragmentation dans l'ordonnancement. La contrainte de localité basique place les jobs de telle sorte qu'ils utilisent le plus petit nombre de groupes de processeurs appelés textit. Nos résultats montrent que les bénéfices de telles contraintes sont suffisants pour compenser la réduction du nombre de jobs backfillés due à la réduction de la fragmentation.Nous proposons enfin une nouvelle contrainte nommée localité totale, dans laquelle l'ordonnanceur modélise la plateforme par un fat tree et se sert de cette information pour placer les jobs là où leur coût de communication est minimal.Notre campagne d'expériences montre que cette contrainte obtient de très bons résultats par rapport à un backfilling basique, et de meilleurs résultats que les contraintes précédentes. / The field of parallel supercomputing has been changing rapidly inrecent years. The reduction of costs of the parts necessary to buildmachines with multicore CPUs and accelerators such as GPUs are ofparticular interest to us. This scenario allowed for the expansion oflarge parallel systems, with machines far apart from each other,sometimes even located on different continents. Thus, the crucialproblem is how to use these resources efficiently.In this work, we first consider the efficient allocation of taskssuitable for CPUs and GPUs in heterogeneous platforms. To that end, weimplement a tool called SWDUAL, which executes the Smith-Watermanalgorithm simultaneously on CPUs and GPUs, choosing which tasks aremore suited to one or another. Experiments show that SWDUAL givesbetter results when compared to similar approaches available in theliterature.Second, we study a new online method for scheduling independent tasksof different sizes on processors. We propose a new technique thatoptimizes the stretch metric by detecting when a reasonable amount ofsmall jobs is waiting while a big job executes. Then, the big job isredirected to separate set of machines, dedicated to running big jobsthat have been redirected. We present experiment results that show thatour method outperforms the standard policy and in many cases approachesthe performance of the preemptive policy, which can be considered as alower bound.Next, we present our study on constraints applied to the Backfillingalgorithm in combination with the FCFS policy: Contiguity, which is aconstraint that tries to keep jobs close together and reducefragmentation during the schedule, and Basic Locality, that aims tokeep jobs as much as possible inside groups of processors calledclusters. Experiment results show that the benefits of using theseconstrains outweigh the possible decrease in the number of backfilledjobs due to reduced fragmentation.Finally, we present an additional constraint to the Backfillingalgorithm called Full Locality, where the scheduler models the topologyof the platform as a fat tree and uses this model to assign jobs toregions of the platform where communication costs between processors isreduced. The experiment campaign is executed and results show that FullLocality is superior to all the previously proposed constraints, andspecially Basic Backfilling.

Les ressources de calcul à haute performance (High-Performance Computing—HPC), telles que les supercalculateurs, les grappes, les grilles de calcul ou les Clouds HPC, sont gérées par des gestionnaires de ressources (Resource Management System—RMS) qui multiplexent les ressources entre plusieurs utilisateurs et décident comment allouer les nœuds de calcul aux applications des utilisateurs. Avec la multiplication de machines péta-flopiques et l’arrivée des machines exa-flopiques attendue en 2020, l’optimisation de l’allocation des ressources aux applications est essentielle pour assurer que leur exécution soit efficace. Cependant, les RMSs existants, tels que les batch schedulers, n’offrent qu’une interface restreinte. Dans la plupart des cas, l’application doit choisir les ressources « aveuglément » lors de la soumission sans pouvoir adapter son choix à l’état des ressources ciblées, ni avant, ni pendant l’exécution.Le but de cette Thèse est d’améliorer la gestion des ressources, afin de permettre aux applications d’allouer des ressources efficacement. Pour y parvenir, nous proposons des architectures logicielles qui favorisent la collaboration entre les applications et le gestionnaire de ressources, permettant ainsi aux applications de négocier les ressources qu’elles veulent utiliser. À cette fin, nous analysons d’abord les types d’applications et leurs besoins en ressources, et nous les divisons en plusieurs catégories : rigide, modelable, malléable et évolutive. Pour chaque cas, nous soulignons les opportunités d’amélioration de la gestion de ressources. Une première contribution traite les applications modelables, qui négocient les ressources seulement avant leur démarrage. Nous proposons CooRMv1, une architecture RMS centralisée, qui délègue la sélection des ressources aux lanceurs d’application. Des simulations montrent qu’un tel système se comporte bien en termes d’extensibilité et d’équité. Les résultats ont été validés avec un prototype déployé sur la plate-forme Grid’5000. Une deuxième contribution se focalise sur la négociation des allocations pour des ressources géographiquement distribuées qui appartiennent à plusieurs institutions. Nous étendons CooRMv1 pour proposer distCooRM, une architecture RMS distribuée, qui permet aux applications modelables de co-allouer efficacement des ressources gérées par plusieurs agents indépendants. Les résultats de simulation montrent que distCooRM se comporte bien et passe à l’échelle pour un nombre raisonnable d’applications. Ensuite, nous nous concentrons sur la négociation des ressources à l’exécution pour mieux gérer les applications malléables et évolutives. Nous proposons CooRMv2, une architecture RMS centralisée, qui permet l’ordonnancement efficace des applications évolutives, et surtout celles dont l’évolution n’est pas prévisible. Une application peut faire des « pré-allocations » pour exprimer ses pics de besoins en ressources. Cela lui permet de demander dynamiquement des ressources, dont l’allocation est garantie tant que la pré-allocation n’est pas dépassée. Les ressources pré-allouées mais inutilisées sont à la disposition des autres applications. Des gains importants sont ainsi obtenus, comme les simulations que nous avons effectuées le montrent.Enfin, nous partons de logiciels utilisés en production pour illustrer l’intérêt, mais aussi la difficulté, d’améliorer la collaboration entre deux systèmes existants. Avec GridTLSE comme application et DIET comme RMS, nous avons trouvé un cas d’utilisation mal supporté auparavant. Nous identifions le problème sous-jacent d’ordonnancement des calculs optionnels et nous proposons une architecture pour le résoudre. Des expériences réelles sur la plate-forme Grid’5000 montrent que plusieurs métriques peuvent être améliorées, comme par exemple la satisfaction des utilisateurs, l’équité et le nombre de requêtes traitées. En outre, nous montrons que cette solution présente une bonne extensibilité. / High-Performance Computing (HPC) resources, such as Supercomputers, Clusters, Grids and HPC Clouds, are managed by Resource Management Systems (RMSs) that multiple resources among multiple users and decide how computing nodes are allocated to user applications. As more and more petascale computing resources are built and exascale is to be achieved by 2020, optimizing resource allocation to applications is critical to ensure their efficient execution. However, current RMSs, such as batch schedulers, only offer a limited interface. In most cases, the application has to blindly choose resources at submittal without being able to adapt its choice to the state of the target resources, neither before it started nor during execution. The goal of this Thesis is to improve resource management, so as to allow applications to efficiently allocate resources. We achieve this by proposing software architectures that promote collaboration between the applications and the RMS, thus, allowing applications to negotiate the resources they run on. To this end, we start by analysing the various types of applications and their unique resource requirements, categorizing them into rigid, moldable, malleable and evolving. For each case, we highlight the opportunities they open up for improving resource management.The first contribution deals with moldable applications, for which resources are only negotiated before they start. We propose CooRMv1, a centralized RMS architecture, which delegates resource selection to the application launchers. Simulations show that the solution is both scalable and fair. The results are validated through a prototype implementation deployed on Grid’5000. Second, we focus on negotiating allocations on geographically-distributed resources, managed by multiple institutions. We build upon CooRMv1 and propose distCooRM, a distributed RMS architecture, which allows moldable applications to efficiently co-allocate resources managed by multiple independent agents. Simulation results show that distCooRM is well-behaved and scales well for a reasonable number of applications. Next, attention is shifted to run-time negotiation of resources, so as to improve support for malleable and evolving applications. We propose CooRMv2, a centralized RMS architecture, that enables efficient scheduling of evolving applications, especially non-predictable ones. It allows applications to inform the RMS about their maximum expected resource usage, through pre-allocations. Resources which are pre-allocated but unused can be filled by malleable applications. Simulation results show that considerable gains can be achieved. Last, production-ready software are used as a starting point, to illustrate the interest as well as the difficulty of improving cooperation between existing systems. GridTLSE is used as an application and DIET as an RMS to study a previously unsupported use-case. We identify the underlying problem of scheduling optional computations and propose an architecture to solve it. Real-life experiments done on the Grid’5000 platform show that several metrics are improved, such as user satisfaction, fairness and the number of completed requests. Moreover, it is shown that the solution is scalable.

Cette thèse porte sur la modélisation et l'evaluation d'algorithmes de transfert de charge dans des systèmes parallèles et/ou distribués. Après une synthèse des différentes approches possibles du transfert de charge et des problèmes rencontres pour leurs mises en oeuvre et leurs évaluations quantitatives, nous développons plusieurs modèles basés sur une évolution markovienne de la configuration des charges de l'ensemble des processeurs. Les indices de performance étudiés afin de comparer les valeurs obtenues avec transfert et sans transfert sont la saturation mémoire, le débit du système, la charge de travail et le temps de réponse moyen. Dans les deux premiers modèles seuls deux sites se transfèrent des tâches, mais les temps de communication et de transfert sont modélisés. Des valeurs critiques concernant la pertinence ou non du transfert sont obtenues. Lorsque les temps de communication et de transfert sont négligés devant les temps de calculs, deux modèles sont étudies. Le premier permet d'évaluer un algorithme d'équilibrage de charge pour un nombre quelconque de sites homogènes totalement connectés, de capacité mémoire finie. Cette étude permet de prévoir le comportement de systèmes massivement parallèles et des bornes supérieures de bénéfices que l'on peut attendre d'un réel transfert sont explicitées. Le deuxième prend en compte l'architecture du réseau et l'algorithme induit un transfert dés que la différence de charge entre deux sites voisins excède un. Dans le cas de réseaux infinis dont la topologie est régulière, ce modèle est ergodique et converge à vitesse exponentielle vers son régime stationnaire. Des résultats de simulations sont présentés pour différentes architectures et comparés aux solutions des équations de champ moyen, qui donnent de très bonnes approximations dans la plupart des cas pour les quantités d'intérêt pratique. Enfin, l'incidence sur la valeur des indices de performance est étudiée et interprétée.

Au cours des dernières années, le volume des données qui sont capturées et générées a explosé. Les progrès des technologies informatiques, qui fournissent du stockage à bas prix et une très forte puissance de calcul, ont permis aux organisations d'exécuter des analyses complexes de leurs données et d'en extraire des connaissances précieuses. Cette tendance a été très importante non seulement pour l'industrie, mais a également pour la science, où les meilleures instruments et les simulations les plus complexes ont besoin d'une gestion efficace des quantités énormes de données. Le parallélisme est une technique fondamentale dans la gestion de données extrêmement volumineuses car il tire parti de l'utilisation simultanée de plusieurs ressources informatiques. Pour profiter du calcul parallèle, nous avons besoin de techniques de partitionnement de données efficaces, qui sont en charge de la division de l'ensemble des données en plusieurs partitions et leur attribution aux nœuds de calculs. Le partitionnement de données est un problème complexe, car il doit prendre en compte des questions différentes et souvent contradictoires telles que la localité des données, la répartition de charge et la maximisation du parallélisme. Dans cette thèse, nous étudions le problème de partitionnement de données, en particulier dans les bases de données parallèles scientifiques qui sont continuellement en croissance. Nous étudions également ces partitionnements dans le cadre MapReduce. Dans le premier cas, nous considérons le partitionnement de très grandes bases de données dans lesquelles des nouveaux éléments sont ajoutés en permanence, avec pour exemple une application aux données astronomiques. Les approches existantes sont limitées à cause de la complexité de la charge de travail et l'ajout en continu de nouvelles données limitent l'utilisation d'approches traditionnelles. Nous proposons deux algorithmes de partitionnement dynamique qui attribuent les nouvelles données aux partitions en utilisant une technique basée sur l'affinité. Nos algorithmes permettent d'obtenir de très bons partitionnements des données en un temps d'exécution réduit comparé aux approches traditionnelles. Nous étudions également comment améliorer la performance du framework MapReduce en utilisant des techniques de partitionnement de données. En particulier, nous sommes intéressés par le partitionnement efficient de données d'entrée avec l'objectif de réduire la quantité de données qui devront être transférées dans la phase intermédiaire, connu aussi comme " shuffle ". Nous concevons et mettons en œuvre une stratégie qui, en capturant les relations entre les tuples d'entrée et les clés intermédiaires, obtient un partitionnement efficace qui peut être utilisé pour réduire de manière significative le surcharge de communications dans MapReduce.

Les algorithmes actuels pour la fouille d’ensembles fréquents sont dépassés par l’augmentation des volumes de données. Dans cette thèse nous nous intéressons plus particulièrement aux données transactionnelles (des collections d’ensembles d’objets, par exemple des tickets de caisse) qui contiennent au moins un million de transactions portant sur au moins des centaines de milliers d’objets. Les jeux de données de cette taille suivent généralement une distribution dite en "longue traine": alors que quelques objets sont très fréquents, la plupart sont rares. Ces distributions sont le plus souvent tronquées par les algorithmes de fouille d’ensembles fréquents, dont les résultats ne portent que sur une infime partie des objets disponibles (les plus fréquents). Les méthodes existantes ne permettent donc pas de découvrir des associations concises et pertinentes au sein d’un grand jeu de données. Nous proposons donc une nouvelle sémantique, plus intuitive pour l’analyste: parcourir les associations par objet, au plus une centaine à la fois, et ce pour chaque objet présent dans les données.Afin de parvenir à couvrir tous les objets, notre première contribution consiste à définir la fouille centrée sur les objets. Cela consiste à calculer, pour chaque objet trouvé dans les données, les k ensembles d’objets les plus fréquents qui le contiennent. Nous présentons un algorithme effectuant ce calcul, TopPI. Nous montrons que TopPI calcule efficacement des résultats intéressants sur nos jeux de données. Il est plus performant que des solutions naives ou des émulations reposant sur des algorithms existants, aussi bien en termes de rapidité que de complétude des résultats. Nous décrivons et expérimentons deux versions parallèles de TopPI (l’une sur des machines multi-coeurs, l’autre sur des grappes Hadoop) qui permettent d’accélerer le calcul à grande échelle.Notre seconde contribution est CAPA, un système permettant d’étudier quelle mesure de qualité des règles d’association serait la plus appropriée pour trier nos résultats. Cela s’applique aussi bien aux résultats issus de TopPI que de jLCM, notre implémentation d’un algorithme récent de fouille d’ensembles fréquents fermés (LCM). Notre étude quantitative montre que les 39 mesures que nous comparons peuvent être regroupées en 5 familles, d’après la similarité des classements de règles qu’elles produisent. Nous invitons aussi des experts en marketing à participer à une étude qualitative, afin de déterminer laquelle des 5 familles que nous proposons met en avant les associations d’objets les plus pertinentes dans leur domaine.Notre collaboration avec Intermarché, partenaire industriel dans le cadre du projet Datalyse, nous permet de présenter des expériences complètes et portant sur des données réelles issues de supermarchés dans toute la France. Nous décrivons un flux d’analyse complet, à même de répondre à cette application. Nous présentons également des expériences portant sur des données issues d’Internet; grâce à la généricité du modèle des ensembles d’objets, nos contributions peuvent s’appliquer dans d’autres domaines.Nos contributions permettent donc aux analystes de découvrir des associations d’objets au milieu de grandes masses de données. Nos travaux ouvrent aussi la voie vers la fouille d’associations interactive à large échelle, afin d’analyser des données hautement dynamiques ou de réduire la portion du fichier à analyser à celle qui intéresse le plus l’analyste. / The recent increase of data volumes raises new challenges for itemset mining algorithms. In this thesis, we focus on transactional datasets (collections of items sets, for example supermarket tickets) containing at least a million transactions over hundreds of thousands items. These datasets usually follow a "long tail" distribution: a few items are very frequent, and most items appear rarely. Such distributions are often truncated by existing itemset mining algorithms, whose results concern only a very small portion of the available items (the most frequents, usually). Thus, existing methods fail to concisely provide relevant insights on large datasets. We therefore introduce a new semantics which is more intuitive for the analyst: browsing associations per item, for any item, and less than a hundred associations at once.To address the items' coverage challenge, our first contribution is the item-centric mining problem. It consists in computing, for each item in the dataset, the k most frequent closed itemsets containing this item. We present an algorithm to solve it, TopPI. We show that TopPI computes efficiently interesting results over our datasets, outperforming simpler solutions or emulations based on existing algorithms, both in terms of run-time and result completeness. We also show and empirically validate how TopPI can be parallelized, on multi-core machines and on Hadoop clusters, in order to speed-up computation on large scale datasets.Our second contribution is CAPA, a framework allowing us to study which existing measures of association rules' quality are relevant to rank results. This concerns results obtained from TopPI or from jLCM, our implementation of a state-of-the-art frequent closed itemsets mining algorithm (LCM). Our quantitative study shows that the 39 quality measures we compare can be grouped into 5 families, based on the similarity of the rankings they produce. We also involve marketing experts in a qualitative study, in order to discover which of the 5 families we propose highlights the most interesting associations for their domain.Our close collaboration with Intermarché, one of our industrial partners in the Datalyse project, allows us to show extensive experiments on real, nation-wide supermarket data. We present a complete analytics workflow addressing this use case. We also experiment on Web data. Our contributions can be relevant in various other fields, thanks to the genericity of transactional datasets.Altogether our contributions allow analysts to discover associations of interest in modern datasets. We pave the way for a more reactive discovery of items' associations in large-scale datasets, whether on highly dynamic data or for interactive exploration systems.