Evènement pour le groupe BioInformatique et Visualisation


Date 2016-03-31  11:00-12:00
TitreRésumer le Negative-Skycube pour optimiser les requêtes skyline multidimensionnelles 
RésuméSoient T une table et D l'ensemble des attributs décrivant les tuples de T. Soient t et u deux tuples appartenant à T. on dit que t domine u si et seulement si t est au moins meilleur que u dans chaque dimension et il existe au moins une dimension dans laquelle t est strictement meilleur que u. On dira également que t est un point skyline de T si et seulement s'il n'est dominé par aucun point de T. Une requête skyline relative à un espace X inclus dans D retourne l'ensemble des points skyline relativement à X. Le skycube de T est l'ensemble des skyline obtenus en considérant chaque sous- ensemble de D. En raison du nombre exponentiel de requêtes skyline, il est crucial de résumer cette information. Les précédents travaux résument la liste des sous-espaces de D pour lesquels un tuple particulier t appartient au skyline. Dans ce travail, nous considérons l'approche complémentaire qui consiste à résumer l'ensemble des sous-espaces pour lesquels un tuple t ne fait pas partie du skyline (Negative- Skycube). Malgré l'apparente équivalence entre ces deux approches, nos résultats expérimentaux montrent qu'elles ne nécessitent pas le même effort. Par exemple, notre approche nécessite moins d'espace et de temps lorsque le nombre de tuples ou le nombre de dimensions augmente. Ceci pourrait s'expliquer par le fait que lorsque le nombre de dimensions augmente, les tuples ont tendance à être incomparables (l'un ne domine pas l'autre et réciproquement), rendant la taille du skyline plus grande. De ce fait, la proportion de sous-espaces dans lesquels un tuple t n'appartient pas au skyline tend à diminuer. Plus précisement, nos expérimentations sur données synthétiques et sur données réelles montrent que (i) le résumé du Negative-Skycube peut être obtenu plus rapidement que les techniques de l'état de l'art, (ii) en général, celui-ci requière moins d'espace et (iii) les requêtes skyline en sont retournées plus rapidement. 
Lieu178 
OrateurPatrick Kamnang Wanko 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index