ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Autres revues >>

Ingénierie des Systèmes d'Information

Networking and Information Systems
1633-1311
Revue des sciences et technologies de l'information
Nouvel éditeur en 2019
 

 ARTICLE VOL 22/3 - 2017  - pp.9-33  - doi:10.3166/isi.22.3.9-33
TITRE
Calculer et compresser le skycube négatif

TITLE
Computing and compressing the negative Skycube

RÉSUMÉ
Soit T une table avec D attributs. Le Skycube de T est l’ensemble de tous les skylines obtenus en considérant chacun des sous-ensembles de dimensions. Afin de réduire le temps de réponse des requêtes du skycube, les solutions de la littérature proposent soit des algorithmes efficaces pour le calcul du skycube complet, soit des techniques de compression du skycube dans le but de gagner en temps et en espace. Intuitivement, les précédents travaux avaient pour objectif de calculer ou de résumer l’information suivante : « pour chaque tuple t, la liste des skylines auxquels t appartient ». Dans ce travail, nous considérons l’information complémentaire, à savoir, « pour chaque tuple t, la liste des skylines auxquels t n’appartient pas ». C’est pourquoi nous l’appelons le Skycube Négatif. En dépit de l’apparente équivalence entre ces deux informations, nos analyses et expérimentations montrent que ces deux points de vue ne conduisent pas à des comportements similaires des algorithmes associés. Plus spécifiquement, nos propositions montrent que (i) le résumé du Skycube Négatif peut être obtenu plus rapidement que les autre méthodes, (ii) en général, le Skycube Négatif requiert moins d’espace, (iii) les requêtes sont plus rapides suivant cette optique et (iv) le Skycube Positif peut être obtenu plus rapidement en calculant d’abord le Skycube Négatif.


ABSTRACT
Given a table T with D dimensions, the skycube of T is the union of all skylines obtained by considering each of the subsets of D (subspaces). The number of these skylines is exponential w.r.t D. To make the skycube practically useful, two lines of research have been pursued so far : the first one aims to propose efficient algorithms for computing it and the second one considers either that the skycube is too large to be computed in a reasonable time or it requires too much memory space to be stored. They therefore propose skycube summarization techniques to reduce time and space consumption. Intuitively, previous efforts have been devoted to compute or summarize the following information : "for every tuple t, list the skylines where t belongs to". In this paper, we consider the complementary statement, i.e., "for every tuple t, list the skylines where t does not belong to". This is what we call the negative skycube. Our proposal shows that (i) the negative summary can be obtained much faster than state of the art techniques for positive summaries, (ii) in general, it consumes less space, (iii) skyline queries evaluation using this summary are much faster and (iv) the positive skycube can be obtained much more rapidly than state of the art algorithms.


AUTEUR(S)
Patrick KAMNANG WANKO, Sofian MAABOUT, Nicolas HANUSSE

MOTS-CLÉS
requête skyline, algorithme, sous-espace, optimisation, k-dominant Skycube.

KEYWORDS
skyline query, algorithm, subspace, optimization, k-dominant.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (254 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier