Skyline Queries with Noisy Comparisons

Benoit Groz 1, 2, 3 Tova Milo 3
1 OAK - Database optimizations and architectures for complex large data
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : We study in this paper the computation of skyline queries-a popular tool for multicriteria data analysis-in the presence of noisy input. Motivated by crowdsourcing applications, we present the first algorithms for skyline evaluation in a computation model where the input data items can only be compared through noisy comparisons. In this model comparisons may return wrong answers with some probability, and confidence can be increased through independent repetitions of a comparison. Our goal is to minimize the number of comparisons required for computing or verifying a candidate skyline, while returning the correct answer with high probability. We design output-sensitive algorithms, namely algorithms that take advantage of the potentially small size of the skyline, and analyze the number of comparison rounds of our solutions. We also consider the problem of predicting the most likely skyline given some partial information in the form of noisy comparisons, and show that optimal prediction is computationally intractable.
Type de document :
Communication dans un congrès
ACM SIGMOD/PODS, May 2015, Melbourne, Australia. 〈10.1145/2745754.2745775〉
Liste complète des métadonnées

Littérature citée [46 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01146568
Contributeur : Benoit Groz <>
Soumis le : mardi 28 avril 2015 - 15:15:49
Dernière modification le : lundi 28 mai 2018 - 14:38:02
Document(s) archivé(s) le : mercredi 19 avril 2017 - 09:13:48

Fichier

groz-milo-skylines-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Benoit Groz, Tova Milo. Skyline Queries with Noisy Comparisons. ACM SIGMOD/PODS, May 2015, Melbourne, Australia. 〈10.1145/2745754.2745775〉. 〈hal-01146568〉

Partager

Métriques

Consultations de la notice

349

Téléchargements de fichiers

622