License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2017.5
URN: urn:nbn:de:0030-drops-70457
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7045/
Go to the corresponding LIPIcs Volume Portal

Amarilli, Antoine ; Amsterdamer, Yael ; Milo, Tova ; Senellart, Pierre

Top-k Querying of Unknown Values under Order Constraints

pdf-format:
LIPIcs-ICDT-2017-5.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{amarilli_et_al:LIPIcs:2017:7045,
  author =	{Antoine Amarilli and Yael Amsterdamer and Tova Milo and Pierre Senellart},
  title =	{{Top-k Querying of Unknown Values under Order Constraints}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Michael Benedikt and Giorgio Orsi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7045},
  URN =		{urn:nbn:de:0030-drops-70457},
  doi =		{10.4230/LIPIcs.ICDT.2017.5},
  annote =	{Keywords: uncertainty, partial order, unknown values, crowdsourcing, interpolation}
}

Keywords: uncertainty, partial order, unknown values, crowdsourcing, interpolation
Collection: 20th International Conference on Database Theory (ICDT 2017)
Issue Date: 2017
Date of publication: 17.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI