Raffinement progressif et personnalisé des requêtes de préférences dans un espace hautement dimensionnel
Institution:
Versailles-St Quentin en YvelinesDisciplines:
Directors:
Abstract EN:
The use of preferences provides personalized the multi-criteria search and enhances the relevance of the result. The most prominent technique is the skyline queries, based on the concept of Pareto dominance defined. These queries can eliminate tuples dominated by other tuples. The user can then choose from the tuples that are not dominated , which can be considered as the best choice. However, one of the main limitations of skyline queries is when the number of dimensions increases, the result size becomes too large to offer any interesting insights. This thesis provides different solutions to this problem. The general idea is to extend the dominance relationships by introducing more flexible and individualized criteria for comparing tuples, then combine them gradually to best meet the needs of the user. Extensions were made to the skyline operator to offer the user the ability to classify tuples to choose the best or select k best solutions. The user can successively use several preference relations by ordering them to take into account the priorities and level of reliability he attributes to each. This thesis also describes the proposed algorithms, along with the to validate our approaches.
Abstract FR:
L’utilisation de préférences permet de personnaliser la recherche multi-critères et d’accroître la pertinence du résultat. L’exemple le plus connu est celui des requêtes skyline, basées sur le concept de dominance défini par Pareto. Ces requêtes permettent d éliminer les n-uplets dominés par d’autres n-uplets. L’utilisateur pourra alors choisir parmi les n-uplets qui ne sont pas dominés, que l’on peut considérer comme les meilleurs choix. Cependant, l’un des principaux problèmes des requêtes skyline est l’augmentation trop importante de la taille du résultat lorsque le nombre de dimensions, ou critères, augmente, rendant le choix par l’utilisateur difficile. Cette thèse apporte différentes solutions à ce problème. L’idée générale est d’étendre les relations de dominances en introduisant des critères plus flexibles et personnalisés pour comparer les n-uplets, puis de les combiner progressivement afin de satisfaire au mieux les besoins de l’utilisateur. Des extensions ont été apportées à l’opérateur skyline afin d’offrir à l’utilisateur la possibilité de classer les n-uplets de choisir la meilleure sélection ou encore de sélectionner les k meilleures solutions. L’utilisateur peut ainsi utiliser successivement plusieurs relations de préférences en les ordonnant afin de prendre en compte les priorités ou niveau de fiabilité qu’il attribue à chacune. Les algorithmes sont détaillés ainsi que l’expérimentation permettant de valider nos approches.