Top-k Querying of Unknown Values under Order Constraints

Abstract : Many practical scenarios make it necessary to evaluate top-k queries over data items with partially unknown values. This paper considers a setting where the values are taken from a numerical domain, and where some partial order constraints are given over known and unknown values: under these constraints, we assume that all possible worlds are equally likely. Our work is the first to propose a principled scheme to derive the value distributions and expected values of unknown items in this setting, with the goal of computing estimated top-k results by interpolating the unknown values from the known ones. We study the complexity of this general task, and show tight complexity bounds, proving that the problem is intractable, but can be tractably approximated. We then consider the case of tree-shaped partial orders, where we show a constructive PTIME solution. We also compare our problem setting to other top-k definitions on uncertain data.
Type de document :
Communication dans un congrès
ICDT 2017 - International Conference on Database Theory, Mar 2017, Venice, Italy. 〈http://edbticdt2017.unive.it/〉. 〈10.4230/LIPIcs.ICDT.2017.5〉
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-01439295
Contributeur : Pierre Senellart <>
Soumis le : mercredi 18 janvier 2017 - 14:50:59
Dernière modification le : jeudi 11 janvier 2018 - 06:23:39
Document(s) archivé(s) le : mercredi 19 avril 2017 - 14:32:47

Fichier

amarilli2017top.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Antoine Amarilli, Yael Amsterdamer, Tova Milo, Pierre Senellart. Top-k Querying of Unknown Values under Order Constraints. ICDT 2017 - International Conference on Database Theory, Mar 2017, Venice, Italy. 〈http://edbticdt2017.unive.it/〉. 〈10.4230/LIPIcs.ICDT.2017.5〉. 〈hal-01439295〉

Partager

Métriques

Consultations de la notice

318

Téléchargements de fichiers

68