Recherche des Skylines à base de l’algorithme SFS

Abstract

Dans ce travail nous avons étudié les meilleurs représentants des deux grandes familles d’algorithmes (avec et sans index) de calculs de Skyline. Tel que nous avons été développé une application qui se base sur l’algorithme Sort First Skyline « SFS », il possède deux fonction essentiel « Domine » et « Incomparable », SFS se comporte de manière plus progressive que son algorithme de base puisque le tri permet de s'assurer qu'un tuple t dominant un autre tuple t’ sera examiné avant et on peut donc directement ajouter les points insérés dans la liste en tant qu’éléments du Skyline final. Cette stratégie préserve les avantages de SFS : de conserver un nombre de tuples candidats minimal en mémoire et découvrir les tuples Skylines plus rapidement. Nous constatons que les critères de préférences et d’efficacité ne sont respectés que par peu d’algorithmes. Pourtant, ces deux critères sont indispensables au bon fonctionnement d’un algorithme de calcul de Skyline. Cependant, en dépassant un certain nombre de dimensions (plus de 10 dimensions), l’algorithme SFS perd ses efficacités et devient inadaptés. Comme perspectives a ce travail nous proposons Deux approches importantes, le SKYCUBE qui représente le cube de tous les Skylines de tous les sous-espaces possibles et non vides, et SUBSKY qui permet un calcul efficace de requêtes Skylines dans des sous-espaces arbitraires.