ACCUEIL

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

APPEL À
CONTRIBUTION
Décisions, argumentation et traçabilité dans l’Ingénierie des Systèmes d’Information
En savoir plus >>
Autres revues >>

Ingénierie des Systèmes d'Information

Networking and Information Systems
1633-1311
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 21/3 - 2016  - pp.119-140  - doi:10.3166/isi.21.3.119-140
TITRE
Approches basées sur la distribution pour l’estimation de la taille du skyline

TITLE
Using histograms for skyline size estimation

RÉSUMÉ
Soit T un ensemble de points dont chacun est défini sur les mêmes attributs. Soit p ∈ T, p est un point skyline de T ssi il n’existe dans T aucun point meilleur que p. Une requête skyline retourne l’ensemble des points skyline. Le nombre de tuples dans le résultat n’est pas toujours proportionnel à la taille (nombre de tuple) des données en entrée. C’est pourquoi estimer la taille du skyline est une question cruciale à laquelle plusieurs travaux se sont consacrés ces dernières années. Ce problème est particulièrement important dans l’optique de l’intégration de l’opérateur skyline au sein de systèmes de gestion de bases de données. S’appuyant sur la distribution des valeurs, nous proposons deux estimateurs présentant de bonnes propriétés : le premier est sans biais et nécessite un parcours de l’ensemble des données tandis que le second est convergent en loi. Ces estimateurs sont simples à mettre en œuvre et montrent leur précision et leur efficience à travers les résultats des expérimentations qui ont été faites.


ABSTRACT
Let T be a set of points each of which is described by the same set of attributes. Let p ∈ T. Then p is a skyline point of T iff there is no other point better than p. A skyline query returns the set of all skyline points. The number of tuples in the result is not always proportional to the size of the source data. Hence, estimate skyline cardinality is a challenging problem which attracted a great deal of work in recent years. This problem is particularly important in case of integration of the skyline operator in database management systems. We propose techniques for estimating skyline cardinality. We first provide an unbiased estimator of the skyline cardinality which requires a pass on data. On another hand, we provide a convergent estimator which does not require any data scanning. It estimates skyline cardinality expectation for those data sets respecting data distribution given as input. The advantages of these solutions are the ease of implementation and, by contrast to other proposals, no costly subskyline queries are required. Our solutions are implemented and some experiments are reported showing both the accuracy of the estimations and the efficiency by which they are obtained.


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

MOTS-CLÉS
Skyline, optimisation, dépendances fonctionnelles

KEYWORDS
Skyline cardinality, expectation, sampling, estimation, algorithms Ingénierie des systèmes d’information – no 3/2016, 119-140 120 ISI.

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  (862 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

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

 English version >> 
Lavoisier