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. |